Minimax-optimal basis for polynomial approximation. Resolves ill-conditioning and oscillations of the monomial basis.
Failure of the Monomial Basis
Numerical: Vandermonde matrices \(V_{ij} = x_i^{j-1}\) have condition numbers that grow exponentially with degree.
Analytical: Runge’s Phenomenon. Interpolating smooth functions at equally spaced nodes leads to divergence at boundaries as degree \(n \to \infty\).
…
Build \(n=15\) Vandermonde matrix on equispaced nodes. Check \(\kappa_2(\bV)\).
Plot Runge’s function \(f(x) = 1/(1+25x^2)\) and its \(n=10\) interpolant. Note boundary oscillations.
Chebyshev Polynomials (\(T_k\))
Defined on \([-1, 1]\) by \(T_k(x) = \cos(k \arccos x)\).
Recurrence: \(T_0=1, T_1=x, T_{k+1}=2x T_k - T_{k-1}\).
Boundedness: \(|T_k(x)| \leq 1\) for all \(x \in [-1, 1]\).
Orthogonality: \(\int_{-1}^1 T_j T_k \frac{dx}{\sqrt{1-x^2}} = 0\) for \(j \neq k\).
Compute \(T_3, T_4\) via recurrence.
Plot \(T_0, ..., T_5\). Note they all oscillate between \(\pm 1\).
Chebyshev Nodes
Zeros of \(T_n(x)\) provide the optimal node distribution for interpolation.
\(x_k = \cos(\frac{(2k-1)\pi}{2n})\) for \(k=1, ..., n\).
- Node Clustering: Nodes cluster near boundaries \(\pm 1\). This suppresses Runge’s oscillations.
The Minimax Property: Among all monic polynomials of degree \(n\), \(\tilde{T}_n = T_n/2^{n-1}\) has the smallest possible maximum value on \([-1, 1]\). Using these nodes minimizes the interpolation error bound.
Plot 10 Chebyshev nodes vs. 10 equispaced nodes. Note clustering.
Repeat the Runge function experiment with Chebyshev nodes. Observe convergence.
Compare \(\kappa_2\) of Vandermonde vs. Chebyshev basis (\(V_{ij} = T_{j-1}(x_i)\)).
Chebyshev Series
Truncated expansions \(f(x) \approx \sum c_k T_k(x)\).
If \(f\) is analytic on \([-1, 1]\), the Chebyshev coefficients \(c_k\) decay exponentially. Truncation error \(\|f - p_n\|_\infty = O(\rho^{-n})\). Insight: Just 20–30 terms often yield machine precision.
Connection to Fourier Series: The Chebyshev polynomials are closely related to the Fourier series. Specifically, \(T_n(x)\) corresponds to the real part of a Fourier series on the unit circle under the mapping \(x = \cos \theta\). This connection explains their remarkable convergence properties for smooth functions.
Compute degree-\(n\) fit to \(e^x\) via np.polynomial.chebyshev.chebfit. Plot error vs. \(n\).
Spectral Differentiation: The derivative of a Chebyshev series satisfies a simple recurrence. Compare chebder accuracy to finite differences for \(f(x) = \sin(\pi x)\).