Home > Mathematics > Interpolation > Newton’s interpolation polynomial

Newton’s interpolation polynomial

Wednesday 4 July 2007, by Astozzia, Nadir SOUALEM

Keywords: , , .

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 (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:

e_0=1

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 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:


\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 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:


\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]

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:


\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]

f[x_0,x_1,x_2] is called2^{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
f[x_0,x_1,x_2,x_3] 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 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).

Theorem.

\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:

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

Therefore, we have:

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

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}]

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

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 x=x_i, the problem is over!

f(x)-P_n(x)=f(x_i)-P_n(x_i)=0.

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

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

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

Forum posts

Any message or comments?

pre-moderation

This forum is moderated before publication: your contribution will only appear after being validated by an administrator.

Who are you?
Your post
  • To create paragraphs, just leave blank lines.

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

Links