Mathematical foundations of Runge Phenomenon & Chebyshev Nodes.
In 1901, German mathematician Carl Runge discovered a startling limitation of polynomial interpolation: increasing the degree of an interpolating polynomial on equally spaced nodes does not necessarily improve accuracy, and can lead to explosive divergence near the domain boundaries. This breakdown occurs whenever a function's complex analytic extension possesses singularities near the real interval. Pafnuty Chebyshev provided the definitive resolution by proving that projecting equidistant points from a semicircle onto the diameter minimizes the maximum amplitude of the monic nodal polynomial. In this computational laboratory, we demonstrate the stark contrast between uniform and Chebyshev interpolation on Runge's function, verify the arcsine nodal density, and track the error attenuation factor ρ = 0.500.
Viva voce questions & analytical theory
What is Runge's phenomenon and why does it occur?
Runge's phenomenon is the catastrophic divergence of high-degree polynomial interpolants on uniform grids near the boundaries of [-1, 1]. It occurs because the analytic continuation of f(z) has poles at ±0.2i, and the Bernstein ellipse passing through these poles has semi-minor axis b = 0.2, inside of which uniform node polynomials cannot converge uniformly.
How do Chebyshev nodes minimize the maximum value of the nodal product polynomial?
The Chebyshev polynomial T_n(x) = cos(n arccos(x)) is the unique monic polynomial of degree n that minimizes the uniform norm on [-1, 1], achieving ||∏(x - x_k)||_∞ = 1 / 2^{n-1}. Any other choice of nodes produces a larger maximum product.
What is the density distribution of Chebyshev nodes as n → ∞?
The nodal density follows the arcsine distribution ρ(x) = 1 / (π √(1 - x²)), meaning nodes cluster densely near the boundaries x = ±1 where interpolation error is most prone to wild oscillations.
How does the Lebesgue constant grow for Chebyshev nodes compared to uniform nodes?
For Chebyshev nodes, the Lebesgue constant grows only logarithmically: Λ_n = (2/π) ln(n) + O(1). In contrast, for uniform nodes it grows exponentially: Λ_n ~ 2^n / (e n ln(n)).
Can Runge's phenomenon occur for smooth analytic functions like e^x or sin(x)?
No; for entire functions (functions with no singularities anywhere in the complex plane), the radius of the Bernstein ellipse is infinite, so uniform node polynomial interpolation converges to zero error everywhere, though Chebyshev nodes still converge much faster.
Why is the second barycentric formula especially convenient for Chebyshev nodes?
For Chebyshev nodes of the first kind, the barycentric weights have a simple explicit closed form: w_k = (-1)^k sin((2k - 1)π / (2n)), eliminating the need to compute product denominators numerically.
What is the practical upper limit of polynomial degree when using Chebyshev interpolation?
Because the Lebesgue constant grows only logarithmically, Chebyshev interpolation is numerically stable even for degree n = 1000 or higher in double precision, forming the foundation of modern spectral methods and software packages like Chebfun.
Algorithm precautions and stability rules
- Always map Chebyshev nodes from the canonical interval [-1, 1] to the physical domain [a, b] using the affine transformation x = (a+b)/2 + (b-a)/2 · cos(θ).
- Do not use naive monomial expansion for high-degree Chebyshev polynomials; always evaluate via the Clenshaw recurrence or barycentric formula.
- Verify that the sampling grid used to measure maximum error is sufficiently dense near endpoints (at least 2000 points) to capture peak oscillations.
- Avoid evaluating trigonometric functions repeatedly in inner loops by precomputing the cosine grid values.
- Be aware that rounding errors can cause cos(0) or cos(π) to slightly exceed the domain [-1, 1] if not strictly clamped.
- Ensure floating point precision remains 64-bit IEEE 754 to prevent underflow of the 2^{1-n} minimax product bound.
Theoretical limitations
- Chebyshev nodes require predefined sampling locations; if experimental measurements are already fixed at uniform intervals, Chebyshev interpolation cannot be directly applied without resampling.
- For non-analytic functions with low derivative smoothness, Chebyshev interpolation convergence drops from exponential to algebraic O(n^{-k}).
- Boundary node clustering can induce mild condition number growth in certain spectral differentiation matrices.