Note that the ¬rst row means that β = ( f (x1 ), . . . , f (x Q ))T and so solving the system

reduces to solving

C± = f ’ Pβ

with f = ( f (x Q+1 ), . . . , f (x N ))T , which can be solved using a solver for positive de¬nite

matrices.

Let us do an example to see how the three different approaches work. To this end we

choose the basis function to be (x, y) = x ’ y 2 log x ’ y 2 , which is conditionally

2

positive de¬nite on Rd — Rd of order m = 2. Thus if we treat the two-dimensional case, P

is the space of linear polynomials in R2 having dimension Q = 3.

=

Our simple example uses lattice points on [0, 1]2 , and we will choose

{(0, 0) , (1, 0) , (0, 1) } with the associated Lagrange basis p1 (x) = 1 ’ x1 ’ x2 , p2 (x) =

T T T

x1 , and p3 (x) = x2 . Table 12.2 contains the results for different spacings. The matrix A is

the standard matrix using the standard basis for VX as it appears for example in (8.10).

It can be seen that the condition numbers are roughly of the same size, even slightly worse,

in the case of the new kernels. But in this example we changed the separation distance and

the number of points. If we are only interested in the effect of the separation distance we

have to keep the number of points ¬xed. This is of interest in itself, for reasons that will

12.3 Change of basis 219

Table 12.2 Condition numbers in the 2 -norm

Spacing Conventional Reproducing-kernel Homogeneous

h matrix A matrix K matrix C

3.5158 — 103 1.8390 — 104 7.5838 — 103

1/8

3.8938 — 104 2.6514 — 105 1.1086 — 105

1/16

5.1363 — 105 4.0007 — 106 1.6864 — 106

1/32

7.6183 — 106 6.2029 — 107 2.6264 — 107

1/64

Table 12.3 Condition numbers for a ¬xed number of centers

Scale parameter Conventional Reproducing-kernel Homogeneous

± matrix A matrix K matrix C

2.4349 — 108 8.4635 — 108 5.4938 — 103

0.001

2.4364 — 106 8.4640 — 106 5.4938 — 103

0.01

2.5179 — 104 8.5134 — 104 5.4938 — 103

0.1

3.6458 — 102 1.3660 — 103 5.4938 — 103

1.0

1.8742 — 106 1.2609 — 103 5.4938 — 103

10

1.1520 — 1011 1.1396 — 105 5.4938 — 103

100

3.5478 — 1015 1.1386 — 107 5.4938 — 103

1000

become clear later, when we want to solve a large RBF system by splitting it up into a

couple of smaller systems.

Thus our next model problem is again thin-plate spline interpolation, but this time on a

uniform 5 — 5 grid in [0, ±]2 with spacing q X = ±/4. Table 12.3 shows the results.

Now the situation has completely changed. The condition number of the matrix C is

independent of the scaling ±. We will spend the rest of this section explaining this behavior.

We start with a lemma that is an improved version of a technique we have already used,

in the proof of Theorem 11.9.

Lemma 12.12 Let = {ξ1 , . . . , ξ Q } be a πm’1 (Rd )-unisolvent set and let p1 , . . . , p Q ∈

πm’1 (Rd ) be such that pk (ξ ) = δk, . Then for any p ∈ π2m’1 (Rd ) it is true that

Q Q

0 = p(x ’ y) ’ pk (y) p(x ’ ξk ) ’ p (x) p(ξ ’ y)

=1

k=1

Q

+ p (x) pk (y) p(ξ ’ ξk ).

k, =1

Proof Obviously it suf¬ces to prove the identity for the monomials q± (x) = x ± , ± ∈ Nd ,

0

|±| ¤ 2m ’ 1. The binomial theorem allows us to write

q± (x ’ y) = aβ qβ (y)q±’β (x).

0¤β¤±

220 Stability

Thus to investigate the expression on the right-hand side of the statement in the lemma for

p = q± , we have to investigate

Q Q

q±’β (x)qβ (y) ’ pk (y)qβ (ξk )q±’β (x) ’ p (x)q±’β (ξ )qβ (y)

=1

k=1

Q

+ p (x) pk (y)q±’β (ξ )qβ (ξk )

,k=1

Q

= q±’β (x)qβ (y) ’ pk (y)qβ (ξk )q±’β (x)

k=1

Q Q

’ p (x)q±’β (ξ ) qβ (y) ’ pk (y)qβ (ξk )

=1 k=1

Q

= q±’β (x) qβ (y) ’ qβ (y) ’ pk (x) qβ (y) ’ qβ (y) q±’β (ξk )

k=1

= q±’β (x) ’ q±’β (x) qβ (y) ’ qβ (y) ,

Q

where we have utilized the projection operator f = k=1 f (ξk ) pk again. Now, since |±| ¤

2m ’ 1, either |± ’ β| ¤ m ’ 1 or |β| ¤ m ’ 1 for every β. Hence, the last expression is

zero for all β ∈ Nd with β ¤ ±. But this means that the expression given in the lemma

0

becomes

aβ q±’β (x) ’ q±’β (x) qβ (y) ’ qβ (y) = 0

β¤±

for p = q± , thus proving the lemma.

This lemma was needed to show that under certain circumstances the kernel κ is in a

certain way homogeneous.

∈ C(Rd — Rd ) satis¬es

Theorem 12.13 Suppose that the symmetric function

(hx, hy) = h » (x, y) + qh (x ’ y) for all h > 0 and x, y ∈ Rd , where » ∈ R and qh ∈

π2m’1 (Rd ). Let = {ξ1 , . . . , ξ Q } be unisolvent for πm’1 (Rd ) with associated Lagrange

basis p1 , . . . , p Q . Let κ be the kernel (12.4) and κ h for h > 0 be the kernel κ for the

set h = {hξ1 , . . . , hξ Q } and the Lagrange functions p1 , . . . , p h associated with this set.

h

Q

Then κ h (hx, hy) = h » κ(x, y) for all x, y ∈ R.

Proof Since obviously pk (x) = pk (x/ h), we have

h

Q Q

κ (hx, hy) = (hx, hy) ’ (hξk , hy) ’

h h

p h (hy) (hx, hξ )

pk (hx)

=1

k=1

Q

+ p h (hy) pk (hx) (hξk , hξ )

h

,k=1

12.3 Change of basis 221