Home > Mathematics > Interpolation > Newton’s interpolation polynomial

Newton’s interpolation polynomial

Wednesday 4 July 2007, by Astozzia, Nadir SOUALEM

Keywords: interpolation , Newton , polynôme d’interpolation .

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 $\{(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 , 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 was:

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

where the ’s are polynomials of degree 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, , 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:

Moreover

$\begin{array}{rcl} e_1&=&(x-x_0)\\ e_2&=&(x-x_0)(x-x_1)\\ e_3&=&(x-x_0)(x-x_1)(x-x_2)\\ \vdots&&\vdots\\ e_n&=&(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \end{array}$

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 . Indeed, they constitute an echelon-degree set of polynomials.
Newton’s interpolation polynomial of degree related to the subdivision $\{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)\}$ is:

$\begin{array}{rcl} 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)\\ &&+\ldots +\alpha_n(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \end{array}$

where

$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 , , evaluated at , 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$

is called a zero-order divided difference.

Newton’s interpolation polynomial of degree , , evaluated at , gives:

$\begin{array}{lll} 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_1] \end{array}$

Hence

$\alpha_1=\frac{f[x_1]-f[x_0]}{x_1-x_0}=f[x_0,x_1]$

is called $1^{st}$ -order divided difference.

Newton’s interpolation polynomial of degree , , evaluated at , gives:

$\begin{array}{rcl} 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) \\ &=&f[x_2] \end{array}$

Therefore:

$\begin{array}{rcl} \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)}\\ \alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0]}{(x_2-x_0)(x_2-x_1)}- \frac{f[x_0,x_1]}{x_2-x_1}\\ \alpha_2&=&\displaystyle\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1} \end{array}$

The following form is generally preferred:

$\begin{array}{rcl} \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)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_0)f[x_0,x_1] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_2)f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&\displaystyle\frac{f[x_2]-f[x_1]}{x_2-x_1}-f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&f[x_1,x_2]-f[x_0,x_1] \end{array}$

Hence

$\alpha_2=\displaystyle\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=f[x_0,x_1,x_2]$

is called $2^{nd}$ -order divided difference.
By recurrence, we obtain:

$\alpha_k=\displaystyle\frac{f[x_1,\ldots,x_k]- f[x_0,\ldots,x_{k-1}]}{x_k-x_0}=f[x_0,\ldots,x_k]$

$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
for instance, we need the following quantities

$\left[\begin{array}{ccccc} 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] \end{array}\right]$

Hence

$f[x_0,x_1,x_2,x_3]=\displaystyle\frac{f[x_1,x_2,x_3]- f[x_0,x_1,x_{2}]}{x_3-x_0}$

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

$f[x_{\sigma(0)},\ldots,x_{\sigma(n)}]=f[x_0,\ldots,x_{n}].$

Newton’s interpolation polynomial of degree

Newton’s interpolation polynomial of degree 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 be the closed set defined by $I=[\min(x,x_0),\max(x,x_n)]$ (the smallest closed set containing and the ’s).

Theorem.

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

Proof. Let 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 ( times), $d^{(n)}(x)$ equals zero at a given point $\xi\in I$ :

$d^{(n)}(\xi)=0.$

Therefore, we have:

$f^{(n)}(\xi)=P_n^{(n)}(\xi)$

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

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

hence

$f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{(n)}(\xi)}{n!}$

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

Theorem.

$\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 , 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 which interpolates 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

$\left\{\begin{array}{rcl} P_{n+1}(x_i)&=&f(x_i),\quad\forall i=0,\ldots,n \\ P_{n+1}(\hat{x})&=&f(\hat{x}). \end{array}\right.$

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

$P_{n+1}(x)=P_{n}(x)+(x-x_0)\ldots(x-x_n)f[x_0,\ldots,x_{n},\hat{x}]$

According to the previous theorem

$f[x_0,\ldots,x_{n},\hat{x}]=\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}$

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

$f(\hat{x})=P_{n}(\hat{x})+(\hat{x}-x_0)\ldots(\hat{x}-x_n)\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}$

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.

$\left[\begin{array}{ccccc} 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]= \displaystyle\frac{6-2}{4-0}=1 & \end{array}\right]$

Consequently:

$\begin{array}{rcl} P_2(x)&=&f[x_0]+f[x_0,x_1]x+f[x_0,x_1,x_2]x(x-2)\\ &=&1+2x+x(x-2)\\ &=&1+x^2 \end{array}$

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

Any message or comments?

Forum registration required

You must be registered before participating in this forum. Please enter your personal identifier . If you have not yet registered, you must register.

Connection | register | password forgotten?

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Links

Newton’s interpolation polynomial

Interpolation

Reminders about Lagrange interpolation polynomials

Newton’s interpolation polynomial and Newton’s basis properties

Divided differences

Newton’s interpolation polynomial of degree

Error of interpolation

An example of computing Newton’s interpolation polynomial

Scilab: computing Newton’s interpolation polynomial

Any message or comments?

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Mathematics

Also in this section

Keywords