RUNGE'S PHENOMENON

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 behaviour of errors when using polynomial interpolation to approximate certain functions.

Contents

Problem

Reason

Mitigations to the problem of Runge's phenomenon

See also

Problem

Consider the function:
:
Runge found that if this function is interpolated at equidistant points ''x''_''i'' between −1 and 1 such that:
:
ight}
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:
:$lim\_\{n$
ightarrow infty} left( max_{-1 leq x leq 1} | f(x) -P_n(x)|
ight) = infty.
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 dangerous.

Reason

The error between the generating function and the interpolating polynomial of order ''N'' is bounded by the ''N''th derivative of the generating function.
For the case of the Runge function shown above,
:
the first two derivatives are
:$$
egin{array}{lcl}
displaystyle f'(x) = -rac{50x}{left(1+25x^2
ight)^2} &
ightarrow&
displaystyleleft|f'(1)
ight|=rac{50}{26^2}=0.0740 \[1.5em]
displaystyle f''(x) = rac{5000(1+25x^2)-50(1+25x^2)^2}{left(1+25x^2
ight)^4} &
ightarrow
&displaystyleleft|f''(1)
ight|=rac{96200}{26^4}=0.2105.
end{array}

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 Chebyshev nodes instead of equidistant nodes. In this case the maximum error is guaranteed to diminish with increasing polynomial order. The phenomenon demonstrates that high degree polynomials are generally unsuitable for interpolation. 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.

See also

★ Compare with the Gibbs phenomenon for sinusoidal basis functions