\section{B-SPLINES (Carl deBoor)}
\noindent{\bf Definition}. Let $\xi=\bigl(\xi_i\bigr)_1^{\ell+1}$ be a
strictly increasing sequence of points, $k>0$, and $P_1$, $\ldots$,
$P_\ell$ a sequence of $\ell$ polynomials each of order $k$ (degree
$<k$). The corresponding {\it piecewise polynomial\/} $f$ of order $k$
is defined by $$f(x)=P_i(x), \qquad\xi_i<x<\xi_{i+1};\quad i=1,\ldots,
\ell.$$ $\xi_i$ are called the {\it breakpoints\/} of $f$. By
convention, $$f(x)=\cases{P_1(x),&$x\le\xi_1$,\cr P_\ell(x),&
$x\ge\xi_{\ell+1}$,\cr} \qquad\hbox{and}\qquad f(\xi_i)=f(\xi_i+) \quad
\hbox{right continuous}.$$
$\cP_{k,\xi}=\bigl\{$piecewise polynomial functions of order $k$ with
breakpoint sequence $\bigl(\xi_i\bigr)_1^{\ell+1}\bigr\}$, and dim
$\cP_{k,\xi}=k\ell$.

Let $\nu=\bigl(\nu_i\bigr)_2^\ell$ be a vector of nonnegative integers,
related to the jump conditions $$\hbox{jump}_{\xi_i}\;D^{j-1}f =0 \hbox{
for }j=1,\ldots,\nu_i \hbox{ and }i=2,\ldots,\ell.$$
$\cP_{k,\xi,\nu}=\bigl\{f\in \cP_{k,\xi}\mid|f$ satisfies the above jump
conditions$\bigr\}$ is a subspace of $\cP_{k,\xi}$ with dimension
$$\sum_{i=1}^\ell k-\nu_i \qquad (\nu_1=0).$$
A basis for $\cP_{k,\xi}$ is $$\phi_{ij}=\cases{(x-\xi_1)^j/j!,&
$i=1$,\cr (x-\xi_i)^j_+/j!,& $i=2,\ldots,\ell$,\cr} \qquad j=0,\ldots,
k-1,$$ where $$(x-\xi_i)^j_+=\cases{0,&$x<\xi_i$,\cr
(x-\xi_i)^j,&$x\ge\xi_i$.\cr}$$
A basis for $\cP_{k,\xi,\nu}$ is $\phi_{ij}$, $j=\nu_i,\ldots,k-1$ and
$i=1,\ldots,\ell$. That these are bases follows from the fact that they
have the right number of elements, and are independent since $\exists$
linear functionals $\lambda_{ij}$ such that $$\lambda_{ij}\phi_{rs}=
\delta_{ir}\delta_{js}. \hskip40pt\left[\lambda_{ij}f=
\hbox{jump}_{\xi_i}\;D^j f.\right]$$

\hrule\medskip\noindent{\bf Definition}. Let $t=(t_i)$ be a
nondecreasing sequence (finite, infinite, or biinfinite). The {\it$i$th
B-spline of order $k$ for the knot sequence $t$} is denoted by
$B_{i,k,t}$ and is defined by $$B_{i,k,t}(x)=(t_{i+k}-t_i)\,
(\tau-x)_+^{k-1}\bigl[t_i,\ldots,t_{i+k}\bigr], \qquad\hbox{all }x\in
E.$$ (The divided difference is applied to $(\tau-x)_+^{k-1}$ considered
as a function of $\tau$.) If $k$ and $t$ are understood, write $B_i$
instead of $B_{i,k,t}$.

\medskip\hrule\medskip
{\bf Properties of B-splines}:
\item{(i)}$B_i(x)=0$ for $x\notin\bigl[t_i,t_{i+k}\bigr]$.
\item{(ii)}$\displaystyle\sum_i B_i(x)=\sum_{i=r+1-k}^{s-1} B_i(x)=1$
for all $t_r<x<t_s$.
\item{(iii)}$B_i(x)>0$ for $t_i<x<t_{i+k}$.
\medskip\hrule\medskip

For $t_i$ equally spaced a distance $h$ apart, cubic ($k=4$) B-splines
are given by $$\eqalign{B_i(x)={2\over3h^3}& \left( {1\over4}
(x-t_{i})_+^3 - (x-t_{i+1})_+^3 + {3\over2}(x-t_{i+2})_+^3 \right.\cr
&\left.{}-(x-t_{i+3})_+^3 + {1\over4}(x-t_{i+4})_+^3 \right).\cr}$$

\midinsert\vglue -1.6in
\centerline{\epsfxsize=4in\epsffile{Bixplot.eps}} \vglue -1.4in
\centerline{Cubic B-spline $B_i(x)$ for equally spaces knots $t_j$.}
\endinsert

\midinsert\vglue -1.2in
\centerline{\epsfxsize=5in\epsffile{bsplplot.eps}} \vglue -0.8in
\centerline{Parabolic B-splines $B_{i,3}(x)$ for the knot sequence
$t=(0,1,1,3,4,6,6,6)$.}
\endinsert

\noindent{\bf Definition}. A spline function of order $k$ with knot
sequence $t$ is any linear combination of B-splines of order $k$ for the
knot sequence $t$. The collection of all such functions is denoted by
${\cal S}_{k,t}$.

\noindent{\bf Theorem (Curry, Sch\"onberg)}. For a given strictly
increasing sequence $\xi=\bigl(\xi_i\bigr)_1^{\ell+1}$,
and a given nonnegative integer sequence $\nu=(\nu_i)_2^\ell$ with
$\nu_i\le k$, all $i$, set
$$n=k+\sum_{i=2}^\ell k-\nu_i = k\ell-\sum_{i=2}^\ell \nu_i =\hbox{dim }
{\cal P}_{k,\xi,\nu}$$ and let $t=\bigl(t_i\bigr)_1^{n+k}$ be any
nondecreasing sequence so that \item{(i)}
$t_1\le t_2\le\cdots\le t_k\le\xi_1$ and $\xi_{\ell+1}\le t_{n+1}\le
t_{n+2}\le\cdots\le t_{n+k}$;
\item{(ii)}for $i=2,\ldots,\ell$, the number $\xi_i$ occurs exactly
$k-\nu_i$ times in $t$.

\noindent Then the sequence $B_1,\ldots,B_n$ of B-splines of order $k$
for the knot sequence $t$ is a basis for ${\cal P}_{k,\xi,\nu}$,
considered as functions on $\bigl[t_k,t_{n+1}\bigr]$, i.e., $${\cal
S}_{k,t}={\cal P}_{k,\xi,\nu} \qquad\hbox{on }\bigl[t_k,t_{n+1}\bigr].$$

\hrule\smallskip{\bf NOTE}: \vtop{\tabskip=0pt\halign{&#\hfil\cr
number of continuity conditions at $\xi+{}$ \cr
number of knots at $\xi$&$=k$\cr}} \medskip\hrule\medskip

Proof. From the definition of divided differences, for any sufficiently
smooth function $g$ $\exists$ constants $d_i$, $\ldots$, $d_{i+k}$ such
that $$g\bigl[t_i,\ldots,t_{i+k}\bigr]= \sum_{r=i}^{i+k} d_r
g^{(j_r)}(t_r),$$ with $j_r=\max\{s\mid| r-s\ge i,\;t_{r-s}=t_r\}$,
$r=i$, $\ldots$, $i+k$. Thus
$$B_i(x)=(t_{i+k}-t_i) \sum_{r=i}^{i+k} d_r\bigl(t_r-x\bigr)_+^{k-1-j_r}
(k-1)!\big/(k-1-j_r)!,$$
which is clearly a piecewise polynomial function of order $k$ with
breakpoints at $t_i$, $\ldots$, $t_{i+k}$, i.e., at some of the points
$\xi_2$, $\ldots$, $\xi_\ell$ (and possibly at some other points outside
$(\xi_1,\xi_{\ell+1})$, but these don't matter). $B_i$ has a jump in its
$s$-th derivative at the breakpoint $xi_j$ only if for some
$r\in[i,i+k]$, we have $\xi_j=t_r$ and $k-1-j_r=s$. Since $j_r$ counts
the number of $t_m$'s equal to $t_r$ and with $i\le m<r$, it follows
that $j_r$ must be less than $k-\nu_j$ which is the total number of
$t_m$'s equal to $\xi_j=t_r$ by construction of $t$. This says that
always $s\ge\nu_j$, and so $$\hbox{jump}_{\xi_j} D^mB_i=0
\qquad\hbox{for }m=0,\ldots,\nu_j-1.$$
Therefore $B_i\in{\cal P}_{k,\xi,\nu}$, all $i$.

Since there are $n$ $B_i$'s and dim ${\cal P}_{k,\xi,\nu}=n$, it
suffices to show that the sequence $\bigl(B_i\bigr)_1^n$ is linearly
independent. This follows from:

\noindent{\bf Lemma (deBoor, Fix, 1973)}. Let $\lambda_i$ be the linear
functional given by the rule $$\lambda_i f=\sum_{r=0}^{k-1} (-1)^{k-1-r}
\psi^{(k-1-r)}(\tau_i)\,D^rf(\tau_i),$$ all $f$, with $\psi(t)=\bigl(
t_{i+1}-t\bigr)\cdots\bigl(t_{i+k-1}-t\bigr) \big/(k-1)!$, and $\tau_i$
some arbitrary point in the open interval $(t_i,t_{i+k})$. Then
$$\lambda_i\,B_j = \delta_{ij},\qquad \hbox{all }j.$$\QED

\medskip\hrule\medskip
\centerline{\bf B-SPLINE INTERPOLATION.}
Let $t=\bigl(t_i\bigr)_1^{n+k}$ be a nondecreasing knot sequence with
$t_i<t_{i+k}$, all $i$, and $\bigl(B_i\bigr)_1^n$ the corresponding
B-splines of order $k$. The span ${\cal S}_{k,t}$ of $B_1$, $\ldots$,
$B_n$ is $n$-dimensional. Given a strictly increasing sequence $\tau=
\bigl(\tau_i\bigr)_1^n$ and function $g$, the problem is to find $f\in
{\cal S}_{k,t}$ such that $f(\tau_i)=g(\tau_i)$ $\forall i$. Or, find
spline coefficients $\alpha_j$ such that
$$\sum_{j=1}^n \alpha_jB_j(\tau_i)=g(\tau_i), \qquad i=1,\ldots,n.$$

\noindent{\bf Theorem (Sch\"onberg, Whitney)}. The matrix $\bigl(
B_j(\tau_i)\bigr)$ is invertible $\Leftrightarrow$ $$B_i(\tau_i)\ne0,
\qquad i=1,\ldots,n,$$i.e., $t_i<\tau_i<t_{i+k}$, all $i$.

\noindent{\bf Theorem (Karlin)}. The matrix $\bigl(B_j(\tau_i)\bigr)$ is
totally positive (all minors $\ge0$).

\noindent{\bf Observation}. $\bigl(B_j(\tau_i)\bigr)$ has bandwidth less
than $k$ if $t_i<\tau_i<t_{i+k}$, all $i$.

\vfil\eject