β!

|β|<2k’|ν|

This time the remainder takes the form

β+ν ν

(w, ·w,z )

D2

(z ’ w)β

S(w, z, ν) :=

β!

|β|=2k’|ν|

ν

with ·w,z on the line segment between w and z.

We have to bound the power function to achieve the desired result. To this end we use

the vector u := u (±) (x) from Theorem 11.8 with an ≥ max{2k ’ 1, m ’ 1}. Moreover, by

the remarks made after Theorem 11.8, we know that for a ¬xed x ∈ all x j relevant to the

construction are contained in the cone associated with x. Hence all line segments between

xi and x or xi and another x j for these x j are contained in . The power function can be

bounded by [P (±) (x)]2 ¤ Q(u), and the latter is given by

,X

±± ±

Q(u) = D1 D2 (x, x) ’ 2 u j D1 (x, x j ) + u i u j (xi , x j ).

j i, j

The summation is always over only those indices j with u j = 0. The ¬rst Taylor expansion

used twice gives

±±

Q(u) = D1 D2 (x, x)

β

±

D2 D1 (x, x)

(x j ’ x)β + R(x, x j , ±)

’2 uj

β!

|β|<2k’|±|

j

β

D2 (xi , xi )

(x j ’ xi )β + R(xi , x j , 0) .

+ ui u j

β!

|β|<2k

i, j

An application of the reproduction property of the coef¬cient vector u together with an

application of the second Taylor expansion yields

±± ±±

Q(u) = D1 D2 (x, x) ’ 2D2 D1 (x, x) ’ 2 u j R(x, x j , ±)

j

±+β

(xi , xi )

D2

(x ’ xi )β +

+ u i u j R(xi , x j , 0)

ui

β!

|β|<2k’|±|

i i, j

±±

= ’D1 D2 (x, x) ’ u j 2R(x, x j , ±) ’ u i R(xi , x j , 0)

j i

±

+ u i D2 (xi , x) ’ S(xi , x, ±) .

i

11.3 Estimates for popular basis functions 183

± ±

Since D2 (xi , x) = D1 (x, xi ), a ¬nal application of the ¬rst Taylor formula and another

application of the reproduction property of the coef¬cient vector leads ¬nally to

Q(u) = ’ u j R(x, x j , ±) + S(x j , x, ±) ’ u i R(xi , x j , 0) .

j i

’|±|

(±) (±)

However, we know that j |u j | ¤ c1 h X, . Moreover, because x ’ x j 2 ¤ c2 h X, and

(±)

xi ’ x j 2 ¤ 2c2 h X, we see that the ¬rst two remainder terms can be bounded by

2k’|±| 2k’|±|

CC (x)h X, and the last term also by CC (x)h X, , using the bound on the 1 -norm of

k’|±|

the coef¬cients again. This gives for the power function P (±) (x) ¤ CC (x)1/2 h X, and

,X

hence the desired result.

The reason for the special treatment of the number C is that in many cases it al-

lows an improvement over the O(h k’|±| ) order, as we will see very soon. Moreover, if all

derivatives of of order 2k are continuous on — then C (x) is uniformly bounded

on .

Moreover, the assumption that X is πm’1 (Rd )-unisolvent is automatically satis¬ed if

h X, ¤ h 0 . The latter condition was mainly made to allow unique polynomial interpolation

in a subset of X for polynomials of degree at most ≥ m ’ 1.

Finally, in the case of a function , the number C (x) has the form

C (x) = max D β (11.7)

(±)

L ∞ (B(0, 2c2 h X, ))

|β|=2k

and is obviously independent of x.

11.3 Estimates for popular basis functions

It is time to apply the general result of Theorem 11.11 to those basis functions that have

accompanied us so far. Our ¬rst application deals with basis functions of in¬nite smoothness.

Without a closer look at the involved constants we immediately get an arbitrary convergence

order.

Theorem 11.14 Let be one of the Gaussians or the (inverse) multiquadrics. Suppose that

is conditionally positive de¬nite of order m. Suppose further that ⊆ Rd is bounded

and satis¬es an interior cone condition. Denote the radial basis function interpolant to

f ∈ N ( ) based on and X = {x1 , . . . , x N } by s f,X . Fix ± ∈ Nd . For every ∈ N with

0

≥ max{|±|, m ’ 1} there exist constants h 0 ( ), C > 0 such that

’|±|

|D ± f (x) ’ D ± s f,X (x)| ¤ C h X, | f |N ()

for all x ∈ , provided that h X, ¤ h 0 ( ).

To derive spectral convergence orders it is crucial to study how the constants h 0 ( ) and

C depend on . We will discuss this in more detail in Section 11.4.

In the case of basis functions with a ¬nite number of continuous derivatives it is important

to know the exact H¨ lder class Cν (Rd ) to which they belong.

k

o

184 Error estimates for radial basis function interpolation

β

Lemma 11.15 Let (x) = x 2 with β > 0, β ∈ 2N. For every ± ∈ Nd there exists a

0

homogenous polynomial p±,β ∈ π|±| (Rd ) such that

β’2|±|

D ± (x) = p±,β (x) x 2

β’|±|

for every x = 0. In particular, there exists a constant c± such that |D ± (x)| ¤ c± x 2

β ’1

for every x = 0, showing that ∈ Cβ’ β ’1 (Rd ).

Proof The proof is by induction on the length of ±. For |±| = 0 there is nothing to show.

Now assume that |±| ≥ 1. Without restriction we can assume ±1 ≥ 1. De¬ne γ = (±1 ’

1, ±2 , . . . , ±d )T . Then there exists a homogeneous polynomial pγ ,β of degree |γ | such that

‚

D ± (x) = D γ (x)

‚x1

‚ β’2|γ |

= pγ ,β (x) x 2

‚x1

‚ pγ ,β β’2|γ |’2

= (x) x 2 + (β ’ 2|γ |)x1 pγ ,β (x) x

‚x1 2 2