Courses
CA-MATH-804: Numerical Analysis
Interpolation

Interpolation

Numerical treatment of problems often involves the process of discretization - i.e. going from a continuous function to set of discrete points.

Interpolation provides a way of approximating continuous functions by discrete data.

Types of functions which can be used are:

  • Polynomial interpolation : using a polynomial to approximate the data,
  • Trigonometric interpolation: using polynomials of trigonometric functions,
  • Spline interpolation: using a set of piecewise polynomials over subintervals of the data.
Theorem:

Given $n+1$ distinct points $x_0, x_1, \ldots, x_n$ and $n+1$ corresponding values $y_0, y_1, \ldots, y_n$ there exists a unique polynomial $\Pi_n \in \mathbb{P}_n$ such that for all $i=0, \ldots, n$

$$ \begin{equation*} \Pi_n\left( x_i \right) = y_i. \end{equation*} $$

Lagrange Interpolation

Definition: Lagrange Polynomials
$$ \begin{equation*} \Pi_n \left( x\right) = \sum\limits_{i=0}^{n} y_i l_i\left(x\right) \end{equation*} $$$$ \begin{equation*} l_{i} \left( x \right) = \prod \limits_{\substack{j = 0,\newline{}j \ne i}}^{n} \dfrac{x - x_j}{x_i - x_j}. \end{equation*} $$
Example:

An .ipynb notebook illustrating the Lagrange polynomials can be accessed here. It can be downloaded from here.

An .ipynb notebook illustrating Runge phenomenon can be accessed [here]. It can be downloaded from [here].

Theorem:

Let $x_0, x_1, \ldots x_n$ be $n+1$ distinct nodes and let $x$ be a point belonging to the domain of a given function $f$.

$$ \begin{equation*} \begin{aligned} E_n(x) & = f(x) − \Pi_n f (x) \\ & = \dfrac{f^{(n+1)}( \xi ) }{ (n + 1)!} \omega_{n+1}(x) \end{aligned} \tag{1} \end{equation*} $$$$ \begin{equation*} \omega_{n+1}(x) = \prod\limits_{i=0}^{n} \left(x - x_i \right). \end{equation*} $$

Piecewise Lagrange Interpolation

Definition: $\mathrm{L}^2$ Space
$$ \begin{equation*} \mathrm{L}^{2}(a, b) = \bigl \lbrace f : (a, b) \rightarrow \mathbb{R}, \int_{a}^{b} | f(x) |^{2} \, \mathrm{d}x < \infty \bigr \rbrace \end{equation*} $$$$ \begin{equation*} \| f \|^{}_{\mathrm{L}^{2}(a, b)} = \left( \int_{a}^{b} | f(x) |^{2} \, \mathrm{d} x \right)^{1 / 2}. \end{equation*} $$

This defines a norm for $\mathrm{L}^{2}(a, b)$. Note that integral of the function $|f|^{2}$ is in the Lebesgue sense - in particular, $f$ needs not be continuous everywhere.

$$ [a, b] = \bigcup\limits_{j=0}^{K−1}I_j.$$

Let ${h = \max\limits_{0 \le j \le K−1} h_j}$.

$$ \begin{equation*} X_h^k = \bigl\lbrace v \in C^0([a, b]) \, : \, v |_{I_j} \in \mathbb{P}_k \left( I_j \right), \quad \forall \, I_j \in \mathcal{T}_h \bigr\rbrace \tag{2} \end{equation*} $$

which is the space of the continuous functions over the interval $[a, b]$ whose restrictions on each $I_j$ are polynomials of degree less than or equal to $k$.

Then, for any continuous function $f$ in $[a, b]$, the piecewise interpolation polynomial $\Pi^k_h f$ coincides on each $I_j$ with the interpolating polynomial of $\left. f \right|_{I_j}$ at the $n + 1$ nodes $\lbrace x_j^{(i)}, 0 \leq i \leq n \rbrace$.

$$ \begin{equation*} \left\Vert f − \Pi_h^k f \right\Vert_\infty \leq C h^{k+1} \left\Vert f^{(k+1} \right\Vert_\infty . \end{equation*} $$
Theorem:

Partition $\mathcal{T_h}$ of $[a, b]$ into $K$ subintervals $I_j = [x_j , x_{j+1}]$ of length $h_j$, with $h = \max\limits_{0 \le j \le K−1} h_j$, such that $[a, b] = \bigcup\limits_{j=0}^{K−1}I_j$. Now using Lagrange interpolation on each subinterval $I_j$ using $n + 1$ equally spaced nodes $\lbrace{ x^{(i)}_{j}, 0 \le i \le n \rbrace}$ with a small $n$. Then $\Pi_n^k$ is the piecewise interpolation polynomial.

$$ \begin{equation*} \left\| \left( f - \Pi_{h}^{k} f\right)^{(m)} \right\|_{\mathrm{L}^{2}(a, b)} \leq C h^{k+1-m} \left\| f^{(k+1)} \right\|_{\mathrm{L}^{2}(a, b)} . \end{equation*} $$$$ \begin{equation*} \begin{aligned} \left\| f-\Pi_{h}^{1} f \right\|_{\mathrm{L}^{2}(a, b)} & \leq C_{1} h^{2} \left\| f^{\prime \prime} \right\|_{\mathrm{L}^{2}(a, b)} \newline \left\| \left( f - \Pi_{h}^{1} f \right)^{\prime}\right\|_{\mathrm{L}^{2}(a, b)} & \leq C_{2} h\left\| f^{\prime \prime} \right\|_{\mathrm{L}^{2}(a, b)} \end{aligned} \end{equation*} $$

for two suitable positive constants $C_{1}$ and $C_{2}$.