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:
Étant donné un ensemble de points du plan, comment déterminer une «bonne» courbe qui passe par ces points.
Notant (ai,bi) les coordonnées des points, on cherche donc une «bonne» fonction f vérifiant f(ai)=bi 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 fera l'objet d'une autre page, qui chercherait 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

Il s'agit de l'interpolation la plus simple, où l'on relie simplement les points par des segments. La fonction f est donc une fonction affine par morceaux, qui n'est pas «bonne» dans le sens où elle n'est pas dérivable.

Sur la figure ci-dessous, et plus généralement sur les figures de cette page:

Interpolation de Lagrange

On choisit ici pour fonction f l'unique fonction polynomiale de degré n-1 vérifiant f(ai)=bi 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 Li l'unique polynôme de degré n-1 valant 1 en ai et 0 en ak pour tout k≠i - polynôme donc on trouve facilement l'expression factorisée - on a f:x ↦ ∑ibiLi(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:

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

Splines

L'idée des splines est de mélanger les deux sections précédentes:
On appelle spline de degré d interpolant des points (ai,bi) avec une régularité r≤d une fonction f
  • telle que f(ai)=bi pour tout i
  • f polynomiale de degré au plus d sur chaque intervalle de la forme [ai,ai+1]
  • de classe Cr
  • Comme la fonction est polynomiale sur chaque intervalle ouvert ]ai,ai+1[, elle y est de classe C. La condition de régularité est en fait une condition qui porte sur les raccordements aux points ai. Par exemple:

    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 [ai,ai+1] une fonction polynomiale de la forme x ↦ ci3(x-ai)3+ci2(x-ai)2+ci1(x-ai)+ci0, ce qui fait 4(n-1) inconnues, où n est le nombre de points à interpoler.

    Détaillons les 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 C2 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 (ai,bi) 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 ti tel que x(ti)=ai et y(ti)=bi).

    On commence par fixer des ti Ce qui n'est pas évident ! Une façon naturelle de faire est de choisir les ti+1-ti proportionnels aux distances entre (ai, bi) et (ai+1, bi+1) , puis on utilise simplement la méthode des splines ci-dessus pour interpoler les (ti, ai) d'une part, et les (ti, bi) 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).