s f,X (x) =

i∈I (x)

where the coef¬cients ai— (x) are determined by minimizing the quadratic form

1

ai (x)2 (4.4)

δ (x ’ x i )

i∈I (x)

under the constraints

a j (x) p(x j ) = p(x), p ∈ πm (Rd ). (4.5)

j∈I (x)

Proof Denote a basis of πm (Rd ) by p1 , . . . , p Q . Suppose our polynomial has the form p =

Q

j=1 b j p j . This reduces the minimization problem (4.2) to ¬nding the optimal coef¬cient

vector b— .

We use the following notation:

b = (b1 , . . . , b Q )T ∈ R Q ,

f = ( f (xi ) : i ∈ I (x))T ∈ R#I (x) ,

P = ( p j (xi )) i∈I (x) ∈ R#I (x)—Q ,

1¤ j¤Q

D = D(x) = diag( ’ xi ) : i ∈ I (x)) ∈ R#I (x)—#I (x) ,

δ (x

R(x) = ( p1 (x), . . . , p Q (x))T ∈ R Q .

38 Moving least squares

Then we have to minimize the function

2

Q

C(b) = f (xi ) ’ ’ xi )

b j p j (xi ) δ (x

i∈I (x) j=1

= [ f i ’ (Pb)i ]2 ’ xi )

δ (x

i∈I (x)

= ( f ’ Pb)T D( f ’ Pb)

= f T D f ’ 2 f T DPb + b T P T DPb

on R Q . Since C(b) is a quadratic function in b we can apply Lemma 4.2. We get a unique

solution if P T D P is positive de¬nite. From

b T P T DPb = b T P T D 1/2 D 1/2 Pb = D 1/2 Pb 2

it follows that P T DP is positive semi-de¬nite. Moreover, b T P T DPb = 0 means that Pb =

0. Thus the polynomial p = b j p j vanishes on every xi , i ∈ I (x). Since this set is assumed

to be πm (Rd )-unisolvent, p and hence b must be zero.

Now that we know the existence of a unique solution we can use the necessary condition

∇C(b— ) = 0 to compute it. We ¬nd that

0 = ∇C(b— ) = ’2 f T DP + 2(b— )T (P T DP),

which gives (b— )T = f T DP(P T DP)’1 , and we obtain the solution

p — (x) = (b— )T R(x) = f T DP(P T DP)’1 R(x).

In the ¬nal step we treat the problem of minimizing (4.4) under the constraints (4.5). This

means that we have to minimize the function

1

= a T D ’1 a

ai2

C(a) :=

(x ’ xi )

δ

i∈I (x)

on the set

M := a ∈ R#I (x) : ai p j (xi ) = p j (x), 1 ¤ j ¤ Q

i∈I (x)

= {a ∈ R#I (x) : P T a = R(x)}.

Since we have supposed {xi : i ∈ I (x)} to be πm (Rd )-unisolvent we can always ¬nd Q

points that allow unique polynomial interpolation. Hence M is not empty. Moreover, D ’1

is obviously positive de¬nite. Thus Lemma 4.2 gives us a unique solution to this problem.

To compute this solution we can use Lagrange multipliers. If a — ∈ M is a solution of the

modi¬ed problem, there has to be a » ∈ R Q such that

‚

∇C(a — ) = »T P T a ’ R(x) .

a=a —

‚a

4.1 De¬nition and characterization 39

Fig. 4.1 Basis functions for m = 0 (on the left) and m = 2 (on the right).

This means that 2(a — )T D ’1 = »T P T or a — = DP»/2, showing in particular that a — is the

unique solution of the modi¬ed problem, which makes it also the solution of the initial

problem. From a — ∈ M we can conclude that R(x) = P T a — = P T DP»/2, which gives the

representation » = 2(P T DP)’1 R(x). Finally, we ¬nd

ai— f (xi ) = f T a — = f T D P(P T DP)’1 R(x) = p — (x).

i∈I (x)

From the proof of the last theorem we can read off interesting properties of the basis

functions a — . The most important of these concern the form of a — and the smoothness of

j j

the approximant.

Corollary 4.4 The basis functions a — are given by

j

Q

a — (x) = δ (x ’ x j ) »k pk (x j ), (4.6)

j

k=1

where the »k are the unique solutions of

Q

»k ’ x j ) pk (x j ) p (x j ) = p (x), 0¤ ¤ Q.

δ (x (4.7)

k=1 j∈I (x)

Figure 4.1 shows two typical basis functions, for m = 0 and m = 2. The data sites form

a regular 100 — 100 grid and the weight function is given by φ(r ) = (1 ’ r )4 (4r + 1) (see

+

Chapter 9). The support radius δ = 0.2 was chosen to be large for illustration purposes; in

practical applications such an ideal point placement would lead to a much smaller choice of

δ, for example δ = 0.05. Note that the basis function for m = 0 is nonnegative as it should

be. The basis function for m = 2, however, becomes negative close to the boundary of its

support. This will make the error analysis for higher-order moving least squares somewhat

harder.

Corollary 4.5 If possesses k continuous derivatives then the approximant s f,X is also

in C k .

Proof From the last corollary we know that the smoothness of s f,X is governed by the

smoothness of and the smoothness of the » j . Since is supported in the unit ball, the

40 Moving least squares

Fig. 4.2 In¬‚uence of the scaling parameter in the moving least squares approximation: from left to

right, δ = 0.05, δ = 0.07, δ = 0.1.

» j are also the solutions of

Q N

»k ’ x j ) pk (x j ) p (x j ) = p (x), 0¤ ¤ Q,