Rungefenomen

Runge phenomenon is a problem in polynomial interpolation where, on a finite interval, high-degree interpolants built from equally spaced nodes exhibit large oscillations near the interval endpoints. As the degree increases, the interpolation error can increase rather than decrease, and the interpolant may fail to converge to the target function.

A classic illustration uses Runge's function f(x) = 1/(1+25x^2) on the interval [-1,1]. When this function is interpolated with polynomials at equidistant nodes, the resulting polynomial oscillations near the endpoints grow with the degree, and the maximum error does not tend to zero. This demonstrates that global high-degree polynomials with uniform node spacing can perform poorly for fairly smooth functions.

Causes and theory: The phenomenon is tied to the behavior of the Lebesgue constant for equispaced nodes, which grows rapidly with the polynomial degree. The combination of a smooth function and a globally defined polynomial basis leads to amplified errors at the ends. The issue is less pronounced for certain highly structured node sets and can be avoided by altering the interpolation strategy.

Remedies: Using nonuniform node distributions, notably Chebyshev or Chebyshev–Lobatto nodes, dramatically reduces endpoint oscillations and yields stable convergence. Alternatively, piecewise polynomial interpolation (splines) or other approximation schemes such as minimax polynomials or spectral methods mitigate the problem by avoiding global high-degree polynomials on the entire interval.

Historical note: The phenomenon is named after Carl Runge, who described the divergence behavior in 1901 while studying polynomial interpolation on [-1,1].