Divergence (Runge Phenomenon) for least-squares polynomial approximation on an equispaced grid and Mock–Chebyshev subset interpolation

摘要

Runge showed more than a century ago that polynomial interpolation of a function f(x), using points evenly spaced on x∈[-1,1], could diverge on parts of this interval even if f(x) was analytic everywhere on the interval. Least-squares fitting of a polynomial of degree N to an evenly spaced grid with P points should improve accuracy if P≫N. We show through numerical experiments that such an overdetermined fit reduces but does not eliminate the Runge Phenomenon. More precisely, define β≡(N+1)/P. The least-squares fit will fail to converge everywhere on [−1, 1] as N→∞ for fixed β if f(x) has a singularity inside a curve D(β) in the complex-plane. The width of the region enclosed by the convergence boundary D shrinks as β diminishes (i. e., more points for a fixed polynomial degree), but shrinks to the interval [−1, 1] only when β→0. We also show that the Runge Phenomenon can be completely defeated by interpolation on a “mock–Chebyshev” grid: a subset of (N+1) points from an equispaced grid with O(N2) points chosen to mimic the non-uniform N+1-point Chebyshev–Lobatto grid.