Chapter 3.3, Problem 7ES

a. Use Algorithm 3.2 to construct the interpolating polynomial of degree three for the unequally spaced points given in the following table:

ALGORITHM 3.2

Newton’s Divided-Difference Formula

To obtain the divided-difference coefficients of the interpolatory polynomial P on the (n + 1) distinct numbers x₀, x₁, … x_n, for the function f:

INPUT numbers x₀, x₁, … x_n; values f(x₀), f(x₁), …, f(x_n) as F_0,0, F_1,0, …, F_n,0.

OUTPUT the numbers F_0,0, F_1,1, …, F_n,n where

$P_n(x)=F_{0,0}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{F}_{ij}}{\displaystyle \underset{j=0}{\overset{i-1}{\prod }}\left(x-x_j\right)}.\left(F_{ij}\text{ is }f\left[x_0,x_1,\dots ,x_i\right].\right)$

Step 1 For i = 1, 2, …, n

For j = 1, 2, …, i

set $F_{i,j}=\frac{F_{i,j-1}-F_{i-1,j-1}}{x_i-x_{i-j}},\left(F_{i,j}=f\left[x_{i-j},\dots ,x_i\right].\right)$

Step 2 OUTPUT (F_0,0, F_1,1, …, F_n,n);

STOP.