Interpolation

Polynomial Interpolation

Interpolation discretizes a function $f$ to finitely many values: given $(t_i, y_i)$, find $p$ with $p(t_i) = y_i$. Through $n$ points $(t_i, y_i)$ there is a unique polynomial of degree $n - 1$,

$$f(t) = c_1 + c_2 t + c_3 t^2 + \cdots + c_n t^{n-1}$$

with $c$ from $y_i = f(t_i)$,

$$\begin{bmatrix} 1 & t_1 & \cdots & t_1^{n-1} \\ 1 & t_2 & \cdots & t_2^{n-1} \\ \vdots & \vdots & & \vdots \\ 1 & t_n & \cdots & t_n^{n-1} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} \qquad \text{or } Vc = y$$

with $V$ the Vandermonde matrix.

Piecewise Polynomials

Nodes $a = t_0 < t_1 < \cdots < t_n = b$, data $\vec{y}$, and a polynomial on each $[t_{k-1}, t_k]$, $k = 1, \ldots, n$. The result is a function on $[a, b]$. The interpolation map $\mathcal{P}(\vec{y}) = p$ with $p(t_k) = y_k$ is linear,

$$\mathcal{P}(\alpha \vec{y} + \beta \vec{z}) = \alpha \mathcal{P}(\vec{y}) + \beta \mathcal{P}(\vec{z})$$

so if the data changes to $\vec{y} + \Delta \vec{y}$,

$$\delta \mathcal{P} = \mathcal{P}(\vec{y} + \Delta \vec{y}) - \mathcal{P}(\vec{y}) = \mathcal{P}(\Delta \vec{y}) = \sum_{k=0}^n (\Delta y)_k \, \mathcal{P}(e_k)$$

With $\|f\|_\infty = \max_{x \in [a, b]} |f(x)|$, the absolute condition number $\kappa$ relates $\|\delta \mathcal{P}\|_\infty$ to $\|\Delta \vec{y}\|_\infty$,

$$\frac{\|\delta \mathcal{P}\|_\infty}{\|\Delta \vec{y}\|_\infty} = \Big\| \sum_{k=0}^n \frac{(\Delta y)_k}{\|\Delta \vec{y}\|_\infty} \mathcal{P}(e_k) \Big\|_\infty, \qquad \max_{0 \le k \le n} \|\mathcal{P}(e_k)\|_\infty \le \kappa \le \sum_{k=0}^n \|\mathcal{P}(e_k)\|_\infty$$

(lower bound from $\Delta \vec{y} = e_j$, upper bound from the triangle inequality). So the conditioning comes down to the effect of each node switched on one by one. The $\mathcal{P}(e_k)$ are the cardinal functions, 1 at $t_k$ and 0 at every other node.

Piecewise Linear

$$p(x) = y_k + \frac{y_{k+1} - y_k}{t_{k+1} - t_k}(x - t_k), \qquad x \in [t_k, t_{k+1}]$$

Instead, use the hat functions

$$H_k(x) = \begin{cases} \frac{x - t_{k-1}}{t_k - t_{k-1}} & x \in [t_{k-1}, t_k] \\ \frac{t_{k+1} - x}{t_{k+1} - t_k} & x \in [t_k, t_{k+1}] \\ 0 & \text{otherwise} \end{cases}, \qquad k = 0, \ldots, n$$

They are linear on each interval and globally continuous, so their linear combinations are too, and they satisfy the cardinality condition $H_k(t_i) = 1$ if $i = k$, 0 otherwise. So $\mathcal{P}(e_k) = H_k$ and

$$p(x) = \sum_{k=0}^n y_k H_k(x)$$

a basis that depends only on the node locations. The absolute condition number is 1 in the $\infty$-norm, $\|\mathcal{P}(\vec{y} + \vec{z}) - \mathcal{P}(\vec{y})\|_\infty = \|\vec{z}\|_\infty$, since a piecewise linear function attains its max at a node.

For $t_i = a + ih$, $h = \frac{b - a}{n}$ and $f \in C^2[a, b]$,

$$\|f - p_n\|_\infty = \max_{x \in [a, b]} |f(x) - p_n(x)| \le Mh^2, \qquad M = \|f''\|_\infty$$

so the error is $O(h^2)$, and doubling the number of nodes is 4 times more accurate. $p$ is continuous but its derivative is not.

Cubic Splines

A cubic on each $[t_{k-1}, t_k]$,

$$S_k(x) = a_k + b_k(x - t_{k-1}) + c_k(x - t_{k-1})^2 + d_k(x - t_{k-1})^3, \qquad k = 1, \ldots, n$$

$4n$ unknown coefficients, with $h_k = t_k - t_{k-1}$. The constraints:

1. Interpolation at both ends, $S_k(t_{k-1}) = y_{k-1}$ and $S_k(t_k) = y_k$, i.e. $a_k = y_{k-1}$ and $a_k + b_k h_k + c_k h_k^2 + d_k h_k^3 = y_k$ ($2n$ equations).
2. $S'$ continuous at the interior nodes, $b_k + 2c_k h_k + 3d_k h_k^2 = b_{k+1}$, $k = 1, \ldots, n - 1$.
3. $S''$ continuous at the interior nodes, $2c_k + 6d_k h_k = 2c_{k+1}$, $k = 1, \ldots, n - 1$.
4. Two end conditions: known $S'$ or $S''$ at the endpoints, or the natural spline $S_1''(t_0) = S_n''(t_n) = 0$, or not-a-knot, $S'''$ continuous at $t_1$ and $t_{n-1}$, i.e. $d_1 = d_2$ and $d_{n-1} = d_n$ ($S_1 = S_2$ and $S_{n-1} = S_n$).

In block form, with $H = \mathrm{diag}(h_1, \ldots, h_n)$, $J$ the $n \times n$ matrix with 1 on the diagonal and $-1$ on the superdiagonal, and $E$ the first $n - 1$ rows of $I$ (deletes the last row),

$$\begin{bmatrix} I & 0 & 0 & 0 \\ I & H & H^2 & H^3 \\ 0 & EJ & 2EH & 3EH^2 \\ 0 & 0 & EJ & 3EH \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix} = \begin{bmatrix} y_{0:n-1} \\ y_{1:n} \\ 0 \\ 0 \end{bmatrix}$$

plus the two end conditions. The accuracy is $\|f - S_n\|_\infty \le Ch^4$, 4th order.