Newton Polynomial

As there is only one interpolation polynomial for a given set of data points it is a bit misleading to call the polynomial Newton interpolation polynomial. The more precise name is interpolation polynomial in the Newton form.

DEFINITION

Given a set of ''k''+1 data points
:

(x_0, y_0),\ldots,(x_k, y_k)

where no two ''x''_''j'' are the same, the interpolation polynomial in the Newton form is Linear Combination of Newton basis polynomials

:

N(x) := \sum_{j=0}^{k} a_{j} n_{j}(x)

with the Newton basis polynomials defined as

:

n_j(x) := \prod_{i=0}^{j-1} (x - x_i)

and the coefficients defined as
:

a_j :=

{Link without Title}

where
:

{Link without Title}

is the notation for Divided Differences .

Thus the Newton polynomial can be written as

:

(x-x_0) + \cdots + [y_0,\ldots,y_k](x-x_0)\cdots(x-x_{k-1})

GENERAL CASE

For the special case of

x_i=i

, there is a closely related set of polynomials, also called the Newton polynomials, that are simply the Binomial Coefficient s for general argument. That is, one also has the Newton polynomials

p_n(z)

given by

:

p_n(z)={z \choose n}= rac{z(z-1)\cdots(z-n+1)}{n!}

In this form, the Newton polynomials generate the Newton Series . These are in turn a special case of the general Difference Polynomials which allow the representation of Analytic Function s through generalized difference equations.

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 be solved faster.

For ''k''+1 data points we construct the Newton basis as
:

n_j(x) := \prod_{i=0}^{j-1} (x - x_i) \qquad j=0,\ldots,k

Using these polynomials as a basis for

\Pi_k

we have to solve
:

\begin{bmatrix}
      1 &         &        &        & 0  \
      1 & x_1-x_0 &        &        &    \
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        &    \
 dots & dots  &        & \ddots &    \
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{k-1}(x_k - x_j)
\end{bmatrix}
\begin{bmatrix}
     a_0 \
     dots \
     a_{k} 
\end{bmatrix}
=
\begin{bmatrix}
     y_0 \
     dots \
     y_{k}
\end{bmatrix}

to solve the polynomial interpolation problem.

This matrix can be solved recursively by solving
:

\sum_{i=0}^{j} a_{i} n_{i}(x_j) = y_j \qquad j = 0,...,k

APPLICATION

As can be seen from the definition of the divided differences new data points can be added to the data set to create a new interpolation polynomial without recalculation the old coefficients. And when a data point changes we usually do not have to recalculate all coefficients. Furthermore if the ''x''_''i'' are distributed equidistantly the calculation of the divided differences becomes significantly easier. Therefore the Newton form of the interpolation polynomial is usually preferred over the Lagrange Form for practical purposes.

Example

The divided differences can be written in the form of a table. For example, for a function

f

is to be interpolated on points

x_0, \ldots, x_n

. Write
:

\begin{matrix}

x_0 & f(x_0) & & \
& & {f(x_1)-f(x_0)\over x_1 - x_0} & \

{ Cellpadding

10px

	CATEGORIES ABOUT NEWTON POLYNOMIAL

	interpolation

	finite differences

	factorial and binomial topics

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Newton Polynomial