MATH566

1Splines

Instead of adopting basis functions defined over the entire sampling interval $[x_{0}, x_{n}]$ as exemplified by the monomial or Lagrange bases, approximations of $f : ℝ \to ℝ$ can be constructed with different branches over each subinterval, by introducing $S_{i} : [x_{i - 1}, x_{i}] \to ℝ$ , and the approximation

p (t) = {\begin{cases} S_{1} (t) & x_{0} ⩽ t < x_{1} \\ S_{2} (t) & x_{1} ⩽ t < x_{2} \\ ⋮ & ⋮ \\ S_{n} (t) & x_{n - 1} ⩽ t < x_{n} \\ S_{n + 1} (t) & t = x_{n} \end{cases} . .

The interpolation conditions $p (x_{i}) = y_{i}$ lead to constraints

S_{i} (x_{i - 1}) = y_{i - 1} .

The form of $S (t)$ can be freely chosen, and though most often $S (t)$ is a low-degree polynomial, the spline functions may have any convenient form, e.g., trigonometric or arcs of circle. The accuracy of the $p (t)$ approximant is determined by the choice of form of $S (t)$ , and by the sample points. It is useful to introduce a quantitative measure of the sampling through the following definitions.

Definition. ${x_{0}, x_{1}, \dots, x_{n}}$ is a partition of the interval $[a, b] \subset ℝ$ if $x_{i} \in ℝ$ , $i = 0, 1, \dots, n$ , satisfy

$a = x_{0} < x_{1} < \dots < x_{n - 1} < x_{n} = b .$

Definition. The norm of partition $X = {x_{0}, x_{1}, \dots, x_{n}}$ of the interval $[a, b] \subset ℝ$ is

$|| X || = {max}_{1 ⩽ i ⩽ n} | x_{i} - x_{i - 1} | .$

Constant splines (degree 0).

A simple example is given by the constant functions

S_{i} (t) = y_{i - 1}

. Arbitrary accuracy of the approximation can be achieved in the limit of

n \to \infty

|| X || \to 0

. Over each subinterval the polynomial error formula gives

f (t) - S_{i} (t) = f^{'} (ξ_{t}) (t - x_{i - 1}),

so overall

| f (t) - p (t) | ⩽ {|| f^{'} ||}_{\infty} || X ||,

which becomes

| f (t) - p (t) | ⩽ {|| f^{'} ||}_{\infty} h,

for equidistant partitions $x_{i} = x_{0} + i h$ , $h = (x_{n} - x_{0}) / n$ . The interpolant $p (t)$ converges to $f (t)$ linearly (order of convergence is 1)

Linear splines (degree 1).

A piecewise linear interpolant is obtained by

S_{i} (t) = \frac{t - x_{i - 1}}{x_{i} - x_{i - 1}} (y_{i} - y_{i - 1}) + y_{i - 1} .

The interpolation error is bounded by

| f (t) - p (t) | ⩽ \frac{1}{2} {|| f^{'} ||}_{\infty} h^{2},

for an equidistant partition, exhibiting quadratic convergence.

Quadratic splines (degree 2).

A piecewise quadratic interpolant is formulated as

S_{i} (t) = b_{i} {(t - x_{i - 1})}^{2} + c_{i} (t - x_{i - 1}) + y_{i - 1} .

The interpolation conditions are met since $S_{i} (x_{i - 1}) = y_{i - 1}$ . The additional parameters of this higher order spline interpolant can be determined by enforcing additional conditions, typically continuity of function and derivative at the boundary between two subintervals

\begin{array}{ll} S_{i} (x_{i}) = b_{i} h_{i}^{2} + c_{i} h_{i} = y_{i}, & i = 1, 2, \dots, n \\ S_{i}^{'} (x_{i}) = 2 b_{i} h_{i} + c_{i} = 2 b_{i + 1} h_{i + 1} + c_{i + 1} = S_{i + 1}^{'} (x_{i}) & i = 1, 2, \dots, n - 1 \end{array} .

An additional condition is required to close the system, for example $S_{n}^{'} (x_{i}) = y_{n}^{'}$ (known end slope), or $S_{n}^{'} (x_{i}) = 0$ (zero end slope), or $S_{n}^{'} (x_{i}) = S_{n}^{'} (x_{i - 1})$ (constant end-slope). The coefficients $b_{i}, c_{i}$ are conveniently determined by observing that $S_{i}^{'} (t)$ is linear over interval $[x_{i - 1}, x_{i}]$ of length $h_{i} = x_{i} - x_{i - 1}$ , and is given by

S_{i}^{'} (t) = \frac{t - x_{i - 1}}{h_{i}} (s_{i} - s_{i - 1}) + s_{i - 1} = \frac{s_{i - 1}}{h_{i}} (x_{i} - t) + \frac{s_{i}}{h_{i}} (t - x_{i - 1}),

with $s_{i} = y_{i}^{'}$ , the slope of the interpolant at $x_{i} .$ The continuity of first derivative conditions $S_{i}^{'} (x_{i}) = S_{i + 1}^{'} (x_{i})$ are satisfied, and integration gives

S_{i} (t) = \frac{s_{i}}{2 h_{i}} {(t - x_{i - 1})}^{2} - \frac{s_{i - 1}}{2 h_{i}} {(x_{i} - t)}^{2} + A_{i} .

The interpolation condition $S_{i} (x_{i - 1}) = y_{i - 1}$ , determines the constant of integration $A_{i}$

A_{i} - \frac{s_{i - 1} h_{i}}{2} = y_{i - 1} \Rightarrow A_{i} = y_{i - 1} + \frac{s_{i - 1} h_{i}}{2},

Imposing the continuity of function condition $S_{i} (x_{i}) = S_{i + 1} (x_{i})$ gives

\frac{s_{i} h_{i}}{2} + y_{i - 1} + \frac{s_{i - 1} h_{i}}{2} = - \frac{s_{i} h_{i + 1}}{2} + y_{i} + \frac{s_{i} h_{i + 1}}{2},

s_{i - 1} + s_{i} = \frac{2}{h_{i}} (y_{i} - y_{i - 1}), i = 1, 2, \dots, n,

a bidiagonal system for the slopes that is solved by backward substituion in $𝒪 (2 n)$ operations. For $i = 1$ , the $s_{0}$ value arising in the system has to be given by an end condition, and the overall system $𝑩 𝒔 = 𝒅$ is defined by

𝑩 = [\begin{array}{lllll} 1 \\ 1 & 1 \\ 1 & 1 \\ ⋱ & ⋱ \\ 1 & 1 \end{array}], 𝒅 = [\begin{array}{l} \frac{2}{h_{1}} (y_{1} - y_{0}) - s_{0} \\ \frac{2}{h_{2}} (y_{2} - y_{1}) \\ ⋮ \\ \frac{2}{h_{n}} (y_{n} - y_{n - 1}) \end{array}], 𝒔 \in ℝ^{n}, 𝑩 \in ℝ^{n \times n} .

The interpolation error is bounded by

| f (t) - p (t) | ⩽ \frac{1}{2} {|| f^{'} ||}_{\infty} h^{2},

for an equidistant partition, exhibiting quadratic convergence.

Cubic splines (degree 3).

The approach outlined above can be extended to cubic splines, of special interest since continuity of curvature is achieved at the nodes, a desirable feature in many applications. The second derivative is linear

S_{i}^{''} (t) = \frac{z_{i - 1}}{h_{i}} (x_{i} - t) + \frac{z_{i}}{h_{i}} (t - x_{i - 1}),

with $z_{i - 1} = S_{i}^{''} (x_{i - 1})$ , $z_{i} = S_{i}^{''} (x_{i})$ the curvature at the endpoints of the $[x_{i - 1}, x_{i}]$ subinterval. Double integration gives

S_{i} (t) = \frac{z_{i - 1}}{6 h_{i}} {(x_{i} - t)}^{3} + \frac{z_{i}}{6 h_{i}} {(t - x_{i - 1})}^{3} + A_{i} (t - x_{i - 1}) + B_{i} (x_{i} - t) .

The interpolation conditions $S_{i} (x_{i - 1}) = y_{i - 1}$ , $S_{i - 1} (x_{i}) = y_{i}$ , gives the integration constants

A_{i} = \frac{y_{i}}{h_{i}} - \frac{z_{i} h_{i}}{6}, B_{i} = \frac{y_{i - 1}}{h_{i}} - \frac{z_{i - 1} h_{i}}{6}

and continuity of first derivative, $S_{i}^{'} (x_{i}) = S_{i + 1}^{'} (x_{i})$ , subsequently leads to a tridiagonal system for the curvatures

h_{i} z_{i - 1} + 2 (h_{i} + h_{i - 1}) z_{i} + h_{i + 1} z_{i + 1} = \frac{6 (y_{i + 1} - y_{i})}{h_{i + 1}} - \frac{6 (y_{i} - y_{i - 1})}{h_{i}}, i = 1, 2, \dots, n - 1 .

End conditions are required to close the system. Common choices include:

Zero end-curvature, also known as the natural end conditions: $z_{0} = z_{n} = 0$ .
Curvature extrapolation: $z_{0} = z_{1}$ , $z_{n} = z_{n - 1}$
Analytical end conditions given by the function curvature: $z_{0} = f^{''} (x_{0})$ , $z_{n} = f^{''} (x_{n})$ .