Lagrange Interpolation

Lagrange interpolation forms a continuous function by fitting the lowest order polynomial to a set of points

How do we do this in practice?

Say we’re given points $(x_i,f_i)$ for $i\in [1,n]$
We have a system of linear equations $f_i=a_0+a_1{x}_i+\cdots +a_n{x}_i^n$

We should be able to use our previous methods as long as none of the points are equal

However, this method is actually problematic because it turns out the matrix is ill defined as $n$ grows and behaves badly with our more sophisticated methods

Gaussian elimination is slow and behaves poorly here due to rounding errors

An alternative solution method constructs the polynomial directly

Define $L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$
$L_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_2-x_1)}$
$L_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$

This means,
$L_i(x_j)=\{\begin{array}{ll}0& \text{if }i\ne j\\ 1& \text{if }i=j\end{array}$

So our required polynomial is $p(x)=f_0{L}_0(x)+f_1{L}_1(x)+f_2{L}_2(x)$

The general problem stated clearly in our notation is given points $(x_0,f_0),(x_1,f_1),\dots ,(x_n,f_n)$ with distinct $x_i$, determine a polynomial $p$ satisfying $\text{deg}(p)\le n$ and $p(x_i)=f_i$

Is there always a unique solution? It turns out yes

Lemma: There exists $L_k\in {\mathcal{P}}_n$ for $k=0,1,\dots ,n$ such that $L_k(x_i)=0$ if $i\ne k$ and $1$ if $i=k$ for all $i,k$, where the $x_i$ are assumed to be distinct. Furthermore, $p_n(x)={\sum }_{k=0}^n{f}_k{L}_k(x)$ satisfies $p_n(x_i)=f_i$ for $i=0,1,\dots ,n$.

$L_k(x)={\prod }_{j\ne k}^{}\frac{x-x_j}{x_k-x_j}$
Trivially, this satisfies our conditions

Furthermore, this polynomial $p_n$ is unique

Suppose $q_n\in {\mathcal{P}}_n$ also satisfies $q_n(x_i)=f_i$
Therefore, $p_n-q_n\in {\mathcal{P}}_n$ and $p_n(x_i)-q_n(x_i)=0$

This is a polynomial of degree $\le n$ with $n+1$ distinct roots, which implies it must be the zero function, i.e. $p_n=q_n$

Definition: We call $p_n(x)$ constructed above the Lagrange interpolation polynomial of degree n

Now what if we want to approximate a function $f$ with this scheme by fitting to sampled points?

Theorem: Suppose $n\ge 1$ and that $f\in C^{n+1}([a,b])$. Let $p_n(x)$ be the Lagrange interpolation polynomial of degree $n$ with interpolation points $x_0,x_1,\dots ,x_n$ for $f$. Then for $x\in [a,b]$, we can write $e_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}{\pi }_{n+1}(x)$ for some $\xi \in (a,b)$ where ${\pi }_{n+1}(x)=(x-x_0)\dots (x-x_n)$.

As a corollary, $|f(x)-p_n(x)|\le \frac{M_{n+1}}{(n+1)!}|{\pi }_{n+1}(x)|$ where $M_{n+1}={\max }_{\zeta \in [a,b]}|f^{(n+1)}(\zeta )|$

When we place the points regularly, we run into pathological cases where both the derivatives grow with $n$ and ${\pi }_{n+1}$ grows with $n$ at the edges of our domain

However we can place points more cleverly using Chebyshev nodes