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.

ProblématiqueModifier

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 particulier) 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. 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 f est la fonction réelle et P le polynôme devant approcher f, il faut minimiser la borne supérieure de la fonction |Pf | 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 et −ε et qui change de signe N+1 fois, donnant une erreur dans les pires cas de ε. (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 Tchebychev 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 × 10−5.
 
Erreur entre le polynôme optimal et exp (en rouge), et entre l'approximation de Tchebychev 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 × 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 et −ε 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.

Approximation par des polynômesModifier

ÉnoncéModifier

Soit f une fonction continue sur un intervalle réel fermé [a, b]. Soit P un polynôme de degré n.

On note ϵ = P – f l'erreur d'approximation entre P et f.

S'il existe ax0 < x1 < … < xn+1b et s ∈ {−1, 1} tels que

pour tout i ∈ {0, … , n + 1}, ϵ(xi) = (−1)i sPf ‖,

alors

P est un polynôme d'approximation optimal de f parmi les polynômes de degré inférieur ou égal à n,

au sens de la norme sup sur [a, b].

DémonstrationModifier

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 à –ε.

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 ε, 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 polynomiale 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 TchebychevModifier

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 f :

 

et l'on coupe la série obtenue après le N-iè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-iè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 Tchebychev. Si un développement de Tchebychev 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 Tchebychev 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. 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 TchebychevModifier

Cette partie est le suivantes reposent principalement sur les ouvrages de Cheney[1] et de Powell[2]


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 des telles familles de fonctions se doivent d'avoir certaines bonne propriétés qu'ont les polynômes. Nous les appellerons «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 HaarModifier

Une familles de fonctions  d'un intervalle   dans   satisfait les conditions de Haar si et seulement si

  1. Toutes les fonctions   sont continues.
  2. Les fonctions   satisfont les conditions équivalentes suivantes :
    1. Pour tous   distincts  
    2. Pour tous   distincts, pour tous  , il existe un unique tuple   tel que la fonction   satisfasse  
    3. Les fonctions   sont linéairement indépendantes et  est l'unique fonction de la forme   ayant strictement plus   racines  

Une famille finie de fonctions   satisfaisant les conditions de Haar est appelée un système de Tchebychev. Bien évidemment les monômes de degré échelonnés   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 qui son degré.


Nous pourrons aussi dire d'un sous-espace vectoriel   de   de dimension   satisfait les conditions de Haar si et seulement si ses bases sont des systèmes de Tchebychev.

Équivalence des caractérisationsModifier

Donnons maintenant la démonstration de l'équivalence des points 2.1, 2.2 et 2.3. Nous procédons pas implications circulaires.

  Supposons la propriété 2.1. Considérons   distincts et  . Par l'hypothèse 2.1, nous avons en particulier que la matrice   est inversible. Il existe donc une unique solution à l'équation   Or, cette dernière équation est équivalente à  . Nous obtenons ainsi l'existence et l'unicité d'un tuple   tel que la   interpole les  en les  .

     a clairement strictement plus de   racines entre   et  , elle en a une infinité. Soit maintenant   ayant   racines distinctes, notées  .  et   coïncident en ces points. Par la propriété 2.2, nous avons donc  . Cela entraîne de plus que les  sont linéairement indépendantes sinon on aurait duplicité de l'écriture de la fonction nulle, ce qui est interdit par l'hypothèse 2.2.

  Soient  distincts. Supposons que la matrice  ne soit pas inversible. Alors ses colonnes sont linéairement dépendantes et donc il existe   tels que  . Alors   sont racines de  qui est donc nulle par la propriété 2.3. Toujours par cette propriété, nous obtenons par indépendance des  que   ce qui est absurde. La matrice est donc inversible et son déterminant est donc non nul.

ExemplesModifier

Voici ici deux exemples de systèmes de Tchebychev :

  • Si   sont deux-à-deux distincts alors   forme un système de Tchebychev sur pour tout intervalle compacte de  .
  • Si   sont deux-à-deux distincts et positifs alors   forme un système de Tchebychev sur pour intervalle compacte de  .


Théorème d'alternanceModifier

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éModifier

Soit   un système de Tchebychev. Soit   une fonction continue. Soient   un polynôme généralisé sur le systèmes de Tchebychev et   l'erreur d'approximation. Alors   est une meilleure approximation uniforme de  , c'est-à-dire  , ssi il existe   tels que  et  

RemarqueModifier

Il est intéressant de noter que si le système de Tchebychev considéré est la base canonique de   alors cet énoncé est exactement celui du théorème dans le cas des polynômes.

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

Théorème de caractérisationModifier

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   un système de Tchebychev, nous noterons  .

ÉnoncéModifier

Soit   un système de Tchebychev. Soit   une fonction continue. Soient   un polynôme généralisé sur le systèmes de Tchebychev et   l'erreur d'approximation. Alors   est de norme minimale ssi   est dans l'enveloppe convexe de  .

DémonstrationModifier

Condition Suffisante : Procédons par contraposée et supposons que   ne soit pas minimale. Alors il est possible de trouver un polynôme généralisé satisfaisant une meilleure erreur d'approximation. Autrement dit, il existe   tels que  .

Posons  . Alors pour tout   nous avons

 

En passant les membres de l'inégalité au carré,

 

Puis  

Et enfin  

Il s'agit donc maintenant de montrer que   n'est pas dans l'enveloppe convexe de  , qui est un sous-ensemble de  , et nous aurons alors démontré la contraposée. Supposons donc le contraire. Il existe  et  tels que   et  . Alors

 

Ceci est bien entendu absurde et nous concluons.

Condition Nécessaire : Pour l'autre sens maintenant, nous procédons de même par contraposée. Supposons donc que   n'est pas dans l'enveloppe convexe,  ,  de .   est fermé car c'est une enveloppe convexe. Il est borné car  'est. En effet   et les   sont continues et   est contenu dans un intervalle borné.   est donc fermé borné en dimension fini (contenu dans  ), il est donc compact. Ainsi   atteint un minimum sur  , disons en  . En particulier  . Soit   quelconque et soit  . Par convexité,  . Puis

 

Pour   suffisamment petit, cette inégalité est violée si  . Donc  . Donc pour tout  ,  .   est un fermé contenu dans  , il est donc aussi compact. Par continuité de   et des  ,   admet un minimum,  . Par ce que nous venons de faire,  . Notons  . Nous allons trouver un   tel que  , ce qui conclura. Posons maintenant  . Par définition,  . Comme pour les autres,  est encore compact. Soit donc   le maximum de   sur  . Nous avons   sinon si   satisfait le maximum alors   et c'est absurde. Alors, si  , nous avons,

 

Si maintenant   alors

 

Alors pour   nous avons

 

Ainsi,  , et   n'est donc pas minimale.

Lemme d'alternanceModifier

Nous allons maintenant produire un lemme pour permettre le lien entre le fait que   soit dans une enveloppe convexe et qu'il y ait l'alternance de signe.

ÉnoncéModifier

Soit  un système de Tchebychev. Soient   et des constante non  . Alors   est dans l'enveloppe convexe de   si et seulement so pour   nous avons  .

DémonstrationModifier

Posons pour commencer pour  le déterminant  . Nous allons montrer que ces déterminants sont tous strictement positifs ou tous strictement négatifs. Pour commencer, ils sont non nuls car le système   satisfait les conditions de Haar. Supposons sont que pour   et   nous ayons

 . Alors par le TVI appliqué à  nous avons l'existence de   tel que  , ce qui est impossible par les conditions de Haar. Ainsi, tous ces déterminant ont le même signe.

Maintenant,   est dans l'enveloppe convexe des   si et seulement si il existe   tels que  et  . Si   alors  . Or par les conditions de Haar, les   forment une base de l'espace   et donc tous les   sont nuls, ce qui n'est pas car leur somme est  . Donc  . De même, pour tout  ,  . En particulier,  . En résolvant ce système linéaire par les règles de Cramer nous avons

 

Puis,  

Les déterminants sont tous du même signe, les   sont strictement positifs. Donc  , c'est-à-dire que les   alternent en signe, ou encore que pour tout  ,   (car ils sont non nuls).

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

Nous allons maintenant utiliser le théorème et le lemme précédemment démontrés pour prouver le théorème d'alternance. Nous prenons les notations de l'énoncé.

Nous avons que   est la meilleur approximation de   pour la norme uniforme si et seulement si   est de norme uniforme minimale. Par le théorème de caractérisation, cela est vrai si et seulement si  est dans l'enveloppe convexe des  . Il existe donc   et   avec   tels que  , ceci viole les contions de Haar si $k<n$. Donc nous avons  . Quitte à ré-indicer, nous prenons les   dans l'ordre croissant  . Par les conditions de Haar, comme dans le lemme, les   sont tous non nuls. Nous pouvons donc appliquer le lemme et obtenir qu'ils alternent en signe. Comme les   sont positifs, ce sont les   qui alternent de signe. Ceci conclut donc la preuve.

Unicité de la meilleure approximationModifier

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éModifier

Soit   un système de Tchebychev. Soit   une fonction continue. Alors il existe une unique meilleure approximation de   dans  .

DémonstrationModifier

Commençons par l'unicité. Supposons donc que   et   sont des meilleures approximations pour  . Nous avons donc que  et cette norme est minimale. Or nous avons alors  . Donc   est encore une meilleure approximation. Soient   donnés par le théorème d'alternance pour  . Supposons que  . Alors au moins l'un des deux ne vaut pas  , disons quitte à renommer  , et donc  . On a

 . Ceci est absurde. Donc  . Donc   à   zéros distincts. Donc par les conditions de Haar, nous obtenons qu'elle est identiquement nulle et donc que  . Nous avons donc l'unicité.

   

Procédons maintenant à la démonstrations de l'existence. Considérons  . Cet ensemble est clairement fermé et borné. Il est non vide puisque la fonction nulle est dans  et   est de dimension finie. Donc   est compact. Ainsi   étant continue sur  , elle y atteint un minimum, disons en  . Or, si   est la meilleure approximation de   alors  par inégalité triangulaire. Donc  . Donc   est bien une meilleure approximation pour  .

Voir aussiModifier


SourcesModifier

  1. (en) CHENEY E.W., Introduction to approximation theory,
  2. (en) POWEL M.J.D., Approximation theory and methods, Cambridge Univetrsity Press,