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.
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
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
The notion of divided differences is a recursive division process.
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