Interpolation

Newton Divided Differences

Newton's divided-difference form builds an interpolating polynomial from a divided-difference table. For three points the polynomial is: P(x) = c0 + c1*(x-x0) + c2*(x-x0)*(x-x1) where c0=f0, c1=f[0,1], c2=f[0,1,2]. Example: (1,1),(2,4),(4,16) with x=3 gives P(3)=9.

The Newton coefficients c0,c1,c2 equal f0, f[0,1], f[0,1,2].

Example

Build a divided-difference table and evaluate the Newton form.

highlighted = computed this step

Step 1 — Set up

Evaluate the Newton polynomial at x equals 3.

x=3x= 3

Step 2 — First differences

Fill the first divided differences.

xffirst113246416\begin{array}{ccc}\text{x} & \text{f} & \text{first} \\ 1 & 1 & \hlmath{3} \\ 2 & 4 & \hlmath{6} \\ 4 & 16 & \text{}\end{array}

Step 3 — Second difference

Fill the second divided difference.

xffirstsecond1131246416\begin{array}{cccc}\text{x} & \text{f} & \text{first} & \text{second} \\ 1 & 1 & 3 & \hlmath{1} \\ 2 & 4 & 6 & \text{} \\ 4 & 16 & \text{} & \text{}\end{array}

Step 4 — Newton coefficients

Use diagonal coefficients c 0 equals 1, c 1 equals 3, and c 2 equals 1.

c0=1c1=3c2=1c_{ 0 }= \hl{1} \quad c_{ 1 }= \hl{3} \quad c_{ 2 }= \hl{1}

Step 5 — Evaluate Newton form

At x 3, the term values are 1, 6, and 2, so P of 3 is 9.

P(3)=1+3⋅(3−1)+1⋅(3−1)(3−2)=1+6+2=9P( 3 )= 1 + 3 \cdot( 3 - 1 )+ 1 \cdot( 3 - 1 )( 3 - 2 )= 1 + \hl{6} + \hl{2} = \hl{9}

Step 6 — Result

The Newton value at 3 is 9.

P(3)=9P( 3 )= \hl{9}
newton-divided-differences The divided-difference table is built recursively: f[i,i+1] = (f[i+1] - f[i]) / (x[i+1] - x[i]) f[i,i+1,i+2] = (f[i+1,i+2] - f[i,i+1]) / (x[i+2] - x[i])