Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Interpolation > Polynà´mes de Tchebychev

Polynà´mes 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.

Définition

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)

Calcul explicite des polynà´mes de Tchebychev

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
PNG - 473.6 ko

Relation de récurrence entre les polynà´mes de Tchebychev

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

Orthogonalité des polynà´mes de Tchebychev

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.

Racines des polynà´mes de Tchebychev

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’}

Extrema des polynà´mes de Tchebychev

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}

Maximum atteint par les polynà´mes de Tchebychev

Une conséquence immédiate des propositions suivantes est que :


\max_{[-1,1]} |T_n(x)|=1

Meilleur choix des points d’interpolation du polynà´me de Lagrange

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}

Un message, un commentaire ?

comments powered by Disqus