Loading AI tools
De Wikipédia, l'encyclopédie libre
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 analytiques), 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 allemand Carl Runge découvrit, en 1901, 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.
Considérons la fonction suivante :
On considère (n + 1) points équi-répartis dans le segment [–1, 1] :
Enfin, on considère le polynôme interpolateur de f aux points (xi), c'est-à-dire l'unique polynôme P de degré inférieur ou égal à n tel que P(xi) = f (xi) pour tout i. On note Pn ce polynôme.
Runge a montré que l'erreur d'interpolation entre Pn 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 :
En fait, lorsqu'on augmente le nombre de points, on constate que le polynôme se met à osciller fortement entre les points xi avec une amplitude de plus en plus grande, comme l'illustre la figure.
Le phénomène de Runge est la conséquence de deux propriétés du problème.
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 équi-répartis, il existe un point tel que
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.
De plus, lorsque les nœuds d'interpolation sont équi-répartis, cela empire cette situation, comme cela est expliqué par la suite. En effet, dans un cadre plus général, l'interpolation lagrangienne sur des nœuds équidistants n'est pas la meilleure. En notant (li) la base des polynômes de Lagrange liée aux points (xi), on a :
dont on tire l'estimation suivante :
La constante est appelée constante de Lebesgue associée aux points (xi). On remarque que la constante de Lebesgue ne dépend que des nœuds d'interpolation (elle est indépendante de la fonction à interpoler). Dans le cas des points équidistants, cette constante peut être estimée par :
avec e, nombre d'Euler ou constante de Néper, valant 2,71828… On voit ainsi que dans ce cas, la constante de Lebesgue tend vite vers de grandes valeurs[1].
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.
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 ) décroît lorsque n augmente (on peut le voir en étudiant la constante de Lebesgue des points de Tchebychev, à la croissance logarithmique).
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.
Il est possible d'obtenir de bons résultats en cherchant un polynôme de degré supérieur (par exemple 2n), 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
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[2].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.