Newton Interpolation Polynomial

Summary

Newton form builds the interpolant using divided differences. Adding a node only appends one term, which is convenient for adaptive interpolation.

Prerequisites

Polynomial Interpolation, Lagrange Polynomial

Method Definition

P_{n} (x) = a_{0} + a_{1} (x - x_{0}) + a_{2} (x - x_{0}) (x - x_{1}) + \dots + a_{n} \prod_{j = 0}^{n - 1} (x - x_{j}),

where $a_{k} = f [x_{0}, \dots, x_{k}]$ are divided differences:

f [x_{i}] = y_{i}, f [x_{i}, \dots, x_{i + k}] = \frac{f [x_{i + 1}, \dots, x_{i + k}] - f [x_{i}, \dots, x_{i + k - 1}]}{x_{i + k} - x_{i}} .

Error / Accuracy

Same pointwise error formula as Lagrange:

f (x) - P_{n} (x) = \frac{f^{(n + 1)} (ξ)}{(n + 1)!} \prod_{i = 0}^{n} (x - x_{i}) .

Worked Example

Nodes $(0, 2), (1, 3), (2, 5)$ :

\begin{aligned} f [x_{0}] & = 2, \\ f [x_{0}, x_{1}] & = \frac{3 - 2}{1 - 0} = 1, \\ f [x_{1}, x_{2}] & = \frac{5 - 3}{2 - 1} = 2, \\ f [x_{0}, x_{1}, x_{2}] & = \frac{2 - 1}{2 - 0} = \frac{1}{2} . \end{aligned}

P (x) = 2 + 1 \cdot (x - 0) + \frac{1}{2} (x - 0) (x - 1) = \frac{1}{2} x^{2} + \frac{1}{2} x + 2,

matching the Lagrange interpolant.

Common Failure Modes

Incorrect denominator $x_{i + k} - x_{i}$ in divided differences.
Treating Newton form as a different polynomial from Lagrange; uniqueness says they coincide.

Connections

Related: Lagrange Polynomial, Polynomial Interpolation by Definition

References

Divided-difference Newton interpolation is classical numerical analysis.^[1]

NIST DLMF, §3.3 Interpolation, https://dlmf.nist.gov/3.3 ↩︎