Knowledge base dedicated to Linux and applied mathematics.

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

All the versions of this article: [English] [français]

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.

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:

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.

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**.

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 is obtained via the successive divided differences:

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!

Given a set of 3 data points , we shall determine Newton’s interpolation polynomial of degree 2 which passes through these points.

Consequently:

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