2

e2ts’s = s, t ∈ R.

Hn (t),

n!

n=0

(2) For every n ∈ N0 and every t ∈ R the Hermite polynomials can be bounded by

√ 2

|Hn (t)| ¤ 2n/2 n! et .

2

Proof The ¬rst property is easily shown if we regard w(s, t) := e2st’s as a function of the

¬rst variable. For complex s this is an entire function having Taylor expansion

∞

‚nw

1

2

w(s, t) = e2st’s = sn ,

‚s n

n! s=0

n=0

which immediately implies the stated representation since

‚ n w(sr t) ‚ n ’(t’s)2 ‚ n ’u 2

2 2

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

e e

‚s n ‚s n ‚u n

s=0 s=0 u=t

For the second property we start with the representation

∞

1

e’t = √ e’r /4 ir t

2 2

e dr ;

2π ’∞

see Theorem 6.10. Differentiating under the integral sign leads to a ¬rst bound

∞

1

e’r /4

2 2

|Hn (t)| ¤ et |r |n dr

√

2π ’∞

∞

21

e’r /4 n

2

= et √ r dr

π 0

15.1 Fast multipole methods 261

∞

2n 2

e’s s (n’1)/2 ds

= √ et

π 0

n + 1 t2

n

2

=√ e.

π 2

To derive the stated result it remains to prove that

√

√

n+1

π2’n/2 n!.

¤

2

This is done as follows. Legendre™s duplication formula from Proposition 5.2 gives

n+1

2n n

n! = √ +1 .

π 2 2

By induction we can easily establish that

n+1

n 1

+1 ≥ √ ,

π

2 2

so this ¬nishes the proof.

These two ingredients would allow us to develop a far-¬eld expansion in the one-

dimensional setting straight away. But since the multivariate case is no more dif¬cult we im-

mediately proceed to it by introducing the multivariate Hermite polynomials and functions.

This is straightforward using tensor products. Hence for ± ∈ Nd and x = (x1 , . . . , xd )T we

0

set

d

x ∈ Rd ,

H± (x) := H± j (x j ),

j=1

and

d

h ± j (x j ) = e’

2

x ∈ Rd .

x

h ± (x) := H± (x),

2

j=1

With these de¬nitions we can ¬nd the far-¬eld expansion of the Gaussian around zero

easily. Remember that ± ¤ p means ± ∞ ¤ p for all ± ∈ Nd .0

Theorem 15.6 Let (x) = e’ x 2 . Suppose that the sources x j , 1 ¤ j ¤ N , satisfy

2

√

x j ∞ ¤ r/ 2, r < 1. Then the sum

N

s(x) = c j (x ’ x j )

j=1

can be expressed as

s(x) = A± h ± (x)

±∈Nd

0

262 Numerical methods

with

N

1

c j x±.

A± =

±! j

j=1

Moreover, if s denotes the approximation s(x) = A± h ± (x) for a p ∈ N then the

±¤ p

approximation error can be bounded as follows:

d’k

d’1

r p+1

c1 d k

|s(x) ’ s(x)| ¤ 1 ’ r p+1 .

√

(1 ’ r )d ( p + 1)!

k

k=0

Proof The alternative representation for s(x) is an immediate consequence of (1) in Lemma

15.5. By de¬nition we have