
3.2 Analysis of Univariate Schemes 73
3.2.2 A Condition for Uniform Convergence
Given Theorem 3.4, we are now ready to state a condition on the subdivision mask
t[x ] for the differences that is sufficient to guarantee that the associated piecewise
linear functions
p
k
[x] converge uniformly. This condition involves the size of the
various coefficients
t[[ i]] of this mask. To measure the size of this sequence of co-
efficients, we first define a vector norm that is analogous to the previous functional
norm. The norm of a vector
p has the form
p=Max
i
|p[[ i ]]|.
(Again, this norm is the infinity norm in standard numerical analysis terminology.)
Given this vector norm, we can define a similar norm for a matrix
A of the form
A=Max
p=0
Ap
p
.
Observe that if the matrix A is infinite it is possible that the infinite sum denoted
by the product
Ap is unbounded. However, as long as the matrix A has rows with
only a finite number of non-zero entries, this norm is well defined. One immediate
consequence of this definition of
A is the inequality Ap≤Ap for all column
vectors
p. We leave it as a simple exercise for the reader to show that the norm of
a matrix
A is the maximum over all rows in A of the sums of the absolute values in
that row (i.e.,
A=Max
i
j
|A[[i, j]]|). Using these norms, the following theorem
(again credited to Dyn, Gregory, and Levin [51]) characterizes those subdivision
schemes that are uniformly convergent.
THEOREM
3.5
Given an affinely invariant subdivision scheme with associated subdivision
matrix
S, let the matrix T be the subdivision matrix for the differences
(i.e.,
T satisfies DS == TD). If T < 1, the associated functions p
k
[x] con-
verge uniformly as
k →∞for all initial vectors p
0
with bounded norm.
Proof Our approach is to bound the difference between the functions p
k
[x] and
p
k−1
[x] and then apply Theorem 3.1. Because p
k−1
[x] is defined using piece-
wise linear interpolation, it interpolates the coefficients of
Sp
k−1
plotted
on
1
2
k
Z, where
S is the subdivision matrix for linear subdivision. Therefore,
p
k
[x] − p
k−1
[x] == p
k
−
Sp
k−1
. (3.4)