Théorie de l'approximation

Modèle:À sourcer Modèle:À recycler 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.

Problématique

Le problème de l'approximation s'est posé très tôt en géométrie, pour les fonctions trigonométriques : ce sont des fonctions dont on connaît les propriétés (parité, dérivabilité, valeurs en des points particuliers) mais qui ne s'expriment pas à partir d'opérations réalisables à la main (les quatre opérations). Cela a conduit à la notion de développement en série entière. On a pu ainsi constituer des tables trigonométriques, puis, avec une démarche similaire, des tables logarithmiques, et de manière générale des tables pour les fonctions couramment utilisées en sciences comme la racine carrée.

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 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 Modèle:Mvar est la fonction réelle et Modèle:Mvar le polynôme devant approcher Modèle:Mvar, il faut minimiser la borne supérieure de la fonction $|P-f|$ sur le domaine. Pour une fonction « convenable », un polynôme optimum de degré Modèle:Mvar est caractérisé par une courbe d'erreur dont la valeur oscille entre Modèle:Math et Modèle:Math et qui change de signe Modèle:Math fois, donnant une erreur dans les pires cas de Modèle:Mvar. Il est possible de construire des fonctions Modèle:Mvar pour lesquelles cette propriété ne tient pas, mais dans la pratique elle est généralement vraie.

• 
  Erreur entre le polynôme optimal de degré 4 et le logarithme népérien Modèle:Math (en rouge), et entre l'approximation de Tchebychev de Modèle:Math (en bleu) sur l'intervalle [2, 4]. Le pas vertical est de Modèle:Nb. L'erreur maximale pour le polynôme optimal est de Modèle:Nb.
• 
  Erreur entre le polynôme optimal de degré 4 et l'exponentielle Modèle:Math (en rouge), et entre l'approximation de Tchebychev et Modèle:Math (en bleu) sur l'intervalle [−1, 1]. Le pas vertical est de Modèle:Nb. L'erreur maximale pour le polynôme optimal est de Modèle:Nb.

Modèle:Clr Dans chaque cas, le nombre d'extrema est de Modèle:Math 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 Modèle:Math et Modèle:Math exactement. Si un polynôme de degré Modèle:Mvar mène à une fonction d'erreur qui oscille entre les extrema Modèle:Math fois, alors ce polynôme est optimal.

Approximation par des polynômes

Énoncé

Soit Modèle:Mvar une fonction continue sur un intervalle réel fermé Modèle:Math. Soit Modèle:Mvar un polynôme de degré Modèle:Mvar.

On note $\epsilon =P-f$ l'erreur d'approximation entre Modèle:Mvar et Modèle:Mvar.

S'il existe $a\le x_0<x_1<\cdots <x_{n+1}\le b$ et $s\in \{-1,1\}$ tels que

$\mathrm{\forall }i\in \{0,\dots ,n+1\},\epsilon (x_i)=(-1{)}^{i}s\Vert P-f{\Vert }_{\mathrm{\infty }}$,

alors Modèle:Mvar est un polynôme d'approximation optimal de Modèle:Mvar parmi les polynômes de degré inférieur ou égal à Modèle:Mvar au sens de la norme sup sur Modèle:Math :

$P=\arg \underset{Q\in {ℝ}_n[X]}{\min }\Vert f-S{\Vert }_{\mathrm{\infty },[a,b]}$

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 Tchebychev 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 Tchebychev au lieu des fonctions trigonométriques habituelles.

On calcule les coefficients dans le développement de Tchebychev d'une fonction Modèle:Mvar :

$f(x)\simeq \sum _{n=0}^{\mathrm{\infty }}{c}_n{T}_n(x)$

dont on ne garde que les Modèle:Mvar premiers termes de la série, ce qui donne un polynôme de degré Modèle:Mvar approchant la fonction Modèle:Mvar.

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, l'erreur commise sur le développement au bout de Modèle:Mvar termes 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 Tchebychev. Si un développement de Tchebychev est interrompu après Modèle:Mvar, alors l'erreur sera proche du terme en Modèle:Math. Les polynômes de Tchebychev possèdent la propriété d'avoir une courbe représentative « au niveau », oscillant entre +1 et −1 dans l'intervalle [−1, 1]. Modèle:Math a Modèle:Math extrema. Cela signifie que l'erreur entre Modèle:Mvar et son approximation de Tchebychev jusqu'à un terme en Modèle:Mvar est une fonction ayant Modèle:Math extrema, dont les maxima (respectivement les minima) sont égaux, et est ainsi proche du polynôme optimal de degré Modèle:Mvar.

Dans les exemples graphiques ci-dessus, on peut voir 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 la fonction exponentielle, dont la série entière est très rapidement convergente, que pour la fonction logarithme.

Systèmes de Tchebychev

Cette partie et les suivantes reposent principalement sur les ouvrages de Cheney et de Powell.

Il est possible de généraliser la caractérisation de «meilleure approximation» avec des espaces de fonctions d'approximations qui ne sont pas des polynômes mais des fonctions standard. Cependant, de telles familles de fonctions se doivent d'avoir certaines bonnes propriétés qu'ont les polynômes. On parle alors de « polynômes généralisés ». Ces « polynômes » auront pour monômes des fonctions de base (que l'on considère agréables) qui satisfont les conditions de Haar.

Conditions de Haar

Une famille de fonctions $\{g_1,\dots ,g_n\}$ d'un intervalle $[a,b]$ dans $ℝ$ satisfait les conditions de Haar si et seulement si

1. Toutes les fonctions $g_i$ sont continues.
2. Les fonctions $g_1,\dots ,g_n$ satisfont les conditions équivalentes suivantes :
   1. Pour tous $x_1,\dots ,x_n\in [a,b]$ distincts $\left|\begin{array}{ccc}{g}_1(x_1)& \cdots & g_n(x_1)\\ ⋮& & ⋮\\ g_1(x_n)& \cdots & g_n(x_n)\end{array}\right|\ne 0$
   2. Pour tous $x_1,\dots ,x_n\in [a,b]$ distincts, pour tous $y_1,\dots ,y_n$, il existe un unique tuple $({\alpha }_1,\dots ,{\alpha }_n)$ tel que la fonction $f=\sum _{i=1}^n{\alpha }_i{g}_i$ satisfasse $\mathrm{\forall }i\in \{1,\dots ,n\}f(x_i)=y_i$
   3. Les fonctions $g_1,\dots ,g_n$ sont linéairement indépendantes et $x\mapsto 0$ est l'unique fonction de la forme $x\mapsto \sum _{i=1}^n{\alpha }_i{g}_i(x)$ ayant strictement plus $n-1$ racines $[a,b]$

Une famille finie de fonctions $g_1,\dots ,g_n\in 𝒞([a,b])$ satisfaisant les conditions de Haar est appelée un système de Tchebychev. Bien évidemment les monômes de degré échelonnés $\{1,X,\dots X^{n-1}\}$ forment un système de Tchebychev : les polynômes sont continus, la condition 2.1 est le déterminant de Vandermonde, la condition 2.2 est la caractérisation du polynôme d'interpolation et la condition 2.3 est le fait qu'un polynôme de degré fixé ne peut avoir plus de racine que son degré.

On peut aussi dire d'un sous-espace vectoriel $E$ de $𝒞([a,b])$ de dimension $n$ satisfait les conditions de Haar si et seulement si ses bases sont des systèmes de Tchebychev.

Exemples

On peut citer deux exemples de systèmes de Tchebychev :

• Si ${\lambda }_1,\dots ,{\lambda }_n$ sont deux-à-deux distincts alors $\{{\mathrm{e}}^{{\lambda }_{1}x},\dots ,{\mathrm{e}}^{{\lambda }_{n}x}\}$ forme un système de Tchebychev sur pour tout intervalle compact de $ℝ$.
• Si ${\lambda }_1,\dots ,{\lambda }_n$ sont deux-à-deux distincts et positifs alors $\{x^{{\lambda }_1},\dots ,x^{{\lambda }_n}\}$ forme un système de Tchebychev sur pour intervalle compact de $ℝ$.

Théorème d'alternance

Les systèmes de Tchebychev permettent de caractériser les meilleures approximations de fonctions continues étant des polynômes généralisés construites à partir des fonctions du-dit système.

Énoncé

Soit $\{g_1,\dots ,g_n\}\subseteq 𝒞([a,b])$ un système de Tchebychev. Soit $f\in 𝒞([a,b])$ une fonction continue. Soient $p^{*}=\sum _{i=1}^n{\alpha }_i^{*}{g}_i$ un polynôme généralisé sur le système de Tchebychev et $r^{*}=f-p^{*}$ l'erreur d'approximation. Alors $p^{*}$ est une meilleure approximation uniforme de $f$, c'est-à-dire $\Vert r^{*}{\Vert }_{\mathrm{\infty }}=\underset{p\in \text{Vect}(g_1,\dots ,g_n)}{\min }\Vert f-p{\Vert }_{\mathrm{\infty }}$, ssi il existe $a\le x_0<\cdots <x_n\le b$ tels que $r(x_i)=(-1{)}^{i}r(x_0)$ et $r(x_0)=\pm \Vert r{\Vert }_{\mathrm{\infty }}$

Remarque

Il est intéressant de noter que si le système de Tchebychev considéré est la base canonique de ${ℝ}_{n-1}[X]$ alors cet énoncé est exactement celui du théorème dans le cas des polynômes.

Démonstration du théorème d'alternance

Théorème de caractérisation

La première chose à faire est de caractériser les meilleures approximations par des polynômes généralisés. On peut commencer par montrer qu'il suffit que l'origine de l'espace soit dans une certaine enveloppe convexe. Pour $\{g_1,\dots ,g_n\}$ un système de Tchebychev, On note $\hat{x}=(g_1(x),\dots ,g_n(x){)}^T$.

Lemme d'alternance

Il vient un lien entre le fait que 0 soit dans une enveloppe convexe et qu'il y ait l'alternance de signe.

Unicité de la meilleure approximation

Jusqu'ici, nous avons caractérisé ce qu'est une meilleure approximation. Nous allons maintenant montrer que la meilleure approximation existe et est unique.

Énoncé

Soit $\{g_1,\dots ,g_n\}\subseteq 𝒞([a,b])$ un système de Tchebychev. Soit $f\in 𝒞([a,b])$ une fonction continue. Alors il existe une unique meilleure approximation de $f$ dans $\text{Vect}(g_1,\dots ,g_n)$.

Démonstration

Commençons par l'unicité. Supposons donc que $p$ et $q$ sont des meilleures approximations pour $f$. Nous avons donc que $\Vert f-p{\Vert }_{\mathrm{\infty }}=\Vert f-q{\Vert }_{\mathrm{\infty }}$ et cette norme est minimale. Or nous avons alors ${\Vert f-\frac{p+q}{2}\Vert }_{\mathrm{\infty }}\le \Vert f-p{\Vert }_{\mathrm{\infty }}$. Donc $r=\frac{p+q}{2}$ est encore une meilleure approximation. Soient $x_0<\cdots <x_n$ donnés par le théorème d'alternance pour $r$. Supposons que $p(x_i)\ne q(x_i)$. Alors au moins l'un des deux ne vaut pas $r(x_i)$, disons quitte à renommer $q(x_i)$, et donc $|f(x_i)-q(x_i)|<\Vert f-r{\Vert }_{\mathrm{\infty }}$. On a

$\Vert f-r{\Vert }_{\mathrm{\infty }}=|f(x_i)-r(x_i)|\le \frac{1}{2}|f(x_i)-p(x_i)|+\frac{1}{2}|f(x_i)-q(x_i)|<\Vert f-r{\Vert }_{\mathrm{\infty }}$. Ceci est absurde. Donc $r(x_i)=p(x_i)=q(x_i)$. Donc $p-q$ à $n+1$ zéros distincts. Donc par les conditions de Haar, nous obtenons qu'elle est identiquement nulle et donc que $p=q$. Nous avons donc l'unicité.

Procédons maintenant à la démonstration de l'existence. Considérons $F=\{p\in \text{Vect}(g_1,\dots ,g_n)|\Vert p{\Vert }_{\mathrm{\infty }}\le 2\Vert f{\Vert }_{\mathrm{\infty }}\}$. Cet ensemble est clairement fermé et borné. Il est non vide puisque la fonction nulle est dans $F$ et $\text{Vect}(g_1,\dots ,g_n)$ est de dimension finie. Donc $F$ est compact. Ainsi $p\mapsto \Vert f-p{\Vert }_{\mathrm{\infty }}$ étant continue sur $F$, elle y atteint un minimum, disons en $p^{*}$. Or, si $p$ est la meilleure approximation de $f$ alors $\Vert p{\Vert }_{\mathrm{\infty }}-\Vert f{\Vert }_{\mathrm{\infty }}\le \Vert f-p{\Vert }_{\mathrm{\infty }}\le \Vert f{\Vert }_{\mathrm{\infty }}$ par inégalité triangulaire. Donc $p\in F$. Donc $p^{*}$ est bien une meilleure approximation pour $f$.

Voir aussi

• Développement limité
• Algorithme de Remez
• Inégalité de Jackson
• Série de Fourier généralisée