Théorie de l'approximation

Un article de Wikipédia, l'encyclopédie libre.

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 à réduire au minimum 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 réduire au minimum 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
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
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. (voir la démonstration.)

[modifier] Approximation de Tchebychev

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 Tn, alors l'erreur sera proche du terme en Tn + 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]. Tn + 1 a n + 2 extrema. Cela signifie que l'erreur entre f et son approximation de Chebyshev jusqu'à un terme en Tn 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. Notez également que cette différence est relativement moins importante pour la fonction exponentielle, dont la série entière est très rapidement convergente, que pour la fonction logarithme.

[modifier] Voir aussi