Interpolation
Numerical treatment of problems often involves the process of discretization - i.e. going from a continuous function to set of discrete points.
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.
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
The Lagrange form of an interpolating polynomial is given by
$$ \begin{equation*} \Pi_n \left( x\right) = \sum\limits_{i=0}^{n} y_i l_i\left(x\right) \end{equation*} $$where $l_{i} \in \mathbb{P}_{n}$ is such that $l_{i}\left( x_{j} \right) = \delta_{ij}$. The polynomials $l_i\left(x\right) \in \mathbb{P}_n$ for $i~=~0,\ldots, n$, are called characteristic polynomials and are given by
$$ \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*} $$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$.
Let $I_x$ be the smallest interval containing the nodes $x_0, x_1, \ldots x_n$ and $x$ and assume that $f \in C^{n+1}\left( I_x \right)$. Then the interpolation error at the point $x$ is defined and given by
$$ \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*} $$where $\xi \in I_x$ and $\omega_{n+1}$ is the nodal polynomial of degree $n + 1$, which is defined as
$$ \begin{equation*} \omega_{n+1}(x) = \prod\limits_{i=0}^{n} \left(x - x_i \right). \end{equation*} $$Piecewise Lagrange Interpolation
Define the following 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*} $$with
$$ \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.
Partition $\mathcal{T_h}$ of $[a, b]$ into $K$ subintervals $I_j = \left[ x_j , x_{j+1} \right]$ of length $h_j$ such that
$$ [a, b] = \bigcup\limits_{j=0}^{K−1}I_j.$$Let ${h = \max\limits_{0 \le j \le K−1} h_j}$.
For $k \geq 1$, introduce on $\mathcal{T}_h$ the piecewise polynomial space
$$ \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$.
As a consequence, if $f \in C^{k+1}([a, b])$, then from \eqref{eq:basic_interpolation_error} within each interval the following error estimate holds
$$ \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*} $$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.
Let $0 \leq m \leq k+1$, with $k \geq 1$ and assume that $f^{(m)} \in$ $\mathrm{L}^{2}(a, b)$ for $0 \leq m \leq k+1$ then there exists a positive constant $C$, independent of $h$, such that
$$ \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*} $$In particular, for $k=1$ and $m=0$, or $m=1$
$$ \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}$.