Théorie de l'approximation

Cet article ne cite pas suffisamment ses sources (novembre 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Cet article concernant les mathématiques doit être recyclé (juin 2020).

Une réorganisation et une clarification du contenu paraissent nécessaires. Améliorez-le, discutez des points à améliorer ou précisez les sections à recycler en utilisant {{section à recycler}}.

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 }$.

${\displaystyle P-f}$

${\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}$.

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.

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.

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.

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