01 - Interpolation

Polynomials of Degree

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

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

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$$

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}$

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$

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$

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)$$

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$