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:
- List the nodes and values in a column
- Fill the divided difference table column by column, each entry from the two entries to its left
- Read the top diagonal: , , , ...
- Plug them into the Newton form
Worked example
Cubic through , , , .
| 1st | 2nd | 3rd | ||
|---|---|---|---|---|
| 6 | ||||
| 0 | 1 | 2 | ||
| 1 | ||||
| 2 | 3 | 4 | ||
| 21 | ||||
| 5 | 66 |
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.