Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Interpolation > Chebychev polynomials

Chebychev polynomials

All the versions of this article: [English] [français]

Chebychev polynomials are a useful and important tool in the field of interpolation. Indeed, in order to minimize the error in Lagrange interpolation, the roots of Chebychev polynomials are definitely the best suited points of interpolation.

Definition

Let n\in \mathbf{N}. The Chebychev polynomial of degree n is the map defined as follows:


T_n:[-1,1] \rightarrow \mathbf{R},\quad x \longmapsto \cos (n\mbox{Arccos } x)

Explicit computation of Chebychev Polynomials

Let x\in [-1,1] and \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}


where E is the floor function and \Re is the real part.
The following table gives the first Chebychev polynomials:

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 kb

Recurrence relation between Chebychev polynomials

Proposition. T_0(x)=1, T_1(x)=x and for any number n\in\mathbf{N}


T_{n+2}(x)=2xT_{n+1}(x)-T_n(x)


Proof. Let x\in[-1,1] and \alpha=\mbox{Arccos } x. By means of trigonometry formulae, we have the following two equalities:

\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


Adding these two equalities, one obtains:

\cos (n+2)\alpha + \cos n\alpha = 2\cos (n+1)\alpha \cdot \cos \alpha


Therefore, for any x in [-1,1]:

T_{n+2}(x)+T_n(x)=2xT_{n+1}(x)


Proposition.The coefficient of the n^{th}-degree term of T_n is 2^{n-1}.

Proof. We shall proceed by induction. The coefficient of T_1 is 1=2^{1-1=0}. Assume that the coefficient of the n^{th}-degree term of T_n is 2^{n-1}. Then, given the previous recurrence relation, one can see that the coefficient of the n+1^{th}-degree term is twice that of T_n (2x\times\ldots). Thus, 2\times 2^{n-1}=2^{n}.

Orthogonality of Chebychev polynomials

Chebychev polynomials are pairwise w-orthogonal; that is, they are orthogonal with regard to a weighted function defined by:

w(x)=\frac{1}{\sqrt{1-x^2}}


In particular:


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


Proof. To compute the previous integral, we use the following substitution:

x=\cos \theta,\quad dx=-\sin\theta d\theta


We thus have:


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


The conclusion is therefore obvious.

Roots of Chebychev polynomials

Proposition. Let n\in \mathbf{N}^{*}. T_n has exactly n simple roots defined as follows:


x_k=\cos \left(\frac{2k+1}{2n}\pi\right),\quad k=0,1,\ldots,n-1.


Proof. Let n\in \mathbf{N}^{*} and 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}


Since T_n has degree n, the (x_k)_{k=0,1,\ldots,n-1} are precisely the roots of T_n. They are simple roots since for all k\neq k’, we have x_k\neq x_{k’}

Extrema of Chebychev polynomials

Proposition. Let n\in \mathbf{N}^{*}. T_n has exactly (n+1) extrema defined by:


x’_k=\cos \left(\frac{k\pi}{n}\right),\quad k=0,1,\ldots,n.


Proof. Let n\in \mathbf{N}^{*} and k=0,1,\ldots,n. The first derivative of T_n is:


\forall x\in [-1,1],T’_n(x)=\frac{n}{\sqrt{1-x^2}}\sin (n\mbox{Arccos } x)


Therefore:


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


Proof.


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

The maximum reached by Chebychev polynomials

A forthwith consequence of the previous propositions is that:


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

Best choice of points of interpolation of Lagrange polynomial

We have seen that if f\in \mathcal{C}^{n+1}([a,b]) and x\in[a,b], then:

\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)|


The aim is to determine the points of interpolation (x_k)_{k=0,1,\ldots,n} such that


\sup_{x\in[a,b]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[a,b]}|Q(x)|


for all n+1^{nth}-degree monic polynomials Q.
Via an affine substitution, the equivalent problem is:


\sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[-1,1]}|Q(x)|


We shall prove that the points of interpolation that verify this property are precisely te roots of the Chebychev polynomial T_{n+1}.

Theorem.


\sup_{x\in[-1,1]}|(x-x_0)(x-x_1)\ldots(x-x_n)|\leq \sup_{x\in[-1,1]}|Q(x)|


where


x_k=\cos \left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,1,\ldots,n.


Proof.
Let \bar{T}_{n+1}=\frac{1}{2^n}T_{n+1} be the monic Chebychev polynomial associated to T_{n+1}. The roots of \bar{T}_{n+1} are those of T_{n+1} and are defined by:


x_k=\cos \left(\frac{2k+1}{2(n+1)}\pi\right),\quad k=0,1,\ldots,n.


We a fortiori have:

\bar{T}_{n+1}=(x-x_0)(x-x_1)\ldots(x-x_n)


Additionally:


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


Since


\bar{T}_{n+1}(x’_k)=\frac{1}{2^n}T_{n+1}(x’_k)=\frac{(-1)^k}{2^n}.


where


x’_k=\cos \left(\frac{k\pi}{(n+1)}\right),\quad k=0,1,\ldots,n+1.


We thus have to show that:


\frac{1}{2^n}\leq \sup_{x\in[-1,1]}|Q(x)|


We shall proceed by contradiction by assuming that:


\frac{1}{2^n} > \sup_{x\in[-1,1]}|Q(x)|.


Since Q and \bar{T}_{n+1} are monic polynomials:


\deg (Q-\bar{T}_{n+1})=n.


Also


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


If k is an even number:

(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

If k is an odd number:

(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

Finally:

(Q-\bar{T}_{n+1})(x’_k)(Q-\bar{T}_{n+1})(x’_{k+1})<0,\quad\forall k=0,1,\ldots,n,\quad


This means that there are (n+1) sign changes for the map (Q-\bar{T}_{n+1}), and consequently, (Q-\bar{T}_{n+1}) has (n+1) roots. But, (Q-\bar{T}_{n+1}) has degree n. Therefore:

Q-\bar{T}_{n+1}=0


Q=\bar{T}_{n+1}


Finally:


 \sup_{x\in[-1,1]}|Q(x)|=\sup_{x\in[-1,1]}|\bar{T}_{n+1}(x)|=\frac{1}{2^n}.


which contradicts our assumption. We finally conclude that:

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

Any message or comments?

comments powered by Disqus