whereλis a fixed constant. The solution to this problem is a natural cubic spline (natural meaning f′′(x1) = f′′(xN) = 0), with the knots sequence {x(i)}Ni=1. Even though this is not what we do here it gives some support to the choice of m = 3. A remark here is that even though N is large the efficient degrees of freedom is far less than N. It is clear that there are many ways to make spline basis functions, one quit intuitively way is to use the truncated power series
s(x) = θ−m+θ−m+1x+· · ·+θ0xm+
n
X
j=1
θj(x−tj)m+, x∈R
=
n
X
j=−m
θjsj(x) (3.3)
this is clearly a spline of degreem. If there is no knots this is just a polynomial of degreem. It is also seen that there aren+m+1 degrees of freedom. In Definition 3.1 there aren+ 1 intervals and the polynomials on each interval havem+ 1 parameters, and there aremrestrictions per knot. With (n+ 1)(m+ 1)−mn= n+m+ 1 and since thesj’s are linearly independent, we actually have a basis forSm(t1, ..., tn).
Each of the basis functions in (3.3) have support on a infinite interval and are strictly increasing as a function of the distance fromtj, so they grow fast. There-fore each of the basis functions can become very large, and as a consequence this can course numerical problems.
These problems are solved with the B-spline basis functions, which only have support in the interval [tj, tj+m+1], so we don’t have the problem of the basis functions going to∞. Further theB-spline basis functions does not have values outside the interval [0,1].
The rest of this chapter will concentrate on the properties of B-spline basis functions. To be able to derive the basis functions and their properties in a quite simple notational setting, it is convenient to introducedivided differences.
This presentation of divided differences follows [6], but only the results needed for the description ofB-splines basis functions are stated, and some of the results are stated and proved in a less general setting than in [6].
3.2 Divided Differences and B-splines
When we are not interested in the actual construction of the B-spline basis functions, but merely in the properties of these, divided differences as defined below give a convenient way of introducingB-spline basis functions.
This sections starts by the definition of divided differences and a little on how to calculate these in order to get a feeling of what they are and how to work with them.
Definition 3.2 Thek-th divided difference of a functiongat the pointstj, ..., tj+k
is the leading coefficient (i.e. the coefficient of xk) of the polynomial of degree k which agrees withg attj, ..., tj+k. It is denoted
[tj, ..., tj+k]g (3.4)
It is maybe not very clear from the definition what this object is. By establishing the existence and uniqueness of this, we can get some feeling of what it is, especially the existence give a direct interpretation of this. The uniqueness and existence of this is of course important in its own right, because it ensures the existence and uniqueness of divided differences.
In order to do this define Pn as the space of all polynomials of degreen, i.e.
pn(x) ∈ Pn ⇒ pn(x) = Pn
j=0ajxj. For a given sequence of distinct points t ={t}n+1j=1 and a function g, there is exactly one polynomial pn(x) ∈ Pn for whichpn(tj) =g(tj) forj∈1,2..., n+ 1. In order to see the uniqueness consider another polynomial qn(x) ∈ Pn, with qn(tj) = g(tj) j = 1, ..., n+ 1, then pn(x)−qn(x) is a polynomial of degree nwithn+ 1 roots, which must be the zero function.
To realize the existence of such a polynomial, define the set of integers between 1 andn+ 1 both included and take away the numberj from this set, or more formal Jj ={1, ..., j−1, j+ 1, .., n+ 1} and look at the polynomial, which is
Now that we have established the existence and uniqueness of divided differ-ences, we can actually write down the divide difference of a functiong as
[t1, ..., tn+1]g= [t1, ..., tn+1]pn= So from the Lagrange form we can get the divided difference directly without calculating the entire polynomial.
3.2 Divided Differences and B-splines 35
In Definition 3.2 it is not required that the points tj, ..., tj+k are distinct. If there are multiple points, then the termagrees means: if there ismpoints that coincide attthenpandgagree m-fold att i.e.
p(j−1)(t) =g(j−1)(t) forj= 1, ..., m
This property is used when working with the boundary conditions later on.
The next example gives complete calculation of the divided differences for a specific function and a knot sequence, and also offers a more complete derivation of (3.6).
Example 3.1 (Divided difference of sin(x)) Look at the functiong(x) = sin(x) and the knot sequencet={0,π4,π2,3π4,1}, this give{g(ti)}5i=1={0,√22,1,√22,0}. From the Lagrange form (3.5) we immediately get that the interpolating poly-nomial of degree 4 which agrees or interpolate g(x) at the points in t, can be written as (O(x3) means terms of degree 3 or less)
3π4 . This example illustrates how to get (3.6).
The definition of theB-spline is given in terms of divided differences, the defi-nition can be given in other ways. Theorem3.1below gives an alternative but equivalent definition.
0 2 4 6 8 10
0.00.20.40.60.81.0
1 1 1
1 1 1 1 1111
B1
B2 B3
B4
Figure 3.1: The figure illustrates how the B-spline basis functions behave when influenced by knots of different multiplicity. The knot sequence is t={0,0,0,0,5,7,9,10}. So B1 see a knot with multiplicity 4, B2 see a knot with multiplicity 3,B3 see a knot with multiplicity 2 and B4 see only isolated knots. So this should illustrate the influence of knots with multiplicity greater than one. It should be noted that this is only the first 4 basis functions for the interval [0,10]. In order to span the space of all spline functions in this interval we would need 3 more basis functions, but only the 4 first have been plotted to make the properties of the single basis functions more clear.
Definition 3.3 The j-th normalizedB-spline of degreek+1for a nondecreasing knot sequencetis defined as
Bj,k,t(x) = (tj+k−tj)[tj, ..., tj+k](· −x)k−+ 1∀x∈R (3.9) The “·” means that the divided difference is to be taken w.r.t. the “·”, which is a place holder for the considered function , whilexis considered as a constant.
The function (x)k−+ 1 should be read ((x)+)k−1is defined by (x)+=
x for x≥0
0 otherwise (3.10)
Normalized here refers to the fact that P
iBi,k,t = 1 for x ∈ [tj1+k, tjn−k].
This fact will not be proved here, but it is quit straight forward by use of the same technique as used to calculate the value of the integral over one spline (see Section3.3), or look at p. 110 in [6].
Since it will normally be clear from the context whatkandtare, theB-splines basis functions will often just be denoted Bj. The normalized B-splines basis functions are often, see e.g. [8], denotedNj.
Figure3.1shows the cubic (k= 4)B-spline basis functions for a knot sequence
3.2 Divided Differences and B-splines 37
as indicated on thex-axis. Note that these do not span the space of all spline functions in the interval, since we would need 3 more basis functions to span this space or equivalent 3 knots greater than or equal to 10.
The knot atx= 0 have multiplicity 4, so the figure should illustrate how multiple knots influence theB-spline basis functions. It is seen that e.g. B1 is not even continuous atx= 0.
Figure3.2goes into some more details about this point. It is seen that the basis functions are all less than one. They are zero outside the interval [0,10], and we therefore do not have the problems that was outlined for the truncated power series.
To prove that theB-spline is actually a spline, some properties of divided dif-ferences is needed. Some of these properties will also be used when deriving the derivative and integral of the B-spline. These properties can also be used to make a more constructive definition ofB-splines, and hence this is done in the next theorem.
Consider pj ∈ Pj (for the definition of Pj see the discussion right after Defi-nition 3.2) the interpolating polynomial for the pair (tj, g), tj ={tl}jl=1. One representation of an interpolating polynomial ofg onnpoint is
pn(x) = p0(x) + (p1(x)−p0(x)) +· · ·+ (pn(x)−pn−1(x))
= [t1]g+ (x−t1)[t1, t2]g+· · ·
+(x−t1)· · ·(x−tn−1)[t1, ..., tn]g (3.11) where the second equality follows directly from the definition of divided dif-ferences, or it can be found by writing down (3.5) and (3.6) explicitly, as an illustration this is done forp1(x)−p0(x) we get
(3.11) is also called the Newton form. This representation will be independent of the order in which we take the pointstj, sopn could also be written as
pn(x) = [tn]g+ (x−tn)[tn, t1]g+· · ·
+(x−tn)(x−t1)· · ·(x−tn−2)[t1, ..., tn]g (3.12)
by equating coefficients ofxn−2in (3.11) and (3.12) we get [t1, ..., tn−1]g−(tn−2+tn−1)[t1, ..., tn]g = [tn, t1, ..., tn−2]g
−(tn+tn−2)[t1, ..., tn]g Sincenwas arbitrary, this gives the formula for distinct points
[t1, ..., tn]g= [t1, ..., tj−1, tj+1, ..., tn]g−[t1, ..., tl−1, tl+1, ..., tn]g tl−tj
(3.13) if tj = tj+1 = · · · = tj+r then the corresponding formula is [tj, ...tj+1]g = g(r)(tj). This follows from taking limits in (3.13) and by using the fact that [tj]g=g(tj). Forg differentiable att1, this give
t1lim→t2
[t1, t2]g= lim
t1→t2
g(t2)−g(t1)
t2−t1 =g′(t1)
From (3.13) it follows immediately thatB-splines can be written as
Bj,k,t(x) = [tj+1, ...tj+k](· −x)k−+ 1−[tj, ...tj+k−1](· −x)k−+ 1 (3.14) Now by using (3.13), it is clear that the divided differences can be written as
[t1, ..., tn]g=
n
X
j=1
cjg(tj) (3.15)
where cj depends on{t}nj=1 but not ong. This is useful to show properties of theB-spline basis functions and its derivatives without having to calculate the actual values of divided differences, which can be quite involved.
The presentation given so far, is rather abstract and does not really offer an intuitive feeling of the construction of B-spline basis functions. It is however convenient if we want to prove properties of the B-spline basis functions. The-orem3.1below gives, by the use of formula (3.6) and (3.14) a direct recursive formula for calculations ofB-spline basis functions. As a remark this shows the correspondence between the introduction of theB-splines in [6] and [8].
Theorem3.1 is not really used in this presentation, since the focus here is the-oretical properties ofB-splines and construction of splines with special bound-ary conditions from B-spline basis functions and, not the direct construction of B-splines. However the theorem perhaps offers a more direct and intuitive definition ofB-spline.
Theorem 3.1 Define Mj,k = tj+kBj,k−tj, then the following recursive formula
3.2 Divided Differences and B-splines 39
holds
Mj,1(x) = I[tj≤x<tj+1](x) tj−tj+1
Mj,k(x) = (tj+k−x)Mj+1,k−1(x)−(tj−x)Mj,k−1(x) tj+k−tj
k >1 andBj,k= (ti+k−ti)Mi,k.
The proof of this is rather long, and is therefore placed in appendix A.1, but the idea is to use (3.6), (3.14) and the definition of divided differences.
With the tools developed above, we can prove the following theorem, which shows thatB-spline basis functions (under some constraint) are actually splines.
The theorem will be used to prove thatB-spline basis functions are actually basis functions.
Theorem 3.2 If tis a (strictly) increasing sequence of knots, then Bj,k,t is a spline of degreek−1.
Proof. Using the properties of divided differences derived above it is easy to write down the derivatives ofBj
Bj(x) =
k
X
l=1
cj+l(tj+l−x)k−+ 1
B′j(x) = −(k−1)
k
X
l=1
cj+l(tj+1−x)k−+ 2 ...
Bj(k−1)(x) = (−1)k−1(k−1)!
k
X
l=1
cj+lI[x≤tj+l](x)
Since (tl−t+j)h+ = (tl−t−j)h+ forh > 0, it follow directly that the firstk−2 derivatives are continuous, and thatBj are polynomials of degree at mostk−1 on each interval defined by the knot sequence and the intervals (−∞, t1] and
[tn,∞).
Theorem 3.2tells us that theB-spline basis functions are really splines, under the condition that the knot sequence is strictly increasing. It does not, however prove that the B-spline basis functions form a basis of the space of all spline
0 2 4 6 8 basis functions from Figure3.1and its 2 first derivative, and illustrate in greater detail than figure 3.1 how the knot with multiplicity 4 at x = 0 effects the smoothness of the splines.
functions. This is the subject of the next theorem, but first a brief discussion of some of the consequences of the properties developed above is given.
Actually theB-spline basis functions does not span the space of all spline func-tions when just calculated from the knot sequence defined in Theorem3.2. This can be seen from the fact that all theB-spline basis functions are zero outside the interval [t1, tn]. The trick is now to add some extra knots outside the inter-val (t1, tn), which will be referred to as outer knots. Exactly how this should be done will be discussed later, but an important point is that we allow knots of multiplicity greater than one for these outer knots.
The consequence of knots with multiplicity higher than one, is that theB-spline basis function is actually not a spline over this knot. This have already been seen in Figure3.1. This is also the reason why we do not, calculate theB-splines outside the interval [t1, tn] (and e.g “R” do not support values here). Figure3.2, where theB-spline basis functions from Figure3.1and their first two derivative is plotted, goes into more details on this point.
To fully appreciate Figure3.2 it should be noted thatBj and all its derivative is zero outside the interval [tj, tj+k]. This follows directly from the definition of divided differences and the fact that (tj−x)k−1+ is a polynomial of degreek−1 in the interval (−∞, tj] and zero in the interval [tj+k,∞).
With this in mind the figure shows how many of the derivatives are continuous for each of the basis functions. It is seen thatB1 is not continuous,B′2 is not continuous and B3′′ is not continuous, whileB(p)4 is continuous forp = 0,1,2.
3.2 Divided Differences and B-splines 41
SoB1, B2, B3are not spline functions over the knot atx= 0.
Hence the figure illustrate the effect of multiple knots, and that we can not allow multiple knots for a spline basis function overR. Therefore we only define theB-spline basis function in the interval [t1, tn] and then add outer knots, the B-spline basis functions will span the space of all spline functions in the interval [t1, tn].
This is stated more precisely in the following theorem, which is a modification of Theorem IX.1 in [6].
Theorem 3.3 Ift1={tj}nj=1is a strictly increasing sequence andt−={tj}0j=1−k+1
and t+ ={tj}n−j=n+11+k are two nondecreasing sequences witht0 ≤t1 andtn+1 ≥ tn, then the sequence{Bj,k,t}nj=2−1−k, witht={t−,t1,t+}, ofB-splines span the restriction of Sˆk−1(t)tox∈[t1, tn]
The restriction here means that the conditions in Definition 3.1 hold for x∈ (t1, tn). In the following t1 will be referred to as the defining knot sequence, {t+,t−}will be referred to as outer knot sequences,{tj}n−1j=2 the interior knots, and{t1, tn} the boundary knots. Now the proof of Theorem3.3is given Proof. That{Bj,k,t}n−1j=2−k belongs to the restriction of ˆSk−1(t) tox∈[x1, xn] follows from Theorem3.2. The spline functions in each of the intervals defined byt1can be written asPk
l=1al([tj, tj+1])xl−1 (i.e. al([tj, tj+1]),j= 1, ...n−1, is to be seen as a function of the interval), this gives k(n−1), (n−1 = the number of intervals) parameters. There arek−1 restrictions per interior knot andn−2 interior knot, this givesk(n−1)−(k−1)(n−2) =n+k−2 degrees of freedom, and the number ofB-splines isn−1−(2−k) + 1 =n+k−2. So if theB-splines are linearly independent, then the theorem is proved. To see this, take Bj and look at xin the interval [tj, tj+1], j > 0, the only other nonzero B-splines in that interval is Bj−k+1, ..., Bj−1, i.e. k−1 of them.
Now it follows from (3.15) thatBj can be written as Bj(x) =Pk
l=1blxl−1 for somebl, this givesk bl’s. So we are short of one free parameter. If we should be able to writeBj as a linear combination ofBj−k+1, ..., Bj−1then we would have to impose some restriction on each of thebl’s, but since these depend on different parts of the knot sequence, this would be the same as putting restrictions on the knot sequence, the conditions have to be true for all knot sequences. The
theorem is hereby proved.
Theorem 3.3 shows that the B-spline basis functions span the space ˆSk when
restricted to the interval defined by t1. Theorem 3.3 therefore provides the justification for usingB-splines instead of e.g. the truncated power series. This justify the use of the termbasis functions.
The advantage of theB-spline basis functions over the truncated power series have been implied through out the text. These are taken here again as a conclu-sion of why the B-spline are superior, at least from a numerical point of view.
B-spline basis function have small support (over k+1 knots) while the basis function from the truncated power series have support over all knots to the right of the defining knot. |Bj(x)| ≤1 for allxandj, while the basis function for the truncated power series can be very large (e.g. one of the basis functions isxk−1).
The next part of this section looks at differentiations and integration ofB-spline basis functions. It will be assumed that the knot sequencetis as in the Theorem 3.3, and thatx∈[t1, tn].