An SVD analysis of equispaced polynomial interpolation

Runge showed more than a century ago that polynomial interpolation of degree N on a uniform, evenly-spaced grid may diverge as N→∞. Here, we present a new angle on polynomial interpolation and the Runge Phenomenon by performing an SVD analysis of the interpolation matrix. We prove that the observed exponential-with-N error growth of the Runge Phenomenon requires that at least the smallest singular value of the interpolation matrix must decay to zero exponentially fast with N, and the matrix condition number κ must grow exponentially with N. Experimentally, four-fifths of the singular values are O(1); the remaining one-fifth of singular values decay exponentially fast with increasing mode number j. The corresponding U modes of the SVD factorization are well approximated by Hermite functions. SVD filtering, which is a common strategy for coping with ill-conditioned matrices by omitting modes of tiny singular value, gave errors no smaller than 7% for Runge's exemplary f(x). Any similar anti-Runge strategy that is based on treating the “good” modes (of O(1) singular values) differently from the “bad” modes of small singular value is likely to fail because these two groups of modes are strongly coupled. A better strategy for exploiting the SVD factorization remains elusive.