Phénomène de Runge

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
La courbe rouge est la fonction de Runge ; la courbe bleue est le polynôme interpolateur de degré 5 et la courbe verte est le polynôme interpolateur de degré 9. L'approximation est de plus en plus mauvaise.

Dans le domaine mathématique de l'analyse numérique, le phénomène de Runge se manifeste dans le contexte de l'interpolation polynomiale, en particulier l'interpolation de Lagrange. Avec certaines fonctions (même infiniment dérivables), l'augmentation du nombre n de points d'interpolation ne constitue pas nécessairement une bonne stratégie d'approximation.

En étudiant cette question, le mathématicien Carle David Tolmé Runge découvrit un résultat contraire à l'intuition : il existe des configurations où l'écart maximal entre la fonction et son interpolation augmente indéfiniment avec n.

Exemple où le phénomène de Runge se produit[modifier | modifier le code]

Considérons la fonction suivante :

f(x) = \frac{1}{1+25x^2}

On considère (n+1) points équirépartis dans le segment [-1, 1]:

 \scriptstyle x_0 = -1, \; x_1 = x_0 + h, \; \cdots, \; x_{k+1} = x_k + h = x_0 + (k+1)h, \; \cdots, \; x_n = 1 \ \text{avec} \  h = \textstyle \frac{2}{n}

Enfin, on considère le polynôme interpolateur de f aux points (x_i), c'est-à-dire l'unique polynôme P de degré inférieur ou égal à n tel que P(x_i) = f(x_i) pour tout i. On note P_n ce polynôme.


Runge a montré que l'erreur d'interpolation entre P_n et f tend vers l'infini lorsque n augmente. Autrement dit, plus on fixe de points où le polynôme a la même valeur que f, moins bien on approche la fonction. Formellement :

\lim_{n \rightarrow \infty} \left( \max_{-1 \leq x \leq 1} | f(x) -P_n(x)| \right) = \infty

En fait, lorsqu'on augmente le nombre de points, on constate que le polynôme se met à osciller fortement entre les points x_i avec une amplitude de plus en plus grande, comme l'illustre la figure.

Explication[modifier | modifier le code]

Par applications répétées du théorème de Rolle, on peut montrer que pour le cas d'une interpolation avec (n+1) points équirépartis, il existe un point \xi \in ]-1;1[ tel que

f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) .

Dans l'exemple choisi, les valeurs des dérivées successives de la fonction augmentent avec le nombre de points, ainsi les oscillations entre chaque point d'interpolation s'amplifient.

Dans un cadre plus général, l'interpolation lagrangienne sur des nœuds équidistants n'est pas une méthode stable. En effet, en notant (li) la base des polynômes de Lagrange liées aux points (xi), on a :

P_n(x) = \sum_{i=0}^n f(x_i) l_i(x),

dont on tire l'estimation suivante :

\left|P_n(x) \right| \leqslant \left( \sum_{i=0}^n \left|l_i(x)\right| \right)\| f\|_\infty \leqslant \sup_{x\in [a,b]} \left( \sum_{i=0}^n \left|l_i(x)\right| \right)\| f\|_\infty.

La constante \Lambda_n = \sup_{x\in [a,b]} \left( \sum_{i=0}^n \left|l_i(x)\right| \right) est appelée constante de Lebesgue associée aux points (xi). Dans le cas des points équidistants, cette constante peut être estimée par :

\Lambda_n \sim \frac{2^{n+1}}{e\,n \ln(n)},

avec e, la constante de Néper valant 2,7183... On voit ainsi que dans ce cas, la constante de Lebesgue tend vite vers de grandes valeurs, plus vite que ne peut converger le polynôme interpolateur vers la fonction f[1].

Solutions au problème posé par le phénomène de Runge[modifier | modifier le code]

Le phénomène de Runge met en lumière le fait que l'interpolation polynomiale n'est pas toujours bien adaptée à l'approximation de fonctions.

Choix des points[modifier | modifier le code]

On peut minimiser l'oscillation des polynômes interpolateurs en utilisant les abscisses de Tchebychev au lieu de points équirépartis pour interpoler. Dans ce cas, on peut montrer que l'erreur d'interpolation (c'est-à-dire \max_{-1 \leq x \leq 1} | f(x) -P_n(x)|) décroît lorsque n augmente (on peut le voir en étudiant la constante de Lebesgue des points de Tchebychev, à la croissance logarithmique).

Segmentation[modifier | modifier le code]

Pour approcher une fonction avec des polynômes, on peut préférer utiliser des splines par exemple (ce sont des polynômes par morceaux). Dans ce cas, pour améliorer l'approximation, on augmente le nombre de morceaux et non le degré des polynômes.

Minimisation sous contraintes[modifier | modifier le code]

Il est possible d'obtenir de bons résultats en cherchant un polynôme de degré supérieur (par exemple 2 n), mais en formulant le problème en termes d'optimisation sous contrainte (afin de résorber les degrés de liberté excédentaires). Parmi tous les polynômes croisant la fonction aux points d'interpolation, on recherche celui qui minimise

  • l'intégrale du carré de sa dérivée première (pénalisation des « pentes raides »).
  • l'intégrale du carré de sa dérivée seconde (pénalisation des faibles rayons de courbure, polynôme « tendu »).
  • une combinaison des deux termes précédents.

Il s'agit de minimiser une forme quadratique sous contraintes linéaires, ce qui revient finalement à résoudre un système d'équations linéaires[réf. nécessaire].

Références[modifier | modifier le code]

  1. Jean-Pierre Demailly, Analyse numérique et équations différentielles, EDP Sciences, coll. « Grenoble Sciences »,‎ 2006 (ISBN 2-86889-891-X[à vérifier : isbn invalide])

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

On pourra comparer le phénomène de Runge au phénomène de Gibbs qui se produit lorsqu'on interpole des fonctions par des polynômes trigonométriques.