Chebyshev Zeros/Nodes
Due to the analogy of Chebyshev polynomials to cosines, the pattern of their zeros is particularly simple. From the last tutorial, we know that as \( x = \cos\theta \), \( T_n(x) = \cos (n\theta) \), hence for a Chebyshev polynomial of order \(n\), it has \(n\) zeros that are located at \(\{x_i, i = 1, 2, \ldots, n\} \), corresponding to \( \theta = \pi/2n, 3\pi/2n, \ldots, (2n-1)\pi/2n \). Mathematically, it means that
\begin{align}
x_i = \cos^{-1}(\frac{(2i-1)\pi}{2n}) \tag{1}
\end{align}
Geometrically, they are the projection of the midpoints along evenly divided equal-length arcs from a unit semicircle onto the interval \( [-1,1] \).
Minimax Property
The Chebyshev polynomials come with a useful property called the minimax property, which implies that out of all possible polynomials of degree \(n\) with a fixed leading coefficient (which may be taken as \(1\)), the Chebyshev polynomial \( 2^{1-n}T_n(x) \) (the \(2^{1-n}\) factor is to make the leading coefficient \(1\) for standardization) deviates the least from zero over the interval \( [-1,1] \). It can be stated more explicitly as
\begin{align}
\max_{-1 \leq x \leq 1} |P(x)| \geq \max_{-1 \leq x \leq 1} |2^{1-n}T_n(x)| = 2^{1-n} \tag{2}
\end{align}
where \( P(x) \) is any polynomial of degree \(n > 1\). The following proof is from the textbook Differential Equations with Applications and Historical Notes by Simmons. The equality part is obvious by noting that \( |\cos(n\theta)| \leq 1 \). For the inequality part, the argument is by assuming, on the contrary, that there is some polynomial that violates (2):
\begin{align}
\max_{-1 \leq x \leq 1} |P(x)| < 2^{1-n} \tag{3}
\end{align}
then the Chebyshev polynomial \( 2^{1-n}T_n(x) = 2^{1-n} \cos(n\theta) \) has the alternating values of \( 2^{1-n}, -2^{1-n}, 2^{1-n}, -2^{1-n}, \ldots \) at the \(n+1\) points \(x_j\) that correspond to \(\theta = 0, \pi/n, 2\pi/n, …, \pi\). If (3) holds, then \( Q(x) = 2^{1-n}T_n(x) -P(x) \) will have the same sign as \( 2^{1-n}T_n(x) \) at these points. (e.g., if at \( x_j \), \( 2^{1-n}T_n(x_j) = 2^{1-n} \) is positive, then \( Q(x_j) = 2^{1-n} -P(x_j) > 2^{1-n} -2^{1-n} > 0 \) is also positive) By the intermediate value theorem, we know that there must be \( n \) zeros, each of them in-between consecutive \( x_j \), on the interval \( [-1,1] \). But this is impossible since \( Q(x) \) is a polynomial of degree at most \(n-1\) (the leading \(x^n\) term cancels out) unless \(Q(x)\) is identically zero (so that \(P(x)\) has to coincide with the Chebyshev polynomial), and a contradiction occurs.
Polynomial Interpolation Error Bound
The property (2) is a key ingredient in deriving the minimum error bound of a polynomial interpolation. For a function \(f(x)\), a polynomial interpolation of degree \(n\), by definition, is a polynomial \( P(x) \) such that it coincides with the original function at \(n+1\) selected points, i.e. \( P(x_i) = f(x_i), i = 1,2,\ldots,n+1 \). We want to choose these \(\{x_i\}\) in a way such that the deviation of \( P(x) \) from \(f(x)\) is minimized throughout the interval (for convenience, let’s say \( [-1,1] \)). Now, we shall show that the error bound is given by
\begin{align}
f(x) -P(x) = \frac{1}{(n+1)!}f^{(n+1)}(\xi_x) \prod_{i=1}^{n+1} (x-x_i) \tag{4}
\end{align}
where \( \xi_x \) is some point also within the interval depending on \(x\), and this assumes that \(f(x)\) is continuously \(n+1\) times differentiable. The derivation is taken from this material. Let
\begin{align}
w(t) &= \prod_{i=1}^{n+1} (x-x_i) \tag{5} \\
\phi_x(t) &= f(t) -P(t) -\frac{f(x)-P(x)}{w(x)}w(t) \tag{6}
\end{align}
Then (6) is also continuously \(n+1\) times differentiable, and \(\phi_x(t)\) vanishes at \(n+2\) distinct points: \(t = x_1, x_2, \ldots, x_{n+1} \), as well as \(x\). By Rolle’s Theorem, between two consecutive zeros of a function, its derivative must have a zero, so \( \phi_x'(t) \) then has at least \(n+1\) distinct zeros, and repeatedly using the theorem, we can conclude that \( \phi_x^{(n+1)}(t) \) has at least one zero over the interval, denoted as \( \xi_x \). Now
\begin{align}
\phi_x^{(n+1)}(t) &= \frac{d^{n+1}}{dt^{n+1}}(f(t) -P(t) -\frac{f(x)-P(x)}{w(x)}w(t)) \\
&= f^{(n+1)}(t) -P^{(n+1)}(t) -\frac{f(x)-P(x)}{w(x)}\frac{d^{n+1}}{dt^{n+1}}w(t) \\
&= f^{(n+1)}(t) -P^{(n+1)}(t) \\
&\quad -\frac{f(x)-P(x)}{w(x)}\frac{d^{n+1}}{dt^{n+1}}(t-x_1)(t-x_2)\cdots(t-x_{n+1}) \\
&= f^{(n+1)}(t) -P^{(n+1)}(t) -\frac{f(x)-P(x)}{w(x)}(n+1)! \tag{7}
\end{align}
So
\begin{align}
\phi_x^{(n+1)}(\xi_x) &= f^{(n+1)}(\xi_x) -P^{(n+1)}(\xi_x) -\frac{f(x)-P(x)}{w(x)}(n+1)! = 0 \\
f^{(n+1)}(\xi_x) -(0) &= \frac{f(x)-P(x)}{w(x)}(n+1)! \\
f(x)-P(x) &= \frac{1}{(n+1)!}f^{(n+1)}(\xi_x) w(x) \tag{8}
\end{align}
which is exactly (4). \( P^{(n+1)} = 0 \) because \( P(x) \) is a polynomial of degree just \(n\).
With (2) and (4), we can immediately establish the error bound of a polynomial interpolation by choosing \( \{x_i\} \) as the \(n+1\) zeros of the Chebyshev polynomial of order \(n+1\):
\begin{align}
\max_{-1 \leq x \leq 1} |f(x) -P(x)| &\leq \max_{-1 \leq x \leq 1} |\frac{1}{(n+1)!}f^{(n+1)}(\xi_x)| \max_{-1 \leq x \leq 1} |\prod_{i=1}^{n+1} (x-x_i)| \\
&= \frac{1}{(n+1)!} \max_{-1 \leq t \leq 1} |f^{(n+1)}(t)| (2^{1-(n+1)}) \\
&= \frac{1}{2^n(n+1)!} \max_{-1 \leq t \leq 1} |f^{(n+1)}(t)| \tag{9}
\end{align}
Exercise
Find the minimum error bound of a \(9\)-points polynomial interpolation for \( \sin(\pi x) \) over the interval \([-1,1]\).
Answer
By (9), the optimal error would be given by
\begin{align}
&\quad \frac{1}{2^9(9+1)!} \max |\frac{d^{10}}{dt^{10}} \sin(\pi t)| \\
&= \frac{1}{2^9(10!)}(\pi^{10})(1) \approx 5\times10^{-5}
\end{align}
Leave a Reply