Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Interpolation and Curve Fitting

The Runge Phenomenon and Chebyshev Nodes

See why high-degree interpolation on evenly spaced points oscillates wildly, and how Chebyshev nodes tame the error. Examples in NumPy and SciPy.

More data should mean a better fit, right? For polynomial interpolation on evenly spaced points the opposite can happen. The classic example is f(x) = 1 / (1 + 25 x^2) on [-1, 1]: as you add equally spaced nodes, the interpolating polynomial matches the function better in the middle and develops huge oscillations near the ends. This failure is the Runge phenomenon.

The good news is that the cause is the choice of nodes, not polynomials themselves. Place the nodes at the right spots and the error shrinks steadily. This lesson shows both behaviours with numbers.

Why it happens

Recall the error formula from Lagrange and Newton interpolation: the error contains the node polynomial w(x) = (x - x0)...(x - xn). With equally spaced nodes, |w(x)| is small in the middle and very large near the endpoints, and it grows with n. Meanwhile the derivatives of 1 / (1 + 25 x^2) also grow quickly. Together they make the maximum error grow without bound as n increases.

Experiment: equally spaced nodes

Python Maximum error grows with n

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error is not just failing to improve; it gets worse, from about 0.4 at degree 4 to about 60 at degree 20. A picture makes the endpoint swings obvious.

Python Plot the oscillation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Chebyshev nodes

The fix is to cluster nodes near the endpoints. The Chebyshev nodes on [-1, 1] are

xk = cos((2k + 1) * pi / (2n + 2)) for k = 0, ..., n.

They are the projections onto the x axis of equally spaced points on a half circle, so they are dense near -1 and 1. Among all node sets they minimize the largest value of |w(x)|, which is exactly the factor that caused trouble. For an interval [a, b], map them with x = (a + b)/2 + (b - a)/2 * xk.

flowchart LR
  A["Equally spaced points<br/>on a half circle"] --> B["Project down<br/>to the x axis"]
  B --> C["Chebyshev nodes:<br/>crowded near the ends"]
Python Chebyshev nodes fix the error

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With Chebyshev nodes the error decreases steadily as n grows, while the equally spaced error explodes.

If you can choose where to sample a function, sample at Chebyshev-like points. If the data are already given at fixed, equally spaced positions, avoid high-degree polynomials and use a piecewise method such as cubic splines.

What to take away for real data

  • Low degree (up to about 5 or 6) on equally spaced data is usually fine.
  • Large n with equal spacing is a trap. Use a spline, a low-degree least-squares fit (least squares curve fitting) or Chebyshev nodes.
  • Noisy data should never be interpolated exactly: passing through every noisy point reproduces the noise. Fit instead.
  • The Runge phenomenon is about a smooth function; it needs no noise to appear.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What goes wrong when you interpolate 1/(1+25x^2) on many equally spaced points?

    The interpolant still passes through all nodes, but the node polynomial is large near the ends, causing wild swings there.
  2. 2. Where are Chebyshev nodes concentrated?

    They are projections of equally spaced points on a half circle, which crowd toward -1 and 1.
  3. 3. Which quantity do Chebyshev nodes minimize?

    Minimizing the maximum of the node polynomial minimizes the part of the error bound you control.
  4. 4. You are given 30 equally spaced, noisy measurements. What is the best approach?

    Exact high-degree interpolation both oscillates and reproduces the noise; fitting a simple model is the sound choice.

Summary

  • Equally spaced nodes plus a high-degree polynomial can make the error grow as n grows (the Runge phenomenon).
  • Chebyshev nodes, cos((2k+1) pi / (2n+2)), cluster near the ends and give steadily shrinking error.
  • For fixed data, prefer piecewise interpolation or least-squares fitting to a high-degree polynomial.

Next: Cubic splines