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} \dfrac{x-x_i}{x_k-x_i}=\dfrac{x-x_0}{x_k-x_0} \cdots \dfrac{x-x_{k-1}}{x_k-x_{k-1}} \dfrac{x-x_{k+1}}{x_k-x_{k+1}} \cdots \dfrac{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->article46] 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)}{(0-2)(0-4)}=\displaystyle\frac{(x-2)(x-4)}{8}\)

\[l_1(x)=\displaystyle\frac{x(x-4)}{(2-0)(2-4)}=-\displaystyle\frac{x(x-4)}{4}\] \[l_2(x)=\displaystyle\frac{x(x-2)}{(4-0)(4-2)}=\displaystyle\frac{x(x-2)}{8}\]

Lagrange interpolation polynomial is:

\[\begin{array}{rcl} P_2(x)&=&1l_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

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