User:MathMartin/Newton polynomial

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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

[edit] 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 xn 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})

[edit] 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 [yn] this yields

[y0] = y0
[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

a0 = y0
a1 = [y0,y1]
a2 = [y0,y1,y2]
a3 = [y0,y1,y2,y3]

[edit] See also

Retrieved from "http://en.wikipedia.org../../../m/a/t/User%7EMathMartin_Newton_polynomial_df3a.html"