3.3 Newton Polynomials

An efficient automated way to calculate interpolating polynomials.

Lagrange is best for pencil and paper but not for automation.
Neville's can be used as well but it is equivalent to Lagrange.

We want to be able to go from:
$N_{n} (x)$ , interpolating $(x_{i}, y_{i})$ for $i = 0, 1, 2, . . ., n$
to:
$N_{n + 1} (x)$ , interpolating $(x_{i}, y_{i})$ for $i = 0, 1, 2, . . ., n, n + 1$ .

We can express this as:

N_{n + 1} (x) = N_{n} (x) + a_{n + 1} (x - x_{0}) (x - x_{1}) \dots (x - x_{n})

for some $a_{n + 1}$

N_{n + 1} (x) = a_{0} + a_{1} (x - x_{0}) + a_{2} (x - x_{0}) (x - x_{1}) + \dots + a_{n + 1} (x - x_{0}) (x - x_{1}) \dots (x - x_{n}) .

This is the Newton form of an interpolating polynomial

By examining coefficients in the recursion for Neville’s method:

P_{i, m + 1} (x) = \frac{(x - x_{i}) P_{i + 1, m} (x) - (x - x_{i + m + 1}) P_{i, m} (x)}{x_{i + m + 1} - x_{i}}

The leading coefficient of $P_{i, m} (x)$ is denoted by $f_{i, m}$
The leading coefficient of $P_{i + 1, m} (x)$ if $f_{i + 1, m}$
we see that the $x^{m + 1}$ term in $P_{i, m + 1} (x)$ has the coefficient

f_{i, m + 1} = \frac{f_{i + 1, m} - f_{i, m}}{x_{i + m + 1} - x_{i}}

f_{i, 0} = f (x_{i})

P_{n} ​ (x) = f_{0, 0} ​ + f_{0, 1} ​ (x - x_{0}) + f_{0, 2} ​ (x - x_{0} ​) (x - x_{1} ​) + \dots + f_{0, n} ​ (x - x_{0} ​) (x - x_{1} ​) \dots (x - x_{n - 1} ​)

Thus, by uniqueness of interpolation, the leading coefficient of $P_{0, n} (x)$ must match that of the Newton polynomial, which is why:

a_{n + 1} = f_{0, n + 1}

Example

Step 1: Construct the Divided Difference Table

We compute divided differences for the points:

(- 5, 15), (- 2, 2), (3, 15)

i	$X_{i}$	$f_{i, 0}$	$f_{i, 1} $	$f_{i, 2}$
0	-5	15	$\frac{2 - 15}{- 2 - (- 5)} = - \frac{13}{3}$	$\frac{(\frac{13}{5} - (- \frac{13}{3}))}{3 - (- 5)} = \frac{13}{15}$
1	-2	2	$\frac{15 - 2}{3 - (- 2)} = \frac{13}{5}$
2	3	15

Step 2: Construct the Newton Polynomials

Polynomial interpolating $(- 5, 15) = x_{0}$ :

$P_{0} (x) = f_{0, 0} (x) = 15$ .

Polynomial interpolating (−5,15) and (−2,2):
$x_{0} \to x_{1}$

$P_{1} (x) = f_{0, 0} + f_{0, 1} (x - x_{0}) = 15 - \frac{13}{3} (x - (- 5))$

Polynomial interpolating (−5,15),(−2,2),(3,15):
$x_{0} \to x_{1} \to x_{2}$

$P_{2} (x) = f_{0, 0} + f_{0, 1} (x - x_{0}) + f_{0, 2} (x - x_{0}) (x - x_{1}) = 15 - \frac{13}{3} (x - (- 5)) + \frac{13}{5} (x - (- 5)) (x - (2))$

Reordering the Points

Since interpolation is unique, the order of points does not change the polynomial. That means:

The polynomial through (−5,15), (−2,2), (3,15)
The polynomial through (3,15), (−2,2), (−5,15) $x_{2} \to x_{1} \to x_{0}$

$P_{2} (x) = f_{3, 0} + f_{1, 1} (x - x_{2}) + f_{0, 2} (x - x_{2}) (x - x_{1}) = 15 + \frac{13}{5} (x - 3) + \frac{15}{15} (x - 3) (x - 2)$

The polynomial through (−2,2), (−5,15), (3,15) $x_{1} \to x_{0} \to x_{3}$

$P_{2} (x) = f_{1, 0} + f_{0, 1} (x - (- 2)) + f_{0, 2} (x - (- 2)) (x - (- 5))$

are all the same

When constructing the interpolating polynomial, you can only move upward diagonally or to the right in the divided difference table. You cannot move downward, and you cannot skip around arbitrarily when selecting divided differences. This is because the points have to be adjacent.