I’ve mentioned the Runge phenomenon in a couple posts before. Here I’m going to go into a little more detail.
First of all, the “Runge” here is Carl David Tolmé Runge, better known for the Runge-Kutta algorithm for numerically solving differential equations. His name rhymes with cowabunga, not with sponge.
Runge showed that polynomial interpolation at evenly-spaced points can fail spectacularly to converge. His example is the function f(x) = 1/(1 + x²) on the interval [−5, 5], or equivalently, and more convenient here, the function f(x) = 1/(1 + 25x²) on the interval [−1, 1]. Here’s an example with 16 interpolation nodes.
Runge found that in order for interpolation at evenly spaced nodes in [−1, 1] to converge, the function being interpolated needs to be analytic inside a football-shaped [1] region of the complex plane with major axis [−1, 1] on the real axis and minor axis approximately [−0.5255, 0.5255] on the imaginary axis. For more details, see [2].
The function in Runge’s example has a singularity at 0.2i, which is inside the football. Linear interpolation at evenly spaced points would converge for the function f(x) = 1/(1 + x²) since the singularity at i is outside the football.
For another example, consider the function f(x) = exp(−1/x²) , defined to be 0 at 0. This function is infinitely differentiable but it is not analytic at the origin. With only 16 interpolation points as above, there’s a small indication of trouble at the ends.
With 28 interpolation points in the plot below, the lack of convergence is clear.
The problem is not polynomial interpolation per se but polynomial interpolation at evenly-spaced nodes. Interpolation at Chebyshev points converges for the examples here. The location of singularities effects the rate of convergence but not whether the interpolants converge.
Related: Help with interpolation
***
[1] American football, that is. The region is like an ellipse but pointy at −1 and 1.
[2] Approximation Theory and Approximation Practice by Lloyd N. Trefethen