When dealing with polynomial interpolations, it seems intuitively clear that the higher the degree of the polynomial, the more accurate the approximation.  However, Runge’s phenomenon shows that this is not the case.  In 1901, German mathematician Carl Runge discovered that sometimes using polynomial interpolation for polynomials of high degrees can cause very large errors.  For example, when trying to interpolate the function f(x)=1/(1+25x^2) using n+1 equidistant points x_1, x_2, ldots, x_{n+1}, where x_i := -1 +(i-1)2/n, it can be shown that the error of the interpolation tends to infinity as n increases.  This is counterintuitive, since as n becomes arbitrarily large, and hence the distances between the points x_1, ldots, x_{n+1} decreases, one would expect the polynomial to become an increasingly better approximation.

Though Runge’s phenomenon shows that increasing n increases the error, the result does not indicate that polynomials of lower degrees will not provide good interpolations of f, since the Weierstrass approximation theorem from mathematical analysis states that any continuous function can be uniformly approximated by a polynomial.  Formally, it states

 ”If f is a continuous real-valued function on [a, b] and if any epsilon >0 is given, then there exists a polynomial p on [a, b] such that |f(x)-P(x)|<epsilon for all xin [a,b]” (Mathworld)

In computer graphics, to avoid this problem, spline interpolation is used.  Splines are polynomials defined piecewise on various intervals.  Spline interpolation can avoid the problem of Runge’s phenomenon by increasing the number of piecewise polynomials used to interpolate the function, while using smaller degrees for the piecewise polynomials.

 The reason that this problem arises when trying to interpolate f(x)=1/(1+25x^2) is that the error of the interpolating polynomial of degree n is approximately as large as the n’th derivative of f.  Now, our choice of f is such that as the order of n increases, so does the magnitude of f^(n)(1), e.g the n’th derivative of f evaluated at 1.  Hence by using splines with multiple piecewise polynomials of smaller degrees, we can avoid this problem.

 Finally, it is interesting to note that Runge was a student of Weierstrass, which explains the relation between the two results.

References:

1.  http://mathworld.wolfram.com/WeierstrassApproximationTheorem.html

2.  http://en.wikipedia.org/wiki/Runge%27s_phenomenon