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 Runge when exploring the behavior of errors when using polynomial interpolation to approximate certain functions. The discovery shows that going to higher degrees does not always improve accuracy. The phenomenon is similar to the Gibbs phenomenon in Fourier series approximations. The Weierstrass approximation theorem states that for every continuous function f ( x ) {\displaystyle f(x)} defined on an interval [ a , b ] {\displaystyle [a,b]} , there exists a set of polynomial functions P n ( x ) {\displaystyle P_{n}(x)} for n = 0 , 1 , 2 , … {\displaystyle n=0,1,2,\ldots } , each of degree at most n {\displaystyle n} , that approximates f ( x ) {\displaystyle f(x)} with uniform convergence over [ a , b ] {\displaystyle [a,b]} as n {\displaystyle n} tends to infinity. This can be expressed as
lim n → ∞ ( sup a ≤ x ≤ b | f ( x ) − P n ( x ) | ) = 0. {\displaystyle \lim _{n\rightarrow \infty }{\Big (}\sup _{a\leq x\leq b}\left|f(x)-P_{n}(x)\right|{\Big )}=0.}
Consider the case where one desires to interpolate through n + 1 {\displaystyle n+1} equispaced points of a function f ( x ) {\displaystyle f(x)} using the n {\displaystyle n} -degree polynomial P n ( x ) {\displaystyle P_{n}(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 ) {\displaystyle f(x)} . However, this particular set of polynomial functions P n ( x ) {\displaystyle P_{n}(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 P n ( x ) {\displaystyle P_{n}(x)} produced in this manner may in fact diverge away from f ( x ) {\displaystyle f(x)} as n {\displaystyle n} increases; this typically occurs in an oscillating pattern that magnifies near the ends of the interpolation points. The discovery of this phenomenon is attributed to Runge.
Problem Consider the Runge function
f ( x ) = 1 1 + 25 x 2 {\displaystyle f(x)={\frac {1}{1+25x^{2}}}\,}
(a scaled version of the Witch of Agnesi). Runge found that if this function is interpolated at equidistant points x 0 , … , x n {\displaystyle x_{0},\dots ,x_{n}} between − 1 {\displaystyle -1} and 1 {\displaystyle 1} such that
x i = 2 i n − 1 {\displaystyle x_{i}={\frac {2i}{n}}-1}
with a polynomial P n ( x ) {\displaystyle P_{n}(x)} of degree less than or equal to n {\displaystyle n} , the resulting interpolation oscillates toward the end of the interval, i.e. close to − 1 {\displaystyle -1} and 1 {\displaystyle 1} . It can even be proven that the interpolation error increases (without bound) when the degree of the polynomial is increased:
… excerpt ends here. Continue reading the full article.
