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é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. 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 ${\displaystyle |P-f|}$ 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.

• 
  Erreur entre le polynôme optimal de degré 4 et le logarithme népérien ln (en rouge), et entre l'approximation de Tchebychev de ln (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 de degré 4 et l'exponentielle e (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

Énoncé

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

On note ${\displaystyle \varepsilon =P-f}$ l'erreur d'approximation entre P et f.

S'il existe ${\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{n+1}\leq b}$ et ${\displaystyle s\in \{-1,\;1\}}$ tels que

${\displaystyle \forall i\in \{0,\ldots ,n+1\},\varepsilon (x_{i})=(-1)^{i}s\|P-f\|_{\infty }}$,

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

${\displaystyle P=\operatorname {arg} \min _{Q\in \mathbb {R} _{n}[X]}\|f-S\|_{\infty ,[a,b]}}$

Démonstration

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

La fonction erreur ${\displaystyle P-f}$ pourrait ressembler au graphique rouge :

L'erreur ${\displaystyle 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.

${\displaystyle P-f}$ atteint ${\displaystyle 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 ${\displaystyle Q}$, un polynôme d'approximation de degré ${\displaystyle n}$ optimal. Cela signifie que les extrema de sa fonction erreur doivent tous avoir en valeur absolue une valeur strictement plus petite que ${\displaystyle \varepsilon }$, de sorte qu'ils sont localisés strictement à l'intérieur du graphique d'erreur pour ${\displaystyle P}$.

La fonction erreur pour ${\displaystyle Q}$ pourrait avoir une représentation graphique ressemblant au graphique bleu ci-dessus. Cela signifie que ${\displaystyle (P-f)-(Q-f)}$ doit osciller entre des nombres non nuls strictement positifs et strictement négatifs, un nombre total de ${\displaystyle N+2}$ fois. Mais ${\displaystyle (P-f)-(Q-f)}$ est égale à ${\displaystyle P-Q}$ qui est un polynôme de degré ${\displaystyle n}$. Il doit avoir au moins les ${\displaystyle 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é ${\displaystyle n}$ ne peut avoir plus de ${\displaystyle n}$ racines. Donc ${\displaystyle P-Q}$ est identiquement nul, c'est-à-dire que ${\displaystyle P=Q}$.

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

${\displaystyle f(x)\simeq \sum _{n=0}^{\infty }c_{n}T_{n}(x)}$

dont on ne garde que les N premiers termes de la série, ce qui donne 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, l'erreur commise sur le développement au bout de N 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 T_N, alors l'erreur sera proche du terme en T_{N + 1}. 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]. T_{n + 1} a n + 2 extrema. Cela signifie que l'erreur entre f et son approximation de Tchebychev 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 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[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, 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 ${\displaystyle \{g_{1},\dots ,g_{n}\}}$ d'un intervalle ${\displaystyle [a,b]}$ dans ${\displaystyle \mathbb {R} }$ satisfait les conditions de Haar si et seulement si

1. Toutes les fonctions ${\displaystyle g_{i}}$ sont continues.
2. Les fonctions ${\displaystyle g_{1},\dots ,g_{n}}$ satisfont les conditions équivalentes suivantes :
   1. Pour tous ${\displaystyle x_{1},\dots ,x_{n}\in [a,b]}$ distincts ${\displaystyle \left|{\begin{matrix}g_{1}(x_{1})&\cdots &g_{n}(x_{1})\\\vdots &&\vdots \\g_{1}(x_{n})&\cdots &g_{n}(x_{n})\end{matrix}}\right|\neq 0}$
   2. Pour tous ${\displaystyle x_{1},\dots ,x_{n}\in [a,b]}$ distincts, pour tous ${\displaystyle y_{1},\dots ,y_{n}}$, il existe un unique tuple ${\displaystyle (\alpha _{1},\dots ,\alpha _{n})}$ tel que la fonction ${\displaystyle f=\sum _{i=1}^{n}\alpha _{i}g_{i}}$ satisfasse ${\displaystyle \forall i\in \{1,\dots ,n\}\quad f(x_{i})=y_{i}}$
   3. Les fonctions ${\displaystyle g_{1},\dots ,g_{n}}$ sont linéairement indépendantes et ${\displaystyle x\mapsto 0}$ est l'unique fonction de la forme ${\displaystyle x\mapsto \sum _{i=1}^{n}\alpha _{i}g_{i}(x)}$ ayant strictement plus ${\displaystyle n-1}$ racines ${\displaystyle [a,b]}$

Une famille finie de fonctions ${\displaystyle g_{1},\dots ,g_{n}\in {\mathcal {C}}([a,b])}$ satisfaisant les conditions de Haar est appelée un système de Tchebychev. Bien évidemment les monômes de degré échelonnés ${\displaystyle \{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 ${\displaystyle E}$ de ${\displaystyle {\mathcal {C}}([a,b])}$ de dimension ${\displaystyle n}$ satisfait les conditions de Haar si et seulement si ses bases sont des systèmes de Tchebychev.

Équivalence des caractérisations

La démonstration de l'équivalence des points 2.1, 2.2 et 2.3 se fera par implications circulaires.

2.1 ⇒ 2.2 Considérons ${\displaystyle x_{1},\dots ,x_{n}\in [a,b]}$ distincts et ${\displaystyle y_{1},\dots ,y_{n}\in \mathbb {R} }$. Par l'hypothèse 2.1, on remarque en particulier que la matrice

${\displaystyle M:=\left({\begin{matrix}g_{1}(x_{1})&\cdots &g_{n}(x_{1})\\\vdots &&\vdots \\g_{1}(x_{n})&\cdots &g_{n}(x_{n})\end{matrix}}\right)}$7

est inversible. Il existe donc une unique solution à l'équation ${\displaystyle M\cdot (a_{1},\dots ,a_{n})^{T}=(y_{1},\dots ,y_{n})^{T}}$ Or, cette dernière équation est équivalente à ${\displaystyle \forall i\in \{1,\dots ,n\}\quad \sum _{j=1}^{n}a_{j}g_{j}(x_{i})=y_{i}}$. Il vient ainsi l'existence et l'unicité d'un tuple ${\displaystyle (\alpha _{1},\dots ,\alpha _{n})}$ tel que la ${\displaystyle f=\sum _{i=1}^{n}\alpha _{i}g_{i}}$ interpole les y_i en les x_i.

2.2 ⇒ 2.3 La fonction nulle ${\displaystyle x\mapsto 0}$ a clairement strictement plus de n - 1 racines entre a et b, car elle en a une infinité. Soit maintenant ${\displaystyle f=\sum _{i=1}^{n}\alpha _{i}g_{i}}$ ayant n racines distinctes, notées ${\displaystyle x_{1},\dots ,x_{n}}$. La fonction nulle et f coïncident en ces points. Par la propriété 2.2, on a donc f = 0. Cela entraîne de plus que les g_i 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.

2.3 ⇒ 2.1 Soient ${\displaystyle x_{1},\dots ,x_{n}\in [a,b]}$ distincts. Supposons que la matrice ${\displaystyle M:=\left({\begin{matrix}g_{1}(x_{1})&\cdots &g_{n}(x_{1})\\\vdots &&\vdots \\g_{1}(x_{n})&\cdots &g_{n}(x_{n})\end{matrix}}\right)}$ ne soit pas inversible. Alors ses colonnes sont linéairement dépendantes et donc il existe ${\displaystyle \alpha _{1},\dots ,\alpha _{n}}$ tels que ${\displaystyle \forall j\in \{1,\dots ,n\}\quad \sum _{i=1}^{n}\alpha _{i}g_{i}(x_{j})=0}$. Alors ${\displaystyle x_{1},\dots ,x_{n}}$ sont racines de ${\displaystyle \sum _{i=1}^{n}\alpha _{i}g_{i}}$ qui est donc nulle par la propriété 2.3. Toujours par cette propriété, il suit par indépendance des g_i que ${\displaystyle \forall i\in \{1,\dots ,n\}\quad \alpha _{i}=0}$ ce qui est absurde. La matrice est donc inversible et son déterminant est donc non nul.

Exemples

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

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

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 ${\displaystyle \{g_{1},\dots ,g_{n}\}\subseteq {\mathcal {C}}([a,b])}$ un système de Tchebychev. Soit ${\displaystyle f\in {\mathcal {C}}([a,b])}$ une fonction continue. Soient ${\displaystyle p^{*}=\sum _{i=1}^{n}\alpha _{i}^{*}g_{i}}$ un polynôme généralisé sur le système de Tchebychev et ${\displaystyle r^{*}=f-p^{*}}$ l'erreur d'approximation. Alors ${\displaystyle p^{*}}$ est une meilleure approximation uniforme de ${\displaystyle f}$, c'est-à-dire ${\displaystyle \|r^{*}\|_{\infty }=\min _{p\in {\textrm {Vect}}(g_{1},\dots ,g_{n})}{\|f-p\|_{\infty }}}$, ssi il existe ${\displaystyle a\leq x_{0}<\cdots <x_{n}\leq b}$ tels que ${\displaystyle r(x_{i})=(-1)^{i}r(x_{0})}$ et ${\displaystyle r(x_{0})=\pm \|r\|_{\infty }}$

Remarque

Il est intéressant de noter que si le système de Tchebychev considéré est la base canonique de ${\displaystyle \mathbb {R} _{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 ${\displaystyle \{g_{1},\dots ,g_{n}\}}$ un système de Tchebychev, On note ${\displaystyle {\hat {x}}=(g_{1}(x),\dots ,g_{n}(x))^{T}}$.

Soit ${\displaystyle \{g_{1},\dots ,g_{n}\}\subseteq {\mathcal {C}}([a,b])}$ un système de Tchebychev. Soit ${\displaystyle f\in {\mathcal {C}}([a,b])}$ une fonction continue. Soient ${\displaystyle p=\sum _{i=1}^{n}\alpha _{i}^{*}g_{i}}$ un polynôme généralisé sur le système de Tchebychev et ${\displaystyle r=f-p}$ l'erreur d'approximation. Alors r est de norme minimale si et seulement si 0 est dans l'enveloppe convexe de ${\displaystyle \{r(x){\hat {x}}\ |\ r(x)=\|r\|_{\infty }\}}$.

Démonstration

Condition suffisante

Procédons par contraposée et supposons que ${\displaystyle \|r\|_{\infty }}$ 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 ${\displaystyle d=(d_{1},\dots ,d_{n})}$ tels que ${\displaystyle \left\|\sum _{i=1}^{n}(\alpha _{i}^{*}-d_{i})g_{i}\right\|_{\infty }<\|r\|_{\infty }}$.

Posons ${\displaystyle X=\{x\in [a,b]\ |\ |r(x)|=\|r\|_{\infty }\}}$. Alors pour tout ${\displaystyle x\in X}$ nous avons

${\displaystyle \left|r(x)-\sum _{i=1}^{n}d_{i}g_{i}(x)\right|\leq \left\|r-\sum _{i=1}^{n}d_{i}g_{i}\right\|_{\infty }=\left\|\sum _{i=1}^{n}(\alpha _{i}^{*}-d_{i})g_{i}\right\|_{\infty }<\|r\|_{\infty }=|r(x)|}$

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

${\displaystyle \left(r(x)-\sum _{i=1}^{n}d_{i}g_{i}(x)\right)^{2}<r(x)^{2}}$

Puis, par développement

${\displaystyle 2r(x)\sum _{i=1}^{n}d_{i}g_{i}(x)>\left(\sum _{i=1}^{n}d_{i}g_{i}(x)\right)^{2}}$

et

${\displaystyle \langle d,r(x){\hat {x}}\rangle =r(x)\sum _{i=1}^{n}d_{i}g_{i}(x)>0}$

Il s'agit donc maintenant de montrer que 0 n'est pas dans l'enveloppe convexe de ${\displaystyle \{r(x){\hat {x}}\ |\ x\in X\}}$, qui est un sous-ensemble de ${\displaystyle \mathbb {R} ^{n}}$, et nous aurons alors démontré la contraposée. Supposons donc le contraire. Il existe ${\displaystyle x_{1},\dots ,x_{n}\in X}$ et ${\displaystyle a_{1},\dots a_{n}\in [0,1]}$ tels que ${\displaystyle \sum _{i=1}^{n}a_{i}r(x_{i}){\hat {x_{i}}}=0}$ et ${\displaystyle \sum _{i=1}^{n}a_{i}=1}$. Alors

${\displaystyle 0=\left\langle {d,0}\right\rangle =\left\langle {d,\sum _{i=1}^{n}a_{i}r(x_{i}){\hat {x_{i}}}}\right\rangle =\sum _{i=1}^{n}a_{i}\langle {d,r(x_{i}){\hat {x_{i}}}}\rangle >0}$

Ceci est bien entendu absurde, CQFD.

Condition nécessaire

On procède également par contraposition. Supposons donc que 0 n'est pas dans l'enveloppe convexe C de l'ensemble ${\displaystyle \{r(x){\hat {x}}\ |\ r(x)=\|r\|_{\infty }\}=\{r(x){\hat {x}}\ |\ x\in X\}}$. C est fermé car c'est une enveloppe convexe. Il est borné car ${\displaystyle \{r(x){\hat {x}}\ |\ r(x)=\|r\|_{\infty }\}}$'est. En effet r et les g_i sont continues et X est contenu dans un intervalle borné. C est donc fermé borné en dimension fini (contenu dans ${\displaystyle \mathbb {R} ^{n}}$), il est donc compact. Ainsi ${\displaystyle \|\cdot \|_{2}}$ atteint un minimum sur C, disons en ${\displaystyle d\in C}$. En particulier ${\displaystyle d\neq 0}$. Soit ${\displaystyle u\in C}$ quelconque et soit ${\displaystyle \lambda \in [0,1]}$. Par convexité, ${\displaystyle \lambda u+(1-\lambda )d\in C}$. Puis

${\displaystyle {\begin{aligned}\|{\lambda u+(1-\lambda )d}\|_{2}^{2}&\geq &\|{d}\|_{2}^{2}\\\|{\lambda u+(1-\lambda )d}\|_{2}^{2}-\|{d}\|_{2}^{2}&\geq &0\\\lambda ^{2}\|{u-d}\|_{2}^{2}+2\lambda \langle {u-d,d}\rangle &\geq &0\end{aligned}}}$

Pour ${\displaystyle \lambda }$ suffisamment petit, cette inégalité est violée si ${\displaystyle \langle {u-d,d}\rangle <0}$. Donc ${\displaystyle \langle {u-d,d}\rangle \geq 0}$. Donc pour tout ${\displaystyle u\in C}$, ${\displaystyle \langle {u,d}\rangle =\langle {u-d,d}\rangle +\|{d}\|_{2}^{2}\geq \|{d}\|_{2}^{2}>0}$. X est un fermé contenu dans C, il est donc aussi compact. Par continuité de r et des g_i, ${\displaystyle \{\langle {d,r(x){\hat {x}}}\rangle \ |\ x\in X\}}$ admet un minimum, ${\displaystyle \epsilon }$. Par ce que nous venons de faire, ${\displaystyle \epsilon >0}$. Notons ${\displaystyle d=(d_{1},\dots ,d_{n})^{T}}$. On va alors chercher ${\displaystyle \mu >0}$ tel que ${\displaystyle \left\|{r-\mu \sum _{i=1}^{n}d_{i}g_{i}}\right\|_{\infty }<\|{r}\|_{\infty }}$, ce qui conclura. Posons maintenant ${\displaystyle Y=\left\{x\in [a,b]]\ |\ \langle {d,r(x){\hat {x}}}\rangle \leq {\frac {\epsilon }{2}}\right\}}$. Par définition, ${\displaystyle Y\cap X=\emptyset }$. Comme pour les autres, Y est encore compact. Soit donc R le maximum de |r| sur Y. On a alors ${\displaystyle R<\|{r}\|_{\infty }}$ sinon si ${\displaystyle y\in Y}$ satisfait le maximum alors ${\displaystyle y\in X}$, ce qui est absurde. Alors, si ${\displaystyle x\in Y}$,

${\displaystyle \forall x\in Y,\,\left|r(x)-\mu \sum _{i=1}^{n}d_{i}g_{i}(x)\right|\leq |r(x)|+\mu \left|\sum _{i=1}^{n}d_{i}g_{i}(x)\right|\leq R+\mu \left\|{\sum _{i=1}^{n}d_{i}g_{i}}\right\|_{\infty }}$

Si maintenant ${\displaystyle x\notin Y}$ alors

${\displaystyle {\begin{aligned}\left|r(x)-\mu \sum _{i=1}^{n}d_{i}g_{i}(x)\right|^{2}&=&r(x)^{2}-2\mu \sum _{i=1}^{n}d_{i}r(x)g_{i}(x)+\mu ^{2}\left(\sum _{i=1}^{n}d_{i}g_{i}(x)\right)^{2}\\&\leq &\|{r}\|_{\infty }^{2}-2\mu \langle {d,r(x){\hat {x}}}\rangle +\mu ^{2}\left(\sum _{i=1}^{n}d_{i}g_{i}(x)\right)^{2}\\&\leq &\|{r}\|_{\infty }^{2}-2\mu {\frac {\epsilon }{2}}+\mu ^{2}\left(\sum _{i=1}^{n}d_{i}g_{i}(x)\right)^{2}&{\textrm {car}}\ x\notin Y\\&\leq &\|{r}\|_{\infty }^{2}+\mu \left(-\epsilon +\mu \left\|{\sum _{i=1}^{n}d_{i}g_{i}}\right\|_{\infty }^{2}\right)\end{aligned}}}$

Alors pour ${\displaystyle 0<\mu <\min \left({\frac {\|{r}\|_{\infty }-R}{2\|{\sum _{i=1}^{n}d_{i}g_{i}}\|_{\infty }}},{\frac {\epsilon }{2\|{\sum _{i=1}^{n}d_{i}g_{i}}\|_{\infty }^{2}}}\right)}$, on a

${\displaystyle {\begin{aligned}\left|r(x)-\mu \sum _{i=1}^{n}d_{i}g_{i}(x)\right|&<&{\frac {\|{r}\|_{\infty }+R}{2}}&\quad {\textrm {pour}}\ x\in Y\\\left|r(x)-\mu \sum _{i=1}^{n}d_{i}g_{i}(x)\right|^{2}&<&\|{r}\|_{\infty }^{2}-{\frac {\mu \epsilon }{2}}&\quad {\textrm {pour}}\ x\notin Y\end{aligned}}}$

Ainsi, ${\displaystyle \left\|{r-\mu \sum _{i=1}^{n}d_{i}g_{i}}\right\|_{\infty }<\|{r}\|_{\infty }}$, et ${\displaystyle r}$ n'est donc pas minimale.

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.

Soit ${\displaystyle \{g_{1},\dots ,g_{n}\}\subseteq {\mathcal {C}}([a,b])}$ un système de Tchebychev. Soient ${\displaystyle a\leq x_{0}<\cdots <x_{n}\leq b}$ et des constantes non ${\displaystyle \lambda _{0},\dots ,\lambda _{n}\in \mathbb {R} ^{*}}$. Alors 0 est dans l'enveloppe convexe de ${\displaystyle \{\lambda _{i}{\hat {x_{i}}}\ |\ i\in \{1,\dots ,n\}\}}$ si et seulement si pour ${\displaystyle i\in \{1,\dots ,n\}}$ nous avons ${\displaystyle \lambda _{i}\lambda _{i-1}<0}$.

Démonstration du lemme

Posons pour commencer pour ${\displaystyle x_{1}<\cdots <x_{n}}$ le déterminant

${\displaystyle D(x_{1},\dots ,x_{n})=\left|{\begin{matrix}g_{1}(x_{1})&\cdots &g_{n}(x_{1})\\\vdots &&\vdots \\g_{1}(x_{n})&\cdots &g_{n}(x_{n})\end{matrix}}\right|}$.

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 ${\displaystyle \{g_{1},\dots ,g_{n}\}}$ satisfait les conditions de Haar. Supposons sont que pour ${\displaystyle x_{1}<\cdots <x_{n}}$ et ${\displaystyle y_{1}<\cdot <y_{n}}$ nous ayons

${\displaystyle D(x_{1},\dots ,x_{n})<0<D(y_{1},\dots ,y_{n})}$. Alors par le théorème des valeurs intermédiaires appliqué à ${\displaystyle \lambda \mapsto D(\lambda x_{1}+(1-\lambda )y_{1},\dots ,\lambda x_{n}+(1-\lambda )y_{n})}$, on a l'existence de ${\displaystyle \lambda \in [0,1]}$ tel que ${\displaystyle D(\lambda x_{1}+(1-\lambda )y_{1},\dots ,\lambda x_{n}+(1-\lambda )y_{n})=0}$, ce qui est impossible par les conditions de Haar. Ainsi, tous ces déterminants ont le même signe.

Dès lors, 0 est dans l'enveloppe convexe des ${\displaystyle \lambda _{i}{\hat {x_{i}}}}$ si et seulement si il existe ${\displaystyle \alpha _{0},\dots ,\alpha _{n}\in [0,1]}$ tels que ${\displaystyle 0=\sum _{i=0}^{n}\alpha _{i}\lambda _{i}{\hat {x_{i}}}}$ et ${\displaystyle \sum _{i=0}^{n}\alpha _{i}=1}$. Si ${\displaystyle \alpha _{0}=0}$ alors ${\displaystyle \sum _{i=1}^{n}\alpha _{i}\lambda _{i}{\hat {x_{i}}}=0}$. Or par les conditions de Haar, les ${\displaystyle \lambda _{i}{\hat {x_{i}}}}$ forment une base de l'espace ${\displaystyle \mathbb {R} ^{n}}$ et donc tous les ${\displaystyle \alpha _{i}}$ sont nuls, ce qui n'est pas car leur somme vaut 1. Donc ${\displaystyle \alpha _{0}\neq 0}$. De même, pour tout i, ${\displaystyle \alpha _{i}\neq 0}$. En particulier, ${\displaystyle {\hat {x_{0}}}=\sum _{i=1}^{n}{\frac {-\lambda _{i}\alpha _{i}}{\lambda _{0}\alpha _{0}}}{\hat {x_{i}}}}$. En résolvant ce système linéaire par les règles de Cramer, on a

${\displaystyle {\frac {-\lambda _{i}\alpha _{i}}{\lambda _{0}\alpha _{0}}}={\frac {D(x_{1},\dots ,x_{i-1},x_{0},x_{i+1},\dots ,x_{n})}{D(x_{1},\dots ,x_{n})}}={\frac {(-1)^{i-1}D(x_{0},\dots ,x_{i-1},x_{i+1},\dots ,x_{n})}{D(x_{1},\dots ,x_{n})}}}$

Puis,

${\displaystyle {\frac {\lambda _{i}}{\lambda _{0}}}={\frac {(-1)^{i}D(x_{0},\dots ,x_{i-1},x_{i+1},\dots ,x_{n})\alpha _{0}}{D(x_{1},\dots ,x_{n})\alpha _{i}}}}$

Les déterminants sont tous du même signe, les ${\displaystyle \alpha _{i}}$ sont strictement positifs. Donc ${\displaystyle {\textrm {sgn}}\lambda _{i}=(-1)^{i}{\textrm {sgn}}\lambda _{0}}$, c'est-à-dire que les ${\displaystyle \lambda _{i}}$ alternent en signe, ou encore que pour tout ${\displaystyle i\in \{1,\dots ,n\}}$, ${\displaystyle \lambda _{i}\lambda _{i-1}<0}$ (car ils sont non nuls).

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

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 p* est la meilleure approximation de f pour la norme uniforme si et seulement si r* est de norme uniforme minimale. Par le théorème de caractérisation, cela est vrai si et seulement si 0 est dans l'enveloppe convexe des ${\displaystyle \{r(x){\hat {x}}\ |\ x\in X\}}$. Il existe donc ${\displaystyle x_{0},\dots ,x_{k}\in X}$ et ${\displaystyle \alpha _{0},\dots \alpha _{k}\in [0,1]}$ avec ${\displaystyle k\leq n}$ tels que ${\displaystyle 0=\sum _{i=1}^{k}\alpha _{i}r(x_{i}){\hat {x_{i}}}}$, ceci viole les conditions de Haar si k < n. Donc nous avons ${\displaystyle k=n}$. Quitte à ré-indicer, on prend les ${\displaystyle x_{i}}$ dans l'ordre croissant ${\displaystyle a\leq x_{0}<\cdots <x_{n}\leq b}$. Par les conditions de Haar, comme dans le lemme, les ${\displaystyle \alpha _{i}r(x_{i})}$ sont tous non nuls. On applique donc le lemme et l'alternance de signe. Comme les ${\displaystyle \alpha _{i}}$ sont positifs, ce sont les ${\displaystyle r(x_{i})}$ qui alternent de signe. Ceci conclut donc la preuve.

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 ${\displaystyle \{g_{1},\dots ,g_{n}\}\subseteq {\mathcal {C}}([a,b])}$ un système de Tchebychev. Soit ${\displaystyle f\in {\mathcal {C}}([a,b])}$ une fonction continue. Alors il existe une unique meilleure approximation de ${\displaystyle f}$ dans ${\displaystyle {\textrm {Vect}}(g_{1},\dots ,g_{n})}$.

Démonstration

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

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

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

Voir aussi

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

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

Sources

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