User:MathMartin/Newton polynomial

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In the mathematical subfield of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points.

The Newton polynomial is sometimes called Newton interpolation polynomial. This is a bit misleading as there is only one interpolation polynomial for a given set of knots. The more precise name is interpolation polynomial in the Newton form.

Main idea[edit]

Solving an interpolation problems leads to a problem in linear algebra where we have to solve a matrix. Using a standard monomial basis for our interpolation polynomial we get the very complicated Vandermonde matrix. By choosing another basis, the Newton basis, we get a much simpler lower triangular matrix which can solved faster.

We construct the Newton basis as

Using this basis we we to solve

to solve the polynomial interpolation problem.

This matrix can be solved recursively by solving the following equations

Interpolation polynomial in Newton form[edit]

Given a set of N+1 data points

where no two xn are the same, the interpolation polynomial is a polynomial function N(x) of degree N with

According to the Stone-Weierstrass theorem such a function exists and is unique.

The Newton polynomial is the solution to the interpolation problem. It is given by the a linear combination of Newton basis polynomials:

with the Newton basis polynomials defined as

and the coefficients defined as


is the notation for divided differences.

Thus the Newton polynomial can be written as

Divided differences[edit]

The notion of divided differences is a recursive division process.

We define

For the first few [yn] this yields

To make the recurive process more clear the divided differences can be put in a tabular form

On the diagonal of this table you will find the coefficients, as

See also[edit]