# Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Interpolation > Newtonâ€™s interpolation polynomial

## Newtonâ€™s interpolation polynomial

In this section, we shall study the polynomial interpolation in the form of Newton. Given a sequence of (n+1) data points and a function f, the aim is to determine an n-th degreee polynomial which interpolates f at these points. We shall resort to the notion of divided differences.

{{{Interpolation}}} Given points , the points defined by are called {{points of interpolation}}. The points defined by are the {{values of interpolation}}. To interpolate a function , the values of interpolation are defined as follows:

{{{Reminders about Lagrange interpolation polynomials}}} We have seen that [Lagrange interpolation polynomial->article71] of degree was:

where the 's are polynomials of degree forming a basis of

Such polynomials are not convenient, since numerically, it is difficult to deduce from . For this reason, we introduce Newton's interpolation polynomial. {{{Newton's interpolation polynomial and Newton's basis properties}}} - The polynomials of Newton's basis, , are defined by:

with the following convention:

Moreover

- The set of polynomials (Newton's basis) are a basis of , the space of polynomials of degree at most equal to . Indeed, they constitute an echelon-degree set of polynomials. - Newton's interpolation polynomial of degree related to the subdivision is:

where

We shall see how to determine the coefficients in the following section entitled the {{divided differences}}. {{{Divided differences}}} Newton's interpolation polynomial of degree , , evaluated at , gives:

Generally speaking, we write:

is called a zero-order {{divided difference}}. Newton's interpolation polynomial of degree , , evaluated at , gives:

Hence

is called -{{order divided difference}}. Newton's interpolation polynomial of degree , , evaluated at , gives:

Therefore:

The following form is generally preferred:

Hence

is called-{{order divided difference}}. By recurrence, we obtain:

is thus called a -{{order divided difference}}. In practice, when we want to determine the -order divided difference for instance, we need the following quantities

Hence

{{Properties.}} Let and be a permutation of . Then

{{{Newton's interpolation polynomial of degree }}} Newton's interpolation polynomial of degree is obtained via the successive divided differences:

{{{Error of interpolation}}} Assume that and . Let be the closed set defined by (the smallest closed set containing and the 's). {{Theorem.}}

{{Proof.}} Let We have:

By successively applying Rolle's theorem ( times), equals zero at a given point :

Therefore, we have:

Since the coefficient of in is ,

hence

We now assume that and . Let be the closed set defined by (the smallest closed set containing and the 's). {{Theorem.}}

{{Proof.}} There are two possible ways: (1) the one encountered in [Lagrange polynomial interpolation->article71] and (2) the following. If , the problem is over!

Let and assume that . Consider the unique polynomial of degree which interpolates at the points . verifies

The polynomial can be written as:

According to the previous theorem

By setting , ,

Since this result is valid regardless of , the case is made! {{{An example of computing Newton's interpolation polynomial}}} Given a set of 3 data points , we shall determine Newton's interpolation polynomial of degree 2 which passes through these points.

Consequently:

{{{Scilab: computing Newton's interpolation polynomial}}} Scilab function newton.sci determines Newton's interpolation polynomial. contains the points of interpolation and the values of interpolation. is Newton's interpolation polynomial computed by means of divided differences.sées. {{newton.sci}}

function[P]=newton(X,Y)//X nodes,Y values;P is the numerical Newton polynomial
n=length(X);// n is the number of nodes. (n-1) is the degree
for j=2:n,
for i=1:n-j+1,Y(i,j)=(Y(i+1,j-1)-Y(i,j-1))/(X(i+j-1)-X(i));end,
end,
x=poly(0,"x");
P=Y(1,n);
for i=2:n, P=P*(x-X(i))+Y(i,n-i+1); end
endfunction;

Therefore, we obtain:

-->X=[0;2;4]; Y=[1;5;17]; P=newton(X,Y)
P = 1 + x^2