Total Positivity Properties of LB-splines

Tom Lyche and Larry L. Schumaker

Abstract. A basic property of both polynomial and more general Tchebycheffian splines is that the associated B-spline collocation matrix has certain total positivity properties, and it is nonsingular if and only if well-known interlacing conditions hold. Using a technique from a recent paper of Mørken, we extend these results to L-splines.

§1. Introduction

One of the most important properties of classical polynomial B-splines is the fact that matrices formed from ordered subsets of them by evaluation at a set of (possibly repeated) points always have nonnegative determinants which are positive if and only if the knots and interpolation points interlace appropriately. This property leads to a number of important facts about splines, including the existence of interpolants and a variation diminishing formula. The analogous total positivity property has been established for Tchebycheffian splines, and a class of generalized B-splines [1], but not for L-splines.

The purpose of this paper is to establish total positivity properties of collocation matrices corresponding to L-splines. Our main motivation is provided by an application to the construction of L-spline wavelets [7]. Our results extend recent work of [2,8].

The organization of this paper is as follows. In Sect. 2 we review L-splines, and in Sect. 3 we state the main theorem of the paper on the positivity of the determinant of the L-spline collocation matrix. Discrete LB-splines are discussed in Sect. 4, while in Sect. 5 we discuss certain lower order LBsplines, and establish a differentiation formula. The proof of the main result is presented in Sect. 6.

§2. L-splines

Before stating the main result of this paper, we need to introduce some notation which we take from [9]. Let I = [a, b] be a closed subinterval of the real line IR. Given functions a_{j} ∈ C^{j}[a, b], j = 0, …, m − 1, let

L := D^{m} + ∑_{j=0}^{m−1} a_{j}D^{j}

be the corresponding linear differential operator of order m, and let L^{∗} be its formal adjoint defined by

L^{∗}f := (−1)^{m}D^{m}f + ∑_{j=0}^{m−1}(−1)^{j}D^{j}(a_{j}f).

We denote the null space of L by

N_{L} := {f ∈ L_{1}^{m}[a, b] : Lf(x) = 0, a ≤ x ≤ b},

where L_{1}^{m}[a, b] is the usual Sobolev space of functions whose m-th derivatives lie in L_{1}[a, b]. Similarly, let N_{L^{∗}} be the null space of L^{∗}. By the assumption on the coefficients of L, both N_{L} and N_{L^{∗}} are m dimensional subspaces of C^{m}[a, b].

To define L-splines, suppose

Δ := {a = x_{0} < x_{1} < ⋯ < x_{κ} < x_{κ+1} = b}

is a partition of I into κ + 1 subintervals, and let M = (m_{1}, …, m_{κ}) be a vector of integers satisfying 1 ≤ m_{i} ≤ m, i = 1, …, κ. Then the associated space of L-splines is defined by

\begin{matrix}S(N_{L}; M; & Δ) := \{s : s|_{(x_{i},x_{i+1})} ∈ N_{L}, i = 0, …, κ, and \\ D_{−}^{j−1}s(x_{i}) = D_{+}^{j−1}s(x_{i}), j = 1, …, m − m_{i}, i = 1, …, κ\}. \end{matrix}

It is well-known that

dim S(N_{L}; M; Δ) = n := ∑_{i=0}^{κ} m_{i},

where m_{0} = m.

It will be convenient to work with the extended knot sequence corresponding to Δ defined by

y := {y_{1} ≤ y_{2} ≤ ⋯ ≤ y_{n+m}},

where

a = y_{1} = ⋯ = y_{m}, y_{n+1} = ⋯ = y_{n+m} = b,

and

{y_{m+1} ≤ ⋯ ≤ y_{n}}

is obtained by repeating each x_{i} a total of m_{i} times, i = 1, …, κ. In the sequel we fix L, and write S_{y} for S(N_{L}; M; Δ).

It is well-known from the theory of ordinary differential equations that there exists a constant h such that on any subinterval J ⊆ I of length less than h, both N_{L} and N_{L^{∗}} are spanned by Extended Complete Tchebycheff (ECT-) systems, see e.g. Theorem 10.5 of [9].

Theorem 2.1. Suppose the extended partition y is such that

y_{i+m} − y_{i} < h,  i = 1, …, n.  (2.1)

Then there exists a unique set of splines {B_{i}}_{i=1}^{n} forming a basis for S_{y} with the properties

1) B_{i}(x) ≡ 0, x ∉ [y_{i}, y_{i+m}],

2) D_{+}^{m−1−r_{i}}B_{i}(y_{i}) = 1,

3) D_{+}^{k}B_{i}(y_{i}) = 0, k = 0, …, m − 2 − r_{i},

4) D_{−}^{k}B_{i}(y_{i+m}) = 0, k = 0, …, m − 2 − ℓ_{i+m}, where

\begin{aligned}ℓ_{i} & := max\{p : y_{i−p} = ⋯ = y_{i}\}. \\ r_{i} & := max\{p : y_{i} = ⋯ = y_{i+p}\}, \end{aligned}  (2.2)

Proof: Let G_{L}(x; y) be the Green’s function associated with L, and let L_{j}^{∗} be the partial adjoint operators defined by

L_{j}^{∗}f := (−1)^{j}D^{j}f + ∑_{k=1}^{j}(−1)^{j−k}D^{j−k}(a_{m−k}f),

for j = 1, …, m. By Theorem 10.15 of [9],

B_{ν,j}(x) = L_{j−1}^{∗}G_{L}(x; x_{ν}), j = 1, …, m_{ν}, ν = 0, …, κ,

form a one-sided basis for S_{y} with the properties

B_{ν,j}(x) = 0, x < x_{ν},  (2.3)
D_{+}^{μ−1}B_{ν,j}(x_{ν}) = δ_{μ,m−j+1}, j, μ = 1, …, m.  (2.4)

Fix 1 ≤ i ≤ n, and suppose

\{y_{i}, …, y_{i+m}\} = \{\overbrace{x_{ℓ}, …, x_{ℓ}}^{n_{ℓ}} < ⋯ < \overbrace{x_{r}, …, x_{r}}^{n_{r}}\}.

By Theorem 10.17 of [9], there exists an LB-spline B_{i} of the form

B_{i}(x) = ∑_{ν=ℓ}^{r} ∑_{j=1}^{n_{ν}} a_{ν,j}^{i}B_{ν,j}(x)

with property 1). In view of (2.3) and (2.4),

D_{+}^{m−1−r_{i}}B_{i}(y_{i}) = ∑_{j=1}^{n_{ℓ}} a_{ℓ,j}^{i}D_{+}^{m−1−r_{i}}B_{ℓ,j}(y_{i}) = a_{ℓ,r_{i}+1}^{i}.

The hypothesis (2.1) assures that y_{i}, …, y_{i+m} are contained in an interval J where the null space of L^{∗} is an ECT system, and so in the construction of B_{i} in equation (10.35) of [9], a_{ℓ,r_{i}+1}^{i} ≠ 0. Now replacing B_{i} by B_{i}/a_{ℓ,r_{i}+1}^{i}, we get an LB-spline with property 2). Since this LB-spline belongs to S_{y}, it also has properties 3) and 4). Theorem 10.17 of [9] also shows that the {B_{i}}_{i=1}^{n} form a basis for S_{y}.

We turn now to the uniqueness assertion. Using Lemma 10.16 and the argument of Theorem 4.18 of [9], it is easy to see that the B_{i} are locally linearly independent in the sense that they are linearly independent on each nonempty subinterval of the form [y_{j}, y_{j+1}]. Fix 1 ≤ i ≤ n, and suppose B̃_{i} is a nontrivial spline in S_{y} satisfying 1) – 4). Then B̃_{i} must be a linear combination of B_{1}, …, B_{n}. In view of 1), 3), and 4) and the local linear independence of the B_{i}’s, it follows that B̃_{i} = cB_{i} for some constant c. Now property 2) implies c = 1, and the proof of uniqueness is complete.

§3. The Main Result

For any given prescribed real numbers a ≤ ξ_{1} ≤ ⋯ ≤ ξ_{q} ≤ b and functions f_{1}, …, f_{q} defined on the interval I, the associated collocation matrix is

M ( \begin{matrix}ξ_{1}, & ⋯ & , ξ_{q} \\ f_{1}, & ⋯ & , f_{q} \end{matrix} ) := (D_{+}^{d_{i}}f_{j}(ξ_{i}))_{i,j=1}^{q},

where

d_{i} := max{j : ξ_{i} = ⋯ = ξ_{i−j}}  (3.1)

for all i. We denote the determinant of this matrix by

D ( \begin{matrix}ξ_{1}, & ⋯ & , ξ_{q} \\ f_{1}, & ⋯ & , f_{q} \end{matrix} ) .  (3.2)

We can now state the main result of this paper. It is proved in Sect. 6 below.

Theorem 3.1. Suppose (2.1) holds. Then for any 1 ≤ q ≤ n and any 1 ≤ ν_{1} < ⋯ < ν_{q} ≤ n,

D ( \begin{matrix}ξ_{1}, & ⋯ & , ξ_{q} \\ B_{ν_{1}}, & ⋯ & , B_{ν_{q}} \end{matrix} ) ≥ 0,  (3.3)

and strict positivity holds if and only if

ξ_{i} ∈ (y_{ν_{i}}, y_{ν_{i}+m}) ∪ {x : D_{+}^{d_{i}}B_{ν_{i}}(x) ≠ 0}, i = 1, …, q,  (3.4)

where the d_{i} are defined in (3.1).

§4. Discrete LB-splines

Let

y = {y_{i}}_{i=1}^{n+m}, t = {t_{i}}_{i=1}^{N+m},

be two extended knot sequences with n ≤ N corresponding to partitions of a closed interval I = [a, b]. We assume that hypothesis (2.1) holds for y, and that t is a refinement of y, i.e., y ⊂ t. This implies that the analog of (2.1) also holds for the partition t. We are interested in the spline spaces S_{y} and S_{t}. Since S_{y} is a subspace of S_{t}, any B-spline B_{j,y} associated with y can be written as a linear combination of the B-splines B_{i,t} in S_{t}:

B_{j,y} = ∑_{i=1}^{N} α_{j}(i)B_{i,t}.  (4.1)

For fixed j we consider the α_{j}(i)’s as functions of i and call them discrete LBsplines associated with S_{y} and S_{t}. By the linear independence and uniqueness of the LB-splines, the discrete LB-splines are uniquely defined by (4.1).

In analogy with the polynomial spline case [6], we call the N × n matrix

A = ( \begin{matrix}α_{1}(1) & ⋯ & α_{n}(1) \\ ⋮ & & ⋮ \\ α_{1}(N) & ⋯ & α_{n}(N) \end{matrix} )  (4.2)

the knot insertion matrix. The following result is an extension to discrete LB-splines of the corresponding result for discrete polynomial splines given in [8].

Theorem 4.1. Let q be an integer with 1 ≤ q ≤ n and suppose 1 ≤ i_{1} < ⋯ < i_{q} ≤ N and 1 ≤ ν_{1} < ⋯ < ν_{q} ≤ n are two increasing integer sequences. Let

V := A ( \begin{matrix}i_{1}, & ⋯ & , i_{q} \\ ν_{1}, & ⋯ & , ν_{q} \end{matrix} )  (4.3)

be the q × q submatrix of A corresponding to rows i_{1}, …, i_{q} and columns ν_{1}, …, ν_{q}. Then det V ≥ 0, and strict positivity holds if and only if the following two conditions are satisfied for k = 1, 2, …, q: C1) α_{ν_{k}}(i_{k}) > 0, C2) if m_{y}(t_{i_{k}}) < m_{t}(t_{i_{k}}) and k > d_{k}, then i_{k−d_{k}} < i_{k} − d_{k} − f_{k}, where

d_{k} = m − r_{t}(i_{k}), f_{k} = min{ℓ_{t}(i_{k}), m_{t}(t_{i_{k}}) − m_{y}(t_{i_{k}}) − 1}.

Here

\begin{aligned}ℓ_{t}(i) & := max\{p : t_{i−p} = ⋯ = t_{i}\} \\ r_{t}(i) & := max\{p : t_{i+p} = ⋯ = t_{i}\}, \end{aligned}  (4.4)

and

m_{t}(x) := \{ \begin{matrix}max\{k − p + 1 : x = t_{p} = ⋯ = t_{k}\}, & x ∈ t, \\ 0, & otherwise \end{matrix}

with a similar definition for m_{y}.

Proof: This result follows from Lemmas 4.3, 4.4, and 4.5 below in the same way as Theorem 6 of [8].

Remark 4.2. Condition C1) requires that the diagonal elements of A be positive. This condition is familiar in the polynomial spline case. Condition C2) is specific to discrete B-splines. Loosely speaking, it prevents picking too many consecutive rows from A.

Our first lemma is the analog of Lemma 3 of [8], and deals with properties of the knot insertion matrix A when inserting at most one knot.

Lemma 4.3. If the knot sequences y and t are identical, then α_{j}(i) = δ_{i,j}, for all i, j. If t is obtained from y by inserting one knot z, then

(i) α_{j}(i) = 0 for j < i − 1 and j > i, (ii) α_{i−1}(i) ≥ 0, with strict inequality iff t_{i+m} > z. (iii) α_{i}(i) ≥ 0, with strict inequality iff t_{i} < z.

Proof: When no knots are inserted, clearly A is the identity matrix. Now suppose we insert one knot z satisfying y_{μ} ≤ z < y_{μ+1}. Then

B_{i,y} = α_{i}(i)B_{i,t} + α_{i}(i + 1)B_{i+1,t}  (4.5)

for all i. Indeed, B_{i,y} = B_{i,t} for i < μ − m + 1 while B_{i,y} = B_{i+1,t} for i > μ. Now for μ − m + 1 ≤ i ≤ μ, (i) follows from the local linear independence and smoothness properties of the B_{i,t}.

To prove (ii) and (iii), fix μ − m + 1 ≤ i ≤ μ. Then the support of the two B-splines on the right of (4.5) are contained in the support of the one on the left, and so all three B-splines are actually Tchebycheffian B-splines with respect to a common ECT system, and the assertions follow from Theorem 5.5 and Lemma 2.3 of [5].

Lemma 4.4. The discrete B-splines are nonnegative for all i and j. Moreover, α_{j}(i) > 0 if and only if

(i) t_{i} ≥ y_{j}, (ii) if t_{i} = y_{j} then r_{t}(i) ≤ r_{y}(j), (iii) t_{i+m} ≤ y_{j+m}, (iv) if t_{i+m} = y_{j+m} then ℓ_{y}(j + m) ≥ ℓ_{t}(i + m). Here ℓ_{t} and r_{t} are defined in (4.4).

Proof: Inserting one knot at a time, we see that the knot insertion matrix is a product of bidiagonal matrices which by the discussion above have only nonnegative elements. This establishes the nonnegativity. The proof of the second assertion depends only on the linear independence and support properties of LB-splines, and is exactly the same as in the polynomial case [6].

Lemma 4.5. If y is a subsequence of ρ which is itself a subsequence of t, then the knot insertion matrix from y to t is the product of the knot insertion matrices from ρ to t and y to ρ, i.e., A_{y,t} = A_{ρ,t}A_{y,ρ}.

Proof: This follows by the uniqueness of the discrete LB-splines and the nature of knot insertion.

§5. Lower Order LB-Splines

For later use we show how to express derivatives of LB-splines in terms of certain lower order LB-splines.

Let J be a subinterval of I of length less than h, where h is the constant introduced just before Theorem 2.1. On this subinterval, N_{L} is spanned by an ECT-system U_{m} = {u_{j}}_{j=1}^{m} which we may suppose is in canonical form (see e.g. [9]):

u_{1}(x) :=w_{1}(x)
u_{2}(x) :=w_{1}(x) ∫_{c}^{x} w_{2}(ξ_{2})dξ_{2}
…
u_{m}(x) :=w_{1}(x) ∫_{c}^{x} w_{2}(ξ_{2}) ∫_{c}^{ξ_{2}} … ∫_{c}^{ξ_{m−1}} w_{m}(ξ_{m})dξ_{m} … dξ_{2},

where c is some point in the interval J, and w_{j} are positive weight functions for j = 1, …, m.

In order to define lower order LB-splines, we introduce some lower order differential operators associated with L and the interval J. For each j = 1, …, m, let

L_{j} := w_{1} ⋯ w_{m}D_{m} ⋯ D_{m−j+1}w_{m−j}^{−1} ⋯ w_{1}^{−1}  (5.1)
M_{j} := w_{1} ⋯ w_{j}D_{j} ⋯ D_{1}  (5.2)
N_{j} := w_{1} ⋯ w_{j}Dw_{j}^{−1} ⋯ w_{1}^{−1},  (5.3)

where

D_{j}f := D (\frac{f}{w_{j}} ) .

We note that for j = 0, …, m,

L = w_{1} ⋯ w_{m}D_{m} ⋯ D_{1} = L_{j}M_{m−j},

L_{j} = N_{m} ⋯ N_{m−j+1} = D^{j} + ∑_{i=0}^{j−1} a_{i}^{j}D^{i},

M_{j} = N_{j} ⋯ N_{1} = D^{j} + ∑_{i=0}^{j−1} b_{i}^{j}D^{i},  (5.4)

for certain functions a_{i}^{j} and b_{i}^{j}, and where D_{0} = M_{0} = L_{0} = N_{0} are defined to be the identity operator. It is easy to see that if f is in the null space of L_{j}, then N_{m−j+1}f is in the null space of L_{j−1}.

Lemma 5.1. The function

G_{j}(x, y) := M_{m−j}G_{L}(x; y)

is the Green’s function for L_{j} on J × J. Moreover, G_{j−1} = N_{m−j+1}G_{j}.

Proof: Here, we use the convention that unless stated otherwise, whenever an operator is applied to a function of two variables, it operates on the first variable. Clearly, G_{j}(x; y) ≡ 0 for x < y, and L_{j}G_{j}(x; y) = L_{j}M_{m−j}G_{L}(x; y) = LG_{L}(x; y) = 0 for x ≥ y. Moreover, using (5.4), we have

D^{k−1}G_{j}(x; y)|_{y=x} = D^{k−1}M_{m−j}G_{L}(x; y)|_{y=x} = δ_{j,k}

for all k = 1, …, j.

Given any knots y_{i} ≤ ⋯ ≤ y_{i+j} lying in the interval J, let Q_{i}^{j} be the LBspline of order j associated with the operator L_{j} and the knots y_{i}, …, y_{i+j}. We define Q_{i}^{j} as the zero function if y_{i} = ⋯ = y_{i+j}. Note that the LB-splines B_{i} in the previous sections coincide with Q_{i}^{m}. Each of the Q_{i}^{j} possesses the analogs of properties 1) – 4) of Theorem 2.1. In addition, we note that if for some μ, the knots y_{μ} = ⋯ = y_{μ+j−1} < y_{μ+j} lie in J, then

Q_{i}^{j}(y_{μ}) = 0 for i ≠ μ and Q_{μ}^{j}(y_{μ}) = 1.  (5.5)

We now give formulae for derivatives of LB-splines.

Theorem 5.2. For any 2 ≤ j ≤ m and any y_{i}, …, y_{i+j} lying in J,

N_{m−j+1}Q_{i}^{j} = Q_{i}^{j−1} − γ_{i+1}^{m−j}Q_{i+1}^{j−1},  (5.6)

where γ_{i}^{m−j} > 0. Moreover, if y_{ℓ}, …, y_{r+m} lie in J, then for all j = 0, …, m − 1,

M_{j} ∑_{i=ℓ}^{r} c_{i}B_{i} = ∑_{i=ℓ}^{r+j} c_{i}^{j} Q_{i}^{m−j},  (5.7)

where c_{i}^{0} := c_{i}, and

c_{i}^{j} := c_{i}^{j−1} − γ_{i}^{j−1}c_{i−1}^{j−1}.  (5.8)

Here the operator D appearing in the definitions of N_{j} and M_{j} is to be interpreted as a left or right derivative as appropriate.

Proof: Since N_{m−j+1}Q_{i}^{j} is an L-spline associated with the operator L_{j−1}, it can be written as a linear combination of the Q_{i}^{j−1}. In fact, it follows from the support and smoothness properties of LB-splines that

N_{m−j+1}Q_{i}^{j} = β_{i}^{m−j}Q_{i}^{j−1} − γ_{i+1}^{m−j}Q_{i+1}^{j−1},

for some β_{i}^{m−j} and γ_{i+1}^{m−j}. But in view of Theorem 2.1,

\begin{aligned}D_{+}^{j−2−r_{i}}N_{m−j+1}Q_{i}^{j}(y_{i}) & = 1, \\ D_{+}^{j−2−r_{i}}Q_{i}^{j−1}(y_{i}) & = 1, \\ D_{+}^{j−2−r_{i}}Q_{i+1}^{j−1}(y_{i}) & = 0, \end{aligned}

where r_{i} are defined in (2.2). This implies that β_{i}^{m−j} = 1. A similar argument at y_{i+j} shows that γ_{i+1}^{m−j} > 0. The second assertion follows easily.

§6. Proof of Theorem 3.1

Let E be the determinant in (3.3). The fact that E = 0 when (3.4) does not hold follows from properties 1), 3), and 4) exactly as in the polynomial case, see Theorem 4.71 of [9]. To show that E > 0 when (3.4) hold we follow [8]. The idea of the proof is to identify the determinant E in (3.3) with a determinant (4.3) formed from discrete B-splines. Suppose

ξ_{1} ≤ ⋯ ≤ ξ_{q} := \overbrace{τ_{1}, …, τ_{1}}^{p_{1}+1} < ⋯ < \overbrace{τ_{ℓ}, …, τ_{ℓ}}^{p_{ℓ}+1},

Let t be a refinement of y such that

(i) t contains τ_{1}, …, τ_{ℓ}, (ii) for each q = 0, …, ℓ − 1, the interval (τ_{q}, τ_{q+1}) contains at least one

element from t, (iii) each distinct knot in t occurs precisely m times.

Let μ_{j} be such that

τ_{j} = t_{μ_{j}} = ⋯ = t_{μ_{j}+m−1}, j = 1, …, ℓ.

Fix 1 ≤ j ≤ ℓ, and let τ = τ_{j}, p = p_{j}, and μ = μ_{j}. Then the rows of E corresponding to τ involve derivatives of orders 0, 1, …, p. Forming linear combinations of these rows using (5.4), we can replace D_{+}^{r} by M_{r} given by (5.2) for r = 0, …, p.

Consider the element M_{r}B_{k}(τ) in the r + 1-st of these rows and column k. By (4.1),

B_{k}(τ) = ∑_{i=μ}^{μ+m−1} α_{k}(i)B_{i,t}(τ),

where B_{i,t} are the LB-splines on t. All of the LB-splines in this sum have support on the interval J = [t_{μ}, t_{μ+2m−1}] which has length at most h since J ⊂ [y_{i}, y_{i+1}] for some integer i. Now we can apply Theorem 5.2 and (5.5) to get

M_{r}B_{k}(τ) = ∑_{i=μ}^{μ+m−1+r} a_{i}^{r,k}Q_{i,t}^{m−r}(τ) = a_{μ+r}^{r,k},

where a_{i}^{r,k} := c_{i}^{r} are defined as in (5.8) starting with c_{i}^{0} := α_{k}(i). It follows that the elements in column k of the rows corresponding to τ are given by a_{μ+r}^{r,k}, for r = 0, 1, …, p. Performing successive row operations, we can convert the determinant to one where the elements in column k of the rows corresponding to τ are given by α_{k}(μ), …, α_{k}(μ + p).

Repeating this process for each of the τ_{1}, …, τ_{ℓ}, we obtain

E = det A ( \begin{matrix}i_{1}, & ⋯ & , i_{q} \\ ν_{1}, & ⋯ & , ν_{q} \end{matrix} ) ,  (6.1)

where A is the knot insertion matrix in (4.2), and

{i_{1}, …, i_{q}} := {μ_{1}, μ_{1} + 1, …, μ_{1} + p_{1}, …, μ_{ℓ}, μ_{ℓ} + 1, …, μ_{ℓ} + p_{ℓ}}.

To complete the proof, we now apply Theorem 4.1 to show that E > 0 when (3.4) holds. In order to apply this theorem, we need to verify conditions C1) and C2). Fix j, and as before set p = p_{j} and μ = μ_{j}. Let k be such that

ξ_{k} = ⋯ = ξ_{k+p} = τ_{j} = t_{μ} = ⋯ = t_{μ+p}.

To verify C1) we need to show that conditions i) – iv) of Lemma 4.4 hold for α_{ν_{k+λ}}(μ + λ) for λ = 0, …, p. These are the diagonal elments of (6.1) corresponding to the rows i_{k}, i_{k+1} …, i_{k+p} = μ, μ + 1, …, μ + p of A. By (3.4), for λ = 0, …, p, we have

a) y_{ν_{k+λ}} ≤ ξ_{k+λ} < y_{ν_{k+λ}+m},

b) if ξ_{k+λ} = y_{ν_{k+λ}} then λ ≥ m − 1 − r_{y}(ν_{k+λ}).

Since t_{μ+λ} = ξ_{k+λ}, it follows immediately from a) that i) of Lemma 4.4 holds. Now r_{t}(μ + λ) ≤ r_{y}(ν_{k+λ}) since from b)

m − 1 − r_{t}(t_{μ+λ}) = ℓ_{t}(t_{μ+λ}) = λ ≥ m − 1 − r_{y}(ν_{k+λ}).

This shows that ii) holds. By a) we have t_{μ+λ} = ξ_{k+λ} < y_{ν_{k+λ}+m} and (iii) follows. From the last inequality and condition ii) in the construction of t we always have t_{μ+λ+m} < y_{ν_{k+λ}+m}. Thus (iv) holds trivially.

Finally, it is easy to see that C2) also holds, since by condition ii) in the construction of t, the interval (τ_{j−1}, τ_{j}) contains the knots t_{μ−m} = ⋯ = t_{μ−1}. This completes the proof of Theorem 3.1.

§7. Remarks

1) Theorem 3.1 implies a variety of properties of L-splines. For example (see [9]), for any coefficients c_{j},

S^{−}( ∑_{j=1}^{q} c_{j}B_{ν_{j}}(x)) ≤ S^{−}(c_{1}, …, c_{q}),

where S^{−} stands for the number of strong sign changes.

2) There is no canonical way to normalize the LB-splines B_{i}. Here we normalized them so that the first nonzero right derivative at the knot y_{i} is equal to one. Alternatively, they can be normalized to have unit integral. If the constant function belongs to N_{L}, then they can also be normalized to form a partition of unity, see [5]. In particular, using equation (4.2) of [5], it can be shown that if we choose the normalizations ∑ B_{i} = 1 and ∫ Q_{i}^{m−1} = 1, then D_{+}B_{i} = Q_{i}^{m−1} − Q_{i+1}^{m−1}.

Acknowledgements. The first author was supported in part by the Research Council of Norway through project STP28402 and SINTEF. The second author was partially supported by NSF Grant 9208413.

References

1. Goodman, T. N. T., and S. L. Lee, Interpolatory and variation-diminish-ing properties of generalized B-splines, Proc. Royal Soc. Edinburgh 96A (1984), 249–259.

2. Jia, R. Q., Total positivity of the discrete spline collocation matrix, J. Approx. Theory 39 (1983), 11–23.

3. Karlin, S., Total Positivity, Stanford Univ. Press, Stanford, 1968.

4. Koch, P. E., T. Lyche, M. Neamtu, and L. L. Schumaker, Control curves and knot insertion for trigonometric splines, Adv. Comput. Math., to appear.

5. Lyche, T., A recurrence relation for Chebyshevian B-splines, Constr. Approx. 1 (1985), 155–173.

6. Lyche, T., and K. Mørken, Making the Oslo algorithm more efficient, SIAM J. Numer. Anal. 23 (1986), 663–675.

7. Lyche, T., and L. L. Schumaker, L-spline wavelets, in Wavelets: Theory, Algorithms, and Applications, C. Chui, L. Montefusco, and L. Puccio (eds.), Academic Press, New York, 1994, 197–212.

8. Mørken, K., Total positivity of the discrete spline collocation matrix II, J. Approx. Theory, to appear.

9. Schumaker, L. L., Spline Functions: Basic Theory, Wiley, New York, 1981, (Reprinted by Krieger, Malabar, Florida, 1993).

Tom Lyche Institutt for Informatikk, University of Oslo P. O. Box 1080, Blindern 0316 Oslo, Norway tom@ ifi.uio.no

Larry L. Schumaker Dept. of Mathematics Vanderbilt University Nashville, TN 37240 s@ mar.cas.vanderbilt.edu