p

(ak z + bk )z ’k

φt (z) := |z| ’ 2 (t z) + |t| log |z| +

2 2

k=0

then the approximation error can be bounded for t = 0 by

|t|2 c + 1 ’p

|φt (z) ’ φt (z)| ¤ c,

( p + 1)( p + 2) c ’ 1

where c = |z/t| > 1.

Proof In the paragraph before this proposition we discussed the ¬rst representation for φt .

To derive the second representation, we write

∞

1 tk

φt (z) = |z ’ t|2 log(z) ’

k zk

k=1

∞

tk

1

= |z ’ t|2 log |z| ’ (z ’ t) (z ’ t) k

k z

k=1

∞

1 k ’(k’1)

’ t k+1 z ’k

= |z ’ t| log |z| ’ (z ’ t)

2

tz

k

k=1

∞

(ak z + bk )z ’k .

= |z ’ t|2 log |z| +

k=0

To obtain the stated error bound, we note that

k’1

|t|k+1 |t|2 1

|ak zz ’k | ¤ =

k(k + 1)|z|k’1 k(k + 1) c

and

k

|t|k+2 |t|2 1

|bk z ’k | ¤ = .

k(k + 1)|z|k k(k + 1) c

15.1 Fast multipole methods 259

This enables us to bound the error as follows:

∞

|ak zz ’k | + |bk z ’k |

|φt (z) ’ φt (z)| ¤

k= p+1

∞

|t|2 1 1

¤ +k

( p + 1)( p + 2) k= p+1 ck’1 c

|t|2 c + 1 ’p

= c.

( p + 1)( p + 2) c ’ 1

For t = 0 the approximation φt coincides with φt . Moreover, the error bound is increasing

in |t| and decreasing in c > 1.

Having the far-¬eld expansion for φt we can proceed as in the model case to approximate

the radial basis sum

N N

s(z) = ± j φz j (z) = ± j |z ’ z j |2 log |z ’ z j | (15.3)

j=1 j=1

with real coef¬cients {± j }, provided that all z j are close to zero. We only have to replace

φt by φt and to exchange the order of summation to obtain the following result.

Corollary 15.3 If φt in (15.3) is replaced by φt then the resulting function s takes the form

p

(Ak z + Bk )z ’k ,

s(z) = A|z| ’ 2 (Bz) + C log |z| +

2

k=0

where the coef¬cients are de¬ned by

N N N

±j, ±jz j, ± j |z j |2

A := B := C :=

j=1 j=1 j=1

and

§

⎪ ’B for k = 0,

⎨

± j z k+1

N

Ak := j

for k ≥ 1,

⎪

© k(k + 1)

j=1

§

for k = 0,

⎪C

⎨

± j z j z k+1

N

Bk := j

⎪’ for k ≥ 1.

© k(k + 1)

j=1

Finally, if all the centers satisfy |z j | ¤ r , we have the error bound

± 1r 2 c + 1 ’p

|s(z) ’ s(z)| ¤ c

( p + 1)( p + 2) c ’ 1

with c = |z|/r .

260 Numerical methods

This shows how a far-¬eld expansion around zero can be derived for thin-plate splines

in two dimensions. Unfortunately, in higher dimensions we can no longer use the trick

of identifying R2 with C. Nonetheless, it is possible to develop expansions for higher-

dimensional spaces and other basis functions by employing Taylor and Laurent expansions.

Here, however, we choose a different approach. We will give a general framework that

works for all functions that are (conditionally) positive de¬nite on every Rd . The starting

point is the fast Gauss transform, which is based on a Hermite expansion of the Gaussian

kernel.

De¬nition 15.4 The Hermite polynomials Hn are de¬ned by

d n ’t 2

2

e.

Hn (t) := (’1)n et

dt n

The Hermite functions h n are de¬ned by h n (t) := e’t Hn (t).

2

We need two results on Hermite polynomials. The ¬rst is the generating function for

Hermite polynomials and the second is Cramer™s inequality.

Lemma 15.5 (1) The generating function for Hermite polynomials is given by

∞