# 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 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 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