Knowledge base dedicated to Linux and applied mathematics.
Home > Mathematics > Interpolation > Chebyshev polynomials
All the versions of this article: <English> <français>
Chebyshev 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.
Other names: Chebysheff, Chebyshov, Tschebyscheff, Tschebycheff
Let $n\in \mathbf{N}$. The Chebyshev 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) $$
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 Chebyshev 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$ |
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}$.
Chebyshev 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.
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’}$
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} $$
A forthwith consequence of the previous propositions is that:
$$ \max_{[-1,1]} |T_n(x)|=1 $$
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 Chebyshev 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 Chebyshev 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 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} $$