Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Interpolation > Newton’s interpolation polynomial

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 (n+1) points \{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)\}, the points defined by (x_i)_{0 \leq i\leq n} are called points of interpolation. The points defined by (y_i)_{0 \leq i\leq n} are the values of interpolation. To interpolate a function f, the values of interpolation are defined as follows:

y_i=f(x_i), \quad \forall i=0,\ldots,n

Reminders about Lagrange interpolation polynomials

We have seen that Lagrange interpolation polynomial of degree n was:

P_n(x)= \sum_{k=0}^n l_k(x)f(x_k)

where the l_k’s are polynomials of degree n forming a basis of \mathcal{P}_n

l_k(x)= \prod_{i=0,\, i\neq k}^{n} \frac{x-x_i}{x_k-x_i}=\frac{x-x_0}{x_k-x_0} \cdots \frac{x-x_{k-1}}{x_k-x_{k-1}} \frac{x-x_{k+1}}{x_k-x_{k+1}} \cdots \frac{x-x_{n}}{x_k-x_{n}}

Such polynomials are not convenient, since numerically, it is difficult to deduce l_{k+1} from l_{k}. For this reason, we introduce Newton’s interpolation polynomial.

Newton’s interpolation polynomial and Newton’s basis properties

- The polynomials of Newton’s basis, e_k, are defined by:

e_k(x)=\prod_{i=0}^{k-1}(x-x_i)=(x-x_0) (x-x_1)\cdots(x-x_{k-1}),\quad k=1,\ldots,n.

with the following convention:




- The set of polynomials (e_k)_{0 \leq k\leq n}(Newton’s basis) are a basis of \mathcal{P}_n, the space of polynomials of degree at most equal to n. Indeed, they constitute an echelon-degree set of (n+1) polynomials.
- Newton’s interpolation polynomial of degree n related to the subdivision \{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)\} is:

P_n(x)&=&\displaystyle\sum_{k=0}^n \alpha_k e_k(x)\\
&=& \alpha_0 + \alpha_1(x-x_0)+\alpha_2(x-x_0)(x-x_1)\\


P_n(x_i)=f(x_i),\quad \forall i=0,\ldots,n.

We shall see how to determine the coefficients (\alpha_k)_{0 \leq k\leq n} in the following section entitled the divided differences.

Divided differences

Newton’s interpolation polynomial of degree n, P_n(x), evaluated at x_0, gives:

P_n(x_0)= \sum_{k=0}^n \alpha_k e_k(x_0)=\alpha_0=f(x_0)=f[x_0]

Generally speaking, we write:

f[x_i]=f(x_i), \quad \forall i=0,\ldots,n

f[x_0] is called a zero-order divided difference.

Newton’s interpolation polynomial of degree n, P_n(x), evaluated at x_1, gives:

P_n(x_1)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_1)\\
&=&\alpha_0 + \alpha_1(x_1-x_0)\\
&=&f[x_0] + \alpha_1(x_1-x_0)\\



f[x_0,x_1] is called 1^{st}-order divided difference.

Newton’s interpolation polynomial of degree n, P_n(x), evaluated at x_2, gives:

P_n(x_2)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_2)\\
&=&\alpha_0 + \alpha_1(x_2-x_0) +\alpha_2(x_2-x_0)(x_2-x_1) \\
&=&f[x_0] + f[x_0,x_1](x_2-x_0)+\alpha_2(x_2-x_0)(x_2-x_1) \\


\alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\
\alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)}{(x_2-x_0)(x_2-x_1)}\\

The following form is generally preferred:

\alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\
\alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)-f[x_1]+f[x_1]\\
\alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+f[x_1]-f[x_0] -f[x_0,x_1](x_2-x_0)\\



f[x_0,x_1,x_2] is called2^{nd}-order divided difference.
By recurrence, we obtain:


f[x_0,\ldots,x_k] is thus called a k^{th}-order divided difference.
In practice, when we want to determine the 3^{rd}-order divided difference
f[x_0,x_1,x_2,x_3] for instance, we need the following quantities

x_0 & f[x_0] &                  & & \cr
x_1 & f[x_1] & f[x_0,x_1] & & \cr
x_2 & f[x_2] & f[x_1,x_2] &  f[x_0,x_1,x_2]  & \cr
x_3 & f[x_3] & f[x_2,x_3] &  f[x_1,x_2,x_3]  & f[x_0,x_1,x_2,x_3]



Properties. Let E=\{0,1,\ldots,n\} and \sigma be a permutation of \mathfrak{S}(E). Then


Newton’s interpolation polynomial of degree n

Newton’s interpolation polynomial of degree n is obtained via the successive divided differences:

P_n(x)= f[x_0] + \sum_{k=1}^n f[x_0,\ldots,x_k] e_k(x)

Error of interpolation

Assume that f\in \mathcal{C}^{n}([a,b]) and x\in[a,b]. Let I be the closed set defined by I=[\min(x,x_0),\max(x,x_n)] (the smallest closed set containing x and the x_i’s).


\exists \xi \in I / f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{n}(\xi)}{n!}

Proof. Let d(x)=f(x)-p(x). We have:

d(x_i)=f(x_i)-P_n(x_i)=0\quad \forall i=0,\ldots,n

By successively applying Rolle’s theorem (n times), d^{(n)}(x) equals zero at a given point \xi\in I:


Therefore, we have:


Since the coefficient of x^n in P_n is f[x_0,\ldots,x_{n}],

f^{(n)}(\xi)=P_n^{(n)}(\xi)=n!\cdot f[x_0,\ldots,x_{n}]



We now assume that f\in \mathcal{C}^{n+1}([a,b]) and x\in[a,b]. Let I be the closed set defined by I=[\min(x,x_0),\max(x,x_n)] (the smallest closed set containing x and the x_i’s).


\forall x\in [a,b],\quad \exists \xi \in I / f(x)-P_n(x)=
\displaystyle\frac{f^{n+1}(\xi)}{(n+1)!} \displaystyle\prod_{i=0}^{n}(x-x_i)

Proof. There are two possible ways: (1) the one encountered in Lagrange polynomial interpolation and (2) the following.

If x=x_i, the problem is over!


Let \hat{x}\in[a,b]and assume that \hat{x}\neq x_i.

Consider the unique polynomial P_{n+1} of degree (n+1) which interpolates f at the points \{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n),(\hat{x},f(\hat{x}))\}. P_{n+1} verifies

P_{n+1}(x_i)&=&f(x_i),\quad\forall i=0,\ldots,n \\

The polynomial P_{n+1} can be written as:


According to the previous theorem


By setting x=\hat{x}, P_{n+1}(\hat{x})=f(\hat{x}),


Since this result is valid regardless of \hat{x}, the case is made!

An example of computing Newton’s interpolation polynomial

Given a set of 3 data points \{(0,1), (2,5),(4,17)\}, we shall determine Newton’s interpolation polynomial of degree 2 which passes through these points.

x_0=0 & f[x_0]=1  &                  & & \cr
x_1=2 & f[x_1]=5   & f[x_0,x_1]=\displaystyle\frac{5-1}{2-0} = 2& & \cr
x_2=4 & f[x_2]=17 & f[x_1,x_2]=\displaystyle\frac{17-5}{4-2}=6  &  f[x_0,x_1,x_2]=



Scilab: computing Newton’s interpolation polynomial

Scilab function newton.sci determines Newton’s interpolation polynomial. X contains the points of interpolation and Y the values of interpolation. P is Newton’s interpolation polynomial computed by means of divided differences.sées.


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,
for i=2:n, P=P*(x-X(i))+Y(i,n-i+1); end

Therefore, we obtain:

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

Any message or comments?

comments powered by Disqus