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: