Runge's phenomenon

Consider the function:

<math>f(x) = \frac{1}{1+25x^2}</math>

Runge found that if you interpolate this function at equidistant points between -1 and 1 such that:

<math>x_i = -1 + (i-1)\frac{2}{n}, i \in \left\{ 1, 2, \cdots n+1 \right\}</math>

with a polynomial <math>P_n(x)</math> which has a degree <math>\leq n</math>, the resulting interpolation would oscillate toward the end of the interval, i.e. close to -1 and 1. It can even be proved that the interpolation error tends toward infinity when the degree of the polynomial increases:

<math>\lim_{n \rightarrow \infty} \left( \max_{-1 \leq x \leq 1} | f(x) -P_n(x)| \right) = \infty</math>

Runge's phenomenon demonstrates that lower-order polynomials are generally to be preferred instead of raising the degree of the interpolation polynomial, even though some of the badness of this interpolation may be overcome by using Chebyshev polynomials instead of equidistant points. Runge's function is nicely interpolated using splines[?] however, and cubic splines are the most common interpolation method in this family.