Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Analyse numérique

Interpolation : polynôme de Lagrange, phénomène de Runge, nœuds de Tchebychev et splines

Existence et unicité du polynôme d'interpolation, erreur d'interpolation, phénomène de Runge, nœuds de Tchebychev, splines linéaires et cubiques et leurs usages.

https://www.electronics-engineering.com/fr/interpolation-polynomiale-runge-splines/

Pas encore de vote : soyez le premier à noter cette page.

Souvent une fonction n’est connue qu’en certains points : les valeurs d’un tableau, les mesures d’une expérience, les échantillons d’un signal, la courbe caractéristique d’un capteur fournie par le fabricant. Interpoler signifie construire une fonction simple qui passe exactement par ces points, pour estimer les valeurs intermédiaires. Dans cette leçon nous voyons le polynôme d’interpolation, le phénomène de Runge qui en montre les limites, les nœuds de Tchebychev et les splines.

Le polynôme d’interpolation

Étant donnés n + 1 points (x_0, y_0), \dots, (x_n, y_n) d’abscisses distinctes, il existe exactement un polynôme de degré au plus n qui passe par tous.

Démonstration de l’unicité. Si deux polynômes p et q de degré au plus n passent par les mêmes n + 1 points, la différence p - q est de degré au plus n et s’annule en n + 1 points distincts. Un polynôme non nul de degré n a au plus n racines, donc p - q = 0.

La forme de Lagrange. On construit les polynômes de base

    \[ \ell_i(x) = \prod_{j \ne i}\frac{x - x_j}{x_i - x_j} \]

qui valent 1 en x_i et 0 en tout autre nœud. Alors

    \[ p_n(x) = \sum_{i=0}^{n}y_i\,\ell_i(x) \]

passe par tous les points. Exemple : pour (0, 1), (1, 3), (2, 7) on obtient p(x) = x^2 + x + 1. La forme de Lagrange est élégante pour les démonstrations ; pour les calculs on utilise la forme de Newton avec les différences divisées, qui permet d’ajouter un point sans tout recalculer.

L’erreur d’interpolation

Si f a n + 1 dérivées continues, pour tout x il existe \xi dans l’intervalle tel que

    \[ f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n + 1)!}\,\prod_{i=0}^{n}(x - x_i) \]

L’erreur dépend de deux facteurs : la « régularité » de la fonction (la dérivée d’ordre élevé) et la répartition des nœuds (le produit).

Le phénomène de Runge

Il semble naturel que plus de points donnent toujours une meilleure interpolation. Ce n’est pas le cas. En 1901 Runge a étudié la fonction

    \[ f(x) = \frac{1}{1 + 25x^2},\qquad x\in[-1, 1] \]

parfaitement régulière, et l’a interpolée en des nœuds régulièrement espacés.

Interpolation de la fonction de Runge avec des nœuds équidistants et avec des nœuds de Tchebychev
À gauche : avec 11 nœuds équidistants le polynôme d’interpolation (en rouge) oscille violemment près des extrémités. À droite : avec 11 nœuds de Tchebychev, plus denses vers les extrémités, le polynôme (en vert) suit de près la fonction (en bleu).

Avec des nœuds équidistants, quand le degré augmente l’erreur près des extrémités croît sans limite : avec 21 nœuds le polynôme atteint des valeurs supérieures à 50, alors que la fonction reste entre 0 et 1. La cause est le produit \prod(x - x_i), qui avec des nœuds équidistants est bien plus grand près des extrémités qu’au milieu. (La raison profonde est complexe, au sens des nombres complexes : f a des pôles en \pm i/5, proches de l’intervalle.)

La leçon pratique : ne pas utiliser de polynômes de degré élevé sur des nœuds équidistants. C’est la même raison pour laquelle un polynôme de degré 10 ajusté à des données expérimentales produit des courbes aux ondulations absurdes entre les points.

Les nœuds de Tchebychev

Si l’on peut choisir les nœuds, il vaut la peine de les resserrer vers les extrémités. Les nœuds de Tchebychev sur [-1, 1] sont

    \[ x_i = \cos\frac{(2i + 1)\pi}{2(n + 1)},\qquad i = 0, \dots, n \]

les projections sur l’axe de points équidistants sur un demi-cercle. Ils rendent le produit \prod|x - x_i| aussi petit que possible (au plus 2^{-n}), et avec eux l’interpolation des fonctions régulières converge toujours. C’est le principe que les bibliothèques numériques utilisent pour approcher les fonctions mathématiques.

Les splines

L’alternative la plus utilisée en pratique est d’interpoler par morceaux : un polynôme de bas degré entre chaque paire de nœuds, raccordés de façon lisse.

  • Linéaire par morceaux : les points sont reliés par des segments. Simple et sans oscillations, mais avec des angles. C’est ce que fait un tableur avec un graphique en lignes, et une table de correspondance dans un microcontrôleur.
  • Spline cubique : entre deux nœuds un polynôme du troisième degré, avec valeurs, dérivées premières et dérivées secondes continues aux nœuds. C’est la courbe la plus « lisse » qui passe par les points : elle minimise l’intégrale du carré de la dérivée seconde, c’est-à-dire l’énergie de flexion d’une lame élastique forcée de passer par les points. C’est exactement l’origine du nom : la spline était la lame de bois flexible que les dessinateurs navals maintenaient avec des poids pour tracer les courbes des coques.

Les coefficients se trouvent en résolvant un système linéaire tridiagonal, ce qui demande O(n) opérations. Les splines ne souffrent pas du phénomène de Runge, et avec un pas h l’erreur est proportionnelle à h^4.

Applications. Les contours des polices de caractères (TrueType utilise des courbes de Bézier quadratiques, PostScript et OpenType des cubiques), les trajectoires de robots et de machines à commande numérique, la linéarisation de capteurs comme les thermocouples et les thermistances à partir des tables du fabricant, le rééchantillonnage de l’audio et des images.

Interpolation et approximation

L’interpolation a un sens quand les données sont exactes. S’il s’agit de mesures bruitées, forcer la courbe à passer par chaque point revient à suivre aussi le bruit. Dans ce cas on cherche une courbe simple qui passe près des points dans l’ensemble : l’approximation aux moindres carrés, sujet de la leçon suivante.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x