Newton Divided Differences

Lagrange interpolation’s fundamental flaw is that it cannot incorporate new data incrementally. Every added node forces a complete rebuild of the entire polynomial. Newton’s divided difference form solves this elegantly: the polynomial is built term by term, and adding a new node simply appends one extra term without disturbing anything that was already computed.

---

The Newton Form

The Newton interpolating polynomial for $n+1$ nodes ($x_0, x_1, \ldots, x_n$) is built iteratively:

$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$

Written compactly:

$P_n(x) = \sum_{k=0}^{n} f[x_0, x_1, \ldots, x_k] \prod_{j=0}^{k-1}(x - x_j)$

Here, the basis polynomials are defined as: $\phi_k(x) = \prod_{j=0}^{k-1}(x - x_j)$

The coefficients $a_k = f[x_0, x_1, \ldots, x_k]$ are called divided differences.

---

Divided Differences

To compute these coefficients efficiently, divided differences are defined recursively.

Order 0 (the data itself):

$f[x_i] = f(x_i)$

Order 1:

$f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$

Order $k$:

$f[x_i, \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}$

Each higher-order difference is built from two lower-order differences, creating a natural triangular table structure that makes calculating the coefficients straightforward.

---

Proof: Deriving the Coefficients

To understand why the coefficient $a_k$ equals the divided difference $f[x_0, \ldots, x_k]$, we can look at how the polynomial is constructed step-by-step.

Let $P_k(x)$ be the valid interpolating polynomial for $k+1$ points. It is defined as the previous polynomial $P_{k-1}(x)$ plus the new basis term multiplied by the unknown coefficient $a_k$:

$P_k(x) = P_{k-1}(x) + a_k(x-x_0)(x-x_1)\cdots(x-x_{k-1})$

For $P_k(x)$ to be a valid interpolating polynomial, it must perfectly hit the true function value at the newly added node $x_k$:

$P_k(x_k) = f(x_k)$

Substitute $x = x_k$ into our iterative polynomial formula:

$P_k(x_k) = P_{k-1}(x_k) + a_k(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})$

Replace $P_k(x_k)$ with $f(x_k)$:

$f(x_k) = P_{k-1}(x_k) + a_k\prod_{j=0}^{k-1}(x_k-x_j)$

Rearrange the equation to isolate the components multiplying $a_k$:

$a_k\prod_{j=0}^{k-1}(x_k-x_j) = f(x_k) - P_{k-1}(x_k)$

Finally, divide both sides to isolate the coefficient:

$a_k = \frac{f(x_k) - P_{k-1}(x_k)}{\prod_{j=0}^{k-1}(x_k-x_j)}$

This isolated coefficient $a_k$ is precisely what we define as the divided difference $f[x_0, \ldots, x_k]$. While this algebraic equation proves how the coefficient forces the polynomial to pass through the new point $x_k$, expanding the term $P_{k-1}(x_k)$ algebraically yields the exact recursive formula defined in the Divided Differences section above.

---

Worked Example: 3 Nodes

Problem: Build the Newton interpolating polynomial through the following three data points.

$x$	$f(x)$
1	2
2	3
4	1

Step 1: Build the Divided Difference Table

$$\begin{array}{ccccccc} x & f[x] & & \text{1st order} & & \text{2nd order} \\ \hline 1 & f[1] = 2 & & & & \\ & & \searrow & & & \\ & & & f[1,2] = 1 & & \\ 2 & f[2] = 3 & \nearrow & & \searrow & \\ & & \searrow & & & f[1,2,4] = -\frac{2}{3} \\ & & & f[2,4] = -1 & \nearrow & \\ 4 & f[4] = 1 & \nearrow & & & \\ \end{array}$$

The diagonal entries, reading from the top of each column are the Newton coefficients:

$f[1] = 2, \qquad f[1,2] = 1, \qquad f[1,2,4] = -\tfrac{2}{3}$

Step 2: Build the Polynomial

$P(x) = 2 + 1\cdot(x-1) + \left(-\tfrac{2}{3}\right)(x-1)(x-2)$

Expanding:

$\boxed{P(x) = -\frac{2}{3}x^2 + 3x - \frac{1}{3}}$

This is the same polynomial produced by Lagrange interpolation on the same nodes. This is expected, since there is a unique minimum-degree polynomial through any set of distinct points. The difference is purely in how efficiently we can extend it.

---

Adding a New Node: The Key Advantage

New node: $(5, 4)$

With Lagrange, adding $x_3 = 5$ would require rebuilding every basis polynomial. With Newton, we only compute a single new column in the divided difference table.

Step 3: Extend the Table

We already have $f[2,4] = -1$ from before. Now compute the new differences involving $x_3 = 5$:

$f[4,5] = \frac{4-1}{5-4} = 3$

$f[2,4,5] = \frac{f[4,5] - f[2,4]}{5-2} = \frac{3 - (-1)}{3} = \frac{4}{3}$

$f[1,2,4,5] = \frac{f[2,4,5] - f[1,2,4]}{5-1} = \frac{\frac{4}{3} - \left(-\frac{2}{3}\right)}{4} = \frac{2}{4} = \frac{1}{2}$

Here is the fully extended table. Notice how the top triangle of data from our original 3 points remains completely unchanged:

$$\begin{array}{ccccccccc} x & f[x] & & \text{1st order} & & \text{2nd order} & & \text{3rd order} \\ \hline 1 & f[1] = 2 & & & & & & \\ & & \searrow & & & & & \\ & & & f[1,2] = 1 & & & & \\ 2 & f[2] = 3 & \nearrow & & \searrow & & & \\ & & \searrow & & & f[1,2,4] = -\frac{2}{3} & & \\ & & & f[2,4] = -1 & \nearrow & & \searrow & \\ 4 & f[4] = 1 & \nearrow & & \searrow & & & f[1,2,4,5] = \frac{1}{2} \\ & & \searrow & & & f[2,4,5] = \frac{4}{3} & \nearrow & \\ & & & f[4,5] = 3 & \nearrow & & & \\ 5 & f[5] = 4 & \nearrow & & & & & \\ \end{array}$$

Step 4: Append the New Term

The old polynomial stays completely intact. We add exactly one new term:

$P_3(x) = \underbrace{2 + (x-1) - \tfrac{2}{3}(x-1)(x-2)}_{\text{previous } P_2(x)} \;+\; \underbrace{\tfrac{1}{2}(x-1)(x-2)(x-4)}_{\text{new term}}$

$\boxed{P_3(x) = 2 + (x-1) - \tfrac{2}{3}(x-1)(x-2) + \tfrac{1}{2}(x-1)(x-2)(x-4)}$

Note

The three previously computed divided differences: $f[1]=2$, $f[1,2]=1$, $f[1,2,4]=-\frac{2}{3}$ were not touched. Only one new column was needed to incorporate the fourth data point.

---

Why Reuse Matters

Aspect	Lagrange	Newton Divided Differences
Adding a new node	Rebuild all $n+1$ basis polynomials	Append one term; reuse all previous coefficients
Work per new node	$O(n^2)$ from scratch	$O(n)$ incremental
Best suited for	Fixed, fully known dataset	Streaming data, adaptive refinement

Newton interpolation is the preferred form for:

• Streaming data: Nodes arrive one at a time and the polynomial must be updated live
• Adaptive interpolation: You refine the approximation until the error is small enough, then stop
• Incremental numerical methods: Where new measurements continuously drive the computation forward

Caution

The Newton and Lagrange forms always produce the same polynomial for the same set of nodes; uniqueness of the interpolating polynomial guarantees this. The difference is purely computational: Newton’s form makes incremental updates cheap, while Lagrange does not.