User:MathMartin/Newton polynomial

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

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

$n_{n}(x):=\prod _{\nu =0}^{n}(x-x_{\nu -1})\qquad n=0,\ldots ,N$

Using this basis we we to solve

$\mathbf {A} \mathbf {a} ={\begin{pmatrix}1&&&&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{1}&\ddots &&\\\vdots &\vdots &&\ddots &\\1&x_{N}-x_{0}&\ldots &\ldots &\prod _{n=0}^{N-1}(x_{N}-x_{n})\end{pmatrix}}{\begin{pmatrix}a_{0}\\\vdots \\a_{N}\end{pmatrix}}={\begin{pmatrix}y_{0}\\\vdots \\y_{N}\end{pmatrix}}$

to solve the polynomial interpolation problem.

This matrix can be solved recursively by solving the following equations

$\sum _{\nu =0}^{n}a_{\nu }n_{\nu }(x_{n})=y_{n}\qquad n=0,...,N$

Interpolation polynomial in Newton form

Given a set of N+1 data points

$(x_{0},y_{0}),\ldots ,(x_{N},y_{N})$

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

$N(x_{n})=y_{n}\qquad n=0,\ldots ,N$

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:

$N(x):=\sum _{n=0}^{N}a_{n}n_{n}(x)$

with the Newton basis polynomials defined as

$n_{n}(x):=\prod _{\nu =0}^{n}(x-x_{\nu -1})$

and the coefficients defined as

$a_{n}:=[y_{0},\ldots ,y_{n}]$

where

$[y_{0},\ldots ,y_{n}]$

is the notation for divided differences.

Thus the Newton polynomial can be written as

$N(x):=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\ldots +[y_{0},\ldots ,y_{N}](x-x_{0})\ldots (x-x_{N-1})$

Divided differences

The notion of divided differences is a recursive division process.

We define

$[y_{\nu }]:=y_{\nu }\qquad {\mbox{ , }}\nu =0,\ldots ,n$

$[y_{\nu },\ldots ,y_{\nu +j}]:={\frac {[y_{\nu +1},\ldots y_{\nu +j}]-[y_{\nu },\ldots y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}}\qquad {\mbox{ , }}\nu =0,\ldots ,n-j,j=1,\ldots ,n$

For the first few [y_n] this yields

$[y_{0}]=y_{0}$

$[y_{0},y_{1}]={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}$

$[y_{0},y_{1},y_{2}]={\frac {y_{3}-y_{1}-{\frac {x_{3}-x_{1}}{x_{2}-x_{1}}}(y_{2}-y_{1})}{(x_{3}-x_{1})(x_{3}-x_{2})}}$

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

${\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}$

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

$a_{0}=y_{0}$

$a_{1}=[y_{0},y_{1}]$

$a_{2}=[y_{0},y_{1},y_{2}]$

$a_{3}=[y_{0},y_{1},y_{2},y_{3}]$

See also

• Neville's schema
• Polynomial interpolation
• Lagrange polynomials
• Bernstein polynomials