Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying the basic recursion formula for generating B-Spline basis functions N(i,j) of a given degree from the basis for the lower degree, and puzzling at the magic.

In particular what I am having a hard time getting through my head is why the new functions obtained have one more degree of continuity (at knots) than the next lower degree. It's obvious that the degree is elevated, but it's not obvious where this continuity is coming from at the knot.

Consider the degree one basis functions. They are piecewise linear functions with slope discontinuities at the knots. How is it that taking a linear combination of these functions gives a piecewise quadratic which has a continuous slope at the knots?

Where is this magic coming from?!!

Thanks!

share|improve this question
    
Could you please provide a formula for the linear combination? Perhaps it then becomes clear that the coefficients are not constant or that convolution is involved. –  LutzL Feb 21 at 16:24
    
The coefficients are linear functions. –  bubba Feb 23 at 3:18

2 Answers 2

up vote 0 down vote accepted

This is the magic of b-splines.

It's not too difficult to see if you examine the progression from degree zero (step functions) to degree one (hat functions).

Take a linear combination of two step functions, with arbitrary coefficients, and write down the conditions that will need to be satisfied in order for the linear combination to be continuous. See what this implies about the coefficients used in the linear combination. You will find that the coefficients have to be the ones used in the b-spline definition -- these coefficients are the only ones that give the magic increase in continuity.

Here are the details.

Suppose $u < v < w$ are three knot values. Let $H(t) = 0$ for $ t \in [u,v)$ and zero elsewhere, and let $K(t) = 0$ for $ t \in [v,w)$ and zero elsewhere. The functions $H$ and $K$ are the b-spline basis functions of degree zero defined by the knots $u,v,w$. We want to construct a b-spline basis function $F$ of degree one. This will be a piecewise linear function that is a linear combination of $H$ and $K$ and is continuous.

So, suppose $$ F(t) = (at+b)H(t) + (ct + d)K(t) $$ where $a,b,c,d$ are constants that we will calculate. Clearly $F(t)=0$ for $t \notin [u,w)$, regardless of our choices for $a,b,c,d$. Then $$ F(u+) = 0 \quad \Rightarrow \quad au + b = 0 \\ F(w-) = 0 \quad \Rightarrow \quad cw + d = 0 \\ $$ Rather than just requiring $F(v-) = F(v+)$, we're going to require that $F(v-) = F(v+) = 1$. This makes $F$ continuous at $t=v$ and also correctly normalizes the height of $F$. Then $$ F(v-) = 1 \quad \Rightarrow \quad av + b = 1 \\ F(v+) = 1 \quad \Rightarrow \quad cv + d = 1 \\ $$ We now have four linear equations that we can solve for $a,b,c,d$. The solutions are: $$ a = \frac{1}{v-u} \quad ; \quad b = \frac{-u}{v-u} \\ c = \frac{-1}{w-v} \quad ; \quad d = \frac{w}{w-v} \\ $$ Substituting these into the formula for $F$, we get $$ F(t) = \frac{t-u}{v-u}H(t) + \frac{w-t}{w-v}K(t) $$ which is a simplified special case of the the deBoor-Cox formula.

To get a bit more insight, draw the graphs of $H, K, F$. To get $F(u) = 0$ and $F(v-) = 1$, I think it's clear that the "multiplier" $at+b$ has to be a linear "ramp" function that is zero at $t=u$ and 1 at $t=v$. In other words, it must be $\tfrac{t-u}{v-u}$.

I suspect you could do similar constructions with higher-degree basis functions, but the details would be messier.

The typical description of b-splines pulls the deBoor-Cox formula out of thin air, and then proceeds to prove that it gives functions with the desired continuity properties. Unfortunately, this sort of "magic" is common in mathematics. It's natural to ask (as you did) why such a definition would ever occur to anyone. The reasoning above shows (I hope) that the deBoor-Cox formula is the only one that works, given the continuity and normalization requirements. It's not magic, it's just an inevitable consequence of the constraints.

share|improve this answer
    
I see what you're getting at, but I am not sure I follow exactly. Consider two step functions $N_{0,0}(u)$, and $N_{0,1}(u)$, where the first is equal to 1 on the interval $u \in [0,1]$ and the second on the interval $u \in [1,2]$. If we want a linear combination of them that a) increases their polynomial degree, $(au+b)N_{0,0}(u)+(cu+d)N_{0,1}(u)$, and b) is continuous at $u = 1$, then we have $(a+b) = (c+d)$. To get the Cox-de Boor relation, we would also have to require $b = 0$, etc.. Am I on the right track here? –  user130112 Feb 22 at 21:34
    
Yes, that's what I was suggesting. To be honest, I've never gone through the computations myself; I just assumed it would work out. I'll take a closer look. Clearly some linear combination (the deBoor-Cox one) will work. My point was that this is essentially the only one that will work. In other words, the formula is inevitable. –  bubba Feb 22 at 23:50
    
Thanks Bubba, that's exactly what I was looking for. I'd up vote your answer, but I don't seem to have enough points. –  user130112 Feb 26 at 18:39
    
If you want to, you can "accept" the answer, I think, instead of upvoting it (or, in addition to upvoting it). Click on the check-mark (or the tick-mark if you're British). –  bubba Feb 27 at 1:01

Splines satisfy many more identities than the Cox-de Boor relations. As an example, the cardinal B-splines $B_n(x)$ of degree $n-1$ and support $[0,n]$ also satisfy

$$B_{n+1}'(x)=B_n(x)-B_n(x-1).$$

This relation directly shows that smoothness increases with degree.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.