Newton polynomial

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