A comment on Ewald Quak’s “About B-splines”

Carl de Boor\(^\ast \)

June 6, 2016.

\(^\ast \)University of Wisconsin, Department of Computer Sciences, e-mail deboor@cs.wisc.edu, crdeboor@gmail.com.

The early contributions to B-spline theory by Tiberiu Popoviciu and by Liubomir Chakalov are recalled.

MSC. 41-XX, 65-XX, 60-XX.

Keywords. B-spline, B-spline recurrence, Marsden’s identity, knot insertion, Popoviciu, Chakalov.

The publication of a paper on the many aspects of B-splines in this journal suggests adding a comment on the contributions to B-splines made by this journal’s founder, Tiberiu Popoviciu.

Briefly, in his paper [ P34b ] on \(n\)-convex functions (a terminology he introduced), Povoviciu proves the recurrence relation for B-splines (see [ Q , (42) ] ), Marsden’s identity (see [ Q , p.46 ] ), and mentions without proof that the B-splines form a generating set for what he calls elementary functions of degree \(n\) with \(m\) vertices by which he means smooth functions whose \((n-1)\)st derivative is a continuous broken line with \(m-2\) interior breaks. In addition, you can find in [ P34a ] Boehm’s formula for knot insertion (if you know what to look for).

To be a bit more explicit (as laid out in [ BP03 ] ), Popoviciu introduces (see [ P34b , p.89 ] ), for a given strictly increasing sequence \(x_1{\lt}\cdots {\lt}x_m\), certain piecewise polynomial functions \(\Psi _i\) with support in the interval 1 \((x_i\mathbin {\ldotp \ldotp }x_{i+n+1})\), \(i=1,\ldots ,m-n-1\), of degree \(\le n\), and proves (see [ P34b , p.93 ] ) the relation

\begin{equation} (x_{n+i+1}-x_i)\Psi _i(x) = (x-x_i)\Psi '_i(x)+(x_{n+i+1}-x)\Psi _{i+1}'(x), \label{recurrence} \end{equation}
1

with, as he writes, the \(\Psi _i'\) defined just like the \(\Psi _i\) except that \(n\) is replaced by \(n-1\). Compare (1) with the well-known recurrence relation (see [ Q , (42) ] )

\[ B_{i,n+1} = \omega _{i,n+1}B_{in} + (1-\omega _{i+1,n+1})B_{i+1,n}, \qquad \omega _{i,n+1}(x):=\tfrac {x-x_i}{ x_{i+n}-x_i} \]

in which \(B_{jk}\) is the B-spline with knots \(x_j,\ldots ,x_{j+k}\) (normalized to be part of a partition of unity), and add to that the fact that Popoviciu’s formula for \(\Psi _i\) readily reduces to \(\Psi _i=\chi _{\lower 3pt\hbox{$\scriptstyle (x_i\mathbin {\ldotp \ldotp }x_{i+1})$}}\) for \(n=0\), to conclude that, for given \(n\), \((x_{i+n+1}-x_i)\Psi _i=B_{i,n+1}\). In fact, since Popoviciu’s formula for \(\Psi _i\) involves ratios of Vandermonde determinants, it is not that hard to derive directly that

\begin{equation} \Psi _i(x) = \mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(x_i,\ldots ,x_{i+n+1})}(\cdot -x)_+^n \label{bspline} \end{equation}
2

with \(\mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(x_i,\ldots ,x_{i+n+1})}=[x_i,\ldots ,x_{i+n+1}]\) the divided difference 2 functional at the nodes \(x_i,\ldots ,x_{i+n+1}\) (provided one knows the handy notation \((\cdot -a)_+^n\) for the \(n\)th truncated power). The simple formula (2) could have been of help in simplifying some of Popoviciu’s arguments concerning \(n\)-convexity. It could also have readily supplied the fact (not proved in the paper) that the \(\Psi _i\) have all derivatives of order \({\lt}n\) continuous.

Popoviciu uses the recurrence relation (1) to prove the positivity of the \(\Psi _i\) on their support, as well as the following formula (see [ P34b , p.93 ] )

\begin{equation} \sum _{i=1}^{n+1}(x_{i+n+1}-x_i)\Psi _i(\xi )(x-x_{i+1})\cdots (x-x_{i+n})= (x-\xi )^n \label{marsden} \end{equation}
3

which we now call Marsden’s identity because of [ Ma70 ] .

While the sequence \(x_1,\ldots ,x_m\) starts out strictly increasing, in the last section of [ P34b ] all is specialized to the case

\[ x_1=\cdots =x_{n+1}=a {\lt} b= x_{n+2}=\cdots =x_{2n+2} \]

which we now associate with the names Bernstein and Bézier.

Finally, on page 7 of [ P34a ] , Popoviciu uses induction to derive from the formula

\begin{equation} (t_n-t_0)\mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(t_0,\ldots ,t_n)} = (t_n -\xi )\mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(\xi ,t_1,\ldots ,t_n)}+(\xi -t_0)\mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(t_0,\ldots ,t_{n-1},\xi )} \label{knotinsert} \end{equation}
4

the fact that, for an increasing refinement \(\sigma \) of the increasing sequence \(\tau \),

\begin{equation} \mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(\tau _0,\ldots ,\tau _n)} = \sum _j\alpha _j(\tau ,\sigma )\mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(\sigma _j,\ldots ,\sigma _{j+n})}\label{oslo} \end{equation}
5

with the coefficients \(\alpha _j(\tau ,\sigma )\) nonnegative and summing to 1. Given formula (2), you will recognize in (4) Boehm’s now standard formula for knot insertion, and in (5) a formula for expressing the B-spline with knots \(\tau _0,\ldots ,\tau _n\) in terms of B-splines of the same order on a finer knot sequence \(\sigma \).

Another early contributor to B-splines is Liubomir Chakalov who studied (see [ C38 ] or its discussion in [ BP03 ] ) B-splines in the sense that he focused on the Peano kernel \(u\) in the integral representation

\[ \mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(x_1,\ldots ,x_{n+1})}f = \int u(s) D^nf(s)\, {\rm d}s \]

of the divided difference. Necessarily,

\[ u(x) = \mathord {\setbox 0=\hbox{$\Delta $}\dimen 0=\wd 0\divide \dimen 0 by 2 \kern \dimen 0\vrule height\ht 0 depth\dp 0 width.5pt\kern -.25pt\kern -\dimen 0\box 0(x_1,\ldots ,x_{n+1})}(\cdot -x)_+^{n-1}/(n-1)! \]

hence, by (2) (see also [ Q , p.22 ] ), \(u\) is a B-spline,

\[ u=B_{1n}/((x_{n+1}-x_1)(n-1)!). \]

Chakalov provides the B-spline recurrence relation in a form that involves a derivative and, more importantly, provides the representation

\[ u(x) = \tfrac 1{2\pi {\rm i}}\int _C \tfrac {(z-x)^{n-1}\, {\rm d}z}{(n-1)!\prod \limits _{j=1}^{n+1}(z-x_j)} \]

of this B-spline in terms of a contour integral (with the contour \(C\) dependent on \(x\) and the \(x_i\)) which was rediscovered many years later by Meinardus and put to good use in [ Me74 ] .

[ Q ] mentions Sommerfeld, and could have mentioned Favard, and even Laplace, as people who, like Popoviciu and Chakalov, came across B-splines in their work well before (Curry and) Schoenberg, although Popoviciu and Chakalov are the only ones I am aware of who developed the B-spline recurrence relations. It seems that it is not enough to have a good idea or insight. One needs, like Schoenberg, the appreciation and courage to develop the idea systematically, make its objects mathematically presentable by giving them names, and give them much exposure in many papers.

Bibliography

B80

W. Boehm, Inserting new knots into B-spline curves, Computer-Aided Design , 12 (1980) no. 4, pp.199–201. \includegraphics[scale=0.1]{ext-link.png}

BP03

C. de Boor and A. Pinkus, The B-spline recurrence relations of Chakalov and of Popoviciu, J. Approx. Theory, 124 (2003) no. 1, pp.115–123. \includegraphics[scale=0.1]{ext-link.png}

C38

L. Chakalov, On a certain presentation of the Newton divided differences in interpolation theory and it applications, Annuaire Univ. Sofia, Fiz. Mat. Fakultet, 34 (1938), pp.353–394 (in Bulgarian).

Ma70

M.J. Marsden, An identity for spline functions with applications to variation-diminishing spline approximation, J. Approx. Theory, 3 (1970), pp.7–49. \includegraphics[scale=0.1]{ext-link.png}

Me74

G. Meinardus , Bemerkungen zur Theorie der B-Splines, in Spline-Funktionen (K. Böhmer, G. Meinardus, and W. Schempp Eds.), Bibliographisches Institut (Mannheim), 1974, pp.165–175.

P34a

T. Popoviciu, Sur quelques propriétés des fonctions d’une ou de deux variables réelles, Mathematica, 8 (1934), pp.1–85. Retrieved on October 3rd, 2016, from http://ictp.acad.ro/popoviciu \includegraphics[scale=0.1]{ext-link.png} \includegraphics[scale=0.06]{auth-homepage-link.png}

P34b

T. Popoviciu, Sur le prolongement des fonctions convexes d’ordre superieur, Bull. Math. Soc. Roumaine des Sc., 36 (1934), pp.75–108. Retrieved on October 3rd, 2016, from http://ictp.acad.ro/popoviciu \includegraphics[scale=0.1]{ext-link.png} \includegraphics[scale=0.06]{auth-homepage-link.png}

Q

E. Quak, About B-splines. Twenty answers to one question: What is the cubic B-spline for the knots -2,-1,0,1,2? , J. Numer. Anal. Approx. Theory, 45 (2016) no. 1, pp.37–83. \includegraphics[scale=0.1]{ext-link.png}

S64

I.J. Schoenberg, Spline functions and the problem of graduation, Proc. Amer. Math. Soc., 52 (1964), pp.947–950. \includegraphics[scale=0.1]{ext-link.png}

  1. I was pleased to see already in Popoviciu’s article this handy use of \(\mathbin {\ldotp \ldotp }\) in the description of an interval.
  2. I was pleased to see this literal notation for divided differences already in [ S64 ] .