Newton Polynomial

See Taylor polynomial

Not as useful compared to using matrices (Polynomial Interpolation), but for proving a point (pedagogical).

Suppose I want to find a cubic that crosses 4 points.

Find so that

Which leads to 4 equations. For simplicity, . Note that the coordinates should be in increasing order, and for pedagogical purposes, uniformly spaced.

Now, we could solve this system with a matrix as shown in the Polynomial Interpolation note, but Newton didn't have these tools at his disposal. So he found a different way.

Taking the difference between each equation:

Then the second difference:

Finally,

Now we go backwards, and find:

Combining and simplifying:

which is almost a Taylor polynomial.

For non-integer spacing (but still uniform), we have:

but is not .

Now, what happens as ? Then , and we have:

(see definition of differentiation).

Similarly,

More generally:

Altogether, as ,

which is exactly a Taylor polynomial.

First Generalization

For number of integer values spaced evenly apart, we have the formula:

and we can calculate the finite differences like so:

and we can find all the coefficients we need on the top "row".

Generalization

Now we do not assume the values are evenly spaced.

todo Note in progress

https://pythonnumericalmethods.berkeley.edu/notebooks/chapter17.05-Newtons-Polynomial-Interpolation.html
https://en.wikipedia.org/wiki/Newton_polynomial
https://en.wikipedia.org/wiki/Divided_differences