Runge's Phenomenon

Numerical Analysis · Axiom Academy

When more data points make things worse! Runge's Surprising Discovery (1901) Carl Runge discovered that for some functions, using more interpolation points with equally spaced nodes can make the approximation worse , not better! Consider the innocent-looking function: Increase the degree and watch the oscillations grow near x = ±1! Recall the interpolation error formula: The Problem: Competing Effects As n increases with equally spaced nodes: (n+1)! in the denominator grows — good! But |ω(x)| = |∏(x - xᵢ)| grows even faster near the endpoints! Also, f⁽ⁿ⁺¹⁾(x) can explode for certain functions For Runge's function, the derivatives grow like: This factorial growth outpaces the (n+1)! in the denominator! The node polynomial ω(x) = ∏(x - xᵢ) has very different behavior for different node placements. For equally spaced nodes, |ω(x)| is large near the endpoints (x ≈ ±1). Chebyshev nodes cluster near the endpoints, keeping |ω(x)| small everywhere! Solutions to the Runge Phenomenon Use non-equally spaced nodes that cluster near endpoints: Minimizes max|ω(x)| over [-1, 1]. Use piecewise low-degree polynomials instead of one high-degree polynomial. Keep local control, avoid global oscillations. Don't require exact interpolation — minimize total error instead. Use lower degree than the number of points. Automatically detect where more points are needed. Put more nodes where the function varies rapidly.

This is the written version of the interactive lesson above. See the full Numerical Analysis course.