16 Chebyshev Polynomials

Chebyshev polynomials are the polynomial analogue of Fourier modes on \([-1,1]\). They oscillate evenly, stay bounded, and give node sets that control interpolation error. The central idea is minimax: among polynomials of a fixed degree, Chebyshev polynomials spread error as evenly as possible instead of allowing large boundary spikes.

16.1 Failure of the Monomial Basis

Polynomial approximation has two separate failure modes. The first is numerical: the monomial basis \(1,x,x^2,...\) leads to ill-conditioned Vandermonde matrices. The second is analytical: even exact interpolation at equally spaced nodes can oscillate badly near the interval endpoints.

Definition: Interpolation Error Polynomial

Given distinct interpolation nodes \(x_1,...,x_n\), define \[ \begin{align} \omega_n(x)=\prod_{j=1}^n (x-x_j). \end{align} \] This polynomial is zero at every node. Its size between the nodes controls how much interpolation can amplify the derivative of the target function.

Theorem: Interpolation Error Formula

Let \(p_{n-1}\) interpolate a function \(f\) at \(n\) distinct nodes \(x_1,...,x_n\). If \(f\) has \(n\) continuous derivatives on \([-1,1]\), then for each \(x\in[-1,1]\) there exists a point \(\xi_x\in[-1,1]\) such that \[ \begin{align} f(x)-p_{n-1}(x) = \frac{f^{(n)}(\xi_x)}{n!}\omega_n(x). \end{align} \] Therefore, \[ \begin{align} \|f-p_{n-1}\|_\infty \leq \frac{\|f^{(n)}\|_\infty}{n!}\|\omega_n\|_\infty. \end{align} \]

Exercise

For three nodes \(x_1,x_2,x_3\), write out \(\omega_3(x)\) and verify that it vanishes at each node.
Use the result above to explain why node choice matters even when \(f^{(n)}\) is fixed.
Build the degree-\(14\) Vandermonde matrix on \(15\) equally spaced nodes in \([-1,1]\). Compute \(\kappa_2(\bV)\).
Plot Runge’s function \(f(x)=1/(1+25x^2)\) and its degree-\(10\) interpolant at equally spaced nodes. Compare the largest error in the middle of the interval with the largest error near the endpoints.

16.2 Chebyshev Polynomials (\(T_k\))

Definition: Chebyshev Polynomial

For \(x\in[-1,1]\), the degree-\(k\) Chebyshev polynomial is \[ \begin{align} T_k(x)=\cos(k\arccos x). \end{align} \] Equivalently, if \(x=\cos\theta\), then \[ \begin{align} T_k(\cos\theta)=\cos(k\theta). \end{align} \]

Theorem: Basic Chebyshev Identities

The polynomials from the result above satisfy \[ \begin{align} T_0(x)=1,\qquad T_1(x)=x,\qquad T_{k+1}(x)=2xT_k(x)-T_{k-1}(x). \end{align} \] They are bounded by \(1\) on \([-1,1]\): \[ \begin{align} |T_k(x)|\leq 1. \end{align} \] They are orthogonal with respect to the weight \((1-x^2)^{-1/2}\): \[ \begin{align} \int_{-1}^1 T_j(x)T_k(x)\frac{dx}{\sqrt{1-x^2}} =0, \qquad j\neq k. \end{align} \]

Exercise

Use \(\cos((k+1)\theta)+\cos((k-1)\theta)=2\cos\theta\cos(k\theta)\) to prove the three-term recurrence in the result above.
Compute \(T_2\), \(T_3\), and \(T_4\) from the recurrence.
Prove \(|T_k(x)|\leq 1\) on \([-1,1]\) directly from the result above.
Substitute \(x=\cos\theta\) into the weighted integral and reduce the orthogonality statement to Fourier cosine orthogonality on \([0,\pi]\).
Plot \(T_0,...,T_5\). Mark the points where each polynomial reaches \(\pm 1\).

16.3 Zeros and Nodes

Theorem: Zeros and Extrema

The zeros of \(T_n\) are \[ \begin{align} x_j=\cos\left(\frac{(2j-1)\pi}{2n}\right), \qquad j=1,...,n. \end{align} \] The extrema of \(T_n\) occur at \[ \begin{align} y_j=\cos\left(\frac{j\pi}{n}\right), \qquad j=0,...,n, \end{align} \] and satisfy \(T_n(y_j)=(-1)^j\).

Definition: Chebyshev Nodes

The Chebyshev interpolation nodes are the zeros of \(T_n\): \[ \begin{align} x_j=\cos\left(\frac{(2j-1)\pi}{2n}\right), \qquad j=1,...,n. \end{align} \] These nodes cluster near \(\pm 1\). The clustering is not cosmetic; it reduces the size of the interpolation error polynomial from the result above.

Theorem: Chebyshev Error Polynomial

If \(x_1,...,x_n\) are the Chebyshev nodes from the result above, then \[ \begin{align} \omega_n(x)=\prod_{j=1}^n (x-x_j) = 2^{1-n}T_n(x). \end{align} \] Consequently, \[ \begin{align} \|\omega_n\|_\infty=2^{1-n}. \end{align} \]

Exercise

Starting from \(T_n(\cos\theta)=\cos(n\theta)\), solve \(\cos(n\theta)=0\) and prove the zero formula in the result above.
Solve \(\cos(n\theta)=\pm 1\) and prove the extrema formula in the result above.
Explain why the Chebyshev nodes cluster near \(\pm 1\) by comparing the spacing of equally spaced \(\theta\) values under \(x=\cos\theta\).
Show that \(T_n\) has leading coefficient \(2^{n-1}\) for \(n\geq 1\).
Use the previous step and the fact that \(T_n\) has zeros \(x_1,...,x_n\) to prove the result above.

16.4 The Minimax Property

Theorem: Chebyshev Minimax Polynomial

Among all monic polynomials \(q\) of degree \(n\) on \([-1,1]\), \[ \begin{align} 2^{1-n}T_n(x) \end{align} \] has the smallest possible infinity norm: \[ \begin{align} \|2^{1-n}T_n\|_\infty = 2^{1-n} \leq \|q\|_\infty. \end{align} \]

Exercise

Let \(m(x)=2^{1-n}T_n(x)\). Use the result above to show that \(m\) is monic and \(\|m\|_\infty=2^{1-n}\).
Suppose another monic polynomial \(q\) satisfies \(\|q\|_\infty<2^{1-n}\). Define \(r=q-m\). What is the degree of \(r\)?
Evaluate the signs of \(m\) at the \(n+1\) extrema from the result above.
Use the assumption \(\|q\|_\infty<2^{1-n}\) to show that \(r\) changes sign between each pair of adjacent extrema.
Conclude that \(r\) has at least \(n\) roots, contradicting its degree. This proves the result above.
Combine the result above and the result above to explain why Chebyshev nodes are the natural interpolation nodes.

16.5 Chebyshev Series

Definition: Chebyshev Series

A Chebyshev expansion writes a function on \([-1,1]\) as \[ \begin{align} f(x)\sim \sum_{k=0}^{\infty} c_kT_k(x). \end{align} \] Using \(x=\cos\theta\), this is exactly a cosine series for the even function \(f(\cos\theta)\).

Theorem: Coefficient Formula

For \(k\geq 1\), \[ \begin{align} c_k=\frac{2}{\pi}\int_0^\pi f(\cos\theta)\cos(k\theta)\,d\theta, \end{align} \] and \[ \begin{align} c_0=\frac{1}{\pi}\int_0^\pi f(\cos\theta)\,d\theta. \end{align} \]

Theorem: Spectral Accuracy

If \(f\) is analytic on and near \([-1,1]\), then its Chebyshev coefficients decay geometrically: \[ \begin{align} |c_k|\leq C\rho^{-k} \qquad \text{for some } \rho>1. \end{align} \] The truncated series \[ \begin{align} p_n(x)=\sum_{k=0}^n c_kT_k(x) \end{align} \] therefore satisfies \[ \begin{align} \|f-p_n\|_\infty=O(\rho^{-n}). \end{align} \] This is called spectral accuracy.

Remark

(Fourier connection) Chebyshev methods are Fourier cosine methods after the change of variables \(x=\cos\theta\). This is why fast cosine transforms can compute Chebyshev coefficients efficiently.

Remark

(Interpolation vs. expansion) Chebyshev interpolation chooses values at Chebyshev nodes. Chebyshev series choose coefficients in the Chebyshev basis. Both work well for the same reason: the basis oscillates evenly and avoids the endpoint instability of monomials.

Exercise

Use the result above to rewrite a Chebyshev expansion as a cosine series in \(\theta\).
Derive the coefficient formula in the result above from Fourier cosine orthogonality.
Compute degree-\(n\) Chebyshev fits to \(e^x\) using np.polynomial.chebyshev.chebfit. Plot \(\|f-p_n\|_\infty\) versus \(n\) on a semilog scale.
Repeat the previous experiment for \(f(x)=|x|\). Compare the coefficient decay with the analytic case in the result above.
Use chebder to differentiate a Chebyshev approximation to \(f(x)=\sin(\pi x)\). Compare the derivative error with a finite-difference approximation using the same number of sample points.