Newton’s Divided-Difference Interpolation: 04-BS-5, May 2017, Q4

Question 4: Newton’s Divided-Difference Interpolation (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Seven unequally spaced nodes and their function values:

$x$	−4	−2	−1	0	2	4	5
$F(x)$	145	−23	−17	−7	1	193	523

Find. The Newton divided-difference table for this data and the interpolating polynomial of highest possible degree, expanded in ordinary powers of $x$.

Approach. Build the divided-difference table column by column, read the leading diagonal as the Newton coefficients, then expand the nested product form. The highest possible degree is decided by the table itself: the last order whose difference is non-zero.

Definition of the divided differences. The zeroth order entries are the data themselves, $F[x_i]=F(x_i)$, and each higher order is formed from two neighbours of the order below: $$F[x_i,\dots,x_{i+j}]=\dfrac{F[x_{i+1},\dots,x_{i+j}]-F[x_i,\dots,x_{i+j-1}]}{x_{i+j}-x_i}$$ Note the divisor uses the two outermost abscissae of the group, which is what makes the scheme work for unequal spacing — as here, where the gaps are 2, 1, 1, 2, 2, 1.
First divided differences. For example $F[x_0,x_1]=\dfrac{-23-145}{-2-(-4)}=\dfrac{-168}{2}=-84$ and $F[x_5,x_6]=\dfrac{523-193}{5-4}=330$. The full column is $$-84,\quad 6,\quad 10,\quad 4,\quad 96,\quad 330$$
Complete the table. Continuing the same rule upward through the orders:

$x_i$ $F[\,\cdot\,]$ 1st 2nd 3rd 4th 5th 6th

−4 145 −84 30 −7 1 0 0

−2 −23 6 2 −1 1 0

−1 −17 10 −2 5 1

0 −7 4 23 11

2 1 96 78

4 193 330

5 523

Two features decide the answer. The fourth-order column is constant at $1$, and consequently the fifth and sixth orders are identically zero. Seven points would in general support a degree-6 polynomial, but here $$\boxed{\text{the highest possible degree is }4}$$ because every coefficient beyond the fourth vanishes.
Write the Newton form. Reading the leading diagonal $145,\,-84,\,30,\,-7,\,1,\,0,\,0$ as the coefficients, $$P(x)=145-84(x+4)+30(x+4)(x+2)-7(x+4)(x+2)(x+1)+1\cdot(x+4)(x+2)(x+1)x$$ The two omitted terms would carry the zero fifth and sixth differences, so nothing is lost by truncating here.
Expand to standard form. Multiplying out each product, $$(x+4)(x+2)(x+1)x=x^4+7x^3+14x^2+8x,\qquad -7(x+4)(x+2)(x+1)=-7x^3-49x^2-98x-56$$ $$30(x+4)(x+2)=30x^2+180x+240,\qquad -84(x+4)=-84x-336$$ Collecting like powers, the cubic terms cancel ($7-7=0$), and $$\boxed{P(x)=x^4-5x^2+6x-7}$$
Verify against every node. Substituting each abscissa reproduces the tabulated ordinate exactly: $P(-4)=256-80-24-7=145$; $P(-2)=16-20-12-7=-23$; $P(-1)=1-5-6-7=-17$; $P(0)=-7$; $P(2)=16-20+12-7=1$; $P(4)=256-80+24-7=193$; $P(5)=625-125+30-7=523$. All seven match, confirming both the table and the expansion.

$x_i$	$F[\,\cdot\,]$	1st	2nd	3rd	4th	5th	6th
−4	145	−84	30	−7	1	0	0
−2	−23	6	2	−1	1	0
−1	−17	10	−2	5	1
0	−7	4	23	11
2	1	96	78
4	193	330
5	523

The quartic $P(x)=x^4-5x^2+6x-7$ drawn through all seven data points. Although seven nodes could support a degree-6 curve, the vanishing fifth and sixth divided differences show the data lie exactly on a quartic.

Quantity	Result
Leading diagonal (Newton coefficients)	$145,\ -84,\ 30,\ -7,\ 1,\ 0,\ 0$
Highest possible degree	$4$ (5th and 6th differences vanish)
Newton form	$145-84(x+4)+30(x+4)(x+2)-7(x+4)(x+2)(x+1)+(x+4)(x+2)(x+1)x$
Expanded polynomial	$P(x)=x^4-5x^2+6x-7$

Topic: Newton’s divided-difference form of the interpolating polynomial for unequally spaced data.

Key relations: recursive definition $F[x_i,\dots,x_{i+j}]=\big(F[x_{i+1},\dots,x_{i+j}]-F[x_i,\dots,x_{i+j-1}]\big)/(x_{i+j}-x_i)$; Newton form $P(x)=\sum_{j}F[x_0,\dots,x_j]\prod_{k\lt j}(x-x_k)$; for a polynomial of degree $m$ the $m$th divided difference equals its leading coefficient and all higher ones vanish.

Why this works: the $j$th divided difference is a discrete stand-in for $f^{(j)}/j!$, so a data set generated by a degree-4 polynomial has a constant fourth difference (equal to the leading coefficient, here $1$) and identically zero fifth and sixth differences. That is why the table, not the number of points, sets the achievable degree. The Newton form is also incremental: each new node simply appends one term without disturbing those already computed, which is its main practical advantage over the Lagrange form. Interpolation through $n+1$ points is unique, so the quartic recovered here is the same polynomial any other method would produce.

Common pitfall: dividing by adjacent-node spacing rather than by the difference of the two outermost abscissae in the group — harmless for equally spaced data, but it corrupts every higher order here where the gaps alternate between 1 and 2. The other frequent error is to force a degree-6 polynomial simply because seven points were supplied; the two zero columns are the data telling you that a quartic already fits exactly, and inflating the degree would only add terms multiplied by zero.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 19 §19.3 (Interpolation — Newton’s Divided Difference Formula); Chapra & Canale, Numerical Methods for Engineers, 7th ed., Ch. 18.

Question 4 of 7: Newton’s Divided-Difference Interpolation

Question 4: Newton’s Divided-Difference Interpolation (20 marks)