Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4632944 | Applied Mathematics and Computation | 2009 | 11 Pages |
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.