gibson:teaching:fall-2016:math753:newtondivdiff

Newton's Divided Difference algorithm is a slick way to compute an th order polynomial interpolant to a set of data points with distinct 's.

It produces a polynomial in the form of Horner's method with base points, e.g.

If we plug in the data points for , to the th-order generalization of the above equation, we get a series of equations in the unknowns .

Lo and behold this is lower-triangular system of equations, which can be written in matrix form like this

Lower-triangular systems can be solved easily via forward substitution. It turns out that for this particular lower-triangular system, the solution can be computed easily by subtracting and dividing numbers in a table. To see how that works, please refer to Newton Divided Difference Application (wikipedia).

Further reading:

- Newton Polynomial (wikipedia).

gibson/teaching/fall-2016/math753/newtondivdiff.txt · Last modified: 2016/11/11 12:15 by gibson