Interpolation Error

Numerical Analysis · Axiom Academy

How accurate is polynomial interpolation? When we interpolate a function f(x) using points x₀, x₁, ..., xₙ, the error at any point x is: Where ξ is some point in the smallest interval containing x and all the nodes x₀, ..., xₙ. f⁽ⁿ⁺¹⁾(ξ): Depends on how smooth f is (its (n+1)th derivative) ∏(x - xᵢ): The "node polynomial" — depends only on node locations Let's define ω(x) = (x - x₀)(x - x₁)···(x - xₙ) ω(x) = 0 at all interpolation nodes (the error is zero there!) ω(x) can be large outside the interval [x₀, xₙ] Outside the interpolation interval, |ω(x)| grows rapidly. Extrapolation is dangerous! We can bound the error if we know bounds on the derivative: For equally spaced nodes on [a, b] with spacing h = (b-a)/n: Error depends on hⁿ⁺¹ — halving h gives ≈2ⁿ⁺¹ improvement But M_ n+1 often grows with n for some functions! More nodes doesn't always mean better approximation For analytic functions (e.g., eˣ, sin x): More nodes → more accuracy For functions with limited smoothness : Gains limited by derivative bounds For some functions : Higher degree can make things worse (Runge phenomenon!) Choose good nodes: Chebyshev nodes minimize |ω(x)| Use piecewise polynomials: Keep degree low, use more pieces Match to smoothness: Don't use degree-10 polynomial on noisy data Interpolation of 1/(1+25x²) with 11 points: equally spaced (red) vs Chebyshev (green)

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