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 + 25*x*²) 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.2*i*, 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

## One thought on “Runge phenomena”