Polynomial Interpolation

Thread one polynomial exactly through known points, then read values between them. Exact on the dots, increasingly adventurous in the gaps.

One parabola threads all three dots exactly and reads 13 at x equals 3, while the straight dashed chord between neighbours already drifts off the curve

Why Does This Exist?

Tables, experiments and simulations give values at scattered points; decisions need values between them. Polynomial interpolation threads a single degree- $(n-1)$ polynomial exactly through $n$ points, then evaluates anywhere. It underlies finite-difference weights, quadrature rules, and every "reconstruct the signal" step in graphics and audio resampling.

Two constructions serve different workflows. Lagrange writes the answer as a weighted sum of basis polynomials (conceptually clean, $O(n^2)$ to add a point). Newton builds with divided differences so new points extend the existing work (the practical choice). Splines trade one global polynomial for local pieces when Runge oscillation threatens. Grid and image resampling live separately in interpolation methods; this page is the polynomial theory behind the weights.

The one idea you need first

$n$ points with distinct $x$ -coordinates admit exactly one polynomial of degree below $n$ through all of them. Uniqueness is the whole licence: Lagrange and Newton must agree because only one answer exists. Taylor series approximates near one point with derivatives; interpolation matches values at many points with none.

Think of It Like This

A flexible ruler pinned at dots

A draftsman's flexible ruler bends through pinned dots on paper, taking the smoothest path that hits every pin. Three pins admit exactly one parabola; more pins force wigglier curves.

Lagrange rebuilds the whole ruler shape from scratch per query point. Newton slides a new pin under the existing ruler and adjusts only what the newcomer disturbs. Splines cut the ruler between pins and join gentle segments. And Runge's phenomenon is the ruler whipping wildly between pins when too many force one strip: the fix is more strips (splines), never a stiffer single ruler.

How It Actually Works

Newton divided differences build a difference table. First order: $f[x_i, x_j] = (f_j - f_i)/(x_j - x_i)$ . Second: $f[x_0, x_1, x_2] = (f[x_1,x_2] - f[x_0,x_1])/(x_2 - x_0)$ . The interpolant reads off the top diagonal:

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

Lagrange instead sums $f_i \ell_i(x)$ with basis $\ell_i$ equal to 1 at $x_i$ and 0 at the other nodes. Same polynomial, different scaffolding. Error at $x$ is bounded by $|f^{(n)}| \cdot |\prod (x - x_i)| / n!$ : small between clustered nodes, explosive outside (never extrapolate polynomials far).

Worked example

Thread $(0, 1)$ , $(1, 3)$ , $(2, 7)$ . First differences: $f[0,1] = (3-1)/1 = 2$ , $f[1,2] = (7-3)/1 = 4$ . Second: $f[0,1,2] = (4-2)/2 = 1$ . The interpolant:

p(x) = 1 + 2x + 1 \cdot x(x-1) = 1 + x + x^2

Verify: $p(0) = 1$ , $p(1) = 3$ , $p(2) = 7$ . All three pins hit. Predict at $x = 3$ : $p(3) = 1 + 3 + 9 = 13$ . That prediction trusts smoothness one step out; two steps further the quadratic keeps climbing while real data may not, which is the extrapolation warning made concrete.

Code

The point is the check: build the divided-difference table and confirm the interpolant hits every node.

1def newton_predict(xs: list[float], ys: list[float], x: float) -> float:2    n = len(xs)3    table = [ys[:]]4    for level in range(1, n):5        prev = table[-1]6        table.append([(prev[i + 1] - prev[i]) / (xs[i + level] - xs[i]) for i in range(n - level)])7    total, prod = table[0][0], 1.08    for level in range(1, n):9        prod *= x - xs[level - 1]  # extend the basis one node at a time10        total += table[level][0] * prod11    return total12
13
14xs, ys = [0.0, 1.0, 2.0], [1.0, 3.0, 7.0]15print([newton_predict(xs, ys, v) for v in xs])  # -> [1.0, 3.0, 7.0]16print(newton_predict(xs, ys, 3.0))  # -> 13.0

Watch Out For

Interpolating with high-degree global polynomials

Degree-15 through 16 evenly spaced nodes oscillates violently between them (Runge): exact on the dots, fiction in the gaps, with errors growing exponentially in degree. Cap global polynomials around degree 5 to 7, switch to splines or least-squares fits beyond that, and place nodes at Chebyshev points if you must go high.

Extrapolating past the last node

Inside the node span the error product $\prod(x - x_i)$ stays small; outside it every factor grows and the polynomial invents trends the data never showed. The $13$ at $x = 3$ is one step of faith, not a measurement. Fit a model with assumptions (linear tail, decay, periodicity) for anything beyond the span.

The Quick Version

One polynomial of degree below $n$ threads $n$ distinct- $x$ points: Lagrange and Newton agree by uniqueness.
Divided differences on the worked dots build $1 + x + x^2$ , predicting 13 at $x = 3$ .
Newton extends point by point; Lagrange rebuilds per query; splines localise when degrees grow.
High-degree global polynomials oscillate (Runge): cap degree, use splines or Chebyshev nodes.
Never extrapolate far: the error product explodes outside the node span.