Then the function s f from (15.7) is in C k ( ) and satis¬es

± |β|’|±|

|(D ± f ’ D ± s f )(x)| ¤ C±’β δ j µ j (β), x∈ , (15.9)

β

j∈I (x) β¤±

for all |±| ¤ k.

Proof The proof is straightforward. We simply use Leibniz™ rule and the fact that the {w j }

form a partition of unity to derive

M

(D ± f ’ D ± s f )(x) = D ± w j (x)[ f (x) ’ s j (x)]

j=1

±

D ±’β w j (x)D β ( f ’ s j )(x).

=

β

j∈I (x) β¤±

The assumed bounds on the derivatives of w j and on the derivatives of D β ( f ’ s j ) now

yield the stated result.

15.4 Partition of unity 277

It is our goal to use this general result in the context of radial basis functions. Hence, we

start with a set of points X = {x1 , . . . , x N } and set X j = X © j . The local approximation

spaces are given by

V j := span{ (·, x) : x ∈ X j )} + P,

where is a conditionally positive de¬nite kernel with respect to P on = ∪ j . The local

approximant s j is then given by the interpolant s f,X j . It is interesting to see that the global

approximant inherits the interpolation property of the local interpolants, i.e. s f (xk ) = f (xk ),

1 ¤ k ¤ N ; this is a consequence of the partition of unity:

N

s f (xk ) = s f,X j (xk )w j (xk ) = f (xk )w j (xk ) = f (xk ).

j=1 j∈I (xk )

In order to use the convergence result from Chapter 11 we have to make some more

assumptions on the covering { j }.

De¬nition 15.18 Suppose that ⊆ Rd is bounded and X = {x1 , . . . , x N } ⊆ are given.

An open and bounded covering { j } N is called regular for ( , X ) if the following prop-

j=1

erties are satis¬ed.

(1) For every x ∈ the number of cells j with x ∈ j is bounded by a global constant K , i.e.

χ j (x) ¤ K for all x ∈ .

(2) There exists a constant Cr > C2 and an angle θ ∈ (0, π/2) such that every patch j © satis¬es

an interior cone condition with angle θ and radius r = Cr h X, . Here C2 is the constant from

Theorem 3.14.

This looks technical at ¬rst sight. But a closer look at each property shows that these

requirements are more or less natural. For example, the ¬rst property is necessary to make

sure that the outer sum in (15.9) is actually a sum over at most K summands. Since K is

independent of N , in contrast with M, which should be proportional to N , this is essential

to avoid losing convergence orders. Moreover, it is crucial for an ef¬cient evaluation of

the global approximant that only a constant number of local approximants have to be

evaluated. To this end, it also has to be possible to locate those K indices in constant time.

The second property is important for employing our estimates on radial basis function

interpolants.

We will state our convergence results only for (conditionally) positive de¬nite functions

with a ¬nite number of continuous derivatives. But it should be clear from the proof that

everything works for kernels also. Moreover, if Gaussians or multiquadrics are used then

the convergence orders are again spectral.

Theorem 15.19 Let ⊆ Rd be open and bounded and suppose that X = {x1 , . . . , x N } ⊆

. Let ∈ Cν (Rd ) be conditionally positive de¬nite of order m. Let { j } be a regular

k

covering for ( , X ) and let {w j } be k-stable for { j }. The error between f ∈ N ( ) and

278 Numerical methods

its partition-of-unity interpolant s f = s f,X j w j is bounded as follows:

j

|D ± f (x) ’ D ± s f (x)| ¤ Ch X,

(k+ν)/2’|±|

| f |N ()

for all x ∈ and all |±| ¤ k/2.

Proof On the one hand, by Theorem 10.46 the function f has a norm-preserving ex-

tension E f ∈ N (Rd ). On the other hand, the restriction f j = E f |( j © ) satis¬es

| f j |N ( j © ) ¤ |E f |N (Rd ) = | f |N ( ) by Theorem 10.47. Hence, if we denote all these

functions by f then we have again | f |N ( j © ) ¤ | f |N ( ) .

Referring to the constants from Theorem 3.14 we can see that Cr ≥ C2 implies h =

h X, ¤ Cr h/C2 . Hence, by Remark 11.12 we can apply Theorem 11.11 to the local setting

j © , Xj = j © X , and h = h X, to get

|D ± ( f ’ s f,X j )(x)| ¤ Ch (k+ν)/2’|±| | f |N ( ), x∈ © .

j

Furthermore, the constant C depends on j © only via θ , which is the same for all j.

To apply (15.9) we need two more ingredients. Since every patch j satis¬es an interior

cone condition with radius Cr h X we have δ j = diam( j ) ≥ Cr h X, . Moreover, every

x ∈ is contained in at most K patches j . Hence, the error bound (15.9) leads to

± |β|’|±|

|D ± ( f ’ s f )(x)| ¤ C±’β δ j µ j (β)

β

j∈I (x) β¤±

± |β|’|±|

C±’β Cr|β|’|±| h X,

(k+ν)/2’|β|

¤K | f |N

Ch X, ()

β

β¤±

(k+ν)/2’|±|

= Ch X, | f |N ()

for all x ∈ and all |±| ¤ k/2.

Next let us have a closer look at the computational complexity. Here, it is easily seen

that it is not enough to require { j } to be regular for ( , X ) to reduce the complexity. For

example, if itself satis¬ed a cone condition we could simply choose j = , yielding

a regular covering but also the global interpolation problem. Hence, we have to make sure

that the cells are small and the covering is local.

De¬nition 15.20 Suppose that ⊆ Rd is bounded and X = {x1 , . . . , x N } ⊆ is given.

An open and bounded covering { j } N is called local for ( , X ) if there exists a constant

j=1

Cloc > 0 such that diam( j ) ¤ Cloc h X, .

If { j } is local and regular for ( , X ) and X is quasi-uniform then we know by Corollary

14.2 that the number of centers from X in each j is bounded by a constant that is inde-

pendent of the total number of centers in X . Moreover, for every j we can choose a ball

B j of radius h X, that is completely contained in © j . This ball B j can be contained

in at most K ’ 1 other cells © k . Hence, we can use our standard volume argument to

conclude from ∪ M B j ⊆ that M ¤ Ch ’d ¤ C N . X,

j=1

15.4 Partition of unity 279

Theorem 15.21 Let X = {x1 , . . . , x N } ⊆ be quasi-uniform and { j } a regular and local

covering for ( , X ). Suppose that { j } can be built in O(N ) time and O(N ) space and that

for every x ∈ at the most K patches j with x ∈ j can be reported in constant time. Then

the partition-of-unity method based on radial basis functions can be implemented in O(N )

space with O(N ) time needed for the preprocessing step. Furthermore, each evaluation of

the global interpolant needs O(1) time.

Proof Using the ¬xed-grid strategy to build our data structure for X , we know that this

can be done in O(N ) time, and space. Since the number of centers in each patch is bounded

by a constant, we need constant space and constant time for each patch to solve the local

interpolation problems. Furthermore, the points in each patch can be reported in constant

time. Since the number M of patches j is bounded by O(N ) this adds up to O(N ) space

and time for solving all of them. By assumption we can determine I (x) = { j : x ∈ j } in

constant time, and the cardinality of I (x) is also bounded by a constant. Thus we have to

add up a constant number of local interpolants to get the value of the global interpolant.