Piecewise Polynomials

Often, our aim is to use some \(f\in\Pi_{<k,\xi}\) to approximate another function \(g\) according to some set of conditions determined by known information about \(g\). Often, these conditions may relate to smoothness, relating to continuity conditions of the approximating function \(f\).

De Boor defines the following subspace of \(\Pi_{<k,\xi}\).

So, \(v_i=0\) implies that there are no continuity conditions at the breakpoint \(\xi_i\), and otherwise \(v_i\) gives the level of continuity.

For the purposes of computation we need a basis for this new space. That is, we want a sequence of functions \(\varphi_1,\varphi_2,...\in\Pi_{<k,\xi,\nu}\) such that any element \(f\) can be written uniquely as \[ f(x) \overset{\Delta}{=} \sum_j \alpha_j\varphi_j(x). \]

Any \(f\in \Pi_{<k,\xi}\) can be written \[ \begin{aligned} f &= \sum_{ij} (\lambda_{ij} f )\varphi_{ij} \\ f(x) &= \sum_{j < k} f^{(j)(\xi_1)}(x - \xi_1)^j/j! + \sum_{i=2}^l\sum_{j<k} \text{jump}_{\xi_i} D^j f(x - \xi_i)_+^j/j!. \end{aligned} \] THe jumps appear as coefficients and enoforcement of the specified constraints \[ \text{jump}_{\xi_i}D^{j-1}f = 0 \quad\text{for }j=1,...,\nu_i\text{ and }i=2,...l, \] are made by simply restricting to functions where the coefficients are zero.

Then the sequence \(\varphi_{ij}, i=2,...,l,j=\nu_i,...,k-1\) is a basis for \(\Pi_{<k,\xi,\nu}\) taking \(v_1=0\) so that \[ \Pi_{<k,\xi,\nu} \ni f =\sum_{i=1}^l \sum_{j=\nu_i}^{k-1} \alpha_{ij}\varphi_{ij}. \] For example, suppose \(f\in\Pi_{<2,\xi,\nu}\) where \(\nu_2=\cdots=\nu_l=1\) and as previously stated, \(v_1=0\) by design. Then \[ f(x) = \alpha_{10} + \alpha_{11}(x - \xi_1) + \sum_{i=1}^l \alpha_{i1}(x - \xi_i)_+ \] for some \(\alpha\).

tpf <- function(x, r) {
  out <- pmax(x, 0)^r
  if(r == 0)
    out[x <= 0] <- 0
  return(out)
}

Figure 1: Example truncated power functions.

The TPB has stability issues as a basis. Therefore, alternatives are preferred. The \(k\)th-order B-spline basis can be defined as scaled \(k\)th divided differences of the TPB and any \(\Pi_{<k,\xi,\nu}\) has a B-spline basis.

For a function \(g\) and knot sequence \(\tau\), the \(k\)th divided difference of \(g\) is \[ [\tau_0,...,\tau_k]g = \begin{cases} \frac{g^{(k)}(\tau_0)}{k!} &\text{when }\tau_0=\tau_1=\cdots=\tau_k,g\in C^k \\ \frac{[\tau_0,...,\tau_{r-1},\tau_{r+1},...,\tau_k]g-[\tau_0,...,\tau_{s-1},\tau_{s+1},...,\tau_k]g}{t_s - t_r} &\text{where } t_s\text{ and }t_r\text{ are any distinct knots in the sequence.} \end{cases} \]

Let \(\tau = (\tau_j)\) be a nondecreasing sequence. The \(j\)th normalised B-spline of order \(k\) for the knot sequence \(\tau\), denoted \(B_{j,k,\tau}\) is \[ \begin{aligned} B_{j,k,\tau}(x) &\overset{\Delta}{=} (\tau_{j+k} - \tau_j)[\tau_j,...,\tau_{j+k}](\cdot - x)_+^{k-1} \\ &= [\tau_{j+1},...,\tau_{j+k}](\cdot - x)_+^{k-1} - [\tau_j,...,\tau_{j+k-1}](\cdot - x)_+^{k-1} \end{aligned} \] where the \(k\)th divided difference of \(g(\cdot)=(\cdot - x)_+^{k-1}\) is to be considered as a function of the knot for fixed \(x\). From the definition, if \(x\notin [\tau_j, \tau_{j+k})\) then \(B_{j,k,\tau}=0\).

Let \(\tau\) be a knot sequence. Then we have \[ B_{j1}(x) = \begin{cases} 1 &\text{if } x\in [\tau_j, \tau_{j+1}) \\ 0 & \text{if } x\notin [\tau_j, \tau_{j+1}) \end{cases} \] the B-spline of order 1. From this, the B-spline of order \(k>1\) on \([\tau_j, \tau_{j+k})\) are given by \[ \begin{aligned} B_{j,k}(x) &= \omega_{j,k}B_{j,k-1}(x) + (1 - \omega_{j+1,k})B_{j+1,k-1}(x) \\ &= \frac{x - \tau_j}{\tau_{j+k-1} - \tau_j}B_{j,k-1}(x) + \frac{\tau_{j+k} - x}{\tau_{j+k} - \tau_{j+1}}B_{j+1,k-1}(x) \\ \omega_{j,k}(x) &= \frac{x-\tau_j}{\tau_{j+k-1} - \tau_j} \end{aligned} \] which depends only on the \(k+1\) knots \(\tau_j,...,\tau_{j+k}\).

A spline function of order \(k\) with knot sequence \(\tau\) is any linear combination of B-splines of order \(k\) \[ \mathcal{S}_{k,\tau} \overset{\Delta}{=} \left\{\sum_i \alpha_i B_{i,k,\tau}|\alpha_i\in\mathbb R, \forall i\right\}. \] Given B-splines are in the set \(\Pi_{<k,\tau}\) we have \(\mathcal{S}_{k,\tau} \subseteq \Pi_{<k,\tau}\), but we also have \(\mathcal{S}_{k,\tau} = \Pi_{<k,\xi,\nu}\) for some \(\tau\) given \(\xi\) and \(\nu\). Additionally, \(\Pi_{<k}\subseteq \mathcal{S}_{k,\tau}\), that is, the set of splines contains all polynomials of order \(k\).

Curry and Schoenberg show that, given strictly increase break sequence \(\xi = (\xi_i)_1^{l+1}\), and non-negative integers \(\nu = (\nu_i)_2^l\) with \(\nu_i \leq k\), set \[ n \overset{\Delta}{=} k + \sum_{i=2}^l (k - \nu_i) = kl - \sum_{i=2}^l \nu_i = \dim\Pi_{<k,\xi,\nu} \] and let \(\tau = (\tau_i)_1^{n+k}\) be non-decreasing sequence constructed from \(xi\) and \(\nu\) by:

• for \(i=2,...,l\), \(\xi_i\) occurs exactly \(k-\nu_i\) times,
• \(\tau_1\leq \tau_2 \leq \cdots \leq \tau_k \leq \xi_1\) and \(\xi_{l+1}\leq \tau_{n+1} \leq \tau_{n+1} \leq \cdots \leq \tau_{n+k}\). Then the sequence \(B_1,...,B_n\) of B-splines of order \(k\) for knot sequence \(\tau\) is a basis for \(\Pi_{<k,\xi,\nu}\) as functions on the basic interval \(I_{k,\tau} = [\tau_k,...,\tau_{n+1}]\). This implies \[ \mathcal{S}_{k,\tau} = \Pi_{<k,\xi,nu} \text{ on } I_{k,\tau}. \] Thus, we have a recipe for constructing a B-spline basis for a piecewise polynomial space \(\Pi_{<k,\xi,\nu}\) by setting a certain knot sequence \(\tau\).

Fewer knots at a break \(\xi\) implies more continuity. The number of continuity conditions at a break plus the number of knots at the break is equal to the order of the spline. Additionally, \(k\)-knots at a break implies no continuity, and \(0\)-knots at a break implies \(k\) continuity conditions.

Truncated Power Basis

B-spline basis

M-spline basis

I-spline basis