Newton's Divided Differences

The Lagrange form has a drawback: add one more data point and every basis polynomial changes. Newton's form builds the same interpolating polynomial one point at a time: $$p(x) = c_0 + c_1(x - x_0) + c_2(x - x_0)(x - x_1) + \cdots + c_n(x - x_0)\cdots(x - x_{n-1}).$$ Each new term vanishes at all the earlier nodes, so it never spoils the fit already made.

The coefficients are divided differences, defined recursively: $f[x_i] = y_i$ and $$f[x_i, \ldots, x_j] = \frac{f[x_{i+1}, \ldots, x_j] - f[x_i, \ldots, x_{j-1}]}{x_j - x_i}.$$ Then $c_k = f[x_0, \ldots, x_k]$, the top edge of the divided-difference table.

Key idea

Fill the table column by column: each entry is (lower-left entry − upper-left entry) divided by the difference of the $x$-values at the two ends of its span. The top entries are the Newton coefficients, and adding a point adds one row and one coefficient.

Why it works

$c_0 = y_0$ makes $p(x_0)$ right; $c_1 = \frac{y_1 - y_0}{x_1 - x_0}$ (a slope) makes $p(x_1)$ right. In general $c_k$ is the leading coefficient of the polynomial through $x_0, \ldots, x_k$. If $p_{\mathrm{L}}$ interpolates at $x_0, \ldots, x_{k-1}$ and $p_{\mathrm{R}}$ at $x_1, \ldots, x_k$, then $$\frac{(x - x_0)p_{\mathrm{R}}(x) - (x - x_k)p_{\mathrm{L}}(x)}{x_k - x_0}$$ has degree at most $k$ and matches all $k + 1$ points (check the middle nodes, then $x_0$ and $x_k$). Comparing leading coefficients gives exactly the recursion, with $x_k - x_0$, the ends of the span, in the denominator.

The divided-difference table for four points. The highlighted x-values are the two ends of the current entry's span.

Worked example: A table for three points

Find the Newton form of the polynomial through $(0, 1)$, $(1, 3)$, $(3, 2)$.

First differences: $f[0, 1] = \frac{3 - 1}{1 - 0} = 2$ and $f[1, 3] = \frac{2 - 3}{3 - 1} = -\frac{1}{2}$.
Second difference: $f[0, 1, 3] = \frac{-\frac{1}{2} - 2}{3 - 0} = -\frac{5}{6}$. The denominator is $3 - 0$, the ends of the span.
$p(x) = 1 + 2x - \frac{5}{6}x(x - 1)$, which expands to $-\frac{5}{6}x^{2} + \frac{17}{6}x + 1$: the same polynomial the Lagrange form gave.

Answer: $p(x) = 1 + 2x - \frac{5}{6}x(x - 1)$

Worked example: Adding a point

Add the point $(4, 5)$ to the data above.

New entries along the bottom: $f[3, 4] = \frac{5 - 2}{4 - 3} = 3$, then $f[1, 3, 4] = \frac{3 - (-\frac{1}{2})}{4 - 1} = \frac{7}{6}$.
Then $f[0, 1, 3, 4] = \frac{\frac{7}{6} - (-\frac{5}{6})}{4 - 0} = \frac{1}{2}$.
New polynomial: the old one plus $\frac{1}{2}x(x - 1)(x - 3)$. At the old nodes the new term is $0$; at $x = 4$: old value $1$, plus $\frac{1}{2}(4)(3)(1) = 6$, total $5$. ✓

Answer: $p(x) + \frac{1}{2}x(x - 1)(x - 3)$

Newton's form is also cheap to evaluate. Nest it like Horner's method: $p(x) = c_0 + (x - x_0)\big(c_1 + (x - x_1)(c_2 + \cdots)\big)$, one multiplication and two additions per coefficient. Building the table takes about $n^{2}/2$ divisions, far less than solving the $(n + 1) \times (n + 1)$ system for the ordinary coefficients.

Common mistake

Dividing by the gap between neighboring $x$-values at every level. Only the first column uses neighbors; the entry $f[x_i, \ldots, x_j]$ always divides by $x_j - x_i$, the outermost pair. With equally spaced nodes the mistake changes every entry by a constant factor, so it is easy to miss; with uneven spacing it gives a polynomial that misses the data. Check: the finished polynomial must reproduce every data point.

Newton's Divided Differences

Practice

Builds on

Leads to

Sources and further reading