Dimension of the subspace of splines on $[a,b]$

Question

Consider a grid $\Delta : a := x_0<x_1<\ldots <x_n =: b$ on $[a,b]$. Denote the space of piecewise polynomials of at most degree $m$ on $[a,b]$ by $\mathcal P_\Delta^m = \mathcal P^m$. We know it is a vector subspace in the vector space of all bounded functions on $[a,b]$. Furthermore, it's also known that $\dim\mathcal P^m = n(m+1)$, since for each subinterval we construct a polynomial of at most degree $m$, therefore we need to select a total of at most $n(m+1)$ coefficients.

Impose restrictions on the mentioned space. Consider all $S:[a,b]\to\mathbb R$ with $$\forall j, 1\leq j\leq n\quad S\in \mathcal P^m[x_{j-1},x_j] \\S\in C^{(m-k)}[a,b],$$ i.e all splines on $[a,b]$ : $\mathcal S_\Delta ^{m,k}$. One can simply check that it's a subspace in $\mathcal P^m$, therefore finite dimensional, but how do we compute its dimension? It's clear our choice of coefficients is going to be limited by conditions. For instance if $[a,b]$ is divided into two subintervals $[a,z]\cup [z,b]$ and we consider $\mathcal S_\Delta ^{2,1}$, then we have some two polynomials $f:[a,z]\to\mathbb R$ and $g:[z,b]\to\mathbb R$ $$f(x) = a_0 + a_1x + a_2x^2\quad\mbox{and}\quad g(x) = b_0 +b_1x + b_2x^2 $$ with the necessary conditions $f(z) = g(z)$ and $f'(z) = g'(z)$.

Question: Are such conditions sufficient when we consider the dimension? E.g if we consider $\mathcal S_\Delta^{2,1}$ on $[a,b] = [a,z]\cup [z,b]$, would the dimension be $2(2+1) - (2-1)(2-1+1) = 4?$

In the general case, we have $n-1$ interior knots and $m-k+1$ (necessary) conditions for each interior knot i.e $$S_j^{(d)}(x_j) = S_{j+1}^{(d)}(x_j)\qquad j=1,\ldots ,n-1\quad d = 0,\ldots, m-k $$

Answer 1

We might express these conditions in terms of matrices in the following way. Suppose we have two polynomials of degree $m$ which must agree at the knot $x$,

\begin{align*} f(x)&=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{m}x^{m},\\ g(x)&=b_{0}+b_{1}x+b_{2}x^{2}+\cdots+b_{m}x^{m}. \end{align*}

We might write these as $f(x)=\vec{x}^{T}\vec{f}=[1,x,x^{2},\ldots,x^{m}][a_{0},a_{1},a_{2},\ldots,a_{m}]^{T}$, and similarly for $g$. Then if we let $p=[\vec{f}^{T},\vec{g}^{T}]^{T},$ the condition $f(x)=g(x)$ may be written as $[\vec{x},-\vec{x}]p=0.$

For $m$ derivatives to be equal at this knot, we may write the matrix

$$A=[A_{x},-A_{x}]= \begin{bmatrix} 1&x&x^{2}&\cdots&x^{m}&-1&-x&-x^{2}&\cdots&-x^{m}\\ 0&1&2x&\cdots&mx^{m-1}&0&-1&-2x&\cdots&-mx^{m-1}\\ 0&0&2&\cdots&m(m-1)x^{m-2}&0&0&-2&\cdots&-m(m-1)x^{m-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&m!&0&0&0&\cdots&-m! \end{bmatrix},$$ which clearly has linearly independent rows, since the leading nonzero entries are in different columns. Then for all but one derivatives to be equal at this knot, we need $Ap=0$. If we only want $k$ derivatives to be equal, we take the first $k+1$ rows of this matrix, which are also linearly independent, and for this submatrix $A'$, we again require $A'p=0.$

Now to have these equalities holding at all of the knots, we make a vector like $p$ but with the coefficients of all of the polynomials in order, and the matrix of equations we need to hold looks like $$ \begin{bmatrix} A_{x_{1}}&-A_{x_{1}}&0&0&\cdots&0\\ 0&A_{x_{2}}&-A_{x_{2}}&0&\cdots&0\\ 0&0&A_{x_{3}}&-A_{x_{3}}&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\ 0&0&0&0&\cdots&-A_{n-1} \end{bmatrix}.$$

Since the main diagonal has all positive entries (though the matrix is not square!), the rows of this matrix, of which there are $(n-1)(m+1)$, are linearly independent. Thus, we have $n(m+1)-(n-1)(m+1)=m+1$ degrees of freedom in this case, the nullity of the matrix above. If we do not want all $m$ derivatives to be equal at each knot, we remove the rows corresponding to the extra conditions from this matrix. We might also add conditions to the polynomials on the intervals $[x_{0},x_{1}]$ and $[x_{n-1},x_{n}]$, at the points $x_{0}$ and $x_{n}$, in order to make the spline unique, when we are trying to approximate a function on this interval.

Answer 2

Let $\dim X = n$. We know that if $\varphi _1,\ldots \varphi _n\in\mathcal L(X,\mathbb R)$ constitute a basis, then $$\bigcap_{j=1}^n\mbox{Ker}\varphi _j = \{0\}. $$ By Rank-Nullity theorem, if $\varphi _1,\ldots,\varphi _k$, $k\leq n$ are linearly indep, then $$\dim\bigcap_{j=1}^k\mbox{Ker}\varphi_j = n-k $$ Denote $g(a\pm0) := \lim_{x\to a\pm} g(x)$. We define $\varphi _{ij} : \mathcal P^m\to\mathbb R$ with $$f\mapsto f^{(j)}(x_i+0) - f^{(j)}(x_i-0),\quad i=1,\ldots ,n-1,\quad j=0,\ldots ,m-k.$$ Of course, the $\varphi _{ij}$ are all linear and clearly the space $\mathcal S^{m,k}$ annihilates all the $\varphi_{ij}$ due to continuity at knots. It suffices to show $\varphi _{ij}$ are linearly independent. Suppose, for a linear combination $$\sum_{i=1}^{n-1}\sum_{j=0}^{m-k}\alpha _{ij}\left [f^{(j)}(x_i+0)- f^{(j)}(x_i-0)\right ] = 0\qquad (f\in\mathcal P^m)$$ Then taking $f(x) = (x-x_{n-1})^{m-k}_+$, where $$(x-c)^r_+ := \begin{cases}(x-c)^r, &x\geq c\\0, &x<c\end{cases}, $$ necessarely $\alpha_{n-1, m-k} = 0$. To see, why this is so it suffices to note that $$f^{(m-k)}(x_{n-1}+0)>0 \quad\mbox{and}\quad f^{(m-k)}(x_{n-1}-0)=0. $$Proceed, by considering $f(x) = (x-x_{n-1})^{m-k-1}_+$. Repeat process with every knot and every power and indeed all the coefficients must be zero.

By Rank-Nullity, the dimension of the spline space $\mathcal S^{m,k}$ is equal to $$ (m+1)n - (m-k+1)(n-1)$$