In the mathematical field of numerical analysis Runge's phenomenon is a problem which occurs when using polynomial interpolation with polynomials of high degree. It was discovered by Carle David Tolmé Runge when exploring the behaviour of errors when using polynomial interpolation to approximate certain functions.

Problem

Consider the function:

$f(x)\; =\; \backslash frac\{1\}\{1+25x^2\}.\backslash ,$

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

$x\_i\; =\; -1\; +\; (i-1)\backslash frac\{2\}\{n\},\backslash qquad\; i\; \backslash in\; \backslash left\backslash \{\; 1,\; 2,\; \backslash dots,\; n+1\; \backslash right\backslash \}$

with a polynomial $P\_n(x)$ which has a degree $\backslash leq\; 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:

$\backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; \backslash left(\; \backslash max\_\{-1\; \backslash leq\; x\; \backslash leq\; 1\}\; |\; f(x)\; -P\_n(x)|\; \backslash right)\; =\; \backslash infty.$

Solutions 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

Interpolation

Runges Phänomen | Phénomène de Runge | Fenomeno di Runge | Fenómeno de Runge | Runges fenomen