264 Numerical methods

The associated radial sum can be written as

∞

N N

c j e’ t ’3/2 e’t dt,

2

c j φmul ( x ’ x j 2) = 1 + 1’ x’x j 2t

0

j=1 j=1

c j = 1.

provided that the coef¬cients satisfy

Proof The representation for the inverse multquadric has already been proven in a more

general form in Theorem 7.15. The representation for the radial sum follows immediately.

For the multiquadric note that

d

φmul (r ) = r φinv (r ).

dr

Hence, using the integral form of φinv yields

r

φmul (r ) = 1 + sφinv (s)ds

0

∞ r

1

se’s t ds t ’1/2 e’t dt

2

= 1+ √

π 0 0

∞

1 ’ e’r t ’1/2 ’t

2

1

= 1+ √ t e dt,

2π t

0

where the exchange of integration order can be justi¬ed by Fubini™s theorem. Again, it is

easy to see that the radial sum has the stated form, taking into account this time the side

condition on the coef¬cients.

Similar results can be derived for more general (inverse) multiquadrics and thin-plate

splines and related functions.

Both representations of the radial sum in Proposition 15.7 make it necessary to discretize

an integral of the form

∞

f (t)t a e’t dt

0

with a = ’1/2 and a = ’3/2, respectively. Hence, a generalized Gauss“Laguerre quadra-

ture rule is the preferred choice. From classical numerical analysis it is well known that the

generalized Laguerre formula gives

∞ n

n! (n + a + 1) (2n)

a ’t

f (t)dt = wk f (tk ) +

te f (ξ )

(2n)!

0 k=1

with ξ ∈ (0, ∞). Here, the tk are the zeros of the Laguerre polynomials L n . These poly-

(a)

nomials are the orthonormal polynomials with respect to the weight function t ’ t a e’t on

[0, ∞). The weights are given by

(n + a + 1)tk

wk = .

2

(a)

n! L n+1 (tk )

15.2 Approximation of Lagrange functions 265

This completes the general framework for deriving a far-¬eld expansion for a radial

function that is (conditionally) positive de¬nite on every Rd . For special functions there

might be better expansions. In any case, the accuracy of the approximate radial sum depends

on the 1 -norm of the coef¬cient vector c. Unfortunately, we know that this can become

arbitrarily high.

15.2 Approximation of Lagrange functions

The idea of this iterative method is that every interpolant s f,X to a function f based on a

(conditionally) positive de¬nite kernel (·, ·) and a set of centers X = {x1 , . . . , x N } can be

written as

N

f k u — (x)

s f,X (x) = k

k=1

with the cardinal functions {u — } from Theorem 11.1 and f k = f (xk ), 1 ¤ k ¤ N . The

k

cardinal or Lagrange functions come from the space

span{ (·, xk ) : 1 ¤ k ¤ N } + P

and satisfy u — (x j ) = δ jk , 1 ¤ j, k ¤ N . They can be found by solving system (11.1). Now,

k

the idea is to replace the cardinal functions by approximations u k that are more easily

computed and to form the approximation

N

s f,X (x) = f k u k (x).

k=1

A possible way to do this is to ¬x a nonnegative integer q that is substantially smaller than

N . Then for every k we choose a set of exactly q indices Lk and force u k to satisfy the

Lagrange conditions u k (x j ) = δ jk for j ∈ Lk . Each of these new cardinal functions can

be computed in constant time (if q is considered constant). But even if in many cases u k

is a good approximation to u — this will not be true in general and is highly dependent on

k

the choice of Lk . Therefore an iteration on the residuals might be useful. A ¬rst possible

iterative scheme is given by

N

= fk u k ,

(1)

s

k=1

(15.4)

N

s ( j+1) = s ( j) + f k ’ s ( j) (xk ) u k , j ≥ 1.

k=1

The iteration stops when all the residuals f k ’ s ( j) (xk ), 1 ¤ k ¤ N , are suf¬ciently close

to zero.

266 Numerical methods

The iterative de¬nition gives that the residuals of level j + 1 are connected to the residuals

of level j by

( j+1)

:= f i ’ s ( j+1) (xi )

ri

N

= f i ’ s (xi ) ’ f k ’ s ( j) (xk ) u k (xi )

( j)

k=1

N

( j) ( j)

= ri ’ u k (xi )rk .

k=1

Using the N — N identity matrix I and the matrix R de¬ned by Rik = u k (xi ) this can be

expressed as

r ( j+1) = (I ’ R)r ( j) .

Hence, the method converges if I ’ R has norm less than one. To ensure this condition,