Lagrange interpolation polynomial

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

We thus have:

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

1 Message

Sections

In the same section