Definition 6.4.1.
For each nonnegative integer, \(n\text{,}\) the Chebyshev Polynomial \(T_{n}\) is defined for \(x \in [-1,1]\) by
\begin{equation}
T_{n}(x) = \cos (n \cos^{-1}x)\tag{6.4.1}
\end{equation}
Section 6.4 Optimal Points for Interpolation
In Chapter 4, we investigated the details of interpolation. In most cases we used equally-spaced points as the interpolation nodes. The main problem with using such points is that the error associated with this increases as the number of points increases. For example, recall the plot in Figure 6.2.2 On the edges on the interpolation domain, the function swings far above the points. In this section, we look at how to select the interpolation nodes \(x_{0},x_{1}, \ldots, x_{n}\) that may do better.
Subsection 6.4.1 Chebyshev Polynomials
In order to determine the optimal points for interpolation, we first examine a set of functions called the Chebyshev polynomials.
These don’t look much like polynomials, but we will see, in fact, they are. To see that they are each polynomials, we first need to establish,
\begin{equation}
\begin{aligned}T_{n+1}(x)\amp = \cos ((n+1) \cos^{-1}x) = \cos (n \cos^{-1}x + \cos^{-1}x)\\ \amp \qquad \text{and using the sum formula of cosine, one gets} \\ T_{n+1}(x)\amp = \cos (n\cos^{-1}x) \cos(\cos^{-1}x) - \sin(n \cos^{-1}x) \sin (\cos^{-1}x).
\end{aligned}\tag{6.4.2}
\end{equation}
Also in similar manner,
\begin{equation}
\begin{aligned}T_{n-1}(x)\amp = \cos ((n-1) \cos^{-1}x) = \cos (n \cos^{-1}x -\cos^{-1}x) \\\amp = \cos (n\cos^{-1}x) \cos(\cos^{-1}x) + \sin(n \cos^{-1}x) \sin (\cos^{-1}x).
\end{aligned}\tag{6.4.3}
\end{equation}
\begin{equation*}
\begin{aligned}T_{n+1}(x) + T_{n-1}(x)\amp = 2 \cos (n \cos^{-1}x) \cos (\cos^{-1}x) \\\amp = 2x T_{n}(x)\end{aligned}
\end{equation*}
or
\begin{equation}
T_{n+1}(x) = 2x T_{n}(x) - T_{n-1}(x),\tag{6.4.4}
\end{equation}
which is called the recurrence relationship for the Chebyshev polynomials.
\begin{equation*}
\begin{aligned}T_{0}(x)\amp = \cos( 0 \cdot \cos^{-1}x) = 1, \\ T_{1}(x)\amp = \cos (\cos^{-1}x) = x .\end{aligned}
\end{equation*}
And then using the recurrence relationship in (6.4.4), we find the Chebyshev polynomials for \(n=2,3\) and \(4\text{,}\)
\begin{equation*}
\begin{aligned}T_{2}(x)\amp = 2x T_{1} (x) - T_{0}(x) = 2x^{2} -1 \\ T_{3}(x)\amp = 2x T_{2} (x) - T_{1} (x) = 2x(2x^{2}-1) - x \\\amp = 4x^{3} -3x \\ T_{4}(x)\amp = 2x T_{3}(x) - T_{2}(x) = 2x(4x^{3}-3x) - (2x^{2}-1) \\\amp = 8x^{4} -6x^{2} -2x^{2} + 1 \\\amp = 8x^{4} -8x^{2} + 1\end{aligned}
\end{equation*}
The following is a graph of the first five Chebyshev polynomials:
The graph of \(T_{0}\) is the constant 1 and each successive polynomial has higher degree.
From the plot one can see one of the most important properties of Chebyshev—on the interval \([-1,1]\text{,}\) all the polynomials, \(T_{n}(x)\text{,}\) satisfy \(-1 \leq T_{n}(x) \leq 1\text{.}\) The following theorem proves this and other important properties.
Theorem 6.4.3.
The Chebyshev polynomial, \(T_{n}(x)\) has the following properties:
-
\(T_{n}(x)\) has \(n\) simple zeros in \([-1,1]\text{.}\) They are\begin{equation} z_{k} = \cos \biggl(\frac{2k-1}{2n}\pi \biggr)\tag{6.4.5} \end{equation}for \(k=1,2, \ldots,n\text{.}\)
-
The extreme values of \(T_{n}(x)\) are located at\begin{equation*} z_{k}' = \cos \biggl(\frac{k\pi}{n}\biggr) \end{equation*}for \(k=0,1,2, \ldots, n\text{.}\)
-
The function values at the extremes are either \(1\) or \(-1\text{.}\) More specifically,\begin{equation*} T_{n}(z_{k}') = (-1)^{k}. \end{equation*}
Proof.
-
\begin{equation*} \begin{aligned}T_{n}(z_{k})\amp = \cos(n \cos^{-1}z_{k} ), \\\amp = \cos\biggl( n \cos^{-1}\biggl(\cos \biggl(\frac{2k-1}{2n}\pi \biggr) \biggr) \biggr), \\\amp = \cos \biggl( n \frac{2k-1}{2n}\pi \biggr), \\\amp = \cos \biggl( \frac{2k-1}{2}\pi \biggr) = 0 .\end{aligned} \end{equation*}
-
The extremes of \(T_{n}(x)\) are found by first finding the derivative of (6.4.1),\begin{equation*} \begin{aligned}T'_{n}(x)\amp = -\sin (n \cos^{-1}x ) \cdot \frac{-1}{\sqrt{1-x^{2}}}, \\\end{aligned} \end{equation*}and then evaluate it at \(z_{k}'\text{:}\)\begin{equation*} \begin{aligned}T'_{n}(z_{k}')\amp = \frac{\sin ( n \cos^{-1}z_{k}') }{\sqrt{1-(z_{k}')^{2}}}, \\\amp = \frac{\sin ( n \cos^{-1}(\cos (k\pi/n)) }{\sqrt{1-(z_{k}')^{2}}}, \\\amp = \frac{\sin (n \cdot k\pi/n)}{\sqrt{1-(z_{k}')^{2}}}= \frac{\sin (k\pi)}{\sqrt{1-(z_{k}')^{2}}}=0.\\\end{aligned} \end{equation*}and since the derivative is 0, it is an extreme value of \(T_{n}(x)\text{.}\)
-
Lastly, we show that the function values of the extremes are either 1 or \(-1\text{.}\)\begin{equation*} \begin{aligned}T_{n}(z_{k}')\amp = \cos \biggl( n \cos^{-1}\biggl( \cos \biggl(\frac{k\pi}{n}\biggr) \biggr) \biggr) \\\amp = \cos \biggl( n \cdot \frac{k\pi}{n}\biggr) = \cos k \pi =(-1)^{k} .\end{aligned} \end{equation*}
Subsection 6.4.2 Monic Polynomials
We are going to show that the roots of the Chebyshev polynomials will be ideal for choosing interpolation nodes. We will need to show that this will be the best choice and in order to accomplish this we need to discuss of subset of the polynomials called the monic polynomials. These will play an important role.
Definition 6.4.4.
A polynomial is monic if its leading coefficient is \(+1\text{.}\) Let \(\widetilde{\Pi}_{n}\) denote the set of all monic polynomials of degree \(n\text{.}\)
And naturally we will define the monic Chebyshev polynomials to be the Chebyshev polynomials with its leading coefficient of \(1\text{.}\)
Definition 6.4.5.
Let
\begin{equation*}
\begin{aligned}\widetilde{T}_{n}(x)\amp = \begin{cases}T_{0}(x)\amp \text{if $n = 0$}\\ \frac{1}{2^{n-1}}T_{n} (x)\amp \text{otherwise}\end{cases}\end{aligned}
\end{equation*}
be the monic Chebyshev Polynomials
And since these polynomials are monic, \(\widetilde{T}_{n}(x) \in \widetilde{\Pi}_{n}\text{.}\) The next theorem is the reason that we are studying the Chebyshev polynomials. It shows that the they have the smallest maximum value on \([-1,1]\text{.}\)
Theorem 6.4.6.
The monic Chebyshev polynomial, \(\widetilde{T}_{n}(x)\) satisfies
\begin{equation*}
\begin{aligned}\frac{1}{2^{n-1}}= \max_{x \in [-1,1]}|\widetilde{T}_{n}(x)| \leq \max_{x \in [-1,1]}|p_{n}(x)|\end{aligned}
\end{equation*}
for any \(p_{n}(x) \in \widetilde{\Pi}_{n}\text{,}\) and if equality holds then \(p_{n}(x) \equiv \widetilde{T}_{n}(x)\text{.}\)
Proof.
Suppose \(p_{n} \in \widetilde{\Pi}_{n}\) with
\begin{equation*}
\begin{aligned}\max_{x \in [-1,1]}|p_{n}(x)| \leq \max_{x \in [-1,1]}|\widetilde{T}_{n}(x)| .\end{aligned}
\end{equation*}
Let \(q(x) = \widetilde{T}_{n}(x) - p_{n}(x)\text{.}\) Since \(\widetilde{T}_{n}\) and \(p_{n}\) are both monic polynomials of degree \(n\text{,}\) it follows that \(q\) is a polynomial of degree at most \(n-1\text{.}\)
If we evaluate \(q\) at the extrema of \(\widetilde{T}_{n}\) (which we called \(z_{k}'\)),
\begin{equation*}
\begin{aligned}q(z_{k})\amp = \widetilde{T}_{n}(z_{k}') - p_{n}(z_{k}') \\\amp = \frac{(-1)^{k}}{2^{n-1}}- p_{n}(z_{k}')\end{aligned}
\end{equation*}
By supposition, \(|p_{n}(z_{k}')| \leq 2^{1-n}\) so
\begin{equation*}
\begin{aligned}q(z_{k})\amp \geq 0\amp \amp \text{when $k$ is even}\\ q(z_{k})\amp \leq 0\amp \amp \text{when $k$ is odd}\end{aligned}
\end{equation*}
therefore by the intermediate value theorem that there is a root between \(x_{k}\) and \(x_{k+1}\) for \(k=0,1,2, \ldots, n-1\) for a total of \(n\) roots. However, \(q\) is a polynomial of degree at most \(n-1\text{,}\) so this implies that \(q \equiv 0\) so \(T_{n}(x)=p_{n}(x)\text{.}\)
The previous theorem says that the monic polynomials with smallest maximum norm (or \(\ell_{\infty}\)) are the Chebyshev polynomials. Let’s return to the error formula for interpolation. Recall that from Theorem 4.2.6, if \(P(x)\) is the interpolated polynomials using the nodes \(x_{0}, x_{1}, \ldots, x_{n}\text{,}\) then the error is given by
\begin{equation*}
\begin{aligned}|f(x)-P(x)|\amp = \biggl\vert \frac{f^{(n+1)}(\xi(x))}{(n+1)!}\prod_{i=0}^{n} (x-x_{i}) \biggr\vert,\end{aligned}
\end{equation*}
where we examine the polynomial part of the error. Let
\begin{equation*}
\begin{aligned}P_{E}(x)\amp = (x-x_{0})(x-x_{1}) \cdots (x-x_{n})\end{aligned}
\end{equation*}
and note that this is a monic polynomial. We seek to examine this polynomial for various interpolation points.
In the previous section, we saw that when the \(x_{i}\) are equally spaced, large oscillations occur toward the edges of the interval \([a,b]\text{.}\)
The previous theorem showed that the Chebyshev Polynomials are the monic polynomials with smallest maximum norm (\(\ell_{\infty}\)). This would also translate to the polynomials with roots at the Chebyshev roots of \(\widetilde{T}_{n+1}\) which are given in (6.4.5).
Example 6.4.7.
Plot the monic polynomials a) \(\widetilde{T}_{7}\text{,}\) b) with equally-spaced roots and c) randomly spaced roots.
These three polynomials are
\begin{equation*}
\begin{aligned}\widetilde{P}_{7}(x)\amp = (x-1)(x-2/3)(x-1/3)x(x+1/3)(x+2/3)(x+1) \\ \widetilde{T}_{7}(x)\amp = \frac{1}{64}\bigl(64x^{7}-112x^{5}+56x^{3}-7x \bigr) \\ \widetilde{R}_{7}(x)\amp = (x+.3867411)(x+.5507757)(x+.6373457) \\\amp \qquad (x-.7616964)(x-.9693658)(x-0.0796216)(x+.4727200)\end{aligned}
\end{equation*}
and a plot of this is in the following figure.
where the solid line is \(\widetilde{T}_{7}\text{,}\) the dashed line is \(\widetilde{P}_{7}\) and the dotted line is \(\widetilde{R}_{7}\text{.}\) As you can see the polynomial \(\widetilde{T}_{7}\) has the smallest value of \(\max_{x\in[-1,1]}P(x)\) of these three polynomials, and the theorem above proved this is always true.
Subsection 6.4.3 Interpolation on the Chebyshev roots
From the discussion above, it appears that if we interpolate on the Chebyshev roots, then we find the best polynomial in the \(\ell_{\infty}\) sense. The next example shows how to interpolate through these points.
Example 6.4.9.
Find the interpolating polynomial, \(P_{3}(x)\) of \(f(x)=e^{-x}\) on \([-1,1]\) using the Chebyshev roots.
Solution.
First, we need to find the values of the roots of \(\widetilde{T}_{4}\text{.}\) Using:
\begin{equation*}
z_{j} = \cos \biggl( \frac{2j+1}{2(n+1)}\pi \biggr)
\end{equation*}
for \(j=0,1,2,3\text{.}\)
| \(j\) | \(z_{j}\) | \(f(z_{j})\) |
| \(0\) | \(0.9238795325\) | \(0.3969759686\) |
| \(1\) | \(0.3826834325\) | \(0.6820287733\) |
| \(2\) | \(-0.3826834325\) | \(1.4662138010\) |
| \(3\) | \(-0.9238795325\) | \(2.5190441710\) |
We can then use either Newton Divided Differences or Lagrange polynomials to find the interpolant through these points to arrive at:
\begin{equation*}
\begin{aligned}p_{4}(x)\amp = -0.1751756924x^{3}+0.5429007218x^{2}-0.9989332286x+0.9946153174\end{aligned}
\end{equation*}
and examining a plot of \(p_{4}(x)\) and \(e^{-x}\) on \([-1,1]\text{,}\) we get:
which look identical, but we can see that the difference is:
and appears to be about accuracy to 2 decimal places. It also appears that the error is nearly uniformly distributed. It won’t be precisely uniformly distributed due to the function being interpolated.
Subsection 6.4.4 Chebyshev Polynomials on \([a,b]\)
The Chebyshev polynomials are defined on \([-1,1]\text{,}\) however, we may want them on a general interval \([a,b]\text{.}\) Thus, we seek a transformation that maps the interval \([-1,1]\) to \([a,b]\text{.}\)
Let \(z \in [-1,1]\text{,}\) and \(x \in [a,b]\text{,}\) then
\begin{equation*}
\begin{aligned}x = \frac{b-a}{2}z + \frac{a+b}{2}\end{aligned}
\end{equation*}
maps the interval \([a,b]\) to \([-1,1]\text{.}\) This is the same transformation as in (eq:convert:interval) of Section sect:gauss:quad.
Thus, the points
\begin{equation}
t_{k} = \frac{b-a}{2}\cos \biggl( \frac{2k-1}{2n}\pi \biggr) + \frac{a+b}{2}\tag{6.4.6}
\end{equation}
for \(k=1,2,3,\ldots n\) are the Chebyshev roots on the interval \([a,b]\text{.}\) The next example shows how to use this transformation to interpolate a function on the interval \([0,2\pi]\text{.}\)
Example 6.4.12.
Use the points above to find the polynomial interpolant, \(P_{4}\) to \(f(x)=\sin x\) on \([0,2\pi]\text{.}\)
Solution.
| \(k\) | \(t_{k}\) | \(f(t_{k})\) |
| \(1\) | \(6.12942481835027\) | \(-0.153155329681726\) |
| \(2\) | \(4.98817448408867\) | \(-0.962211599609498\) |
| \(3\) | \(3.14159265358397\) | \(0\) |
| \(4\) | \(1.29501082308539\) | \(0.962211599607993\) |
| \(5\) | \(0.15376048883981\) | \(0.153155329692107\) |
Use Newton Divided Difference or Lagrange on the set of points \(\{(t_{k}, f(t_{k}))\}\) to arrive at
\begin{equation*}
\begin{aligned}P_{4} (x)\amp = 0.08515387329\,{x}^{3}- 0.8025563455\,{x}^{2}+ 1.709864800\,x- 0.09108960667\end{aligned}
\end{equation*}
Note: due to the symmetry of \(\sin x\) as well as the symmetry of the interpolation points, there is no \(x^{4}\) term for \(P_{4}\text{.}\) For a comparison, the 4th degree polynomial that passes through the points \(x=0,\pi/2,\pi,3\pi/2,2\pi\) is
\begin{equation*}
\begin{aligned}\widehat{P}_{4}(x)\amp = 0 + \frac{2}{\pi}x -\frac{4}{\pi^{2}}x(x-\pi/2) +\frac{8}{3\pi^{3}}x(x-\pi/2)(x-\pi) \\\amp \qquad + 0 x(x-\pi/2)(x-\pi)(x-3\pi/2) \\\end{aligned}
\end{equation*}
and a plot of the errors
As can be seen from the plot, the Chebyshev approximation, \(P_{4}(x)\) has the smaller maximum error (by about 75%) than the Legendre approximation, \(\widehat{P}_{4}(x)\text{,}\) however neither of these are reasonable approximations in that they still are only accurate to about 1 decimal place. In the next example, we extend the number of points to improve the approximation.
Example 6.4.15.
Extend the example to 9 points. Provide both the Interpolated Polynomial for equally-spaced points on \([0,2\pi]\) and the Chebyshev points on \([0,2\pi]\text{.}\)
Solution.
Using the points \(x_{i} = i \frac{\pi}{4}\) for \(i=0,1,2,\ldots,8\) leads to the polynomial that can be written:
\begin{equation*}
\begin{aligned}\widehat{P}_{8}(x)\amp ={\frac{8x}{315\pi^{7}}}\biggl( 1280\,\sqrt{2}{x}^{6}-8960\,\sqrt{ 2}{x}^{5}\pi +24752\,\sqrt{2}{x}^{4}{\pi }^{2}\\\amp \qquad -34160\,\sqrt{2}{x}^{3 }{\pi }^{3}+24500\,\sqrt{2}{x}^{2}{\pi }^{4}-8540\,\sqrt{2}x{\pi }^{ 5}\\\amp \qquad +1128\,{\pi }^{6}\sqrt{2}-1792\,{x}^{6}+12544\,{x}^{5}\pi -34720\,{ x}^{4}{\pi }^{2}\\\amp \qquad +48160\,{x}^{3}{\pi }^{3}-34783\,{x}^{2}{\pi }^{4}+ 12061\,x{\pi }^{5}-1470\,{\pi }^{6}\biggr).\end{aligned}
\end{equation*}
To find the polynomial that passes through the Chebyshev points, we build a table of \(t_{j}\) from (eq:cheby:pts:[a,b]) and \(f(t_{j})\text{.}\)
| \(j\) | \(t_{j}\) | \(f(t_{j})\) |
| 1 | 6.23545745567117 | -0.0477097333130245 |
| 2 | 5.86229169995749 | -0.408576233017198 |
| 3 | 5.16096948600951 | -0.901063626090171 |
| 4 | 4.21608062324342 | -0.879346445795841 |
| 5 | 3.14159265358397 | 0 |
| 6 | 2.06710468392645 | 0.879346445800469 |
| 7 | 1.12221582116592 | 0.901063626088372 |
| 8 | 0.420893607226473 | 0.408576233021196 |
| 9 | 0.0477278515232653 | 0.0477097333278532 |
The interpolating polynomial that passes through these points is:
\begin{equation*}
\begin{aligned}p_{8}(x)\amp = 0.0001448292x^{7}-0.0031849587x^{6}+0.0220637455x^{5} \\\amp \qquad -0.0322337298x^{4}-.1255921078x^{3}-0.0257364715x^{2} \\\amp \qquad +1.0061352440x-0.00002385113\end{aligned}
\end{equation*}
The plots of the sine function and the interpolates are nearly identical. The following shows the differences \(|\sin x - p_{8}(x)|\) and \(|\sin x - P_{0,\ldots, 8}(x)|\text{,}\)
where the solid line is \(p_{8}(x)\text{,}\) with the Chebyshev nodes and the dashed line is \(\widehat{P}_{8}(x)\text{,}\) where the equally-spaced nodes have been used. The maximum error using \(\widehat{P}_{8}(x)\) is about 5 times larger than the maximum error with \(p_{8}(x)\text{.}\) Also, as we have seen earlier, the error \(|p_{8}(x)-f(x)|\) is distributed uniformly across the interval.
As has been seen in this section, when the nodes used for interpolation are those of the roots of the Chebyshev polynomials of appropriate order the maximum error is minimized. Recall that this is the \(\ell_{\infty}\) error. As was discussed at the beginning of this chapter, other norms are often used as well. For example, the \(\ell_{2}\) norm is very common. We will investigate how to interpolate that minimizes this norm in the next section.
