Phénomène de Runge

Imaginez des points régulièrement espacés sur une courbe, puis un unique polynôme contraint de passer par chacun. Ajouter des points semble devoir améliorer le tracé. Pourtant, près des extrémités, le polynôme peut former des vagues de plus en plus hautes alors que la courbe visée reste calme.

Cette dégradation paradoxale est le phénomène de Runge. Elle ne vient pas d'une erreur de calcul : elle résulte du choix de nœuds équidistants associé à un polynôme global de degré élevé. Rapprocher les nœuds des bords, comme le font les nœuds de Chebyshev, réduit fortement ces oscillations.

Soit une fonction continue sur un intervalle fermé. Pour un entier n, on choisit n + 1 abscisses distinctes, appelées nœuds, et l'on construit l'unique polynôme de degré au plus n qui prend aux nœuds les mêmes valeurs que la fonction. Avec des nœuds équidistants, le phénomène de Runge désigne l'apparition d'oscillations près des extrémités lorsque le degré augmente, au point que l'erreur peut y croître au lieu de tendre vers zéro.

Dans l'exemple historique mis en évidence par Carl Runge, la fonction est $f(x)=\frac{1}{1+x^2}f(x)=\backslash frac\{1\}\{1+x^2\}$ sur l'intervalle [−5, 5]. Pour un entier n ≥ 1, les nœuds équidistants, indexés par l'entier k allant de 0 à n, sont définis par $x_k=-5+\frac{10k}{n}x\_k=-5+\backslash frac\{10k\}\{n\}$. La suite des interpolants ne converge pas uniformément vers la fonction : les écarts s'amplifient dans des zones proches de −5 et de 5.

Le degré élevé n'est donc pas, à lui seul, le problème. La difficulté vient de son association avec une interpolation globale et des nœuds équidistants. Des nœuds de Chebyshev, plus denses près des extrémités, contrôlent mieux l'amplification de l'erreur. Une interpolation par morceaux, notamment par splines de faible degré, constitue une autre stratégie courante.

On interpole la fonction $f(x)=\frac{1}{1+x^2}f(x)=\backslash frac\{1\}\{1+x^2\}$ sur [−5, 5] et l'on observe le point d'abscisse 4,5. Les données sont : cinq nœuds équidistants pour le degré 4, onze pour le degré 10, et les valeurs de la fonction à chacun de ces nœuds.

1. Pour chaque degré n, les nœuds sont $x_k=-5+\frac{10k}{n}x\_k=-5+\backslash frac\{10k\}\{n\}$, avec k entier de 0 à n. Les espacements valent donc 2,5 pour le degré 4 et 1 pour le degré 10.

2. La valeur de référence au point choisi est $f(\mathrm{4,5})=\frac{1}{\mathrm{21,25}}\approx \mathrm{0,04706}f(4\{,\}5)=\backslash frac\{1\}\{21\{,\}25\}\backslash approx0\{,\}04706$.

3. On évalue les deux polynômes avec la formule de Lagrange, où p_n est l'interpolant de degré au plus n. Dans le produit, j indexe tous les autres nœuds que x_k, d'où la condition j ≠ k : Le calcul donne p₄(4,5) ≈ −0,28912 et p₁₀(4,5) ≈ 1,57872.

4. Les erreurs absolues sont donc environ 0,33618 puis 1,53166. Le contrôle est refaisable en remplaçant 4,5 dans la formule : malgré six nœuds supplémentaires, l'erreur est multipliée par environ 4,56. Avec les onze nœuds-racines de Chebyshev $x_k=5\cos \text{\hspace{0.17em}⁣}\left(\frac{(2k+1)\pi }{22}\right),k=0,\dots ,10x\_k=5\backslash cos\backslash !\backslash left(\backslash frac\{(2k+1)\backslash pi\}\{22\}\backslash right),\backslash quad\; k=0,\backslash ldots,10$, le même calcul donne environ 0,03518, soit une erreur d'environ 0,01188. Les profils comparés rendent visible l'oscillation qui cause cet écart.

Lorsqu'un ajustement interpolant se met à onduler près des bords alors que les données y restent régulières, augmenter encore le degré est un mauvais réflexe. On compare d'abord l'erreur au centre et aux extrémités. Une croissance localisée aux bords signale le risque de Runge.

Si les positions d'échantillonnage peuvent être choisies, on préfère des nœuds de Chebyshev lorsque l'objectif reste un polynôme global. Leur concentration près des extrémités limite l'amplification responsable des grandes oscillations.

Si les mesures sont déjà prises sur une grille régulière, une interpolation par morceaux est souvent plus robuste. Des splines de faible degré sont préférables quand on veut une courbe lisse sans imposer à tout l'intervalle un seul polynôme de degré élevé.

Phénomène de Runge et surajustement. Le surajustement décrit un modèle qui épouse aussi le bruit et généralise mal. Le phénomène de Runge existe même avec des valeurs exactes et sans bruit : pour la fonction 1/(1 + x²), les oscillations viennent de l'interpolation polynomiale sur nœuds équidistants.

Interpolation et approximation. Un interpolant passe exactement par toutes les données imposées ; une approximation n'y est pas nécessairement contrainte. Si une courbe lisse reste légèrement éloignée d'un point mesuré, elle peut être une approximation, mais elle n'est pas l'interpolant de ces données.

Phénomène de Runge et instabilité numérique. Une instabilité due aux arrondis change avec la précision du calcul ou l'algorithme d'évaluation. Les oscillations de Runge persistent en arithmétique exacte : modifier seulement la précision ne les supprime pas, tandis que changer les nœuds le peut.

Davantage de nœuds ne garantit pas une meilleure précision. Dans l'exemple à l'abscisse 4,5, passer de 5 à 11 nœuds équidistants fait croître l'erreur absolue d'environ 0,33618 à 1,53166. Il faut contrôler l'erreur sur tout l'intervalle, surtout près des bords.

Le phénomène n'affecte pas toute fonction de la même façon. L'échec de la fonction de Runge ne prouve pas que toute interpolation équidistante diverge. Le symptôme à rechercher est une oscillation qui s'amplifie avec le degré ; en son absence, on ne conclut pas par simple analogie.

Changer la formule d'évaluation ne suffit pas. Une forme barycentrique peut rendre le calcul de l'interpolant plus stable, mais elle représente le même polynôme pour les mêmes nœuds. Pour réduire l'erreur d'interpolation elle-même, il faut changer la répartition des nœuds ou employer une méthode par morceaux.

L'article interpolation polynomiale de Lagrange détaille la construction de l'unique polynôme passant par des valeurs données, point de départ du phénomène de Runge.