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).