Runge's phenomenon

In the mathematical field of numerical analysis, Runge's phenomenon (German: [ˈʁʊŋə]) is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation points.

It was discovered by Carl David Tolmé Runge (1901) when exploring the behavior of errors when using polynomial interpolation to approximate certain functions.

[1] The discovery shows that going to higher degrees does not always improve accuracy.

The Weierstrass approximation theorem states that for every continuous function f(x) defined on an interval [a,b], there exists a set of polynomial functions Pn(x) for n=0, 1, 2, ..., each of degree at most n, that approximates f(x) with uniform convergence over [a,b] as n tends to infinity, that is, Consider the case where one desires to interpolate through n+1 equispaced points of a function f(x) using the n-degree polynomial Pn(x) that passes through those points.

Naturally, one might expect from Weierstrass' theorem that using more points would lead to a more accurate reconstruction of f(x).

However, this particular set of polynomial functions Pn(x) is not guaranteed to have the property of uniform convergence; the theorem only states that a set of polynomial functions exists, without providing a general method of finding one.

The Pn(x) produced in this manner may in fact diverge away from f(x) as n increases; this typically occurs in an oscillating pattern that magnifies near the ends of the interpolation points.

[2] Consider the Runge function (a scaled version of the Witch of Agnesi).

Runge found that if this function is interpolated at equidistant points xi between −1 and 1 such that: with a polynomial Pn(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 increases (without bound) when the degree of the polynomial is increased: This shows that high-degree polynomial interpolation at equidistant points can be troublesome.

Runge's phenomenon is the consequence of two properties of this problem.

The phenomenon is graphically obvious because both properties combine to increase the magnitude of the oscillations.

The error between the generating function and the interpolating polynomial of order n is given by for some

function: It is elementary to prove that with equidistant nodes where

Although often used to explain the Runge phenomenon, the fact that the upper bound of the error goes to infinity does not necessarily imply, of course, that the error itself also diverges with n. 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 the formula[3]

A standard example of such a set of nodes is Chebyshev nodes, for which the maximum error in approximating the Runge function is guaranteed to diminish with increasing polynomial order.

When equidistant samples must be used because resampling on well-behaved sets of nodes is not feasible, the S-Runge algorithm can be considered.

[4] In this approach, the original set of nodes is mapped on the set of Chebyshev nodes, providing a stable polynomial reconstruction.

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.

One can also fit a polynomial of higher degree (for instance, with

), and fit an interpolating polynomial whose first (or second) derivative has minimal

, with respect to the polynomial coefficients and the Lagrange multipliers,

, the constraint equations generated by the Lagrange multipliers reduce

will approach a form very similar to a piecewise polynomials approximation.

approaches the linear piecewise polynomials, i.e. connecting the interpolation points with straight lines.

[5] Using Bernstein polynomials, one can uniformly approximate every continuous function in a closed interval, although this method is rather computationally expensive.

[citation needed] This method proposes to optimally stack a dense distribution of constraints of the type P″(x) = 0 on nodes positioned externally near the endpoints of each side of the interpolation interval, where P"(x) is the second derivative of the interpolation polynomial.

The method has demonstrated that it has a better interpolation performance than Piecewise polynomials (splines) to mitigate the Runge phenomenon.

[7] For every continuous function there is a table of nodes on which the interpolation process converges.