Page principale

Interpolation

On s'intéresse dans cette page au problème de l'interpolation dans le plan, que l'on peut énoncer de la façon suivante: Notant (a_i,b_i) les coordonnées des points, on cherche donc une «bonne» fonction f vérifiant f(a_i)=b_i pour tout i.

Ce problème, qui vise à obtenir une fonction définie sur un intervalle à partir de données isolées, a de nombreuses applications (CAO, logiciels de graphisme, usinage, étalonnage...).

À noter qu'il existe un problème proche, celui de l'approximation (qui fait l'objet d'une autre page) qui consiste à chercher une fonction «proche» des points d'un certain point de vue, mais sans nécessairement imposer que le graphe de cette fonction passe par les points.

Interpolation Linéaire

Interpolation de Lagrange

On choisit ici pour fonction f l'unique fonction polynomiale de degré n-1 vérifiant f(a_i)=b_i pour tout i, où n est le nombre de points.
La preuve d'existence et l'unicité d'un tel polynôme est un exercice classique de niveau L1Si l'on note L_i l'unique polynôme de degré n-1 valant 1 en a_i et 0 en a_k pour tout k≠i - polynôme donc on trouve facilement l'expression factorisée - on a f:x ↦ ∑_ib_iL_i(x). .

On obtient alors une fonction polynômiale répondant à la question, ce qui est très bon du point de vue de la régularité (une telle fonction est C^∞).

Cependant, la fonction obtenue semble parfois être sujette à des oscillations de grande amplitude non désirées. De plus, bouger un des points peut avoir des conséquences importantes sur des valeurs d'interpolation éloignées. Essayer par exemple:

• de placer 2 des points à des abscisses très proches
• de presque aligner tous les points sauf un.

Pour résoudre ces problème, on peut:

• relacher la contrainte que la courbe doit absolument passer par tous les points. Il ne s'agit plus alors d'un problème d'interpolation, mais d'approximation - dont il sera question dans une autre page
• trouver une autre façon d'interpoler, de façon régulière, mais en évitant les problèmes ci-dessus. La section suivante montre une façon de faire cela.

Splines

L'idée des splines est de mélanger les deux sections précédentes:

• on va construire des interpolations segment par segment (pour éviter les «interactions à longue distance» constatées avec l'interpolation de Lagrange)
• mais en conservant l'idée des polynômes pour imposer une certaine régularité à la fonction.

Comme la fonction est polynomiale sur chaque intervalle ouvert ]a_i,a_i+1[, elle y est de classe C^∞. La condition de régularité est en fait une condition qui porte sur les raccordements aux points a_i. Par exemple:

• r=0 correspond au cas où l'on demande simplement la continuité de f. Si d=1, l'interpolation linéaire ci-dessus répond à la question.
• r=1 correspond au cas où l'on demande de plus un raccordement continu de la dérivée, c'est-à-dire des tangentes.
• r=2 correspond au cas où l'on demande de plus un raccordement continu de la dérivée seconde, c'est-à-dire de la courbure.

Noter que si r=d, on peut montrer que les conditions de raccordements entrainent que l'on doit choisir le même polynôme sur tous les segments (ce qui est sauf cas particulier impossible si le nombre de points est strictement plus grand que d+1). On retombe dans ce cas sur l'interpolation de Lagrange vue ci-dessus.

Un cas particulier particulièrement utilisé est celui des splines de degré 3, et de régularité 2, c'est celui-ci que nous allons détailler dans la suite.
On cherche donc sur chaque intervalle [a_i,a_i+1] une fonction polynomiale de la forme x ↦ cⁱ₃(x-a_i)³+cⁱ₂(x-a_i)²+cⁱ₁(x-a_i)+cⁱ₀, ce qui fait 4(n-1) inconnues, où n est le nombre de points à interpoler.
Détaillons les contraintes:

• Chaque fonction polynomiale doit passer par les 2 points aux extrémités du segment, ce qui donne 2 contraintes (donc 2(n-1) au total). Ces contraintes sont cⁱ₀=b_i et cⁱ₃(a_i+1-a_i)³+cⁱ₂(a_i+1-a_i)²+cⁱ₁(a_i+1-a_i)+cⁱ₀=b_i+1
• Le raccordement des dérivées impose des contraintes de la forme 3cⁱ₃(a_i+1-a_i)²+2cⁱ₂(a_i+1-a_i)+cⁱ₁ = cⁱ⁺¹₁ (n-2 contraintes, une pour chaque point sauf les 2 points extrèmes).
• Le raccordement des dérivées secondes impose des contraintes de la forme 6cⁱ₂(a_i+1-a_i)+2cⁱ₂ = 2cⁱ⁺¹₂ (n-2 contraintes).

On obtient donc finalement 4(n-1)-2 contraintes linéaires - i.e. 2 de moins que le nombre d'inconnues.
En rajoutant 2 conditions (typiquement en imposant que les dérivées secondes aux points extrémaux sont nulles), on obtient un système linéaire à 4(n-1) inconnues et 4(n-1) équations. On peut montrer que ce système est de Cramer, et donc admet une unique solution.
On peut en fait montrer qu'il est possible de se ramener à un système à n inconnues, de forme très particulièreLa matrice correspondante est tridiagonale., qui se résout en temps linéaire. Voir par exemple cette page pour les explications.
La simulation ci-contre montre que, bien que la courbe obtenue soit toujours assez régulière (de classe C² partout, et C^∞ en dehors des points), on évite partiellement les écueils mentionnés pour l'interpolation de Lagrange. Vous pouvez cliquer sur cette phrase pour copier les points du graphique sur l'interpolation de Lagrange sur ce nouveau graphique pour voir la différence.

Splines paramétrées

Dans tout ce qui précède, on interpole un ensemble de points par le graphe d'une fonction. On voit donc les données en ordonnées comme une fonction des données en abscisse, ce qui empêche en particulier des retours en arrière. On ne peut pas en général cliquer sur des points et obtenir une courbe qui passe par ces points dans l'ordre. On peut en fait obtenir ce résultat à l'aide d'une variante des splines, appélée splines paramétrées. L'idée est très simple: partant de n points (a_i,b_i) du plan, on va chercher une courbe paramétrée (x(t), y(t)) dont le graphe passe par ces points (i.e. telle qu'il existe pour tout i≤n t_i tel que x(t_i)=a_i et y(t_i)=b_i).

On commence par fixer des t_i Ce qui n'est pas évident ! Une façon naturelle de faire est de choisir les t_i+1-t_i proportionnels aux distances entre (a_i, b_i) et (a_i+1, b_i+1) , puis on utilise simplement la méthode des splines ci-dessus pour interpoler les (t_i, a_i) d'une part, et les (t_i, b_i) d'autre part. Si l'on note t ↦ x(t) et t ↦ y(t) les fonctions d'interpolation obtenues, on obtient donc une courbe paramétrée (x(t), y(t)) répondant au problème.

Un inconvénient tout de même : les courbes obtenues dépendent du repère choisi, ce qui n'est pas souhaitable ! Pour cette raison, on préfère en graphisme et CAO l'utilisation des Courbes de Bézier (qui ne répondent cependant pas tout à fait au même problème).