Newton's interpolation polynomial

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

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

Therefore, we obtain:

Newton’s interpolation polynomial

Keywords:

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

Sections

In the same section

Keywords