Interpolation estimates unknown function values from known data points by building a curve that passes through those points. This cheat sheet compares three core methods: Lagrange interpolation, Newton divided differences, and cubic spline interpolation. College students need these tools for numerical analysis, data modeling, engineering computation, and scientific programming.
The goal is to choose a method that is accurate, efficient, and stable for the data at hand.
Lagrange interpolation gives one polynomial written directly from the data points, while Newton interpolation builds the same polynomial in a nested form that is easier to update. Divided differences measure changes across nodes and become the coefficients in the Newton polynomial. Cubic splines use piecewise cubic functions to avoid the oscillations that high-degree polynomials can produce.
Error depends on node placement, function smoothness, spacing, and the degree or spline conditions used.
Key Facts
- The Lagrange interpolating polynomial through n + 1 points is P_n(x) = sum from i = 0 to n of y_i L_i(x), where L_i(x) = product over j not equal to i of (x - x_j)/(x_i - x_j).
- Each Lagrange basis polynomial satisfies L_i(x_k) = 1 if i = k and L_i(x_k) = 0 if i is not equal to k.
- The Newton interpolating polynomial is P_n(x) = f[x_0] + f[x_0,x_1](x - x_0) + ... + f[x_0,...,x_n](x - x_0)(x - x_1)...(x - x_(n-1)).
- A divided difference is defined recursively by f[x_i,...,x_(i+k)] = (f[x_(i+1),...,x_(i+k)] - f[x_i,...,x_(i+k-1)])/(x_(i+k) - x_i).
- The polynomial interpolation error has the form f(x) - P_n(x) = f^(n+1)(c)/(n + 1)! times product from i = 0 to n of (x - x_i), for some c in the interval.
- A cubic spline uses a different cubic polynomial S_i(x) on each interval [x_i, x_(i+1)] and requires continuity of S, S', and S'' at interior knots.
- A natural cubic spline uses endpoint conditions S''(x_0) = 0 and S''(x_n) = 0, while a clamped spline specifies endpoint slopes S'(x_0) and S'(x_n).
- High-degree interpolation with equally spaced nodes can show Runge oscillation, so Chebyshev nodes or splines are often more stable choices.
Vocabulary
- Interpolation
- Interpolation is the process of estimating a function value between known data points using a curve that matches those points.
- Node
- A node is an input value x_i where the function value y_i or f(x_i) is known.
- Lagrange basis polynomial
- A Lagrange basis polynomial L_i(x) is a polynomial that equals 1 at node x_i and 0 at all other interpolation nodes.
- Divided difference
- A divided difference is a recursive slope-like quantity used as a coefficient in the Newton interpolation formula.
- Knot
- A knot is a node in spline interpolation where adjacent polynomial pieces meet.
- Natural cubic spline
- A natural cubic spline is a cubic spline whose second derivative is set to zero at both endpoints.
Common Mistakes to Avoid
- Using repeated x-values in an interpolation table is wrong because standard Lagrange and Newton formulas require distinct nodes to avoid division by zero.
- Extrapolating far outside the given nodes is risky because interpolation formulas are designed for values inside the data interval and may grow inaccurately outside it.
- Assuming a higher-degree polynomial is always more accurate is wrong because high-degree interpolation can create large oscillations, especially with equally spaced nodes.
- Forgetting continuity conditions in cubic splines is wrong because spline pieces must match in value, first derivative, and second derivative at interior knots.
- Mixing the order of nodes when using Newton divided differences can cause coefficient errors because the nested polynomial must use the same node order as the divided difference table.
Practice Questions
- 1 Given points (1, 2), (2, 5), and (4, 17), construct the Lagrange interpolating polynomial and estimate P(3).
- 2 For data f(0) = 1, f(1) = 3, and f(2) = 9, compute the divided differences f[0,1], f[1,2], and f[0,1,2].
- 3 A natural cubic spline is built on nodes x_0 = 0, x_1 = 1, x_2 = 3, and x_3 = 4. State the two endpoint second derivative conditions and the continuity conditions required at x_1 and x_2.
- 4 Explain why cubic spline interpolation may be preferred over a single high-degree polynomial when modeling many smooth data points.