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]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≫NP≫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β≡(N+1)/P. The least-squares fit will fail to converge everywhere on [−1, 1] as N→∞N→∞ for fixed β if f(x  ) has a singularity inside a curve D(β)D(β) in the complex-plane. The width of the region enclosed by the convergence boundary DD shrinks as β diminishes (i. e., more points for a fixed polynomial degree), but shrinks to the interval [−1, 1] only when β→0β→0. We also show that the Runge Phenomenon can be completely defeated by interpolation on a “mock–Chebyshev” grid: a subset of (N+1)(N+1) points from an equispaced grid with O(N2)O(N2) points chosen to mimic the non-uniform N+1N+1-point Chebyshev–Lobatto grid.