Runge's phenomenon

The red curve is the Runge function.
The blue curve is a 5th-order interpolating polynomial (using six equally-spaced interpolating points).
The green curve is a 9th-order interpolating polynomial (using ten equally-spaced interpolating points).
At the interpolating points, the error between the function and the interpolating polynomial is (by definition) zero. Between the interpolating points (especially in the region close to the endpoints 1 and −1), the error between the function and the interpolating polynomial gets worse for higher-order polynomials.

In the mathematical field of numerical analysis, Runge's phenomenon is a problem that occurs when using polynomial interpolation with polynomials of high degree. It was discovered by Carl David Tolmé Runge when exploring the behavior of errors when using polynomial interpolation to approximate certain functions (Runge 1901).

Problem

Consider the function:

Runge found that if this function is interpolated at equidistant points x_i between −1 and 1 such that:

with a polynomial P_n(x) of degree ≤ n, the resulting interpolation oscillates toward the end of the interval, i.e. close to −1 and 1. It can even be proven that the interpolation error tends toward infinity when the degree of the polynomial increases:

However, the Weierstrass approximation theorem states that there is some sequence of approximating polynomials for which the error goes to zero. This shows that high-degree polynomial interpolation at equidistant points can be troublesome.

Reason

The error between the generating function and the interpolating polynomial of order N is given by

for some ξ in [−1, 1].

For the case of the Runge function (also called the Cauchy-Lorentz function) shown above,

the first two derivatives are

The magnitude of higher order derivatives of the Runge function get even larger. Therefore, the bound for the error (between the interpolating points) when using higher order interpolating polynomials becomes larger.

Mitigations to the problem of Runge's phenomenon

The oscillation can be minimized by using nodes that are distributed more densely towards the edges of the interval, specifically, with asymptotic density (on the interval [-1,1]) given by (Berrut & Trefethen 2004). A standard example of such a set of nodes is Chebyshev nodes, for which the maximum error is guaranteed to diminish with increasing polynomial order. The phenomenon demonstrates that high degree polynomials are generally unsuitable for interpolation with equidistant nodes. The problem can be avoided by using spline curves which are piecewise polynomials. When trying to decrease the interpolation error one can increase the number of polynomial pieces which are used to construct the spline instead of increasing the degree of the polynomials used.

Another method is fitting a polynomial of lower degree using the method of least squares. Generally, when using m equidistant points, if then least squares approximation P_N(x) is well-conditioned (Dahlquist & Björk 1974).

See also

• Compare with the Gibbs phenomenon for sinusoidal basis functions
• Taylor series
• Chebyshev nodes

References

• Runge, Carl (1901), "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten", Zeitschrift für Mathematik und Physik 46: 224–243 .
• Berrut, Jean-Paul; Trefethen, Lloyd N. (2004), "Barycentric Lagrange interpolation", SIAM Review 46: 501–517, doi:10.1137/S0036144502417715, ISSN 1095-7200 .
• Dahlquist, Germund; Björk, Åke (1974), "4.3.4. Equidistant Interpolation and the Runge Phenomenon", Numerical Methods, pp. 101–103, ISBN 0-13-627315-7 .