Interpolation and splines · Definition
Runge phenomenon
Before you start you need to know
Increasing the degree of an interpolating polynomial should improve the approximation. However, with equally spaced nodes the opposite happens near the endpoints of the interval.
Definition
The Runge phenomenon is the oscillatory, divergent behavior of polynomial interpolation errors at high degree when the nodes are equally spaced on an interval.
The interpolation error depends on the nodal product \( \prod_{i=0}^{n}(x-x_i) \) and on the derivative \( f^{(n+1)} \). With equally spaced nodes this product grows sharply near \( x=\pm1 \), and if the derivatives of \( f \) grow fast, the error blows up at the endpoints.
Take \( f(x)=\frac{1}{1+25x^2} \) on \( [-1,1] \). Interpolating with 5 equally spaced nodes gives a reasonable fit, but with 15 nodes the polynomial oscillates with large amplitude near \( x=\pm1 \) while the true function stays smooth. Raising the degree makes the approximation worse instead of better.
A typical mistake is to assume that more nodes always give a better result. To avoid it, use Chebyshev nodes, which cluster toward the endpoints and greatly reduce the nodal product.
One would expect more nodes to improve interpolation, but without care in node placement this is not the case. The phenomenon is corrected by changing the nodes or by using piecewise interpolation.
Think about it
If the derivatives of \( f \) were bounded by a constant \( M \) for every order, would the interpolation error with equally spaced nodes tend to zero as \( n \) increases?
Yes. The error is bounded by \( \frac{M\,2^{n+1}}{(n+1)!} \), which tends to zero because the factorial grows faster than \( 2^{n+1} \). The problem appears when the derivatives grow so fast that they overcome that factorial.
Exercises 10
- What does the Runge phenomenon describe?
- What type of nodes reduces the Runge phenomenon?
- Which classic function is used to illustrate the Runge phenomenon?
- Which factor of the interpolation error grows sharply near the endpoints with equally spaced nodes?
- What happens to the error when the degree increases with equally spaced nodes for \( f(x)=\frac{1}{1+25x^2} \) on \( [-1,1] \)?
- You interpolate \( f(x)=\frac{1}{1+25x^2} \) on \( [-1,1] \) with equally spaced nodes. Which statement best describes the behavior when going from degree 5 to degree 15?
- If the interpolation error is written as \( \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod(x-x_i) \), what happens when switching from equally spaced nodes to Chebyshev nodes?
- What is the main reason piecewise interpolation avoids the Runge phenomenon?
- For \( f(x)=\frac{1}{1+25x^2} \) on \( [-1,1] \), compare the maximum of \( |\prod(x-x_i)| \) for \( n=10 \) with equally spaced nodes versus Chebyshev nodes. Which statement is correct?
- Why does \( f(x)=\frac{1}{1+25x^2} \) produce oscillations with equally spaced nodes even though it is infinitely differentiable on \( [-1,1] \)?
References
- Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
- Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.