u — (x; , X ) = A’1 ’1 ,Z R = u — (z; —¦ S ’1 , Z )

—¦S ’1 ,Z (z)

—¦S

= u — (T x; —¦ S ’1 , T (X )).

This means that the power function is found from

N

u — (x; , X ) (x ’ x j )

= (0) ’ 2

2

P ,X (x) j

j=1

N

u — (x; , X )u — (x; , X ) (x j ’ xk )

+ j k

j,k=1

N

’1

u — (z; —¦ S ’1 , Z ) —¦ S ’1 (z ’ z j )

= —¦ S (0) ’ 2 j

j=1

N

u — (z; —¦ S ’1 , Z )u — (z; —¦ S ’1 , Z ) —¦ S ’1 (z j ’ z k )

+ j k

j,k=1

=P —¦S ’1 ,T (X ) (T x),

¬nishing the proof.

After this preparatory result, we can state and prove our convergence estimates for the

solution of a partial differential equation by collocation with positive de¬nite functions.

304 Generalized interpolation

Theorem 16.15 Let ⊆ Rd be a polygonal and open region. Let L = 0 be a linear dif-

ferential operator of order ¤ k, with coef¬cients c± ∈ C 2(k’ ) ( ) that either vanish on

or have no zero there. Suppose that ∈ C 2k (Rd ) is a positive de¬nite function. Suppose

further that the boundary-value problem

Lu = f ,

in

u=g ‚

on

has a unique solution u ∈ N ( ) for given f ∈ C( ) and g ∈ C(‚ ). Let su, be the

interpolant (16.12) based on . Then the following error estimates,

|Lu(x) ’ Lsu, (x)| ¤ Ch k’, N ( ), x∈ ,

u (16.16)

X1

|u(x) ’ su, (x)| ¤ Ch k 2 ,‚ N ( ), x ∈‚ ,

u (16.17)

X

are satis¬ed for all suf¬ciently dense sets of data sites. Here C denotes a generic constant.

Proof We use the notation from the beginning of this section and that introduced in the

paragraph following the proof of Theorem 16.11. By Theorem 10.46 the function u has a

natural extension to the whole of Rd , and the extended function has the same norm as the

original one. Thus we can assume that u ∈ N (Rd ).

The function L corresponding to the linear operator L = |β|¤ cβ D β is a positive

de¬nite kernel in C 2k’2 ( — ). Moreover, the assumptions imposed on the coef¬cient

functions of L and on itself show that the number C L (x) from Theorem 11.13 is uniformly

bounded on , if we replace k by k ’ in that theorem. Hence, our analysis made so far

together with the theorem just cited yields

|Lu(x) ’ Lsu, (x)| ¤ P ¤ Ch k’, N ( ), x∈ ,

(x) u u

L ,X 1 N() X1

which is (16.16).

Let us now turn to the estimate on the boundary. First of all, our general theory leads

us to

|u(x) ’ su, (x)| ¤ P N ( ), x ∈‚ .

,X 2 (x) u

Unfortunately, we cannot apply either Theorem 11.13 or Theorem 11.11 directly. Why is

this so? The estimates on the power function require that the region where x comes from

has to satisfy an interior cone condition in Rd . But our region of interest is ‚ , which

de¬nitely does not satisfy an interior cone condition. It does not even contain an interior

point. The remedy to this problem is to use the fact that ‚ is locally a hyperplane, which

can be mapped af¬nely to Rd’1 . The image of this mapping satis¬es an interior cone

condition in Rd’1 ; thus we can use this to work in Rd’1 . Let us make this more precise. The

boundary ‚ is the union of a ¬nite number of surfaces H ⊆ H = {y ∈ Rd : a T y = b}.

˜

Each surface H is a simple polygonal region in Rd’1 , in the sense that there exists an af¬ne

bijective mapping T y = Sy + c such that T ( H ) = {z ∈ Rd : z d = 0} = Rd’1 , where T (H )

˜

is a simple polygonal region in Rd’1 satisfying therefore an interior cone condition in Rd’1 .

16.3 Solving PDEs by collocation 305

Since we have only a ¬nite number of these regions, we can assume that the angles and

radii of all the cone conditions are the same.

We will bound the error now for one of these surfaces, say H . Let Y = {y1 , . . . , y M } =

X 2 © H . Let Z = T (Y ) = {z 1 , . . . , z M } and z = T x for x ∈ H . If h X 2 ,‚ is suf¬ciently

small then we can ¬nd for x ∈ H an y j0 ∈ X 2 © H with x ’ y j0 2 ¤ 2h X 2 ,‚ . Hence we

have

z ’ z j0 ¤S x ’ y j0 ¤ Ch X 2 ,‚ ,

2 2

which means that h Z ,T (H ) ¤ Ch X 2 ,‚ . Since —¦ S ’1 is a positive de¬nite function even

when restricted to Rd’1 , which has the same smoothness properties as , we can now apply

Theorem 11.11 to T (H ) ⊆ Rd’1 and Z = H (Y ) to get

¤ Ch k ,T (H ) ¤ Ch k 2 ,‚ , z ∈ T (H ),

P —¦S ’1 ,Z (z) Z X

provided that h X 2 ,‚ is suf¬ciently small. By Lemma 16.14 and Theorem 16.11 we can

estimate, for x ∈ H ,

|u(x) ’ su, (x)| ¤ P ¤P

,X 2 (x) u ,Y (x) u N ( )

N()

¤P ¤ Ch k 2 ,‚ u N ( ) .

—¦S ’1 ,Z (z) u N() X

Since this can be done for every surface and since the number of surfaces is ¬nite, this

completes our proof.

Theorem 16.15 shows that in order to get good approximation results the interior

should be discretized more ¬nely than the boundary. A good choice is obviously

h k’, ≈ h k 2 ,‚ .

X

X1

Moreover, more information on L and might lead to a better estimate on C L (x), yielding

additional approximation orders.

As stated before, in the case of an elliptic second-order operator estimates (16.16) and

(16.17) together lead to an estimate of u ’ su, on .

De¬nition 16.16 A linear operator L : C 2 ( ) ’ C( ) of the form

d

‚ ‚u d

‚u

Lu(x) = ’ (x) + (x) + b0 (x)u(x)

a j,k (x) b j (x)

‚xk ‚x j ‚x j

j,k=1 j=1

with a j,k ∈ C 1 ( ) and b j ∈ C( ) is called an elliptic differential operator of the second

order if the matrix A(x) = (a j,k (x)) ∈ Rd—d is uniformly positive de¬nite on . This means

that there exists an ± > 0 such that

c T A(x)c ≥ ±c T c