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})n=0,\dots ,N$

Using this basis we we to solve

$\mathbf{𝐀}\mathbf{𝐚}=\left(\begin{array}{ccccc}1& & & & 0\\ 1& x_1-x_0& & & \\ 1& x_2-x_1& \ddots & & \\ ⋮& ⋮& & \ddots & \\ 1& x_N-x_0& \dots & \dots & \prod _{n=0}^{N-1}(x_N-x_n)\end{array}\right)\left(\begin{array}{c}{a}_0\\ ⋮\\ a_N\end{array}\right)=\left(\begin{array}{c}{y}_0\\ ⋮\\ y_N\end{array}\right)$

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}n=0,...,N$

Interpolation polynomial in Newton form

Given a set of N+1 data points

$(x_0,y_0),\dots ,(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}n=0,\dots ,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,\dots ,y_n]$

where

$[y_0,\dots ,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)+\dots +[y_0,\dots ,y_N](x-x_0)\dots (x-x_{N-1})$

Divided differences

The notion of divided differences is a recursive division process.

We define

$[y_{\nu }]:=y_{\nu }\text{ , }\nu =0,\dots ,n$

$[y_{\nu },\dots ,y_{\nu +j}]:=\frac{[y_{\nu +1},\dots y_{\nu +j}]-[y_{\nu },\dots y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }}\text{ , }\nu =0,\dots ,n-j,j=1,\dots ,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{array}{ccccc}{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{array}$

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