Home > Mathematics > Interpolation > Lagrange interpolation polynomial

Lagrange interpolation polynomial

Monday 25 June 2007, by Astozzia, Nadir SOUALEM

All the versions of this article: [English] [français]

In this section, we shall study the interpolation polynomial in the Lagrange form. Given a set of (n+1) data points and a function f, the aim is to determine a polynomial of degree n which interpolates f at the points in question.

Interpolation

Given a set of data 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 $(y_i)_{0 \leq i\leq n}$ are the values of interpolation. To interpolate a function , we define the values of interpolation as follows:

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

Lagrange interpolation polynomial

The purpose here is to determine the unique polynomial of degree , which verifies

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

The polynomial which meets this equality is Lagrange interpolation polynomial

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

where are polynomials of degree that form 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}}$

Properties of Lagrange interpolation polynomial and Lagrange basis

They are the polynomials which verify the following property:

$l_k(x_i) = \delta_{ki}=\left\{\begin{array}{ll} 1 & i=k \\ 0 & i\neq k \\ \end{array} \right.,\quad \forall i=0,\ldots,n.$

They form a basis of the vector space $\mathcal{P}_n$ of polynomials of degree at most equal to

$\sum_{k=0}^n \alpha_k l_k(x)=0$

By setting: , we obtain:

$\sum_{k=0}^n \alpha_k l_k(x_i)=\sum_{k=0}^n \alpha_k \delta_{ki}=0\Longrightarrow\alpha_i=0$

The set $(l_k)_{0 \leq k\leq n}$ is linearly independent and consists of vectors. It is thus a basis of $\mathcal{P}_n$ .
Finally, we can easily see that:

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

Existence and uniqueness of Lagrange interpolation polynomials

Existence.
The proof is shown above. Actually, it corresponds to the construction of Lagrange interpolation polynomial with regard to the basis $(l_k)_{0 \leq k\leq n}$
of $\mathcal{P}_n$ .

Uniqueness. Consider two elements and of $\mathcal{P}_n$ which verify

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

Let $R_n=(P_n-Q_n)\in \mathcal{P}_n$ . The polynomial has roots which are exactly the $(x_i)_{0 \leq i\leq n}$ since

$R_n(x_i)=P_n(x_i)-Q_n(x_i)=f(x_i)-f(x_i)=0,\quad \forall i=0,\ldots,n.$

has then roots and $R_n\in \mathcal{P}_n$ . Therefore,

$R_n=0 \Longrightarrow P_n=Q_n.$

We have thus shown the existence and uniqueness of Lagrange interpolation polynomial.

Error in Lagrange interpolation

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 $x_i,~\forall~i$ ).

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 to prove this theorem: 1) the one encountered in The polynomial interpolation in the form of Newton and, 2) the following proof.

If , the problem is over:

Now, assume that $x\neq x_i$ and let us define the application $\Phi$ as follows:

$\Phi(x)=\displaystyle\frac{f(x)-P_n(x)}{\displaystyle\prod_{i=0}^{n}(x-x_i)}.$

We also define the application :

$g(x,t)=f(t)-P_n(t)-\displaystyle\prod_{i=0}^{n}(t-x_i)\Phi(x)$

$g(x,\cdot)$ is times differentiable and evaluates to zero at the points $x_0,x_1,\ldots,x_n,x$ of the interval . By successively applying Rolle’s theorem, $g^{(n+1)}(x,\cdot)$ evaluates to zero at a point $\xi\in I$ :

$g^{(n+1)}(x,\xi)=0$

The $(n+1)^{th}$ derivative of $g(x,\cdot)$ can be easily calculated:

$g^{(n+1)}(x,t)=f^{(n+1)}(t)-(n+1)!\Phi(x)$

By setting $t=\xi$ , we have:

$g^{(n+1)}(x,\xi)=f^{(n+1)}(\xi)-(n+1)!\Phi(x)=0$

Therefore

$\Phi(x)=\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}$

We finally conclude that

$f(x)-P_n(x)= \displaystyle\frac{f^{n+1}(\xi)}{(n+1)!} \displaystyle\prod_{i=0}^{n}(x-x_i)$

Corollary.
Assume that $f\in \mathcal{C}^{n+1}([a,b])$ and $x\in[a,b]$ .

$\forall x\in [a,b],\quad |f(x)-P_n(x)|\leq \displaystyle\frac{\displaystyle|\prod_{i=0}^{n}(x-x_i)|}{(n+1)!}\sup_{x\in[a,b]}|f^{n+1} (x)|$

Alternatively stated:

$\forall x\in [a,b],\quad |f(x)-P_n(x)|\leq \displaystyle\frac{(b-a)^{n+1}}{(n+1)!}\sup_{x\in[a,b]}|f^{n+1} (x)|$

Example: computing Lagrange interpolation polynomials

Given a set of three data points $\{(0,1), (2,5),(4,17)\}$ , we shall determine the Lagrange interpolation polynomial of degree 2 which passes through these points.

First, we compute and :

$l_0(x)=\displaystyle\frac{(x-2)(x-4)}{8},l_1(x)=-\displaystyle\frac{x(x-4)}{4},l_2(x)=\displaystyle\frac{x(x-2)}{8}$

Lagrange interpolation polynomial is:

$\begin{array}{rcl} P_2(x)&=&l_0(x)+5l_1(x)+17l_2(x)\\ &=&1+x^2 \end{array}$

Scilab: computing Lagrange interpolation polynomial

The Scilab function lagrange.sci determines Lagrange interpolation polynomial. encompasses the points of interpolation and the values of interpolation. is the Lagrange interpolation polynomial.

lagrange.sci

function[P]=lagrange(X,Y)//X nodes,Y values;P is the numerical Lagrange polynomial interpolation
n=length(X);// n is the number of nodes. (n-1) is the degree
x=poly(0,"x");P=0;
for i=1:n, L=1;
  for j=[1:i-1,i+1:n] L=L*(x-X(j))/(X(i)-X(j));end
  P=P+L*Y(i); 
end
endfunction

We thus have:

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

Any message or comments?

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

Links

Lagrange interpolation polynomial

Interpolation

Lagrange interpolation polynomial

Properties of Lagrange interpolation polynomial and Lagrange basis

Existence and uniqueness of Lagrange interpolation polynomials

Error in Lagrange interpolation

Example: computing Lagrange interpolation polynomials

Scilab: computing Lagrange 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