Polynomial Interpolation

Numerical Analysis · Axiom Academy

LESSON Polynomial Interpolation The foundation of curve fitting through data points Given n+1 distinct data points (x₀, y₀), (x₁, y₁), ..., (xₙ, yₙ), find a polynomial P(x) of degree at most n that satisfies: Example: 3 points determine a unique parabola (degree ≤ 2). 4 points determine a unique cubic (degree ≤ 3). Existence and Uniqueness Theorem For n+1 data points with distinct x-values , there exists exactly one polynomial of degree at most n that passes through all points. The interpolating polynomial can be written as: The n+1 conditions P(xᵢ) = yᵢ give us n+1 linear equations for n+1 unknowns (the coefficients a₀, a₁, ..., aₙ). This is the Vandermonde matrix . It's invertible when all xᵢ are distinct! Direct Method: Solve the System We could solve the Vandermonde system to find the coefficients. But this approach has problems: Vandermonde matrices are often ill-conditioned Solving requires O(n³) operations Adding a new point means solving a new system from scratch Instead of finding coefficients directly, we use clever formulations: Lagrange form: Explicit formula, no system to solve Newton form: Easy to add new points Both give the same unique polynomial, just written differently! Interpolation is a linear operation. If P interpolates (xᵢ, yᵢ) and Q interpolates (xᵢ, zᵢ), then αP + βQ interpolates (xᵢ, αyᵢ + βzᵢ). n+1 points give a polynomial of degree at most n, not exactly n. Example: Points (0,1), (1,1), (2,1) are interpolated by P(x) = 1 (degree 0, not 2).

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