MATH566 Lesson 7: Piecewise polynomial interpolation - Splines

Overview

• Interval partition and approaches to piecewise interpolation

• Spline interpolation:

  • Constant splines

  • Linear splines

  • Quadratic splines

  • Cubic splines

• Spline bases

Interval partition, piecewise interpolation

• Numerical experiments: high-degree polynomial interpolants can diverge

• Idea: for $f:[a,b]\to ℝ$, break up interval $[a,b]$ into smaller pieces

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

Definition. The norm of partition $X=\{x_0,x_1,\dots ,x_m\}$ of the interval $[a,b]\subset ℝ$ is

• Define $S_i:[x_{i-1},x_i]\to ℝ$, $S_i\left(t\right)$ polynomial of degree $n\ll m$

• Approaches to piecewise polynomials interpolation:

  • Splines: enforce $S_i^{\left(k\right)}\left(x_i\right)=S_{i+1}^{\left(k\right)}\left(x_i\right)$ (continuity up to derivative of order $k$)

  • Piecewise Lagrange: further divide $[x_{i-1},x_i]$ into $n$ intervals, no derivatives

Piecewise constant interpolation

• Simplest case: constant functions $S_i\left(t\right)=y_{i-1}$

• Apply polynomial error formula over each subinterval

  ${\displaystyle f\left(t\right)-S_i\left(t\right)=f^{\text{'}}\left({\xi }_t\right)(t-x_{i-1})}$

• Overall

  ${\displaystyle |f\left(t\right)-p\left(t\right)|⩽{||f^{\text{'}}||}_{\infty }||X||}$

• For equidistant (uniform) partition $x_i=x_0+ih$, $h=(x_m-x_0)/m$

  ${\displaystyle |f\left(t\right)-p\left(t\right)|⩽{||f^{\text{'}}||}_{\infty }h,}$

• The interpolant $p\left(t\right)$ converges to $f\left(t\right)$ linearly (order of convergence is 1)

• Type of approximation used analytically in construction of integrals from Riemann sums

Linear splines

• A piecewise linear interpolant is obtained by

  ${\displaystyle S_i\left(t\right)=\frac{t-x_{i-1}}{x_i-x_{i-1}}(y_i-y_{i-1})+y_{i-1}.}$

• Interpolation error is bounded by

  ${\displaystyle |f\left(t\right)-p\left(t\right)|⩽\frac{1}{2}{||f^{\text{'}}||}_{\infty }{h}^2}$

• Converges as $𝒪\left(h^2\right)$ (“quadratic convergence”, more properly algebraic convergence as $𝒪(1/n^2)$)

Quadratic splines

• Piecewise quadratic interpolant, $S_i:[x_{i-1},x_i]\to ℝ$

  ${\displaystyle S_i\left(t\right)=b_i{(t-x_{i-1})}^2+c_i(t-x_{i-1})+y_{i-1}.}$

• Interpolation condition at left already satisfied $S_i\left(x_{i-1}\right)=y_{i-1}$

• Enforce interpolation condition at right

  ${\displaystyle \begin{array}{ll}{S}_i\left(x_i\right)=b_i{h}_i^2+c_i{h}_i=y_i,& i=1,2,\dots ,n\end{array}}$

• Only $n$ conditions for $2n$ parameters. Enforce continuity of derivative in interior

  ${\displaystyle \begin{array}{ll}{S}_i^{\text{'}}\left(x_i\right)=2b_i{h}_i+c_i=2b_{i+1}{h}_{i+1}+c_{i+1}=S_{i+1}^{\text{'}}\left(x_i\right)& i=1,2,\dots ,n-1\end{array}.}$

• Still one condition left to choose. Examples:

  • $S_n^{\text{'}}\left(x_i\right)=y_n^{\text{'}}$ (known end slope)

  • $S_n^{\text{'}}\left(x_i\right)=S_n^{\text{'}}\left(x_{i-1}\right)$ (constant end-slope)

• To compute $b_i,c_i$ a linear system $𝑩𝒔=𝒅$ is formed and solved for $s_i=y_i^{\text{'}}$

Quadratic spline bidiagonal system

• The interpolation error is bounded by

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

  for an equidistant partition, exhibiting algebraic “quadratic” convergence.

Cubic splines

• Approach similar to quadratic, but with continuity up to second derivative

• Continuity of curvature (second derivative) important in applications

• The second derivative is linear

  ${\displaystyle S_i^{\text{'}\text{'}}\left(t\right)=\frac{z_{i-1}}{h_i}(x_i-t)+\frac{z_i}{h_i}(t-x_{i-1}),}$

• Obtain tridiagonal system

  ${\displaystyle h_i{z}_{i-1}+2(h_i+h_{i-1})z_i+h_{i+1}{z}_{i+1}=d_i,i=1,2,\dots ,n-1.}$ ${\displaystyle d_i=\frac{6(y_{i+1}-y_i)}{h_{i+1}}-\frac{6(y_i-y_{i-1})}{h_i}}$

• End conditions are required to close the system:

  • Zero end-curvature, “natural end conditions”: $z_0=z_n=0$

  • Curvature extrapolation: $z_0=z_1$, $z_n=z_{n-1}$

  • Known curvature: $z_0=f^{\text{'}\text{'}}\left(x_0\right)$, $z_n=f^{\text{'}\text{'}}\left(x_n\right)$.

Spline bases

• Splines are also linear combinations of basis functions

  ${\displaystyle {ℬ}_k(t;𝒙)=\{B_{0,k}\left(t\right),B_{1,k}\left(t\right),\dots ,B_{n,k}\left(t\right)\}}$

• The basis functions are non-zero only over a few subintervals

Figure 1. $B$-spline sets ${ℬ}_0,{ℬ}_1,{ℬ}_2,{ℬ}_3,{ℬ}_4$ with $𝒙=\left[\begin{array}{llllll}0& 1& 2& 3& 4& 5\end{array}\right]$