for all x ∈ and all ± with |±| ¤ k ’ 1, provided that h X, ¤ h 0 .

11.3 Estimates for popular basis functions 187

Proof Set h = h X, . Let us denote the right-hand side of (11.5) by F( p, h). Next we de¬ne

the bijective map T : π2k (Rd ) ’ π2k (Rd ) by

T p(x) = h ’2k p(hx) ’ x 2k

log h.

2

(x/ h) = h 2k (x) ’ h ’2k x 2k

Since log h we have

2

(x) ’ p(x) = h 2k ( (x/ h) ’ T p(x/ h))

for every p ∈ π2k (Rd ), giving

D β (x) ’ D β p(x) = h 2k’|β| D β (x/ h) ’ D β T p(x/ h)

for every β ∈ Nd with |β| ¤ 2k ’ 1. This means in particular that

0

D 2± (0) ’ D 2± p(0) = h 2k’2|±| (D 2± (0) ’ D 2± T p(0))

and, moreover,

D± ’ D± p (±)

L ∞ (B(0,c2 h))

± ±

= |D (x) ’ D p(x)|

sup

(±)

2 ¤c2 h

x

|D ± (x/ h) ’ D ± T p(x/ h)|

= h 2k’|±| sup

(±)

2 ¤c2 h

x

= h 2k’|±| sup |D ± (x) ’ D ± T p(x)|

(±)

2 ¤c2

x

= h 2k’|±| D ± ’ D± T p L ∞ (B(0,c2 )) .

(±)

Finally, by setting = max{m ’ 1, 2k} in Theorem 11.9 we obtain

2

P (±) (x) ¤ inf F( p, h)

,X

p∈π2k (Rd )

= h 2k’2|±| inf F(T p, 1)

p∈π2k (Rd )

= h 2k’2|±| inf F( p, 1).

p∈π2k (Rd )

The last in¬mum is a constant, which proves the stated bound.

Let us summarize our results on bounding the power function in the following way. For

every basis function we have found a function F such that

P 2 ,X (x) ¤ F(h X, ), x∈ .

The basis functions together with their functions F are collected in Table 11.1. The function

F is given only up to a constant that may depend on , d, and but not on X . The

spectral convergence results for Gaussians and (inverse) multiquadrics will be obtained in

Section 11.4.

188 Error estimates for radial basis function interpolation

Table 11.1 Upper bounds on P 2 ,X in terms of h

(x) = φ(r ), r = x F(h)

2

e’±r , e’c| log h|/ h

2

±>0

Gaussians

(’1) β (c2 + r 2 )β , e’c/ h

β > 0, β ∈ N

multiquadrics (MQs)

(c2 + r 2 )β , e’c/ h

β<0

inverse MQs

(’1) β/2 r β , hβ

β > 0, β ∈ 2N

powers

k∈N

(’1)k+1 r 2k log r , h 2k

thin-plate splines

φd,k (r ) h 2k+1

compactly supported

functons

11.4 Spectral convergence for Gaussians and (inverse) multiquadrics

In Theorem 11.14 we saw that interpolation by Gaussians and (inverse) multiquadrics leads

to arbitrarily high algebraic approximation orders for functions from the associated native

space, i.e.

f ’ s f,X ¤ C h X, | f |N

L∞( ) ()

holds for every ∈ N. It is now our goal to conclude also even spectral convergence orders,

i.e.

¤ e’c/ h X, | f |N

f ’ s f,X (11.8)

L∞( ) ()

with a certain constant c > 0. To this end we have to study how the constants h 0 , c1 , c2

depend on the polynomial degree . For example, if we use the result on local polynomial

reproduction given in Theorem 3.14, which was based on norming sets, we know that a

possible choice is h 0 = c0 / 2 , c1 = 2, c2 = c2 2 , where c0 , c2 are constants independent of

. The analysis to come will show that this allows error estimates of the form

√

’c/ h X,

f ’ s f,X L ∞ ( ) ¤ Ce | f |N ( ) . (11.9)

To gain the full spectral order given in (11.8), however, we need a local polynomial repro-

duction that allows h 0 and c2 to depend linearly on 1/ and , respectively. To achieve this

we have to sacri¬ce something, namely the uniform bound on c1 . We will see that it does

not really matter if this constant grows even exponentially in .

The following result speci¬es what we have just stated. Unfortunately, it does not seem to

have such an elegant proof as the other results on local polynomial reproduction that we have

encountered so far. The only known proof is based on some deeper results from algebraic

geometry and the theory of nondegenerate points. To give the proof here would exceed the

scope of this text. The interested reader should have a look at Madych and Nelson [114]

for details. But let us point out again that the somewhat weaker estimates given in (11.9)

follow easily from Theorem 3.14 and the proof of Theorem 11.22 below.

11.4 Spectral convergence for Gaussians and (inverse) MQs 189

Proposition 11.20 De¬ne γ1 = 2 and γd = 2d(1 + γd’1 ) for d = 2, 3, . . . . Let and q be

positive integers with q ≥ γd ( + 1). Let be a cube in Rd . Subdivide into q d identical

subcubes. If X ⊆ is a set of N ≥ q d points such that each subcube contains at least one

of these points then, for all p ∈ π (Rd ),

+1)

¤ e2dγd ( L ∞ (X ) .

p p

L∞( )

This result allows us to state a new version of a local polynomial reproducing process.