Newton polynomials (named after their inventor Isaac Newton) are polynomials used for polynomial interpolation. Rather than solving the huge Vandermonde matrix equation obtained in the polynomial interpolation by Gauss-Jordan elimination, we notice that we can do clever tricks by writing the polynomial in a different way. Given a data set:

where no two are the same, we assume the :s are values of a function, , at some certain -points named . We know from Weierstrass' theorem that there exists a unique polynomial of degree that pass through all these points, and we write it thusly:

or more formal:

We notice that:

And the equation may be written:

...

And the solution giving the coefficients is thus:

...

and this equation system will quickly grow to unrealistic proportions. Thus we need to find a better way to retrieve the coefficients . It turns out there exists a recusive formula for doing this in an efficient way.

Table of contents
1 Divided Differences
2 Example
3 See Also

Divided Differences

We see that the polynomial for a certain may be defined recursively, thus:

so that interpolates the function in the points . The coefficients are dependent only on the obtained function values of (our :s), so it is natural to say that as only depends on , only on and only on , and we define a notation for the divided differences:

This definition gives us the formal definition of the divided differences:

So that for example:

These are not easily grasped when put like this, but once the functions are arranged in a tabular form, things look simpler. Here for example, for a data set of (and we know that for all ):

On the diagonal of this table you will find the coefficients, as . Insert these into the formula at the top and you have your unique interpolation polynomial:

expanding into:

This is usually called the common newtonian interpolation polynomial.

Example

to be written

See Also