Interpolation spline - Spline interpolation

Dans le domaine mathématique de l'analyse numérique , l' interpolation spline est une forme d' interpolation où l'interpolant est un type spécial de polynôme par morceaux appelé spline . Autrement dit, au lieu d'ajuster un seul polynôme de haut degré à toutes les valeurs à la fois, l'interpolation spline ajuste les polynômes de faible degré à de petits sous-ensembles des valeurs, par exemple, en ajustant neuf polynômes cubiques entre chacune des paires de dix points , au lieu d'adapter un seul polynôme de degré dix à chacun d'eux. L'interpolation spline est souvent préférée à l' interpolation polynomiale car l' erreur d'interpolation peut être réduite même en utilisant des polynômes de faible degré pour la spline. L'interpolation spline évite également le problème du phénomène de Runge , dans lequel une oscillation peut se produire entre les points lors de l'interpolation à l'aide de polynômes de haut degré.

introduction

Interpolation avec des splines cubiques entre huit points. Les dessins techniques dessinés à la main pour la construction navale sont un exemple historique d'interpolation spline ; les dessins ont été construits à l'aide de règles flexibles qui ont été pliées pour suivre des points prédéfinis.

À l'origine, spline était un terme désignant les règles élastiques qui étaient pliées pour passer à travers un certain nombre de points prédéfinis, ou nœuds . Ceux-ci ont été utilisés pour faire des dessins techniques pour la construction navale et la construction à la main, comme illustré sur la figure.

Nous souhaitons modéliser des types de courbes similaires à l'aide d'un ensemble d'équations mathématiques, avec un polynôme pour chaque paire de nœuds et , où . Il y aura donc des polynômes et des nœuds : le premier polynôme commence à , et le dernier polynôme se termine à . ${\style d'affichage y=q_{i}(x)}$${\style d'affichage (x_{i-1},y_{i-1})}$${\style d'affichage (x_{i},y_{i})}$${\displaystyle i=1,2,\dots ,n}$${\style d'affichage n}$${\style d'affichage n+1}$${\style d'affichage (x_{0},y_{0})}$${\style d'affichage (x_{n},y_{n})}$

La courbure de toute courbe est définie comme ${\style d'affichage y=f(x)}$

${\displaystyle \kappa ={\frac {y''}{(1+y'^{2})^{3/2}}}.}$

Pour que la spline prenne une forme qui minimise la flexion (sous la contrainte de passer par tous les nœuds), on va définir les deux et être continue partout, y compris au niveau des nœuds. Ainsi les dérivées première et seconde de chaque polynôme successif doivent avoir des valeurs identiques aux nœuds, c'est-à-dire que ${\style d'affichage y'}$${\displaystyle y''}$

${\displaystyle {\begin{cases}q'_{i}(x_{i})=q'_{i+1}(x_{i})\\q''_{i}(x_{i} )=q''_{i+1}(x_{i})\end{cas}}\qquad 1\leq i\leq n-1.}$

Cela ne peut être réalisé que si des polynômes de degré 3 ou supérieur - des polynômes cubiques ou supérieur - sont utilisés. L'approche classique consiste à utiliser des polynômes d'exactement degré 3 — splines cubiques .

Algorithme pour trouver la spline cubique d'interpolation

Nous souhaitons trouver chaque polynôme étant donné les points passant par . Pour ce faire, nous ne considérerons qu'un seul morceau de la courbe, , qui interpolera de à . Cette pièce aura des pentes et à ses extrémités. Ou, plus précisément, ${\style d'affichage q_{i}(x)}$${\style d'affichage (x_{0},y_{0})}$${\style d'affichage (x_{n},y_{n})}$${\style d'affichage q(x)}$${\style d'affichage (x_{1},y_{1})}$${\style d'affichage (x_{2},y_{2})}$${\style d'affichage k_{1}}$${\style d'affichage k_{2}}$

${\displaystyle q(x_{1})=y_{1},}$

${\style d'affichage q(x_{2})=y_{2},}$

${\displaystyle q'(x_{1})=k_{1},}$

${\displaystyle q'(x_{2})=k_{2}.}$

L'équation complète peut être écrite sous la forme symétrique ${\style d'affichage q(x)}$

${\displaystyle q(x)={\big (}1-t(x){\big )}\,y_{1}+t(x)\,y_{2}+t(x){\big ( }1-t(x){\grand )}{\Grand (}{\grand (}1-t(x){\grand )}\,a+t(x)\,b{\Grand )}, }$

( 1 )

où

${\displaystyle t(x)={\frac {x-x_{1}}{x_{2}-x_{1}}},}$

( 2 )

${\displaystyle a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1}),}$

( 3 )

${\displaystyle b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1}).}$

( 4 )

Mais que sont et ? Pour dériver ces valeurs critiques, nous devons considérer que ${\style d'affichage k_{1}}$${\style d'affichage k_{2}}$

${\displaystyle q'={\frac {dq}{dx}}={\frac {dq}{dt}}{\frac {dt}{dx}}={\frac {dq}{dt}}{\ frac {1}{x_{2}-x_{1}}}.}$

Il s'ensuit alors que

${\displaystyle q'={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t){\frac {a(1-t)+bt }{x_{2}-x_{1}}}+t(1-t){\frac {ba}{x_{2}-x_{1}}},}$

( 5 )

${\displaystyle q''=2{\frac {b-2a+(ab)3t}{{(x_{2}-x_{1})}^{2}}}.}$

( 6 )

En fixant t = 0 et t = 1 respectivement dans les équations ( 5 ) et ( 6 ), on obtient de ( 2 ) qu'en effet les dérivées premières q′ ( x ₁ ) = k ₁ et q′ ( x ₂ ) = k ₂ , et aussi les dérivées secondes

${\displaystyle q''(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}},}$

( 7 )

${\displaystyle q''(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}.}$

( 8 )

Si maintenant ( x _i , y _i ), i = 0, 1, ..., n sont n + 1 points, et

${\displaystyle q_{i}=(1-t)\,y_{i-1}+t\,y_{i}+t(1-t){\big (}(1-t)\,a_{ i}+t\,b_{i}{\grand )},}$

( 9 )

où i = 1, 2, ..., n , et sont n polynômes du troisième degré interpolant y dans l'intervalle x _{i −1} ≤ x ≤ x _i pour i = 1, ..., n tels que q′ _i ( x _i ) = q′ _{i +1} ( x _i ) pour i = 1, ..., n  − 1, alors les n polynômes définissent ensemble une fonction différentiable dans l'intervalle x ₀ ≤ x ≤ x _n , et ${\displaystyle t={\tfrac {x-x_{i-1}}{x_{i}-x_{i-1}}}}$

${\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1}),}$

( 10 )

${\displaystyle b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})}$

( 11 )

pour i = 1, ..., n , où

${\displaystyle k_{0}=q_{1}'(x_{0}),}$

( 12 )

${\displaystyle k_{i}=q_{i}'(x_{i})=q_{i+1}'(x_{i}),\qquad i=1,\dots ,n-1,}$

( 13 )

${\displaystyle k_{n}=q_{n}'(x_{n}).}$

( 14 )

Si la suite k ₀ , k ₁ , ..., k _n est telle que, de plus, q′′ _i ( x _i ) = q′′ _{i +1} ( x _i ) est vraie pour i = 1, ... , n  − 1, alors la fonction résultante aura même une dérivée seconde continue.

De ( 7 ), ( 8 ), ( 10 ) et ( 11 ) découle que c'est le cas si et seulement si

${\displaystyle {\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1} }}+{\frac {1}{x_{i+1}-x_{i}}}\right)2k_{i}+{\frac {k_{i+1}}{x_{i+1}- x_{i}}}=3\gauche({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+ {\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)}$

( 15 )

pour i = 1, ..., n  − 1. Les relations ( 15 ) sont n − 1 équations linéaires pour les n + 1 valeurs k ₀ , k ₁ , ..., k _n .

Pour les règles élastiques étant le modèle pour l'interpolation spline, on a qu'à gauche du "nœud" le plus à gauche et à droite du "nœud" le plus à droite la règle peut se déplacer librement et prendra donc la forme de une droite avec q′′ = 0 . Comme q′′ devrait être une fonction continue de x , les « splines naturelles » en plus des n − 1 équations linéaires ( 15 ) devraient avoir

${\displaystyle q''_{1}(x_{0})=2{\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1 }-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0,}$

${\displaystyle q''_{n}(x_{n})=-2{\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1} )(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0,}$

c'est à dire que

${\displaystyle {\frac {2}{x_{1}-x_{0}}}k_{0}+{\frac {1}{x_{1}-x_{0}}}k_{1}=3 {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},}$

( 16 )

${\displaystyle {\frac {1}{x_{n}-x_{n-1}}}k_{n-1}+{\frac {2}{x_{n}-x_{n-1}}} k_{n}=3{\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}.}$

( 17 )

Finalement, ( 15 ) avec ( 16 ) et ( 17 ) constituent n + 1 équations linéaires qui définissent de manière unique les n + 1 paramètres k ₀ , k ₁ , ..., k _n .

Il existe d'autres conditions de fin, "spline serrée", qui spécifie la pente aux extrémités de la spline, et la populaire "spline sans nœud", qui exige que la troisième dérivée soit également continue aux x ₁ et x _{N -1} point. Pour la spline « pas de nœud », les équations supplémentaires seront :

${\displaystyle q'''_{1}(x_{1})=q'''_{2}(x_{1})\Rightarrow {\frac {1}{\Delta x_{1}^{2 }}}k_{0}+\gauche({\frac {1}{\Delta x_{1}^{2}}}-{\frac {1}{\Delta x_{2}^{2}}} \right)k_{1}-{\frac {1}{\Delta x_{2}^{2}}}k_{2}=2\left({\frac {\Delta y_{1}}{\Delta x_{1}^{3}}}-{\frac {\Delta y_{2}}{\Delta x_{2}^{3}}}\right),}$

${\displaystyle q'''_{n-1}(x_{n-1})=q'''_{n}(x_{n-1})\Rightarrow {\frac {1}{\Delta x_ {n-1}^{2}}}k_{n-2}+\gauche({\frac {1}{\Delta x_{n-1}^{2}}}-{\frac {1}{ \Delta x_{n}^{2}}}\right)k_{n-1}-{\frac {1}{\Delta x_{n}^{2}}}k_{n}=2\left( {\frac {\Delta y_{n-1}}{\Delta x_{n-1}^{3}}}-{\frac {\Delta y_{n}}{\Delta x_{n}^{3 }}}\droite),}$

où . ${\displaystyle \Delta x_{i}=x_{i}-x_{i-1},\ \Delta y_{i}=y_{i}-y_{i-1}}$

Exemple

Interpolation avec des splines "naturelles" cubiques entre trois points

Dans le cas de trois points, les valeurs de sont trouvées en résolvant le système d'équation linéaire tridiagonale${\style d'affichage k_{0},k_{1},k_{2}}$

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}} {\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_ {3}\\\end{bmatrice}}}$

avec

${\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}},}$

${\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}},}$

${\displaystyle a_{22}=2\left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\ droite),}$

${\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}}},}$

${\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}},}$

${\displaystyle b_{1}=3{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}},}$

${\displaystyle b_{2}=3\gauche({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right),}$

${\displaystyle b_{3}=3{\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}.}$

Pour les trois points

${\style d'affichage (-1,0,5),\ (0,0),\ (3,3),}$

on obtient ça

${\displaystyle k_{0}=-0.6875,\ k_{1}=-0.1250,\ k_{2}=1.5625,}$

et de ( 10 ) et ( 11 ) que

${\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0,1875,}$

${\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750,}$

${\displaystyle a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750,}$

${\displaystyle b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875.}$

Sur la figure, la fonction spline constituée des deux polynômes cubiques et donnée par ( 9 ) est affichée. ${\displaystyle q_{1}(x)}$${\style d'affichage q_{2}(x)}$

Voir également

• Spline cubique Hermite
• Spline Centripète Catmull–Rom
• Interpolation spline discrète
• Interpolation cubique monotone
• NURBS
• Interpolation multivariée
• Interpolation polynomiale
• Spline de lissage
• Ondelette spline
• Cannelure à plaque mince
• Spline polyharmonique

Code informatique

TinySpline : bibliothèque C open source pour les splines qui implémente l'interpolation de splines cubiques

SciPy Spline Interpolation : un package Python qui implémente l'interpolation

Interpolation cubique : bibliothèque C# open source pour l'interpolation de splines cubiques

Les références

• Schoenberg, Isaac J. (1946). "Contributions au problème de l'approximation de données équidistantes par des fonctions analytiques : partie A.—Sur le problème du lissage ou de la graduation. Une première classe de formules d'approximation analytique" . Trimestriel de Mathématiques Appliquées . 4 (2) : 45-99. doi : 10.1090/qam/15914 .
• Schoenberg, Isaac J. (1946). "Contributions au problème de l'approximation de données équidistantes par des fonctions analytiques : partie B.—Sur le problème de l'interpolation oscillatoire. Une deuxième classe de formules d'approximation analytique" . Trimestriel de Mathématiques Appliquées . 4 (2) : 112-141. doi : 10.1090/qam/16705 .

Liens externes

• Outil de calcul et de visualisation en ligne d'interpolation de spline cubique (avec code source JavaScript)
• "Interpolation spline" , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
• Splines cubiques dynamiques avec JSXGraph
• Cours sur la théorie et la pratique de l'interpolation spline
• Papier qui explique étape par étape comment se fait l'interpolation de splines cubiques, mais uniquement pour des nœuds équidistants.
• Recettes numériques en C, allez au chapitre 3 section 3-3
• Une note sur les splines cubiques
• Informations sur l'interpolation spline (y compris le code en Fortran 77)