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.

{{{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
```