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 (n+1) 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 f, 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 n, P_n 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 l_k are polynomials of degree n 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 l_k 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 n

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

By setting: x=x_i, 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 n+1 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 P_n and Q_n 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 R_n has (n+1) 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.

R_n has then (n+1) 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 I be the closed set defined by I=[\min(x,x_0),\max(x,x_n)] (the smallest closed set containing x 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 x=x_i, the problem is over:

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

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:

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

g(x,\cdot) is (n+1) times differentiable and evaluates to zero at the (n+2) points x_0,x_1,\ldots,x_n,x of the interval I. 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 l_0,l_1 and l_2:

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. X encompasses the points of interpolation and Y the values of interpolation. P is the Lagrange interpolation polynomial.

lagrange.sci

We thus have:

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