Théorie de l'approximation

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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[modifier | modifier le code]

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ômes[modifier | modifier le code]

Énoncé[modifier | modifier le code]

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émonstration[modifier | modifier le code]

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 Tchebychev[modifier | modifier le code]

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 Tchebychev[modifier | modifier le code]

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 Haar[modifier | modifier le code]

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èmes 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érisations[modifier | modifier le code]

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.

Exemples[modifier | modifier le code]

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'alternance[modifier | modifier le code]

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 | modifier le code]

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

Remarque[modifier | modifier le code]

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'alternance[modifier | modifier le code]

Théorème de caractérisation[modifier | modifier le code]

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 | modifier le code]

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émonstration[modifier | modifier le code]

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'alternance[modifier | modifier le code]

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 | modifier le code]

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émonstration[modifier | modifier le code]

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'alternance[modifier | modifier le code]

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 approximation[modifier | modifier le code]

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

Énoncé[modifier | modifier le code]

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

Démonstration[modifier | modifier le code]

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 aussi[modifier | modifier le code]


Sources[modifier | modifier le code]

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