Théorie de l'approximation

En mathématiques, la théorie de l'approximation concerne la façon dont les fonctions peuvent être approchées par de plus simples fonctions, en donnant une caractérisation quantitative des erreurs introduites par ces approximations.

Un problème particulièrement intéressant est celui de l'approximation de fonctions par d'autres définies uniquement à partir d'opérations de base d'un ordinateur, comme par exemple l'addition et la multiplication, afin de créer des bibliothèques de fonctions mathématiques qui à l'exécution produisent des valeurs les plus proches possibles des valeurs théoriques. C'est ce qui s'appelle l'approximation polynomiale ou rationnelle (c'est-à-dire par des fonctions rationnelles).

L'objectif est de donner une approximation aussi précise que possible d'une fonction réelle donnée, de façon à fournir des valeurs les plus exactes possibles, à la précision près de l'arithmétique en virgule flottante d'un ordinateur. Ce but est atteint en employant un polynôme de degré élevé, et/ou en rapetissant le domaine sur lequel le polynôme doit approcher la fonction. Le rapetissement du domaine peut souvent être effectué, bien que cela nécessite la composition par d'autres fonctions affines, de la fonction à approcher. Les bibliothèques mathématiques modernes réduisent souvent le domaine en le divisant en de multiples minuscules segments et emploient un polynôme de bas degré sur chaque segment.

Une fois le domaine et le degré du polynôme choisis, le polynôme lui-même est choisi de façon à minimiser l'erreur dans le pire des cas. Autrement dit, si $f$ est la fonction réelle et $P$ le polynôme devant approcher $f$, il faut minimiser la borne supérieure de la fonction $\mid P-f\mid$ sur le domaine. Pour une fonction « convenable », un polynôme optimum de degré $N$ est caractérisé par une courbe d'erreur dont la valeur oscille entre $+\varepsilon$ et $-\varepsilon$ et qui change de signe $N+2$ fois, donnant une erreur dans les pires cas de $\varepsilon$. (Il est possible de construire des fonctions $f$ pour lesquelles cette propriété ne tient pas, mais dans la pratique elle est généralement vraie.) Des exemples de représentations graphiques, pour $N=4$, montrent l'erreur obtenue en approchant $Log$ et $\exp$, et sont présentés ci-dessous.

Erreur entre le polynôme optimal et Log (en rouge), et entre l'approximation de Chebyshev de Log (en bleu) sur l'intervalle [2, 4]. Le pas vertical est de $10^{-5}$. L'erreur maximale pour le polynôme optimal est de $6,07 \times 10^{-5}$

Erreur entre le polynôme optimal et $\exp$ (en rouge), et entre l'approximation de Chebyshev et $\exp$ (en bleu) sur l'intervalle [-1, 1]. Le pas vertical est de $10^{-4}$. L'erreur maximale pour le polynôme optimal est de $5,47 \times 10^{-4}$

Dans chaque cas, le nombre d'extrema est de $N+2$ c'est-à-dire 6. Deux des extrema sont les extrémités du segment. Les courbes en rouge, pour le polynôme optimal, sont de « niveau » c'est-à-dire qu'elles oscillent entre $+\varepsilon$ et $-\varepsilon$ exactement. Si un polynôme de degré $N$ mène à une fonction d'erreur qui oscille entre les extrema $N+2$ fois, alors ce polynôme est optimal.

Énoncé

Soit $f$ une fonction continue sur un intervalle réel fermé $[a, b]$. Soit $P$ un polynôme de degré $n$. On note $\epsilon = P-f$ l'erreur d'approximation entre $P$ et $f$. S'il existe $a \le x_0 < x_1 < ... < x_{n+1} \le b$ et $s \in \{-1, 1\}$ tel que pour tout $i \in \{0, ..., n+1\}, \epsilon(x_i) = (-1)^i s ||P-f||_{\infty}$, alors $P$ est un polynôme d'approximation optimal de $f$ au sens de la norme sup sur $[a, b]$, parmi les polynômes de degré inférieur ou égal à $n$.

Démonstration

Commençons par le montrer sur un graphique. Posons $n=4$. Supposons que $P$ soit un polynôme de degré $n$ possédant les propriétés ci-dessus, dans le sens que $P-f$ oscille entre $n+2$ extrema de signes alternés, de $+\varepsilon$ à $-\varepsilon$.

La fonction erreur $P-f$ pourrait ressembler au graphique rouge:

L'erreur $P-f$ pour le polynôme de niveau est représentée en rouge, et l'erreur pour le prétendu meilleur polynôme est représentée en bleu

$P-f$ atteint $n+2$ extrema (dont deux se trouvent aux extrémités), qui ont la même grandeur en valeur absolue situés dans 6 intervalles sur le graphique ci-dessus.

Soit à présent $Q$, un polynôme d'approximation de degré $n$ optimal. Cela signifie que les extrema de sa fonction erreur doivent tous avoir en valeur absolue une valeur strictement plus petite que $\varepsilon$, de sorte qu'ils sont localisés strictement à l'intérieur du graphique d'erreur pour $P$. La fonction erreur pour $Q$ pourrait avoir une représentation graphique ressemblant au graphique bleu ci-dessus. Cela signifie que $(P-f)-(Q-f)$ doit osciller entre des nombres non nuls strictement positifs et strictement négatifs, un nombre total de $n+2$ fois. Mais $(P-f)-(Q-f)$ est égale à $P-Q$ qui est un polynôme de degré $n$. Il doit avoir au moins les $n+1$ racines situées entre différents points en lesquels la fonction polynôme prend des valeurs non nulles. Or, dans un anneau intègre, un polynôme non nul de degré $n$ ne peut avoir plus de $n$ racines. Donc $P-Q$ est identiquement nul, c'est-à-dire que $P = Q$.

Approximation de Chebyshev

Il est possible d'obtenir des polynômes très proches d'un polynôme optimal en développant une fonction donnée avec des polynômes de Chebyshev puis en coupant le développement à un certain degré. Ce procédé est semblable au développement en séries de Fourier d'une fonction, en analyse de Fourier, mais en utilisant les polynômes de Chebyshev au lieu des fonctions trigonométriques habituelles.

On calcule les coefficients dans le développement de Chebyshev d'une fonction $f$:

$f(x) \simeq \sum_{n=0}^\infty c_n T_n(x)$

et on coupe la série obtenue après le $N$^ème terme, on obtient un polynôme de degré $N$ approchant la fonction $f$.

La raison pour laquelle ce polynôme est presque optimal est que, pour des fonctions admettant un développement en série entière, dont la série a une convergence rapide et est coupée après le $N$^ème, l'erreur résultant de la coupure est approximativement égale au terme suivant immédiatement la coupure. C'est-à-dire que, le premier terme juste après la coupure domine la somme de toutes les termes suivants appelée reste de la série. Ce résultat subsiste si le développement se fait avec des polynômes de Chebyshev. Si un développement de Chebyshev est coupé après le terme en $T_n$, alors l'erreur sera proche du terme en $T_{n+1}$. Les polynômes de Chebyshev possèdent la propriété d'avoir une courbe représentative « au niveau », oscillant entre +1 et -1 dans l'intervalle [- 1, 1]. $T_{n+1}$ a $n+2$ extrema. Cela signifie que l'erreur entre $f$ et son approximation de Chebyshev jusqu'à un terme en $T_n$ est une fonction ayant $n+2$ extrema, dont les maxima (respectivement les minima) sont égaux, et est ainsi proche du polynôme optimal de degré $n$.

Dans les graphiques ci-dessus, notez que la fonction d'erreur représentée en bleu est parfois meilleure (lorsqu'elle reste en dessous) que la fonction représentée en rouge, mais plus mauvaise sur certains intervalles, ce qui signifie que ce n'est pas tout à fait le polynôme optimal. Cette différence est relativement moins importante pour l'exponentielle, dont la série entière est très rapidement convergente, que pour la fonction logarithme.

Voir aussi

• Développement limité
• Polynômes de Chebyshev
• Algorithme de Remez
• Inégalité de Jackson (en)

• Cet article est partiellement ou en totalité issu de l'article intitulé « Théorie de l'approximation/Démonstrations » (voir la liste des auteurs).