Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
2  
You might want to see this article instead. –  Timmy Turner Aug 13 '12 at 2:16
1  
I did a quick computation myself, using n=5, 10, 25, 100 and Maple, and I came to the same conclusion as the original poster. So it looks like Wikipedia is wrong. –  Jitse Niesen Aug 13 '12 at 16:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.