Knowledge base dedicated to Linux and applied mathematics.
Accueil > Mathématiques > Interpolation > Polynomes de Tchebychev
Toutes les versions de cet article : <English> <français>
Les polynômes de Tchebychev constituent un outil important dans le domaine de l’interpolation : en effet, on démontre que pour minimiser l’erreur d’interpolation de Lagrange, les racines des polynômes de Tchebychev sont les candidats pour être les points d’interpolations.
Soit $n\in \mathbf{N}$. On appelle polynôme de Tchebychev de degré $n$, l’application définit comme suit :
$$ T_n :[-1,1] \rightarrow \mathbf{R},\quad x \longmapsto \cos (n\mbox{Arccos } x) $$
Soit $x\in [-1,1]$ et $\alpha=\mbox{Arccos } x$.
$$ \begin{array}{ccl} T_n(x)&=&\Re((\cos n\alpha +i\sin n\alpha))\\ &=&\Re((\cos \alpha +i\sin \alpha)^n)\\ &=&\Re((\cos \mbox{Arccos } x +i\sin \mbox{Arccos } x)^n)\\ &=&\Re(( x +i\sqrt{1-x^2})^n)\\ &=&\Re(\displaystyle\sum_{k=0}^n C_{n}^{k}x^{n-k} i^{k}(\sqrt{1-x^2})^k)\\ &=&\displaystyle\sum_{k=0}^{E[n/2]} C_{n}^{2k}x^{n-2k} (i)^{2k}(1-x^2)^k\\ &=&\displaystyle\sum_{k=0}^{E[n/2]} C_{n}^{2k}x^{n-2k}(x^2-1)^k \end{array} $$
où $E$ désigne la partie entière et $\Re$ la partie réelle.
Le tableau suivant donne les premiers polynômes de Tchebychev :
$n$ | $T_n$ |
0 | 1 |
1 | $x$ |
2 | $2x^2-1$ |
3 | $4x^3-3x$ |
4 | $8x^4-8x^2+1$ |
5 | $16x^5-20x^3+5x$ |
Proposition.On a $T_0(x)=1$ et $T_1(x)=x$ et pour tout $n\in\mathbf{N}$
$$ T_{n+2}(x)=2xT_{n+1}(x)-T_n(x) $$
Preuve. Soit $x\in[-1,1]$ et $\alpha=\mbox{Arccos } x$. On a en utilisant les formules de trigonométrie classiques, on a les deux égalités suivantes :
$$\cos (n+2)\alpha = \cos (n+1)\alpha \cdot \cos \alpha - \sin (n+1)\alpha \cdot \sin \alpha$$
$$\cos n\alpha = \cos (n+1)\alpha \cdot \cos \alpha + \sin (n+1)\alpha \cdot \sin \alpha$$
En sommant ces deux égalités, on obtient :
$$\cos (n+2)\alpha + \cos n\alpha = 2\cos (n+1)\alpha \cdot \cos \alpha$$
On a alors que pour tout $x$ dans $[-1,1]$ :
$$T_{n+2}(x)+T_n(x)=2xT_{n+1}(x)$$
Proposition.Le coefficient du terme de degré $n$ de $T_n$ est $2^{n-1}$.
Preuve. On procède par récurrence : le coefficient de $T_1$ est
$1=2^{1-1=0}$. Supposons que le coefficient du terme de degré $n$ de $T_n$ soit $2^{n-1}$, alors on voit d’apres la relation de récurrence précédente que le coefficient du terme de degré $(n+1)$ est deux fois celui de $T_n$ ($2x\times\ldots)$ donc $2\times 2^{n-1}=2^{n}$.
Les polynômes de Tchebychev sont $w$-orthogonaux, c’est à dire orthogonaux relativement à la fonction poids définie par :
$$w(x)=\frac{1}{\sqrt{1-x^2}}$$
En l’occurence, on a :
$$ \int_{-1}^{1}T_n(x)T_m(x)w(x)dx= \left\{\begin{array}{ccl} \displaystyle\pi &si& n=m=0\\ \displaystyle \frac{\pi}{2} &si& n=m\neq 0\\ \displaystyle 0 &si& n\neq m\\ \end{array} \right. $$
Preuve.Pour calculer l’intégrale précédente, on fait le changement de variable :
$$x=\cos \theta,\quad dx=-\sin\theta d\theta$$
On a alors :
$$ \begin{array}{ccl} \displaystyle \int_{-1}^{1}T_n(x)T_m(x)w(x)dx&=& - \displaystyle \int_{\pi}^{0}\frac{\cos n\theta \cdot\cos m\theta \sin \theta}{|\sin \theta|}d\theta\\ &=& \displaystyle \int_{0}^{\pi}\cos n\theta \cdot\cos m\theta d\theta\\ &=&\displaystyle \frac{1}{2} \int_{0}^{\pi}\cos (n+m)\theta +\cos (n-m)\theta d\theta\\ \end{array} $$
Il est alors facile de conclure.
Proposition. Soit $n\in \mathbf{N}^{*}$. $T_n$ admet exactement $n$ racines simples définies par :
$$ x_k=\cos \left(\frac{2k+1}{2n}\pi\right),\quad k=0,1,\ldots,n-1. $$
Preuve. Soit $n\in \mathbf{N}^{*}$ et $k=0,1,\ldots,n-1$ :
$$ \begin{array}{ccl} T_n(x_k)&=&\displaystyle\cos (n\mbox{Arccos } x_k)\\ &=&\displaystyle\cos (n\mbox{Arccos }\cos \left(\frac{2k+1}{2n}\pi\right) )\\ &=&\displaystyle\cos n\left(\frac{2k+1}{2n}\pi\right)\\ &=&\displaystyle\cos \left(\frac{2k+1}{2}\pi\right)\\ &=&0 \end{array} $$
$T_n$ étant de degré $n$, les $(x_k)_{k=0,1,\ldots,n-1}$ sont exactement les zéros de $T_n$. Elles sont simples puisque pour tout $k\neq k’$, on a $x_k\neq x_{k’}$
Proposition. Soit $n\in \mathbf{N}^{*}$. $T_n$ admet exactement $(n+1)$ extrema définis par :
$$ x’_k=\cos \left(\frac{k\pi}{n}\right),\quad k=0,1,\ldots,n. $$
Preuve. Soit $n\in \mathbf{N}^{*}$ et $k=0,1,\ldots,n$. La dérivée de $T_n$ est définie :
$$ \forall x\in [-1,1],T’_n(x)=\frac{n}{\sqrt{1-x^2}}\sin (n\mbox{Arccos } x) $$
On a alors :
$$ \begin{array}{ccl} T’_n(x’_k)&=&\displaystyle\frac{n}{\sqrt{1-(x’_k)^2}}\sin (n\mbox{Arccos } x’_k)\\ &=&\displaystyle\frac{n}{\sqrt{1-\cos^2\left(\frac{k\pi}{n}\right)}}\sin (n\mbox{Arccos } \cos \left(\frac{k\pi}{n}\right))\\ &=&\displaystyle\frac{n}{\sqrt{1-\cos^2\left(\frac{k\pi}{n}\right)}}\sin (k\pi)\\ &=&0 \end{array} $$
Proposition.
$$ T_n(x’_k)=(-1)^k,\quad k=0,1,\ldots,n.$$
Preuve.
$$ \begin{array}{ccl} T_n(x’_k)&=&\displaystyle\cos (n\mbox{Arccos } x’_k)\\ &=&\displaystyle\cos (n\mbox{Arccos } \cos \left(\frac{k\pi}{n}\right))\\ &=&\displaystyle\cos (n\frac{k\pi}{n})\\ &=&\displaystyle\cos (k\pi)\\ &=&(-1)^k \end{array} $$
Une conséquence immédiate des propositions suivantes est que :
$$ \max_{[-1,1]} |T_n(x)|=1 $$
Nous avons vu que si $f\in \mathcal{C}^{n+1}([a,b])$ et $x\in[a,b]$, on a :
$$\forall x\in [a,b],\quad |f(x)-P_n(x)|\leq \displaystyle\frac{\displaystyle|(x-x_0)(x-x_1)\ldots(x-x_n)|}{(n+1) !}\sup_{x\in[a,b]}|f^{n+1} (x)|$$
L’objectif est de déterminer les points d’interpolation $(x_k)_{k=0,1,\ldots,n}$ de telle manière que
$$ \sup_{x\in[a,b]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[a,b]}|Q(x)| $$
pour tout polynôme $Q$ normalisé de degré $(n+1)$.
Par un changement de variable affine, il est équivalent de résoudre le problème suivant :
$$ \sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[-1,1]}|Q(x)| $$
Nous allons montrer que les point d’interpolation qui vérifient cette propriété sont exactement les racines du polynôme de Tchebychev $T_{n+1}$.
Théorème.
$$ \sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[-1,1]}|Q(x)| $$
avec
$$ x_k=\cos \left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,1,\ldots,n. $$
Preuve.
Soit $\bar{T}_{n+1}=\frac{1}{2^n}T_{n+1}$ le polynà´me de Tchebychev $T_{n+1}$ normalisé. Les racines de $\bar{T}_{n+1}$ sont donc celles de $T_{n+1}$ , elles sont définies par :
$$ x_k=\cos \left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,1,\ldots,n. $$
On a donc a fortiori
$$\bar{T}_{n+1}=(x-x_0)(x-x_1)\ldots(x-x_n)$$
Par ailleurs
$$ \begin{array}{ccl} \displaystyle \sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|&=&\displaystyle \sup_{x\in[-1,1]} |\bar{T}_{n+1}(x)|\\ &=&\displaystyle\frac{1}{2^n}\sup_{x\in[-1,1]} |T_{n+1}(x)|\\ &=&\displaystyle\frac{1}{2^n} \end{array} $$
De plus
$$ \bar{T}_{n+1}(x’_k)=\frac{1}{2^n}T_{n+1}(x’_k)=\frac{(-1)^k}{2^n}. $$
avec
$$ x’_k=\cos \left(\frac{k\pi}{(n+1)}\right),\quad k=0,1,\ldots,n+1. $$
On doit donc montrer à présent que :
$$ \frac{1}{2^n}\leq \sup_{x\in[-1,1]}|Q(x)| $$
nous allons raisonner par l’absurde en supposant que :
$$ \frac{1}{2^n} > \sup_{x\in[-1,1]}|Q(x)|. $$
Puisque $Q$ et $\bar{T}_{n+1}$ sont normalisé, on a
$$ \deg (Q-\bar{T}_{n+1})=n. $$
On a
$$ \begin{array}{ccl} \forall k=0,1,\ldots,n+1,\quad (Q-\bar{T}_{n+1})(x’_k)&=&Q(x’_k)-\bar{T}_{n+1}(x’_k)\\ &=&\displaystyle Q(x’_k)-\frac{(-1)^k}{2^n} \end{array} $$
Si $k$ est pair :
$$(Q-\bar{T}_{n+1})(x’_k)=\displaystyle Q(x’_k)-\frac{(-1)^k}{2^n}< \displaystyle\frac{1}{2^n}-\frac{1}{2^n}=0$$
Si $k$ est impair :
$$(Q-\bar{T}_{n+1})(x’_k)=\displaystyle Q(x’_k)-\frac{(-1)^k}{2^n}>\displaystyle-\frac{1}{2^n}-\frac{-1}{2^n}=0$$
Au final :
$$ (Q-\bar{T}_{n+1})(x’_k)(Q-\bar{T}_{n+1})(x’_{k+1})<0,\quad\forall k=0,1,\ldots,n,\quad $$
Cela veut donc dire qu’il y a $(n+1)$ changements de signe pour l’application $(Q-\bar{T}_{n+1})$, par suite $(Q-\bar{T}_{n+1})$ admet $(n+1)$ racines, or $(Q-\bar{T}_{n+1})$ est de degré $n$ donc :
$$Q-\bar{T}_{n+1}=0$$
$$Q=\bar{T}_{n+1}$$
et donc
$$ \sup_{x\in[-1,1]}|Q(x)|=\sup_{x\in[-1,1]}|\bar{T}_{n+1}(x)|=\frac{1}{2^n}. $$
ce qui contredit ce que l’on a supposé.
On conclut donc que :
$$\begin{array}{ccl} \displaystyle\frac{1}{2^n}&=&\displaystyle\sup_{x\in[-1,1]}|\bar{T}_{n+1}(x)|\\ &=&\displaystyle\sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\\ &\leq&\displaystyle \sup_{x\in[-1,1]}|Q(x)| \end{array} $$