01. Lagrange Interpolation

Polynomials of Degree

Polynomials of Degree less than or equal to $n$ is

$${\Pi }_n=\{\text{real polynomials of degree}\le n\}$$

Link to original

Polynomials Interpolating Data

Given data $f_i$ at distinct $x_i$ for $i=0,1,\cdots n$ with $x_0<x_1<\cdots <x_n$ then

Polynomial $p_n$ interpolates the data if

$$p_n(x_i)=f_i$$

Link to original

Lagrange Basis Polynomial

Let $x_0<x_1<\cdots <x_m$
For $k=0,1,\cdots ,n$

Cardinal polynomial is defined as

$$L_{n,k}(x)=\frac{(x-x_0)\cdots (x-x_{k-1})(x-x_{k+1})\cdots (x-x_n)}{(x_k-x_0)\cdots (x_k-x_{k-1})(x_k-x_{k+1})\cdots (x_k-x_n)}\in {\Pi }_n$$

where $L_{n,k}(x_i)={\delta }_{ik}$

Link to original

Existence of Interpolating Polynomials

For any Polynomials interpolating data then

$$\exists p_n\in {\Pi }_n\text{ such that }{p}_n(x_i)=f_i\text{ for }i=0,1,\cdots n$$

Proof

Consider for $k=0,1,\cdots ,n$ the cardinal polynomial

$$L_{n,k}(x)=\frac{(x-x_0)\cdots (x-x_{k-1})(x-x_{k+1})\cdots (x-x_n)}{(x_k-x_0)\cdots (x_k-x_{k-1})(x_k-x_{k+1})\cdots (x_k-x_n)}\in {\Pi }_n$$

Then

$$L_{n,k}={\delta }_{ik}$$

as $L_{n,k}(x_i)=0$ for $i=0,\cdots ,k-1,k+1,\cdots ,n$ and $L_{n,k}(x_k)=1$
So $L_{n,k}(x_i)={\delta }_{ik}$

Thus define Lagrange Interpolating Polynomial

$$p_n(x)=\sum _{k=0}^n{f}_k{L}_{n,k}(x)\in {\Pi }_n$$

Hence

$$p_n(x_i)=\sum _{k=0}^n{f}_k{L}_{n,k}(x_i)=f_i\text{ for }i=0,1,\cdots ,n$$

Lagrange Interpolating Polynomial

$$p_n(x)=\sum _{k=0}^n{f}_k{L}_{n,k}(x)\in {\Pi }_n$$

Link to original

Uniqueness of Interpolating Polynomial

Interpolating Polynomial of Degree $\le n$ is unique

Proof

Consider two interpolating polynomials $p_n,q_n\in {\Pi }_n$

Consider difference $d_n=p_n-q_n\in {\Pi }_n$ then

$$d_n(x_k)=0\text{ for }k=0,1,\cdots ,n$$

As $d_n$ is a polynomial of degree at most $n$ but it has at least $n+1$ roots

By the Fundamental Theorem of Algebra then

$$d_n\equiv 0⟹p_n=q_n$$

Link to original

Lagrange Interpolating Polynomial for Smooth Function

Let $f(x)$ have at least $n+1$ smooth derivatives in interval $(x_0,x_n)$
Let $f_k=f(x_k)$ for $k=0,1,\cdots ,n$ then

Exists Lagrange Interpolating Polynomial $p_n$ for data $(x_k,f_k)$ for $k=0,1,\cdots ,n$

Link to original

Error Formula for Polynomial Interpolation

Let $f$ be $(n+1)$-times continuously differentiable on interval
Let $p_n$ be the polynomial interpolant at $\{x_i{\}}_{i=0}^n$

For every $x\in [x_0,x_n]$ there exists $\xi =\xi (x)\in (x_0,x_n)$ such that

$$e(x)\equiv f(x)-p_n(x)=(x-x_0)(x-x_1)\cdots (x-x_n)\frac{f^{n+1}(\xi )}{(n+1)!}$$

where $f^{(n+1)}$ is the $(n+1)$st derivative of $f$

Proof

For $x=x_k$ where $k=0,1,\cdots ,n$ then

$$e(x)=0$$

by definition

Otherwise suppose $x\ne x_k$

Let

$$\varphi (t)\equiv e(t)-\frac{e(x)}{\pi (x)}\pi (t)$$

where

$$\begin{array}{rl}\pi (t)& \equiv (t-x_0)(t-x_1)\cdots (t-x_n)\\ & =t^{n+1}-\left(\sum _{i=0}^n{x}_i\right)t^n+\cdots +(-1{)}^{n+1}{x}_0{x}_1\cdots x_n\\ & \in {\Pi }_{n+1}\end{array}$$

As

$$\varphi (t)=0\text{ at }(n+2)\text{ points }\text{ where }t=x_0\text{ and }t=x_k\text{ for }k=0,1,\cdots ,n$$

Then

$${\varphi }^{\prime }(t)=0\text{ at }(n+1)\text{ points }\text{ for }t={\xi }_k\text{ for }k=0,\cdots ,n$$

Then

$${\varphi }^{\prime \prime }(t)=0\text{ at }n\text{ points }\text{ for }t={\overline{\xi }}_k\text{ for }k=0,\cdots ,n-1$$

Hence

$$\exists \xi \in (x_0,x_n)\text{ such that }{\varphi }^{(n+1)}(\xi )=0$$

However

$${\varphi }^{(n+1)}(t)=e^{(n+1)}(t)-\frac{e(x)}{\pi (x)}{\pi }^{(n+1)}(t)=f^{(n+1)}(t)-\frac{e(x)}{\pi (x)}(n+1)!$$

As $p_n^{(n+1)}(t)\equiv 0$ and $\pi (t)$ is a monic polynomial of order $(n+1)$ then result follows

Link to original

Hermite Interpolation Theorem

Exists unique polynomial $p_{2n+1}\in {\Pi }_{2n+1}$ such that

$$p_{2n+1}(x_1)=f_i\text{ and }{p}_{2n+1}^{\prime }(x_i)=g_i$$

for $i=0,1,\cdots ,n$

Proof - Construction

Let $L_{n,k}(x)$ be the Lagrange basis polynomial then

Let

$$\begin{array}{rl}{H}_{n,k}(x)& =[L_{n,k}(x){]}^2(1-2(x-x_k)L_{n,k}^{\prime }(x_k))\\ K_{n,k}(x)& =[L_{n,k}(x){]}^2(x-x)k\end{array}$$

where

$$\begin{array}{rlrlrl}{H}_{n,k}(x_i)& ={\delta }_{ik}& & \text{ and }{H}_{n,k}^{\prime }(x_i)& & =0\\ K_{n,k}(x_i)& =0& & \text{ and }{K}_{n,k}^{\prime }(x_i)& & ={\delta }_{ik}\end{array}$$

Then

$$p_{2n+1}(x)=\sum _{k=0}^n[f_k{H}_{n,k}(x)+g_k{K}_{n,k}(x)]$$

Hence $p_{2n+1}(x)$ satisfies conditions

Link to original

Error Formula for Hermite Interpolating Polynomials

Let $f$ be a function with at least $2n+2$ smooth derivatives

Let $p_{2n+1}$ be the Hermite Interpolating Polynomial where

$$f_i=f(x_i)\text{ and }{g}_i=f^{\prime }(x_i)$$

Then for all $x\in [x_0,x_n]$, there exists $\xi \in (x_0,x_n)$ such that

$$e(x)\equiv f(x)-p_{2n+1}(x)=[(x-x_0)(x-x_1)\cdots (x-x_n){]}^2\frac{f^{(2n+2)}(\xi )}{(2n+2)!}$$

where $f^{(2n+2)}$ is the $(2n+2)$th derivative of $f$

Link to original

Chebyshev Points

For $i=0,1,\cdots ,n$ then

$$x_i=\cos {\theta }_i\text{ where}{\theta }_i=\frac{(2i+1)\pi }{2(n+1)}$$

where $-1\le x_i\le 1$

Note that the points get more clustered the closer they are to $\pm 1$

Link to original

Best Polynomial Approximations

Let $f\in C([-1,1])$

For $L_{\infty }$ norm where $||\cdot |{|}_{\infty }$ is defined by $||f|{|}_{\infty }={\sup }_{x\in [-1,1]}|f|$ then

There exists $p_n^{\ast }$ such that

$$||f-p_n^{\ast }|{|}_{\infty }=\underset{p_n\in {\Pi }_n}{\min }||f-p_n|{|}_{\infty }$$

Link to original

Lebesgue Constant

Let ${\mathcal{L}}_n$ be interpolation operator that outputs interpolant $p_n$ given $f$ so

$${\mathcal{L}}_{n}f=p_n$$

where ${\mathcal{L}}_n$ is well-defined once $\{x_i{\}}_{i=0}^n$ is chosen

Lebesgue Constant ${\Lambda }_n$ is defined as

$${\Lambda }_n=\underset{f\in C([-1,1])}{\sup }\frac{||{\mathcal{L}}_{n}f|{|}_{\infty }}{||f|{|}_{\infty }}\left(=\underset{f\in C([-1,1])}{\sup }\frac{||p_n|{|}_{\infty }}{||f|{|}_{\infty }}\right)$$

Link to original

Lebesgue Inequality

Let $f$ be continuous with $f\in C([-1,1])$

Let $p_n$ be the polynomial interpolant of $f$ at $\{x_i{\}}_{i=0}^n$
Let ${\Lambda }_n$ be the Lebesgue Constant then

$$||f-p_n|{|}_{\infty }\le ({\Lambda }_n+1)||f-p_n^{\ast }|{|}_{\infty }$$

Proof

$$||f-p_n|{|}_{\infty }\le ||f-p_n^{\ast }|{|}_{\infty }+||p_n^{\ast }-p_n|{|}_{\infty }$$

As

$$p_n^{\ast }-p_n={\mathcal{L}}_n(p_n^{\ast }-p_n)={\mathcal{L}}_n(p_n^{\ast }-f)$$

since $p_n^{\ast }-p_n\in {\Pi }_n$ thus $L_n(p_n^{\ast }-p_n)=p_n^{\ast }-p_n$
Hence

$$||p_n^{\ast }-p_n|{|}_{\infty }\le ||{\mathcal{L}}_n(p_n^{\ast }-f)||\le {\Lambda }_n||f-p_n^{\ast }|{|}_{\infty }$$

Hence result follows

Link to original

Association of Lebesgue Function with Lagrange Basis Polynomials

Lebesgue Constant can be characterised using Lagrange Basis Polynomials by

$${\Lambda }_n=\underset{x\in [-1,1]}{\max }\sum _{k=0}^n|L_{n,k}(x)|$$

where

$$\sum _{k=0}^n|L_{n,k}(x)|$$

is the Lebesgue function associated with set of interpolation points $\{x_i{\}}_{i=0}^n$

Link to original