NationMaster - Encyclopedia: Runge's phenomenon

The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. The approximation only gets worse.

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. Image File history File links Download high-resolution version (700x664, 46 KB)Illustration of Runges phenomenon at higher resolution Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1. ... Image File history File links Download high-resolution version (700x664, 46 KB)Illustration of Runges phenomenon at higher resolution Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1. ... Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ... Carle David TolmÃ© Runge (August 30, 1856 â€“ January 3, 1927) was a German mathematician, physicist, and spectroscopist. ...

Problem

Consider the function: Partial plot of a function f. ...

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

Runge found that if this function is interpolated at equidistant points x_i between −1 and 1 such that: In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...

$x_i = -1 + (i-1)frac{2}{n},qquad i in left{ 1, 2, dots, n+1 right}$

with a polynomial $P n (x)$ which has a degree $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: In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...

$lim_{n rightarrow infty} left( max_{-1 leq x leq 1} | f(x) -P_n(x)| right) = 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. In mathematical analysis, the Weierstrass approximation theorem states that every continuous function defined on an interval [a,b] can be uniformly approximated as closely as desired by a polynomial function. ...

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. In the mathematical subfield of numerical analysis Chebyshev nodes are the roots of the Chebyshev polynomial of the first kind. ... In the mathematical subfield of numerical analysis a spline is a special curve defined piecewise by polynomials. ...

Problem GA_googleFillSlot("encyclopedia_square");

Solutions to the problem of Runge's phenomenon

See also

Problem