Chebychev polynomials

Definition

Let $n\in \mathbf{N}$ . The Chebychev polynomial of degree 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

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


0	1
1
2
3
4
5

Recurrence relation between Chebychev polynomials

Proposition. , 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

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

Proposition.The coefficient of the $n^{th}$ -degree term of

is $2^{n-1}$ .

Proof. We shall proceed by induction. The coefficient of is $1=2^{1-1=0}$ . Assume that the coefficient of the $n^{th}$ -degree term of 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 ( $2x\times\ldots)$ . Thus, $2\times 2^{n-1}=2^{n}$ .

Orthogonality of Chebychev polynomials

Chebychev polynomials are pairwise -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}^{*}$ . has exactly 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

has degree

, the $(x_k)_{k=0,1,\ldots,n-1}$ are precisely the roots of

. 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}^{*}$ . has exactly 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

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

. 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

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

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

sign changes for the map $(Q-\bar{T}_{n+1})$ , and consequently, $(Q-\bar{T}_{n+1})$ has

roots. But, $(Q-\bar{T}_{n+1})$ has degree

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

Definition

Explicit computation of Chebychev Polynomials

Recurrence relation between Chebychev polynomials

Orthogonality of Chebychev polynomials

Roots of Chebychev polynomials

Extrema of Chebychev polynomials

The maximum reached by Chebychev polynomials

Best choice of points of interpolation of Lagrange polynomial

Sections

In the same section