Mathematics.

numerical analysis

Interpolation Methods

Numerical Analysis30 minDifficulty5 out of 10

You should know: numerical methods, polynomial functions

Overview

Interpolation is the problem of constructing a function — almost always a polynomial — that passes exactly through a given set of data points, so that values between the known points can be estimated. Given n+1 distinct points (x₀,y₀), …, (xₙ,yₙ), there is exactly one polynomial of degree ≤ n that passes through all of them; the Lagrange form and Newton's divided-difference form are two different, algebraically equivalent recipes for writing down that same unique polynomial. Interpolation underlies reading between tabulated values (steam tables, standard normal tables), computer graphics (smooth curves through control points), and is the conceptual seed of numerical integration and differentiation, both of which approximate a function by an interpolating polynomial and then integrate or differentiate that polynomial exactly.

Intuition

Two points determine a unique line; three points (not all collinear) determine a unique parabola; n+1 points determine a unique degree-≤n polynomial through all of them. The Lagrange formula builds this polynomial directly: basis piece Lᵢ(x) is engineered to vanish at every node except xᵢ, where it equals exactly 1, so scaling it by yᵢ and summing all the pieces guarantees the sum hits every data point exactly. Newton's form instead builds the polynomial up one point at a time — start with the constant that matches the first point, add a linear correction term that fixes the second point without disturbing the first, add a quadratic correction that fixes the third without disturbing the first two, and so on — which makes it cheap to extend when a new data point arrives.

Formal Definition

Definition

For distinct nodes x₀, …, xₙ with values y₀, …, yₙ, the Lagrange form writes the unique interpolating polynomial as a weighted sum of basis polynomials Lᵢ, each built to equal 1 at xᵢ and 0 at every other node:

P(x)=∑i=0nyi Li(x),Li(x)=∏j=0j≠inx−xjxi−xjP(x) = \sum_{i=0}^{n} y_i\, L_i(x), \qquad L_i(x) = \prod_{\substack{j=0 \\ j \ne i}}^{n} \dfrac{x - x_j}{x_i - x_j}
Lagrange interpolation formula
P(x)=f[x0]+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+⋯P(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots
Newton's divided-difference form (same polynomial, built incrementally)
f[xi,…,xi+k]=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xif[x_i,\ldots,x_{i+k}] = \dfrac{f[x_{i+1},\ldots,x_{i+k}] - f[x_i,\ldots,x_{i+k-1}]}{x_{i+k}-x_i}
Recursive definition of divided differences

Worked Examples

  1. Build the three Lagrange basis polynomials evaluated at x = 3.

    L0(3)=(3−2)(3−4)(1−2)(1−4)=(1)(−1)(−1)(−3)=−13L_0(3) = \dfrac{(3-2)(3-4)}{(1-2)(1-4)} = \dfrac{(1)(-1)}{(-1)(-3)} = \dfrac{-1}{3}

  2. Second basis polynomial at x = 3.

    L1(3)=(3−1)(3−4)(2−1)(2−4)=(2)(−1)(1)(−2)=1L_1(3) = \dfrac{(3-1)(3-4)}{(2-1)(2-4)} = \dfrac{(2)(-1)}{(1)(-2)} = 1

  3. Third basis polynomial at x = 3.

    L2(3)=(3−1)(3−2)(4−1)(4−2)=(2)(1)(3)(2)=13L_2(3) = \dfrac{(3-1)(3-2)}{(4-1)(4-2)} = \dfrac{(2)(1)}{(3)(2)} = \dfrac{1}{3}

  4. Combine: P(3) = y₀L₀(3) + y₁L₁(3) + y₂L₂(3) = 1(−1/3) + 3(1) + 3(1/3).

    P(3)=−13+3+1=113≈3.667P(3) = -\tfrac{1}{3} + 3 + 1 = \tfrac{11}{3} \approx 3.667

Answer: P(3) = 11/3 ≈ 3.667.

Practice Problems

Difficulty 4/10

Using the points (1,1), (2,3), (4,3), evaluate the interpolating polynomial at x = 1.5.

Difficulty 4/10

For the nodes x₀=1, x₁=2, x₂=4 with values y₀=1, y₁=3, y₂=3, compute the second divided difference f[x₀,x₁,x₂].

Difficulty 6/10

A steam table lists specific volume 1.696 m³/kg at 200°C and 1.937 m³/kg at 250°C for a fixed pressure. Using linear interpolation (the degree-1 Lagrange polynomial), estimate the specific volume at 220°C.

Quiz

Through n+1 distinct data points, there exists:
In the Lagrange basis polynomial Lᵢ(x), what is the value of Lᵢ at the node xᵢ itself?
An advantage of Newton's divided-difference form over Lagrange's form is that:

Summary

  • Interpolation constructs the unique polynomial of degree ≤ n passing through n+1 given data points.
  • The Lagrange form P(x) = Σ yᵢLᵢ(x) builds this polynomial directly from basis polynomials that are 1 at their own node and 0 elsewhere.
  • Newton's divided-difference form builds the same polynomial incrementally, e.g. P(x) = 1 + 2(x−1) − (2/3)(x−1)(x−2) for the points (1,1),(2,3),(4,3), giving P(3) = 11/3 by both methods.
  • Interpolation underlies reading between tabulated values and is the conceptual basis for numerical integration and differentiation.

References

  1. WebsiteWikipedia — Polynomial interpolation
  2. WebsiteWikipedia — Lagrange polynomial
  3. BookBurden, R. L. & Faires, J. D. Numerical Analysis, 10th ed. Cengage, 2015.