Burden & Faires, 9th Ed. - §3.3–3.4
Chapter 6: Divided Differences & Hermite Interpolation
Newton's divided-difference formula · Forward & backward difference tables · Osculating (Hermite) polynomials
Lagrange's form (Chapter 5) is clean to write down but expensive to extend - adding a new data point forces a total rebuild. Newton's divided-difference form solves the same interpolation problem but builds the polynomial incrementally, coefficient by coefficient, so that adding a node only adds a term. This chapter builds that machinery, specializes it to equally spaced data, and then extends interpolation itself to match not just function values but derivatives too - Hermite interpolation.
Section 3.3
Newton's Divided-Difference Formula
Why Not Just Use Lagrange?
The Practical Problem with Lagrange's Form
Adding one more data point $(x_{n+1},f(x_{n+1}))$ to a Lagrange interpolant means every single basis polynomial $L_{n,k}$ changes, because each one is built from all the nodes at once - none of the earlier computation survives. Newton's form instead writes $P_n(x)$ as a sum where each new term only depends on the new point:
$$P_n(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 + f[x_0,\ldots,x_n]\prod_{i=0}^{n-1}(x-x_i)$$
Adding node $x_{n+1}$ just appends one more term - nothing already computed needs to change.
Divided Differences
Definition - Divided Differences
The zeroth divided difference is $f[x_i] = f(x_i)$. For $k\ge1$, the $k$th divided difference is defined recursively:
$$f[x_i,x_{i+1},\ldots,x_{i+k}] = \frac{f[x_{i+1},\ldots,x_{i+k}] - f[x_i,\ldots,x_{i+k-1}]}{x_{i+k}-x_i}$$
The coefficients in Newton's formula above are exactly the top-diagonal entries $f[x_0], f[x_0,x_1], f[x_0,x_1,x_2],\ldots$ of the divided-difference table - structurally the same triangular table as Neville's Method (Chapter 5), but storing coefficients instead of point-evaluations, which is what makes them reusable at any $x$, not just one target point.
Divided-difference table for $f(x)=\ln x$ at $x=1.0,1.3,1.6,1.9,2.2$. The highlighted top diagonal ($f[x_0]$, $f[x_0,x_1]$, $f[x_0,x_1,x_2]$, …) are exactly the coefficients of Newton's polynomial $P_4(x)$ - hover any cell to see which two cells of the previous column produced it.
📘 Example 6.1 - Building the Newton Polynomial from the Table
Using the table above for $f(x)=\ln x$, write $P_4(x)$ explicitly and evaluate at $x=1.5$.
Solution Top-diagonal coefficients: $f[x_0]=0$, $f[x_0,x_1]=0.874548$, $f[x_0,x_1,x_2]=-0.304027$, $f[x_0,x_1,x_2,x_3]=0.116888$, $f[x_0,\ldots,x_4]=-0.043176$.
$$P_4(x) = 0 + 0.874548(x-1) - 0.304027(x-1)(x-1.3) + 0.116888(x-1)(x-1.3)(x-1.6) - 0.043176(x-1)(x-1.3)(x-1.6)(x-1.9)$$
At $x=1.5$: $(x-1)=0.5$, $(x-1.3)=0.2$, $(x-1.6)=-0.1$, $(x-1.9)=-0.4$.
$$P_4(1.5) = 0 + 0.874548(0.5) - 0.304027(0.5)(0.2) + 0.116888(0.5)(0.2)(-0.1) - 0.043176(0.5)(0.2)(-0.1)(-0.4)$$
$$= 0.437274 - 0.030403 - 0.001169 - 0.000173 = 0.405529$$
$P_4(1.5)=0.405529$ - identical to Neville's Method's answer in Chapter 5, Example 5.3 (both compute the same unique interpolating polynomial, Theorem 5.1), but Newton's form gives an explicit, reusable formula rather than a single point-value.
Section 3.3 continued
Forward & Backward Difference Formulas
Equally Spaced Nodes - Newton's Forward-Difference Formula
When nodes are equally spaced with step $h$ ($x_i = x_0+ih$), divided differences simplify to ordinary finite differences. Define the forward difference $\Delta f(x_i) = f(x_{i+1})-f(x_i)$ and $\Delta^k f(x_i) = \Delta^{k-1}f(x_{i+1})-\Delta^{k-1}f(x_i)$. Then $f[x_0,\ldots,x_k] = \dfrac{\Delta^k f(x_0)}{k!\,h^k}$, and with $x = x_0+sh$:
$$P_n(x) = f(x_0) + s\,\Delta f(x_0) + \binom{s}{2}\Delta^2 f(x_0) + \cdots + \binom{s}{n}\Delta^n f(x_0), \qquad \binom{s}{k}=\frac{s(s-1)\cdots(s-k+1)}{k!}$$
This is Newton's Forward-Difference Formula - cheapest to evaluate near $x_0$ (small $s$).
Newton's Backward-Difference Formula
Symmetrically, define $\nabla f(x_i)=f(x_i)-f(x_{i-1})$. With $x=x_n+sh$ ($s$ typically negative, measuring backward from the last node):
$$P_n(x) = f(x_n) + s\,\nabla f(x_n) + \binom{s+1}{2}\nabla^2 f(x_n) + \cdots + \binom{s+n-1}{n}\nabla^n f(x_n)$$
Cheapest to evaluate near $x_n$, the right end of the table.
Same Polynomial, Different Bookkeeping
Forward, backward, and general divided-difference forms all compute the exact same unique interpolating polynomial (Theorem 5.1) - the choice between them is purely about which end of the data table is closest to the point you want to evaluate, which minimizes round-off from adding many small terms.
Section 3.4
Hermite Interpolation
The Idea - Match Derivatives, Not Just Values
Ordinary interpolation only constrains $P(x_i)=f(x_i)$. Hermite interpolation (also called osculating interpolation - "osculating" literally means "kissing," describing curves that touch tangentially) additionally requires $P'(x_i)=f'(x_i)$ at every node. With $n+1$ nodes, that's $2n+2$ conditions, uniquely determining a polynomial of degree $\le 2n+1$.
Construction via Divided Differences with Repeated Nodes
The elegant trick: build an ordinary divided-difference table, but list each node twice - $z_0=z_1=x_0,\, z_2=z_3=x_1,\ldots$ - and whenever a divided difference would divide by zero (because $z_i=z_{i-1}$), substitute the known derivative directly:
$$f[z_{2i},z_{2i+1}] := f'(x_i)$$
Every other entry of the table is computed by the ordinary divided-difference recursion. The resulting Newton-form polynomial through the doubled node list is the Hermite polynomial.
📘 Example 6.2 - Cubic Hermite Interpolant for $f(x)=\sin x$
Construct the Hermite polynomial matching $f(x)=\sin x$ and $f'(x)=\cos x$ at $x_0=0$ and $x_1=1$.
Solution $f(0)=0,\,f'(0)=1,\,f(1)=0.841471,\,f'(1)=0.540302$. Repeated-node table with $z=(0,0,1,1)$:
Top diagonal coefficients: $0,\; 1,\; -0.158529,\; -0.142640$. So
$$H_3(x) = 0 + (1)(x-0) - 0.158529\,x^2 - 0.142640\,x^2(x-1)$$
At $x=0.5$: $H_3(0.5)=0.478198$ vs. true $\sin(0.5)=0.479426$ - error $\approx1.2\times10^{-3}$, noticeably better than an ordinary degree-3 Lagrange fit using only function values at the same two points would achieve, precisely because the derivative information pins down the curve's slope, not just its height.
| $z_i$ | $Q_{i,0}$ | $Q_{i,1}$ | $Q_{i,2}$ | $Q_{i,3}$ |
|---|---|---|---|---|
| 0 | 0 | |||
| 0 | 0 | 1.000000 = f'(0) | ||
| 1 | 0.841471 | 0.841471 | $-0.158529$ | |
| 1 | 0.841471 | 0.540302 = f'(1) | $-0.301169$ | $-0.142640$ |
$f(x)=\sin x$ (gray) against the cubic Hermite interpolant $H_3(x)$ (purple) from Example 6.2, using only 2 nodes but matching both value and slope at each - compare visually to how much worse a degree-1 secant line (matching values only) would track the curvature.
Practice
Practice Problem
Try this problem yourself before expanding the solution below.
✏️ Practice Problem 6.1 - Newton's Divided-Difference Form for $\sqrt{x}$
Using the data $(1,1),(4,2),(9,3),(16,4)$ (i.e. $f(x)=\sqrt{x}$ at perfect squares), build the divided-difference table, write Newton's divided-difference polynomial $P_3(x)$, and use it to estimate $\sqrt{6}$.
Solution
The divided-difference table:
Reading the top diagonal gives the coefficients, so
$$P_3(x) = 1 + 0.333333(x-1) - 0.016667(x-1)(x-4) + 0.000794(x-1)(x-4)(x-9).$$
Evaluating at $x=6$: $P_3(6) = 2.476190$.
$P_3(6)=2.476190$ vs. the true $\sqrt6=2.449490$, an error of $0.0267$ - the polynomial degrades away from the well-spaced nodes it was built on, exactly the interpolation-error behavior of Chapter 5.
| $x_i$ | $f[x_i]$ | 1st | 2nd | 3rd |
|---|---|---|---|---|
| 1 | 1 | 0.333333 | -0.016667 | 0.000794 |
| 4 | 2 | 0.200000 | -0.004762 | |
| 9 | 3 | 0.142857 | ||
| 16 | 4 |
Connections Across the Course
- Newton's divided-difference form is what makes Chapter 7's piecewise construction practical - each spline segment reuses this same incremental machinery locally.
- Hermite interpolation's derivative-matching idea reappears directly in clamped cubic splines, which pin down the spline's endpoint slopes exactly the way $H_3$ pins down its slope at $x_0$ and $x_1$.
- The forward-difference formula's coefficients $\Delta^k f(x_0)/(k!h^k)$ reappear as the building blocks for the finite-difference formulas of Chapter 8.