Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Newton's divided difference form gives the same interpolating polynomial as the Lagrange form, but it is built up one term at a time. Adding a new data point only adds one new term.

Divided differences

and in general

Newton form

The error bound is the same as for Lagrange. If a point is added, keep everything and just add .

Method

Steps:

  1. List the nodes and values in a column
  2. Fill the divided difference table column by column, each entry from the two entries to its left
  3. Read the top diagonal: , , , ...
  4. Plug them into the Newton form

Worked example

Cubic through , , , .

1st2nd3rd
6
012
1
234
21
566

How each entry is found:

  • 1st: , ,
  • 2nd: ,
  • 3rd:

Check: . When the data are noisy, passing through every point is a bad idea, and Least Squares Approximation is used instead.