I'm currently learning about the Runge function. On Wikipedia, I read the following:
Consider the function:
$ \dfrac{1}{1+25x^2}$
Runge found that if this function is interpolated at equidistant points $x_i$ between −1 and 1 such that:
$x_i = -1 + (i-1)\dfrac{2}{n},\quad i \in \left\{ 1, 2, \dots, n+1 \right\}$
with a polynomial $P_n(x)$ of degree ≤ 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:
$\lim\limits_{n \to \infty} \left( \max\limits_{-1 \leq x \leq 1} | f(x) -P_n(x)| \right) = +\infty.$
This shows that high-degree polynomial interpolation at equidistant points can be troublesome.
Reason
The error between the generating function and the interpolating polynomial of order $n$ is given by
$f(x) - P_n(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod\limits_{i=1}^{n+1} (x-x_i)$
for some in (−1, 1). Thus,
$\max\limits_{-1 \leq x \leq 1} |f(x) - P_n(x)| \leq \max\limits_{-1 \leq x \leq 1} \frac{|f^{(n+1)}(x)|}{(n+1)!} \max\limits_{-1 \leq x \leq 1} \prod\limits_{i=0}^n |x-x_i|$
For the case of the Runge function, interpolated at equidistant points, each of the two multipliers in the upper bound for the approximation error grows to infinity with $n$. 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$.
What I don't understand is how it is possible that the right factor $\max\limits_{-1 \leq x \leq 1} \prod\limits_{i=0}^n |x-x_i|$ can go to infinity as $n$ increases.
What I've already tried is calculating the factor for n = 1, n = 2, n = 3, n = 4 and n = 5 and the strange thing is that it looks like that this factor becomes lower when I use more points (and doesn't go to infinity).