Editing Runge's phenomenon (section)

==Problem==
Consider the '''Runge function'''
:<math>f(x) = \frac{1}{1+25x^2}\,</math>
(a scaled version of the [[Witch of Agnesi]]).
Runge found that if this function is [[interpolation|interpolated]] at equidistant points ''x''<sub>''i''</sub> between &minus;1 and 1 such that:

:<math>x_i = \frac{2i}{n} - 1,\quad i \in \left\{ 0, 1, \dots, n \right\}</math>

with a [[polynomial]] ''P''<sub>''n''</sub>(''x'') of degree &le;&nbsp;''n'', the resulting interpolation oscillates toward the end of the interval, i.e. close to &minus;1 and 1. It can even be proven that the interpolation error increases (without bound) when the degree of the polynomial is increased:

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

This shows that high-degree polynomial interpolation at equidistant points can be troublesome.

===Reason===
Runge's phenomenon is the consequence of two properties of this problem. 
* The magnitude of the ''n''-th order derivatives of this particular function grows quickly when ''n'' increases.
* The equidistance between points leads to a [[Lebesgue constant]] that increases quickly when ''n'' increases.

The phenomenon is graphically obvious because both properties combine to increase the magnitude of the oscillations.

The error between the generating function and the interpolating polynomial of order ''n'' is given by
:<math>f(x) - P_n(x) = \frac{f^{(n + 1)}(\xi)}{(n + 1)!} \prod_{i=0}^{n} (x - x_i) </math>

for some <math>\xi</math> in (&minus;1,&nbsp;1). Thus, 
:<math>
  \max_{-1 \leq x \leq 1} |f(x) - P_n(x)| \leq 
    \max_{-1 \leq x \leq 1} \frac{\left|f^{(n + 1)}(x)\right|}{(n + 1)!} 
    \max_{-1 \leq x \leq 1} \prod_{i=0}^n |x - x_i|
</math>.

Denote by <math>w_n(x)</math> the nodal function
:<math>w_n(x) = (x - x_0)(x - x_1)\cdots(x - x_n)</math>

and let <math>W_n</math> be the maximum of the magnitude of the <math>w_n</math> function:
:<math>W_n=\max_{-1 \leq x \leq 1} |w_n(x)|</math>.

It is elementary to prove that with equidistant nodes
:<math>W_n \leq n!h^{n+1} </math>

where <math>h=2/n</math> is the step size.

Moreover, assume that the (''n''+1)-th derivative of <math>f</math> is bounded, i.e.
:<math>\max_{-1 \leq x \leq 1} |f^{(n+1)}(x)| \leq M_{n+1}</math>.

Therefore, 
:<math>\max_{-1 \leq x \leq 1} |f(x) - P_{n}(x)| \leq M_{n+1} \frac{h^{n+1}}{(n+1)}</math>.

But the magnitude of the (''n''+1)-th derivative of Runge's function increases when ''n'' increases. The consequence is that the resulting upper bound tends to infinity when ''n'' tends to infinity.

Although often used to explain the Runge phenomenon, the fact that the upper bound of the error goes to infinity does not necessarily 
imply, of course, that the error itself also diverges with ''n.''