nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

当前位置：首页 >> >> Approximate approximations from scattered data

Weierstra?-Institut

f¨ r Angewandte Analysis und Stochastik u

im Forschungsverbund Berlin e.V.

Preprint

ISSN 0946 – 8633

Approximate Approximations from Scattered Data

F. Lanzara1 , V. Maz’ya2 , G. Schmidt3

1

Dipartimento di Matematica, Universit` “La Sapienza”, a Piazzale Aldo Moro 2, 00185 Roma, Italy lanzara@mat.uniroma1.it Department of Mathematics, University of Link¨ping, o 581 83 Link¨ping, Sweden o vlmaz@mai.liu.se Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany schmidt@wias-berlin.de

2

3

submitted: 29 Sep 2005

No. 1058 Berlin 2005

W I A S

1991 Mathematics Subject Classi?cation. 41A30, 65D15, 41A63, 41A25. Key words and phrases. scattered data quasi-interpolation, cubature of integral operators, multivariate approximation, error estimates .

Edited by Weierstra?-Institut f¨r Angewandte Analysis und Stochastik (WIAS) u Mohrenstra?e 39 10117 Berlin Germany Fax: E-Mail: World Wide Web: + 49 30 2044975 preprint@wias-berlin.de http://www.wias-berlin.de/

Abstract The aim of this paper is to extend the approximate quasi-interpolation on a uniform grid by dilated shifts of a smooth and rapidly decaying function on a uniform grid to scattered data quasi-interpolation. It is shown that high order approximation of smooth functions up to some prescribed accuracy is possible, if the basis functions, which are centered at the scattered nodes, are multiplied by suitable polynomials such that their sum is an approximate partition of unity. For Gaussian functions we propose a method to construct the approximate partition of unity and describe the application of the new quasi-interpolation approach to the cubature of multi-dimensional integral operators.

1

Introduction

The approximation of multivariate functions from scattered data is an important theme in numerical mathematics. One of the methods to attack this problem is quasi-interpolation. One takes values u(xj ) of a function u on a set of nodes {xj } and constructs an approximant of u by linear combinations u(xj )ηj (x) , where ηj (x) is a set of basis functions. Using quasi-interpolation there is no need to solve large algebraic systems. The approximation properties of quasi-interpolants in the case that xj are the nodes of a uniform grid are well-understood. For example, the quasi-interpolant u(hj)?

j∈Zn

x ? hj h

(1.1)

can be studied via the theory of principal shift-invariant spaces, which has been developed in several articles by de Boor, DeVore and Ron (see e.g. [2], [3]). Here ? is supposed to be a compactly supported or rapidly decaying function. Based on the Strang-Fix condition for ?, which is equivalent to polynomial reproduction, convergence and approximation orders for several classes of basis functions were obtained (see also Schaback/Wu [20], Jetter/Zhou [7]). Scattered data quasi-interpolation by functions, which reproduce polynomials, has been studied by Buhmann, Dyn, Levin in [1] and Dyn, Ron in [4] (see also [24] for further references). In order to extend the quasi-interpolation (1.1) to general classes of approximating functions, another concept of approximation procedures, called Approximate Approximations, was proposed in [9] and [10]. These procedures have the common feature, that they are accurate without being convergent in a rigorous sense. Consider, for example, the quasi-interpolant on the uniform grid M u(x) = D?n/2 u(hj) η

j∈Zn

x ? hj √ , h D

(1.2)

where η is su?ciently smooth and of rapid decay, h and D are two positive parameters. It was shown that if Fη ? 1 has a zero of order N at the origin (Fη denotes the Fourier transform of η), then M u approximates u pointwise √ |Mu(x) ? u(x)| cN,η (h D)N sup |?N u| + ε |?N ?1 u(x)| (1.3)

Rn

1

with a constant cN,η not depending on u, h, and D, and ε can be made arbitrarily small if D is su?ciently large (see [13], [14]). In general, there is no convergence of the approximate quasiinterpolant Mu(x) to u(x) as h → 0. However, one can ?x D such that up to any prescribed accuracy Mu approximates u with order O(hN ). The lack of convergence as h → 0, which is even not perceptible in numerical computations for appropriately chosen D, is compensated by a greater ?exibility in the choice of approximating functions η. In applications, this ?exibility enables one to obtain simple and accurate formulae for values of various integral and pseudodi?erential operators of mathematical physics (see [12], [15], [17] and the review paper [21]) and to develop explicit semi-analytic time-marching algorithms for initial boundary value problems for linear and non linear evolution equations ([11], [8]). The approximate quasi-interpolation approach was extended to nonuniform grids up to now in two directions. The case that the set of nodes is a smooth image of a uniform grid have been studied in [16]. It was shown that formulae similar to (1.2) preserve the basic properties of approximate quasi-interpolation. A similar result for quasi-interpolation on piecewise uniform grids was obtained in [6]. It is the purpose of the present paper to generalize the method of approximate quasiinterpolation to functions with values given on a rather general grid. We start with a simple quasi-interpolant for a set of nodes close to a uniform grid of size h in the sense, that for some positive constant κ and any j ∈ Zn there exists at least one node xj with |xj ? hj| < κh. Then under some additional assumption on the nodes we construct a quasi-interpolant with gridded centers x ? hj √ Λj (u)η Mu(x) = D?n/2 . h D j∈Zn Here Λj are linear functionals of the data at a ?nite number of nodes around xj . It can be shown that estimate (1.3) remains true for Mu under the same assumptions on the function η. In order to treat more general distributions of the nodes xj we modify the approximating functions. More precisely, we consider approximations of the form M u(x) =

j

u(xj )Pj (x)η

x ? xj hj

(1.4)

with some polynomials Pj . We show that one can achieve the approximation of u with arbitrary order N up to a small saturation error, as long as an ”approximate partition of unity” x ? xj Pj (x)}η with other polynomials Pj exists. Here we mean that for any ε > 0 one hj can ?nd polynomials such that Pj (x)η x ? xj ? 1 < ε. hj

j

Then one can choose the polynomials Pj in (1.4) such that |M u(x) ? u(x)| This estimate is valid as long as η

j

C sup hN ?N u j

j

L∞

+ ε |u(x)| .

x ? xj hj

≥c>0

and η is su?ciently smooth and of rapid decay, but is not subjected to additional requirements as the Strang-Fix condition. Moreover, we propose a method to construct the polynomials such that the series 2 2 Pj (x) e?|x?xj | /hj D

j

2

approximates the constant function 1 up to an arbitrary prescribed accuracy. This method does not require solving a large system of linear equations. Instead, in order to obtain the local representation of the partition of unity, one has to solve a small number of approximation problems, which are reduced to linear systems of moderate size. By a suitable choice of η it is possible to obtain explicit semi-analytic or other e?cient approximation formulae for multi-dimensional integral and pseudo-di?erential operators which are based on the quasi-interpolant (1.4). So the cubature of those integrals, which is one of the applications of the approximate quasi-interpolation on uniform grids, can be carried over to the case when the integral operators are applied to functions given at scattered nodes. We give a simple example of formula (1.4). Let {xi } be a sequence of points on R such that 0 < xi+1 ? xi 1. Consider a sequence of functions ζj on R supported by a ?xed neighborhood of the origin. Suppose that the sequence {ζj (x ? xj )} forms an approximate partition of unity on R, |1 ? ζj (x ? xj )| < ε .

j

One can easily see that the quasi-interpolant Mh u(x) =

j

u(hxj )

x/h ? xj?1 xj+1 ? x/h x x ζj ? xj + ζj?1 ? xj?1 xj+1 ? xj h xj ? xj?1 h c h2 u′′

L∞ (R)

satis?es |Mh u(x) ? u(x)|

where the constant c depends on the functions ζj .

+ ε |u(x)| ,

The outline of the paper is as follows. In Section 2 we consider an extension of the approximate quasi-interpolation to scattered nodes close to a uniform grid. We construct the quasi-interpolant Mu with gridded centers and coe?cients depending on scattered data and obtain approximation estimates. Further the results of some numerical experiments are presented which con?rm the predicted approximation orders. In Section 3 we show that an approximate partition of unity can be obtained from a given system of rapidly decaying approximating functions if these functions are multiplied by polynomials. Using the approximate partition of unity, one can construct approximate quasi-interpolants of high order approximation rate up to some prescribed saturation error. This is the topic of Section 4. Section 5 contains an application to the cubature of convolution integral operators. A construction of the approximate partition of unity for the case of Gaussians and some numerical examples are given in Section 6.

2

Quasi-interpolants with gridded centers

Here we give a simple extension of the quasi-interpolation operator on uniform grids (1.2) to a quasi-interpolant, which uses the values u(xj ) on a set of scattered nodes X = {xj } ? Rn if it is close to a uniform grid. Precisely we suppose Condition 2.1 There exist h > 0 and κ1 > 0 such that for any j ∈ Zn the ball B(hj, hκ1 ) centered at hj with radius hκ1 contains nodes of X. De?nition 2.1 Let xj ∈ X. The collection of mN = Vj,h = (N ? 1 + n)! ? 1 nodes xk ∈ X will be n!(N ? 1)! called the star of xj and denoted by st (xj ) if the Vandermonde matrix

xk ? x j α , |α| = 1, ..., N ? 1, (2.1) h is not singular. The union of the node xj and its star is denoted by ST (xj ) = xj ∪ st (xj ).

3

Condition 2.2 Assume Condition 2.1 and denote by xj ∈ X the node closest to h j. There exists κ2 > 0 such that for any j ∈ Zn (a) st (xj ) ? B(xj , h κ2 ) with | det Vj,h | (b)

j∈Zn

c > 0;

ST (xj ) = X.

2.1

Error estimate

(j)

To formulate our ?rst result we denote by {bα,k }, xk ∈ st (xj ), |α| = 1, ..., N ? 1, the elements of the inverse matrix of Vj,h and de?ne the functional Λj (u) = u(xj ) 1 ?

N ?1 |α|=1

xj j? h

α xk ∈st (ej ) x

(j) bα,k

+

xk ∈st (ej ) x

u(xk )

N ?1 |α|=1

bα,k j ?

(j)

xj h

α

.

Theorem 2.1 Suppose that for some K > n and the smallest integer n0 > n/2 the function η(x), x ∈ Rn , satis?es the conditions (1 + |x|)K |? β η(x)| ≤ Cβ for all 0 ≤ |β| ≤ n0 , and ? α(Fη ? 1)(0) = 0, 0 ≤ |α| < N . If the set of nodes X satis?es Conditions 2.1 and 2.2, then for any ε > 0 there exists D such that the quasi-interpolant M u(x) = D?n/2

j∈Zn N approximates any u ∈ W∞ (Rn ) with

Λj (u)η

x ? hj √ h D

(2.2)

|Mu(x) ? u(x)|

cN,η,D h sup |?N u| + ε

Rn

N

N ?1 k=0

√ |?k u(x)|( Dh)k ,

(2.3)

where cN,η,D does not depend on u and h.

N Proof. For given u ∈ W∞ (Rn ) we consider the quasi-interpolant (1.2) on the uniform grid {hj}

M u(x) = D?n/2

u(hj) η

j∈Zn

x ? hj √ , h D

with h given by Condition 2.1. It was proved in [16] that under the decay and moment conditions on η, formulated in the statement of the theorem, M u can be represented as M u(x) = u(x) +

N ?1 |α|=0

√

Dh 2πi

|α| ? αu(x)

α!

k∈Zn \{0}

√ ? αFη( Dk) e2πi(k,x) + UN (x)

with a function UN bounded by √ |UN (x)| ≤ C1 ( Dh)N sup |?N u|

Rn

√ and a constant C1 depending only on η. Moreover, the sequences {? αFη( D ·)} ∈ l1 (Zn ) and √ |? αFη( Dk)| → 0 as D → ∞ .

k∈Zn \{0}

4

Hence, we can ?nd D such that Mu satis?es the inequality |Mu(x) ? u(x)| |UN | + ε

N ?1 k=0

√ |?k u(x)|( Dh)k .

It remains to estimate |Mu ? Mu|. Recall the Taylor expansion of u around y ∈ Rn u(x) = with the remainder satisfying |RN (y, x)| cN |x ? y|N sup

B(y,|x?y|) N ?1 |α|=0

? αu(y) (x ? y)α + RN (y, x) α!

(2.4)

|?N u| .

(2.5)

For j ∈ Zn we choose xj ∈ X and use (2.4) with y = xj . We split Mu(x) = M (1) u(x) + D?n/2 with M (1) u(x) = D?n/2

N ?1

RN (xj , hj) η

j∈Zn

x ? hj √ h D

? αu(xj ) x ? hj √ (hj ? xj )α η . α! h D n |α|=0 j∈Z x ? hj √ h D

(2.6)

Because of |hj ? xj | ≤ κ1 h for any j we derive from (2.5) |M (1) u(x) ? Mu(x)| cN (κ1 h)N D?n/2

j∈Zn

η

sup

B(x,hκ1 )

|?N u| .

(2.7)

The next step is to approximate ? αu(xj ), 1 |α| < N , by a linear combination of u(xk ), (j) xk ∈ st (xj ). Let {aα }1 |α|≤N ?1 be the unique solution of the linear system with mN unknowns

N ?1 |α|=1

aα (xk ? xj )α = u(xk ) ? u(xj ) , α!

(j)

xk ∈ st (xj ) .

(2.8)

From (2.4) and (2.8) follows that

N ?1 |α|=1

xk ? xj h|α| (j) (aα ? ? αu(xj )) α! h

α

= RN (xj , xk ) .

?1 By Condition 2.2(a) the norms of Vj,h are bounded uniformly in j, this leads together with (2.5) to the inequality (j) |aα ? ? αu(xj )| C2 hN ?|α| sup |?N u|. (2.9) α! B(ej ,hκ2 ) x

Hence, if we replace the derivatives ? αu(xj ) in (2.6) by aα , then we get the sum D?n/2

j∈Zn

(j)

u(xj ) +

aα x ? hj √ , (hj ? xj )α η α! h D |α|=1

N ?1

(j)

5

which in view of aα = coincides with (2.2). Moreover, |M u(x) ? M

(1) (j)

α! h|α|

xk ∈st (ej ) x

bα,k (u(xk ) ? u(xj ))

(j)

u(x)|

C2 h

N

N ?1 |α|=1

κ1 D?n/2

j∈Zn

|α|

η

x ? hj √ h D

sup

B(x,hκ2 )

|?N u| .

(2.10)

Now the inequality sup D?n/2

Rn j∈Zn

x?j η √ D

≤ C3

for all D ≥ D0 > 0 implies that (2.7) and (2.10) lead to |Mu(x) ? M u(x)| ≤ C4 hN which proves (2.3). sup

B(x,hκ2 )

|?N u| ,

2.2

Numerical Experiments with Quasi-interpolants

The behavior of the quasi-interpolant Mu was tested by one- and two-dimensional experiments. In all cases the scattered grid is chosen such that any ball B(hj, h/2), j ∈ Zn , contains one randomly chosen node xj , thus xj = xj . All the computations were carried out with MATHEMATICA R . The following ?gures show the graph of Mu ? u for di?erent smooth functions u using basis functions for second (Fig. 1) and fourth (Fig. 2) order of approximation with h = 1/32 (dashed line) and h = 1/64 (solid line).

0.0012 0.00025

0.001

-1

-0.5

0.5

1

0.0008

-0.00025

0.0006

-0.0005

0.0004

-0.00075

0.0002

-0.001

-1

-0.5

0.5

1

-0.00125

Figure 1: The graphs of M u(x) ? u(x) with D = 2, N = 2, st (xj ) = {xj+1 }, when u(x) = x2 (on the

left) and u(x) = 1/(1 + x2 ). Dashed and solid lines correspond to h = 1/32 and h = 1/64.

In Fig. 3 the di?erence Mu ? u is plotted for the function u(x) = (1 + |x|2 )?1 , x ∈ R2 . 2 In formula (2.2) we use η(x) = π ?1 e?|x| , D = 2, for which N = 2, and therefore the star st (xj ) contains 2 nodes. We have chosen st (xj1 ,j2 ) = {xj1 +1,j2 , xj1 ,j2 +1 }. In Table 1 we give some computed values of M u(0) ? u(0) for D = 2 and D = 4 with di?erent h, which con?rm h2 -convergence of the two-dimensional quasi-interpolant.

6

-1

-0.5

0.5

1

2

10

6

2

10

6

-1

-0.5 2 10

6

0.5

1

6

10

6

1

10

5

1 1.2 10

5

10

5

(on the left) and u(x) = 1/(1 + x2 ). Dashed and solid lines correspond to h = 1/32 and h = 1/64.

Figure 2: The graphs of M u(x) ? u(x) with D = 4, N = 4, st (xj ) = {xj?2 , xj?1 , xj+1 }, when u(x) = x4

h 2?4 2?5 2?6 2?7 2?8

D=2 ?6.2 · 10?3 ?1.6 · 10?3 ?3.9 · 10?4 ?9.8 · 10?5 ?2.4 · 10?5

D=4 ?1.3 · 10?2 ?3.3 · 10?3 ?8.3 · 10?4 ?2.1 · 10?4 ?5.2 · 10?5

Table 1: Values of M u(0) ? u(0)

3

Approximate partition of unity

In the following two sections we consider irregularly distributed nodes. First we show that an approximate partition of unity can be obtained from a given system of approximating functions centered at the scattered nodes if these functions are multiplied by polynomials. We are mainly interested in rapidly decaying basis functions which are supported on the whole space. But we start with the simpler case of compactly supported basis functions.

3.1

Basis functions with compact support

Lemma 3.1 Let {B(xj , hj )}j 0 be an open locally ?nite covering of Rn by balls centered in xj and radii hj . Suppose that the multiplicity of this covering does not exceed a positive constant ?n and that there are positive constants c1 and c2 satisfying c1 hm hj c2 hm (3.1)

provided the balls B(xj , hj ) and B(xm , hm ) have common points. Furthermore, let {ηj } be a bounded sequence of continuous functions on Rn such that supp ηj ? B(xj , hj ). We assume that the functions Rn ? y → ηj (hj y) are continuous uniformly with respect to j and s(x) :=

j

ηj (x)

c on Rn

(3.2)

where c is a positive constant. Then for any ε > 0 there exists a sequence of polynomials {Pj } with the following properties: (i) the degrees of all Pj are bounded (they depend on the least majorant of the continuity modulae of ηj and the constants ε, c, c1 , c2 , ?n );

7

0.00025 0 -0.00025 -0.0005 -0.04 -0.02 0 0.02 0.04 0

0.04 0.02

-0.02 -0.04

Figure 3: The graph of Mu ? u with D = 2, N = 2, h = 1/128, when u(x) = 1/(1 + |x|2 ), x ∈ R2 . (ii) there is such a constant c0 that |Pj | < c0 on B(xj , hj ); (iii) the function Θ :=

j

Pj ηj for all x ∈ Rn .

(3.3)

satis?es |Θ(x) ? 1| < ε

(3.4)

Proof. Since the functions B(xj , 1) ? y → s(hj y) are continuous uniformly with respect to j, for an arbitrary positive δ there exist polynomials Pj subject to Pj (x) ? 1 < δ on B(xj , hj ) , s(x)

?1 L∞ )

and the degree of Pj , deg Pj , is independent of j. Letting δ = ε (?n η ηj (x) Pj (x) ? Then sup

Rn j

we obtain (3.5)

1 s(x)

≤ 1 s(x)

ε . ?n ≤ ε,

ηj (x) Pj (x) ?

(3.6)

since at most ?n terms of this sum are di?erent from zero. But ηj (x) Pj (x) ? 1 = s(x) ηj (x)Pj (x) ? 1 s(x) ηj (x) =

j j

j

j

ηj (x)Pj (x) ? 1 ,

which proves (3.4).

8

Remark 3.1 Let the functions {ηj } in Lemma 3.1 satisfy the additional hypothesis ηj ∈ C k (Rn ). Then one can ?nd a sequence of polynomials {Pj } of degrees Lj such that sup

B(xj ,hj )

Pj (x) ?

1 s(x)

C(k)

hk j Lk j

B(xj ,hj )

sup |?k s(x)|

(see, e.g., [18]). This shows that it su?ces to take polynomials Pj with deg Pj > c(k) ε?1/k in order to achieve the error ε in (3.6).

3.2

Basis functions with noncompact support

Here we consider approximating functions supported on the whole Rn . We suppose that the functions ηj are scaled translates x ? xj ηj (x) = η hj of a su?ciently smooth function η with rapid decay. Lemma 3.2 For any ε > 0 there exists Lε and polynomials {Pj } of degree deg Pj ≤ Lε such that the function Θ de?ned by (3.3) satis?es (3.4) under the following assumptions on η, the nodes {xj } and the scaling parameters {hj }: 1. There exists K > 0 such that cK :=

j

1 + h?1 | · ? xj | j

?K L∞

< ∞.

(3.7)

2. There exists p > 0 such that 1+|·|

K p2 |·|2

e

η

L∞

,

1+|·|

K

?η

L∞

≤ cp < ∞ .

(3.8)

3. There exists C ≥ 1 such that all indices j, m hj ≤C. hm 4. (3.2) is valid. Proof. From (3.7) and (3.8) the sum s(x) = j ηj (x) converges absolutely for any x to a positive, smooth and bounded function s. Suppose that we have shown that for any ε > 0 and all indices j there exist polynomials Pj such that ηj (x) Pj (x) ? 1 s(x) ≤ ε 1 + hj ?1 |x ? xj | cK

?K

(3.9)

,

(3.10)

(cK is de?ned in (3.7)) and deg Pj ≤ Lε . Then sup

Rn j

ηj (x) Pj (x) ?

1 s(x)

≤ ε,

and as in the proof of Lemma 3.1 we conclude sup

Rn j

ηj (x)Pj (x) ? 1 ≤ ε .

9

To establish (3.10) we use a result on weighted polynomial approximation from [5], which will 2 2 be stated in a simpli?ed form. Introduce the weight wp (x) = e?p |x| , p > 0, and consider the best weighted polynomial approximation of a function g given on Rn EN (g)wp ,∞ := inf sup |wp (x)(g(x) ? P(x))| ,

P∈ΠN Rn

where ΠN denotes the set of polynomials, which are of degree at most N in each variable 1 x1 , . . . , xn . Then for g ∈ W∞ (Rn ) EN (g)wp ,∞ ≤ C ?g L∞ . N 1/2 (3.11)

Let us ?x an index j and make the change of variables y = hj ?1 (x ? xj ). Then (3.10) is proved if we show that there exists a polynomial Pj such that for all y ∈ Rn η(y) Pj (y) ? 1 s(y) ? ≤ ε 1 + |y| cK

?K

(3.12)

1 with s(y) = s(hj y + xj ). Since s?1 ∈ W∞ (Rn ) according to (3.11) we can ?nd a polynomial Pj ? ? satisfying 1 ε 2 2 e?p |y| < sup Pj (y) ? n s(y) ? cp cK R

with the constant cp in the decay condition (3.8). Now (3.12) follows immediately from |η(y)| 1 + |y|

K

≤ cp e?p

2 |y|2

.

From (3.11) we see that deg Pj depends on the norm of the gradient sup ?

Rn

1 1 1 = hj sup ? ≤ sup 2 s(y) ? s(x) Rn Rn (s(x))

m

hj x ? xm ?η hm hm

,

which is bounded uniformly in j in view of (3.2), (3.8), and (3.9).

4

Quasi-interpolants of a general form

N In this section we study the approximation of functions u ∈ W∞ (Rn ) by the quasi-interpolant (1.4). We will show that within the class of generating functions of the form polynomial times compactly supported or rapidly decaying generating function it su?ces to have an approximate partition of unity in order to construct approximate quasi-interpolants of high order accuracy up to some prescribed saturation error.

Let us assume the following hypothesis concerning the grid {xj }: Condition 4.1 For any xj there exists a ball B(xj , hj ) which contains mN nodes xk ∈ st (xj ) with xk ? xj α N ?1 c, (4.1) | det Vj,hj | = det hj |α|=1 (see De?nition 2.1), with c > 0 not depending on xj .

10

4.1

Compactly supported basis functions

Theorem 4.1 Suppose that the function system {ηj } satis?es the conditions of Lemma 3.1, let N u ∈ W∞ (Rn ) and ε > 0 arbitrary. There exist polynomials Pj,k , independent on u, whose degrees are uniformly bounded, such that the quasi-interpolant M u(x) =

k

u(xk )

ST (xj )?xk

Pj,k (x)ηj (x)

(4.2)

satis?es the estimate |M u(x) ? u(x)| ChN m sup

B(xm ,λ hm )

|?N u| + ε |u(x)|,

(4.3)

where xm is an arbitrary node and x is any point of the ball B(xm , hm ). By λ we denote a constant greater than 1 which depends on c1 and c2 in (3.1). The constant C does not depend on hm , m and ε. Proof. For given ε we choose polynomials Pj (x) such that the function (3.3) satis?es |Θ(x) ? 1| < ε and introduce the auxiliary quasi-interpolant M

(1) N ?1 j |α|=0

for all x ∈ Rn ,

u(x) =

? αu(xj ) (x ? xj )α Pj (x)ηj (x) . α!

(4.4)

Using the Taylor expansion (2.4) with y = xj we write M (1) u(x) as M (1) u(x) = u(x)Θ(x) ? which gives |M (1) u(x) ? u(x)| |RN (xj , x)Pj (x)ηj (x)| + |u(x)| |Θ(x) ? 1| . RN (xj , x)Pj (x)ηj (x) ,

j

j

This, together with the estimate for the remainder (2.5), shows that for x ∈ B(xm , hm ) |M (1) u(x) ? u(x)| C1 hN m sup

B(xm ,λ hm )

|?N u| + ε|u(x)| ,

(4.5)

where the ball B(xm , λ hm ) contains all balls B(xj , hj ) such that B(xj , hj ) and B(xm , hm ) intersect. ? αu(x Similar to the proof of Theorem 2.1 we approximate in M (1) u the values of the derivatives j ) by a linear combination of u(xk ), where xk ∈ st (xj ). The solution of

N ?1 |α|=1

aα (xk ? xj )α = u(xk ) ? u(xj ) , α!

(j)

xk ∈ st (xj ) ,

is given by aα =

(j) (j) bα,k (u(xk ) |α| hj xk ∈st (xj )

α!

? u(xj )),

11

(4.4) by {aα } gives the quasi-interpolant M u(x) =

j

where {bα,k } are the elements of the inverse of Vj,hj . Replacing the derivatives {? αu(xj )} in

(j) N ?1 xk ∈st (xj ) |α|=1

(j)

u(xj ) 1 ? +

xk ∈st (xj )

bα,k

(j)

x ? xj hj

α

α

u(xk )

N ?1 |α|=1

bα,k

(j)

x ? xj hj

Pj (x)ηj (x)

=

j xk ∈ST (xj )

u(xk ) Pj,k (x) ηj (x)

which can be rewritten as the quasi-interpolant (4.2). By (2.4) we obtain again

N ?1 |α|=1

hj

|α|

α!

(aα ? ? αu(xj ))

(j)

xk ? x j hj

α

= RN (xj , xk ) ,

?1 hence the boundedness of Vj,hj from Condition 4.1 and the estimate of the remainder (2.5) imply (j) N ?|α| |aα ? ? αu(xj )| α! C2 hj sup |?N u|. B(xj ,hj )

Therefore we obtain the inequality |M u(x) ? M (1) u(x)| and, for any x ∈ B(xm , hm ), |M u(x) ? M (1) u(x)| This inequality and (4.5) lead to (4.3). C3 hN m sup

B(xm ,λ hm )

C2

j

hN sup |?N u| j

B(xj ,hj )

N ?1 |α|=1

x ? xj hj

|α|

|Pj (x)ηj (x)|

|?N u|.

4.2

Quasi-interpolants with noncompactly supported basis functions

Theorem 4.2 Suppose that additionally to the conditions of Lemma 3.2 the inequality 1 + h?1 | · ? xj | j

N ?K L∞

j

<∞

(4.6)

N is ful?lled, let u ∈ W∞ (Rn ) and ε > 0 arbitrary. There exist polynomials Pj,k , independent on u, whose degrees are uniformly bounded, such that the quasi-interpolant

M u(x) =

k

u(xk )

ST (xj )?xk

Pj,k

x ? xj x ? xj η hj hj

(4.7)

satis?es the estimate |M u(x) ? u(x)| C sup hN ?N u m

m L∞

+ ε |u(x)| .

(4.8)

The constant C does not depend on u and ε.

12

Proof. Analogously to (4.4) we introduce the quasi-interpolant M (1) u(x) =

j N ?1 |α|=0

x ? xj x ? xj ? αu(xj ) (x ? xj )α Pj η α! hj hj

and obtain the estimate |M (1) u(x) ? u(x)| From (3.12) we have Pj x ? xj x ? xj η hj hj ≤ x ? xj 1 η c hj + |x ? xj | ε 1+ cK hj

?K

RN (xj , x)Pj

j

x ? xj x ? xj η hj hj

+ |u(x)| |Θ(x) ? 1| .

with the lower bound c of s(x) (see (3.2)). Together with (3.8) and (2.5) this provides RN (xj , x)Pj x ? xj x ? xj η hj hj x ? xj ≤ cN hN ?N u L∞ j hj

N

cp ?p2 |x?xj |2 /h2 ε j + e c cK

1+

x ? xj hj

?K

resulting in |M (1) u(x) ? u(x)| |u(x)| |Θ(x) ? 1| + cN ?N u x ? xj cp ?p2 |x|2 N hN 1 + e |x| L∞ × j c hj

j L∞ ?K

+

ε cK

hN 1 + j

j

x ? xj hj

N ?K

.

Now we can proceed as in the proof of Theorem 4.1. Remark 4.1 Let for ?xed x the parameter κx be chosen such that e?p

|xj ?x|>κx

2 |x?x |2 /h2 j j

x ? xj hj

N

1+

x ? xj hj

?K

< ε.

Then the estimate (4.8) can be sharpened to |M u(x) ? u(x)| C

|xj ?x|≤κx

max

hN j

B(x,κx )

sup |?N u| + ε (|u(x)| + ?N u

L∞ ) .

5

Application to the computation of integral operators

Here we discuss a direct application of the quasi-interpolation formula (4.7) for the important 2 example η(x) = e?|x| . Suppose that the density of the integral operator with radial kernel Ku(x) = is approximated by the quasi-interpolant M u(x) =

j xk ∈ST (xj )

Rn

g(|x ? y|)u(y) dy

(5.1)

u(xk ) Pj,k

x ? xj ?|x?xj |2 /h2 j . e hj

(5.2)

Using the following lemma it is easy to derive cubature formulae for (5.1).

13

L

L

Lemma 5.1 For any P(x) =

the polynomial Sβ (t) being de?ned by Sβ (t) = 1 2i

|β|

|β|=0

cβ x one can write P(x)e

β

?|x|2

=

|β|=0

cβ Sβ (?x ) e?|x| with

2

Hβ

t , 2i

2 2

(5.3)

where Hβ denotes the Hermite polynomial of n variables Hβ (t) = e |t| (??t )β e?|t| . Proof. We are looking for the polynomial Sβ (t) de?ned by the relation xβ e?|x| = Sβ (?x )e?|x| , Since and we obtain (5.3). In view of Lemma 5.1 we can write Pj,k (x) e?|x| = Tj,k (?x ) e?|x| with some polynomials Tj,k (x). Then (5.2) can be rewritten as M u(x) =

j xk ∈ST (xj )

2 2 2 2

x ∈ Rn .

2 |λ|2

(5.4)

F(Sβ (?x )e?|x| )(λ) = π n/2 e?π F(xβ e?|x| )(λ) = π n/2 ?

2

2

Sβ (2πiλ) e?π

2 |λ|2

?λ 2πi

β

u(xk ) Tj,k (?hj ?xj ) e?|x?xj |

2 /h2 j

.

The cubature formula for the integral Ku is obtained by replacing u by its quasi-interpolant M u ? Ku(x) = KM u(x) =

j xk ∈ST (xj )

u(xk ) Tj,k (?hj ?xj ) hn j

Rn

g(hj |z|) e?|z+tj | dz ,

2

(5.5)

where tj = (x ? xj )/hj . By introducing spherical coordinates in Rn we obtain g(hj |z|)e

?|z+tj |2

dz = e

?|tj |2

∞ 0

?n?1 g(hj ?) e?? d ?

S n?1

2

e

?2?|tj | cos(ωtj ,ω)

dσω ,

Rn

where S n?1 is the unit sphere in Rn . The integral over S n?1 can be represented by means of the modi?ed Bessel functions of the ?rst kind In in the following way e

S n?1 ?2?|tj | cos(ωtj ,ω)

2 π (n?1)/2 dσω = Γ( n?1 ) 2

π

0

e?2?|tj | cos ? (sin ?)n?2 d? = 2π n/2 (? |tj |)1?n/2 I n?2 (2?|tj |)

2

(see [22, p.154] and [23, p.79]). If we denote by L(r) = 2 π

n/2 1?n/2 ?r 2 ∞ 0

r

e

?n/2 e?? g(hj ?) I(n?2)/2 (2? r) d? ,

2

then (5.5) leads to the following cubature formula for the integral Ku ? Ku(x) = hn j

j xk ∈ST (xj )

u(xk ) Tj,k (?hj ?xj ) L

|x ? xj | . hj

14

6

Construction of the Θ-function with Gaussians

In this section we propose a method to construct the approximate partition of unity for the basis functions 2 2 ηj (x) = (π D)?n/2 e?|x?xj | /hj D if the set of nodes {xj } satisfy Condition 2.1 piecewise with di?erent grid sizes hj .

6.1

Scattered nodes close to a piecewise uniform grid

Let us explain the assumption on the nodes: Suppose that a subset of nodes xj ∈ J0 satis?es Condition 2.1 with h = h1 . The remaining nodes xk ∈ X \ J0 lie in a bounded domain ? ? Rn and satisfy Condition 2.1 with h = h2 = Hh1 for some small H. To keep good local properties of quasi-interpolants one wants to approximate the data at these nodes by functions of the form 2 2 polynomial times e?|x?xk | /h2 D , whereas outside ? quasi-interpolants with functions of the form 2 /h2 D polynomial times e?|x?xj | 1 should be used. Our aim is, to develop a simple method to construct polynomials Pj such that Θ(x) = (π D)?n/2

xj ∈J1

Pj

x ? xj ?|x?xj |2 /h2 D 1 √ e + h1 D x

k ∈J2

Pk

x ? xk ?|x?xk |2 /h2 D 2 √ e h2 D

(6.1)

is almost the constant function 1. Here J2 denotes the set of nodes xk ∈ ? and J1 = {xj } \ J2 the remaining nodes. First we derive a piecewise uniform grid on Rn which is associated to the splitting of the set of scattered nodes into J1 and J2 . We start with Poisson’s summation formula for Gaussians (π D)?n/2

m∈Zn

e?|x?h1 m|

2 /h2 D 1

=

k∈Zn

e?π

2 D|k|2

e 2πi(x,k)/h1 ,

which shows that 1 ? (π D)?n/2

m∈Zn

e?|x?h1 m|

2 /h2 D 1

≤ C1 e?π

2D

with some constant C1 depending only on the space dimension. Thus for any ε > 0 there exists D > 0 such that the function system {e?|x?h1 m| /h1 D }m∈Zn forms an approximate partition of unity with accuracy ε. We can represent any of these functions very accurately by a linear combination of dilated Gaussians due to the equation (see [15]) e?|x|

2 /D 1 2 2

=

D1 πD(D1 ? h2 D) ?e

?|x|2 /D1

n/2 m∈Zn

e ?h

2 |m|2 /(D ?h2 D) 1

e ?|x?hm|

2 /h2 D

e 2πi(D1 ?h

k∈Zn \{0}

2 D)(x,k)/hD

1

e ?π

2 D(D ?h2 D)|k|2 /D 1 1

(6.2) ,

which is valid for any D1 > h2 D > 0. Applied to our setting with h = h2 and D1 = h2 D we 1 obtain the approximate re?nement relation e?|x|

2 /h2 D 1

?

ak e?|x?h2 k|

k∈Zn

2 /h2 D 2

≤ C2 e?|x|

2 /h2 D 1

e?π

2 D(1?H 2 )

(6.3)

(because by assumption h2 = Hh1 ) with the coe?cients ak = πD(1 ? H 2 )

?n/2 ?H 2 |k|2 /(1?H 2 )D

e

.

15

Again, the constant C2 depends only on the space dimension. De?ne by S ∈ Zn the minimal index set such that 2 2 ak < e?π D(1?H ) .

k∈Zn \S

Then it is clear from (6.3) that for any disjoint Z1 and Z2 with Z1 ∪ Z2 = Zn 1 ? (π D)?n/2 e?|x?h1 m|

m∈Z1

2 /h2 D 1

+

m∈Z2 k∈S

ak e?|x?h1 m?h2 k|

2 /h2 D 2

≤ C3 e?π

2 D(1?H 2 )

.

(6.4) Condition 6.1 Denote Z2 = {m ∈ Zn : h1 m + h2 k ∈ ? for all k ∈ S}. The constant κ1 of Condition 2.1 and the domain ? are such that for all nodes xk ∈ ?, i.e. the nodes belonging to J2 , one can ?nd m ∈ Z2 , k ∈ S with |xk ? h1 m ? h2 k| < κ1 h2 . Setting Z1 = Zn \ Z2 we connect the index sets Z1 , Z2 with the splitting of the scattered nodes into J1 , J2 . By this way we construct an approximate partition of unity using Gaussians with the ”large” scaling factor h1 centered at the uniform grid G1 := {h1 m}m∈Z1 outside ? and using Gaussians with scaling factor h2 and the centers G2 := {h1 m + h2 k}m∈Z2 ,k∈S in ?.

It is obvious, that the above de?nition of piecewise quasi-uniformly distributed scattered nodes and the construction of an associated approximate partition of unity on piecewise uniform grids can be extended to ?nitely many scaling factors hj . Since there will be no di?erence for the subsequent considerations we will restrict to the two-scale case. From (6.4) we see that for any ε > 0, and given h1 and h2 there exists D > 0 such that the linear combination (π D)?n/2

g1 ∈G1

e?|x?g1 |

2 /h2 D 1

+

g2 ∈G2

ag2 e?|x?g2 | ?

2 /h2 D 2

(6.5)

with ag2 = ak for g2 = h1 m + h2 k, m ∈ Z2 , k ∈ S, approximates the constant function 1 with an ? error less than ε/2. The idea of constructing the Θ-function (6.1) is to choose for each g1 ∈ G1 and g2 ∈ G2 ?nite sets of nodes Σ(g1 ) ? J1 and Σ(g2 ) ? J2 , respectively, and to determine polynomials Pj,g? such that

xj ∈Σ(g? )

Pj,g?

x ? xj ?|x?xj |2 /h2 D ? √ e h? D

approximate

e?|x?g? |

2 /h2 D ?

, ? = 1, 2 .

If the L∞ -error of the sums over g? can be controlled, then we get e?|x?g1 |

g1 ∈G1

2 /h2 D 1

?

xj ∈J1

Pj

x ? xj ?|x?xj |2 /h2 D 1 √ e h1 D

with the polynomials Pj = and ag2 e?|x?g2 | ?

g2 ∈G2

2 /h2 D 2

g1 ∈G(xj )

Pj,g1 x ? xk ?|x?xk |2 /h2 D 2 √ e h2 D

(6.6)

?

xk ∈J2

Pk

with the polynomials Pk =

g2 ∈G(xk )

ag2 Pk,g2 , ?

(6.7)

16

where we denote G(xj ) = {g : xj ∈ Σ(g)}. Note that we have to choose the subsets Σ(g? ) such that the sets G(xj ) ? G? are ?nite and nonempty for any node xj ∈ J? . Additionally, one has to choose these sets such that for some κ1 > 0 and any g? ∈ G? the ball B(g? , κ1 h? ) contains at least one node xj ∈ J? . This is always possible, since Conditions 2.1 resp. 6.1 are valid. The proposed construction method of Θ does not require solving a large algebraic system. Instead, to obtain the local representation of Θ one has to solve a small number of approximation problems, which are reduced in the next sections to linear systems of moderate size. After this preparation we write Θ as Θ(x) =(π D)?n/2

g1 ∈G1

e?|x?g1 | ag2 e ?

g2 ∈G2

2 /h2 D 1

+

g1 ∈G1

ωg1 ( +

x ) h1 ag2 ωg2 ( ? x ), h2

+ (π D) where ωg? (y) = (π D)?n/2

?n/2

?|x?g2 |2 /h2 D 2

g2 ∈G2

h? yj ∈Σ(g? )

Pj,g?

y ? yj ?|y?yj |2 /D 2 √ e ? e?|y?g? /h? | /D D

(6.8)

with yj = xj /h? , xj ∈ J? . Hence for su?ciently large D Θ(x) ? 1 < ε + 2 ωg1

g1 ∈G1

x h1

+

g2 ∈G2

ag2 ωg2 ?

x h2

.

(6.9)

6.2

Construction of Polynomials

Let us introduce ω(y) := (π D)?n/2

yj ∈Σ

Pj

y ? yj ?|y?yj |2 /D 2 √ e ? e?|y| /D , D

(6.10)

where Σ is some ?nite point set in Rn . We will describe a method for constructing polynomials 2 Pj such that e ρ|y| |ω(y)| for some ρ > 0 becomes small. In what follows we use the representation

Lj

Pj (x) = Hence by Lemma 5.1 Pj

cj,β xβ .

|β|=0

j √ y ? yj ?|y?yj |2 /D 2 √ cj,β Sβ ( D?y ) e?|y?yj | /D . e = D |β|=0

L

and ω can be written as

Lj

ω(y) = (πD)

?n/2 yj ∈Σ |β|=0

√ 2 2 cj,β Sβ ( D?y ) e?|y?yj | /D ? e?|y| /D .

(6.11)

To estimate the L∞ -norm of ω we represent this function as convolution.

17

Lemma 6.1 Let P(t) be a polynomial and let 0 < D0 < D. Then P(?ξ ) e?|ξ?x|

2 /D

= c1 e?|ξ|

2 /(D?D ) 0

? P(?ξ ) e?|ξ?x|

n/2

2 /D 0

,

where ? stands for the convolution operator and c1 = Proof. From e?|ξ?x| we obtain P(?ξ )e?|ξ?x|

2 /D 2 /D

D πD0 (D ? D0 ) e?|ξ?t|

.

= c1

Rn

2 /(D?D ) 0

e?|t?x|

2 /D

0

dt

= P(??x )e?|ξ?x|

2 /D

= c1

Rn

e?|ξ?t|

2 /(D?D ) 0

P(?t )e?|t?x|

2 /D

0

dt .

Using Lemma 6.1 and (6.11) we write ω as c1 ω(y) = (πD)n/2

Lj

e

Rn

?|y?t|2 /(D?D0 ) yj ∈Σ |β|=0

√ 2 2 cj,β Sβ ( D?t )e?|t?yj | /D0 ? e?|t| /D0 dt (6.12)

and, by Cauchy’s inequality, we obtain

Lj

||ω||L∞ where

c2

yj ∈Σ |β|=0

√ 2 2 cj,β Sβ ( D?t )e?|t?yj | /D0 ? e?|t| /D0

L2

,

(6.13)

If we de?ne polynomials Tβ by

c2 = (πD0 )?n/2 (2π(D ? D0 ))?n/4 .

2 /D 0

Tβ (x) = e |x| then ||ω||L∞ c2 e

?| · |2 /D0

√ 2 Sβ ( D?x )e?|x| /D0 ,

Lj

(6.14)

?

yj ∈Σ |β|=0

cj,β Tβ ( · ? yj )e?| · ?yj |

2 /D

0

L2

.

An estimate for the sum of |ωg? | can be derived from Lemma 6.2 Let 0 < D0 < D and denote ρ = D ? D0 . Then the estimate (D ? D0 )2 + DD0

2

sup |ω(y)| e ρ|y|

Rn

c3

Q(c)

(6.15)

is valid, where for c = {cj,β } the quadratic form Q(c) is de?ned by

Lj

Q(c) =

Rn

e

2(D?D0 )|t|2 /DD0

e

?|t|2 /D0

?

yj ∈Σ |β|=0

cj,β Tβ (t ? yj ) e?|t?yj |

2 /D

2

0

dt

(6.16)

and c3 =

Dn/4 . (2π 3 D0 (D ? D0 )((D ? D0 )2 + DD0 ))n/4

18

Proof. Starting with (6.12), using (6.14) and |x ? t|2 = √ t ax ? √ a

2

+ (1 ? a)|x|2 +

a?1 2 |t| a

for a > 0, we derive the representation ω(y) = c1 2 e?(1?a)|y| /(D?D0 ) n/2 (πD) e?|t?ax|

2 /a(D?D ) 0

e(1?a)|t|

2 /a(D?D ) 0

Rn Lj

× Then Cauchy’s inequality leads to ω(y) e(1?a)|y| ≤ c3 with e

Rn

2 /(D?D ) 0

yj ∈Σ |β|=0

cj,β Tβ (t ? yj )e?|t?yj |

2 /D

0

? e?|t|

2 /D 0

) dt .

Lj 2(1?a)|t|2 /a(D?D0 ) yj ∈Σ |β|=0

cj,β Tβ (t ? yj )e?|t?yj |

2 /D

0

? e?|t|

2 /D 0

2

dt

1/2

(6.17)

c3 = (πD0 )?n/2 If we choose the parameter a such that (1 ? a)|t|2 |t|2 |t|2 ? =? , a(D ? D0 ) D0 D

a 2π(D ? D0 )

n/4

.

i.e. a =

D D0 , (D ? D0 )2 + D D0

then the right hand side of (6.17) takes the form (6.16). Next we estimate r := min Q(c) .

c

(6.18)

Using (6.14), after elementary calculations one obtains

Lj

Q(c) =

Rn

e

n/2

(D?D0 )|t|2 /DD0 yj ∈Σ |β|=0 Lj

√ 2 2 cj,β Sβ ( D?t ) e?|t?yj | /D0 ? e?|t| /D0

Lj Lk

2

dt

= with

πD 2

1?2

yj ∈Σ |β|=0

cj,β Cβ,0 (yj , 0) +

yj ,yk ∈Σ |β|=0 |γ|=0

cj,β ck,γ Cβ,γ (yj , yk )

√ √ 2 2 2 2 2 Cβ,γ (x, y) := Sβ (? D?x )Sγ (? D?y ) e (D?D0 )(|x| +|y| )/D0 e?D|x?y| /2D0 .

Lj yj ∈Σ |β|=0

The minimum of Q(c) is attained by the solution c = {cj,β } of the linear system Cβ,γ (yj , yk )cj,β = C0,γ (0, yk ) , yk ∈ Σ , 0 ≤ |γ| ≤ Lk . (6.19)

19

Then by Lemma 6.2 the sum Pj y ? yj y ? yj ?|y?yj |2 /D √ cj,β √ e = D D y ∈Σ |β|=0

j

Lj

β

e?|y?yj |

2 /D

(6.20)

yj ∈Σ

approximates e?|y|

2 /D

with

2 /D

(π D)?n/2 e?|y|

?

yj ∈Σ

Pj

y ? yj ?|y?yj |2 /D 2 √ e ≤ c3 e ?ρ|y| r1/2 . D

In the next section we show that (6.19) has a unique solution and give an estimate of r.

6.3

Existence and estimates

Let us give another representation of the quadratic form Q(c) de?ned by (6.16). Introduce the transformed points D yj , yj ∈ Σ , tj = D0 then, because of 1 1 D ? D0 D ? D0 2 |yj |2 |t| ? |t ? yj |2 = ? |t ? tj |2 + 2 D D0 D0 D D0 Q(c) can be written as

Lj

Q(c) =

Rn

e

?|t|2 /D

?

e

2 (D?D0 )|yj |2 /D0

yj ∈Σ

|β|=0

cj,β Tβ (t ? yj ) e?|t?tj |

2 /D

2

dt .

(6.21)

Since Tβ are polynomials of degree β, the minimum problem for Q(c) is equivalent to ?nding the best L2 -approximation

Lj

min

dj,β Rn

e

?|t|2 /D

?

yj ∈Σ |β|=0

dj,β (t ? tj )β e?|t?tj |

2 /D

2

dt .

Lemma 6.3 Let {xj } a ?nite collection of nodes. For all Lj ≥ 0 the polynomials Pj of degree Lj , which minimize e?| · | ? are uniquely determined.

Lj

2

j

Pj ( · ? xj ) e?| · ?xj |

2

L2

,

(6.22)

Proof. The application of Lemma 5.1 gives for Pj (x) =

2 2

cj,β xβ

|β|=0 Lj

e?| · | ? = π 2

n/2

j

Pj ( · ? xj )e?| · ?xj |

Lj

2 L2

=

Rn

e?|x| ?

Lj ,Lk

2

j

|β|=0

cj,β Sβ (?x ) e?|x?xj |

2

2

dx

1?2

j

|β|=0

cj,β Bβ,0 (xj , 0) +

j,k |β|,|γ|=0

cj,β ck,γ Bβ,γ (xj , xk ) ,

20

where we use the notation Bβ,γ (x, y) = Sβ (??x ) Sγ (??y ) e?|x?y|

2 /2

.

The coe?cients {cj,β } are chosen to minimize (6.22), that is the vector {cj,β } is a solution of the linear system

Lj

j

|β|=0

cj,β Bβ,γ (xj , xk ) = B0,γ (0, xk ).

(6.23)

To show that the matrix of this system is positive de?nite we use the representation e?|x?y| which implies Bβ,γ (x, y) = (2π)?n/2 Sβ (?it) Sγ (?it) e?|t|

2 /2 2 /2

= (2π)?n/2

Rn

e?|t|

2 /2

ei(t,x) e?i(t,y) dt ,

ei(t,x) e?i(t,y) dt .

Rn

Let {vj,β } be a constant vector and consider the sesquilinear form

Lj ,Lk

j,k |β|,|γ|=0

Bβ,γ (xj , xk ) vj,β vk,γ

Lj ,Lk

= (2π)

?n/2 j,k |β|,|γ|=0

vj,β vk,γ

Rn Lj

Sβ (?it) Sγ (?it) e?|t|

2

2 /2

e i(t,xj ?xk ) dt

= (2π)?n/2

Rn

e?|t|

2 /2

j

|β|=0

vj,β Sβ (?it) ei(t,xj ) dt ≥ 0 .

The change of integration and summation is valid because the integrand is absolutely integrable and the sums are ?nite. We have to show that the inequality is strict when {vj,β } = 0. This is equivalent to show that

Lj

σ(t) =

j |β|=0

vj,β Sβ (?it) ei(t,xj ) = 0

identically only if all components vj,β = 0 for all j and β. To this end similar to [19, Lemma 3.1] we introduce the function

Lj

fε (x) :=

Rn

e?ε

2 |t|2 /4

σ(t) e?i(t,x) dt =

j |β|=0

vj,β Sβ (?x )

e?ε

2 |t|2 /4

e i(t,xj ?x) dt

Rn

Lj

= ε?n

j |β|=0

vj,β Sβ (?x )

Lj

e?|t|

2 /4

e i(t,xj ?x)/ε dt

Rn

2 /ε2

=

4π ε2

n/2 j

|β|=0

vj,β Sβ (?x )e?|x?xj |

.

21

Let us ?x k and consider fε (x) for |x ? xk | < ε for su?ciently small ε > 0. 2 2 Sβ (?x )e?|x?xj | /ε → 0 as ε → 0 and

Lk |β|=0 Lk

We have

vk,β Sβ (?x )e

?|x?xk |2 /ε2

=

|β|=0

vk,β Sβ (ε?1 ?t )e?|t|

2

t=(x?xk )/ε

.

Because of fε (x) = 0 for all ε > 0 there exist ε0 such that

Lk |β|=0

vk,β Sβ (?x )e?|x?xk |

2 /ε2

=0

(6.24)

for ε ≤ ε0 . On the other hand,

Lk |β|=0

vk,β Sβ (?x )e?|x?xk |

2 /ε2

= ε?2Lk e?|x?xk |

2 /ε2

Π2Lk (ε) ,

where Π2Lk (ε) is a polynomial of degree 2Lk in ε with coe?cients depending on |x ? xk |. Therefore (6.24) holds for any ε > 0, in particular

Lk |β|=0

vk,β Sβ (?x )e?|x?xk | = 0 .

2 2

2

Since by (5.4) we conclude vk,β = 0 for all β. Sβ (?x )e?|x?xk | = (x ? xk )β e?|x?xk | ,

Let now for given Σ and degrees Lj the coe?cient vector c = {cj,β } be a unique solution of the linear system (6.19). To estimate r = Q(c) we denote by y? ∈ Σ the point closest to 0 and by L? the degree of the polynomial P?. Lemma 6.4 The minimal value of (6.18) can be estimated by r≤ π 2

n/2 D L? +1+n/2 |y?|2(L? +1) 2(L? +1)

D0

(L? + 1)!

.

Proof. It follows from the representation (6.21) that

Lj

r=

Rn yj ∈Σ

e

2 (D?D0 )|yj |2 /D0

|β|=0

cj,β Tβ (t ? yj ) e?|t?tj |

2 /D

2 /D

? e?|t|

2 /D

2

dt

≤ min = D 2

P∈ΠL?

Rn n/2

P(t)e?|t?t? | min e?|t|

Rn

2

2 /D

? e?|t|

2

dt

√ 2(t,z? ) 2

P∈ΠL?

P(t) ? e?|z? | e?

2

dt

√ with t? = Dy?/D0 , z? = Dy?/D0 , and ΠL? denotes the set of polynomials of degree L?. The minimum is attained when P(t) = 1 2|β| β!π n/2

L?

aβ Hβ (t)

|β|=0

22

with the coe?cients aβ = e?|z? |

2

2|β| β! π n/2

e

Rn

?|t|2

Hβ (t)e

√ ? 2(t,z? )

dt =

e?|z? |

2

2|β| β!π n/2

e?

Rn

√

2(t,z? )

(??t )β e?|t| dt .

2

Integrating by parts, we obtain aβ = π n/4 which together with

∞ |β|=L? +1

(?1)|β| zβ ?|z? |2 /2 ? √ e , β!

z2β ? = β!

∞ s=L? +1

|z?|2s s!

|z?|2(L? +1) |z? |2 e (L? + 1)!

leads to r≤ D 2

n/2

∞ |β|=L? +1

|aβ |2 = π n/2

D 2

n/2 |z?|2(L? +1)

(L? + 1)!

.

6.4

Approximate partition of unity with Gaussians

Now we are in position to prove the main result of this section. Suppose that the nodes {xj } are as described in subsection 6.1 and let G1 ∪ G2 be the associated piecewise uniform grid with stepsizes h1 and h2 . Assign to each grid point g? ∈ G? , ? = 1, 2, a ?nite set of nodes Σ(g? ), ?x a common degree L for all polynomials Pj in (6.1) and solve the linear system

L xj ∈Σ(g? ) |β|=0

Cβ,γ

xj ? g? xk ? g? xk ? g? , cj,β (g? ) = C0,γ 0, h? h? h?

(6.25)

for all xk ∈ Σ(g? ) and 0 ≤ |γ| ≤ L with

√ √ 2 2 2 2 2 Cβ,γ (x, y) = Sβ (? D?x )Sγ (? D?y ) e (D?D0 )(|x| +|y| )/D0 e?D|x?y| /2D0 ,

D0 < D is some arbitrary positive number. Following (6.20) de?ne the polynomials Pj Pk x ? xj √ h1 D x ? xk √ h2 D

L

=

g1 ∈G(xj ) |β|=0 L

cj,β (g1 )

x ? xj √ h1 D

β

,

β

xj ∈ J1 , (6.26) , xk ∈ J2 ,

=

g2 ∈G(xk

x ? xk √ ag2 ck,β (g2 ) ? h2 D ) |β|=0

Theorem 6.1 Under Conditions 2.1 and 6.1 on the scattered nodes {xj } for any ε > 0 there exist D > 0 and L such that the function (6.1) is an approximate partition of unity satisfying |Θ(x) ? 1| < ε for all x ∈ Rn ,

if the polynomials {Pj } of degree L are generated via (6.26) by the solutions {cj,β (g? )} of the linear systems (6.25) for all g? ∈ G1 ∪ G2 .

23

Proof. From (6.9) we have to show that sup

Rn g1 ∈G1

ωg1

x h1

+

g2 ∈G2

ag2 ωg2 ?

x h2

≤

ε 2

(6.27)

if L is su?ciently large. We start with estimating the ?rst sum ωg1

g1 ∈G1

x h1

,

where g1 = h1 m, m ∈ Z1 ? Zn . Using (6.10) we can write ωg1 x x =ω ?m , h1 h1

where the points yj in (6.10) are given by yj = xj /h1 ? m, xj ∈ Σ(g1 ). By Lemmas 6.2 and 6.4 we have ωg1

g1 ∈G1

x h1

≤ c3

π 2

n/4 m∈Z1

e?ρ|x/h1 ?m|

2

D(L? m +1+n/2)/2 D0 ? m

L +1

(L?m

x?m ?m + 1)! h1

L? m +1

where x?m ∈ Σ(g1 ) is the node closest to g1 = h1 m and L?m is the degree of the polynomial P?m ,g1 . Since |x?m ? h1 m| ≤ κ1 h1 by Condition 2.1 and L?m = L for all ?m we conclude that ωg1

g1 ∈G1

x h1

≤ c3

π 2

n/4 D (L+1+n/2)/2 κL+1 1 L+1 D0 (L + 1)!

sup

Rn m∈Z1

e?ρ|x/h1 ?m| .

2

(6.28)

From ρ=

D ? D0 ∈ (0, D) (D ? D0 )2 + DD0 x h

for any ?xed D0 ∈ (0, D) ,

we see, that for ?xed D and D0 ωg1

g1 ∈G1

→ 0 if

L → ∞.

(6.29)

We turn to ag2 ωg2 ?

g2 ∈G2

x h2

with g2 = h1 m + h2 k, m ∈ Z2 , k ∈ S. Using (6.10) we have ωg2 x ? mh1 x =ω ?k , h2 h2

and the points yj in (6.10) are given by yj = (xj ? mh1 )/h2 ? k with xj ∈ Σ(g2 ). Hence ag2 ωg2 ?

g2 ∈G2

x h2

=

m∈Z2 k∈S

ak ω

x ? mh1 ?k h2

2

≤ c3

π 2

n/4 m∈Z2 k∈S

ak e?ρ|(x?mh1 )/h2 ?k|

D(L? k +1+n/2)/2

L? +1 D0 k

(L?k

x?k ? mh1 ?k h2 + 1)!

L? k +1

.

24

Here x?k ∈ Σ(g2 ) is the node closest to g2 = h1 m + h2 k and L?k is the degree of the polynomial P?k ,g2 . By Condition 6.1 for ?xed D and D0 D(L+1+n/2)/2

L+1 D0

x?k ? mh1 ?k h2 (L + 1)!

L+1

≤ δ(L) → 0 if

L→∞

uniformly for all g2 ∈ G2 . Hence we obtain ag2 ωg2 ?

g2 ∈G2

x h2

≤ C1 δ(L)

ak e?ρ|(x?mh1 )/h2 ?k|

m∈Z2 k∈S

2

(6.30)

because of L?k = L for all ?k . The sum ak e?ρ|(x?mh1 )/h2 ?k| =

k∈Zn

2

h2 1 πD(h2 ? h2 ) 1 2

n/2 k∈Zn

e?h2 |k|

2

2 /(h2 ?h2 )D 1 2

e?ρ|x?mh1 ?h2 k|

2 /h2 2

can be easily estimated by using equation (6.2). Setting (h2 ? h2 )D = h2 D1 ? h2 /ρ 1 2 1 2 we derive D1 = D + and after some algebra e?h2 |k|

k∈Zn

2 2 /(h2 ?h2 )D 1 2

2 h2 1 D0 2 ? D = D + H2 . D ? D0 h2 ρ 1

e?ρ|x?h2 k|

n/2

2 /h2 2

= Therefore we obtain sup

πD(1 ? H 2 ) ρD1

e?|x|

2 /h2 D 1 1

1 + O(e?π

2 D 2 (1?H 2 )/D

1

) .

Rn m∈Z k∈S 2

ak e?ρ|(x?mh1 )/h2 ?k| ≤ C2 sup

2

Rn m∈Z 2

e?|x?mh1 |

2 /h2 D 1 1

≤ C3

with some constant C3 depending on D, D0 and the space dimension n. Now (6.27) follows immediately from (6.29) and (6.30). Remark 6.1 It can be seen from (6.28) that in principle the parameter D0 can be any value of the interval (0, D) not too close the its end points. In numerical experiments we have not seen any signi?cant dependence on this parameter. The choice D0 = D/2 might be advantageous because the di?erential expressions Cβ,γ (x, y) simplify to √ √ Cβ,γ (x, y) = Sβ (? D?x )Sγ (? D?y ) e4(x,y)/D .

6.5

Numerical Experiments

We have tested the construction (6.26, 6.25) for a quasi-uniform distribution of nodes on R with the parameters D = 2, D0 = 3/2, h = 1, κ1 = 1/2. To see the dependence of the approximation error from the number of nodes in Σ(m), m ∈ Z, and the degree of polynomials we provide graphs of the di?erence to 1 for the following cases :

25

- Σ(m) consists of 1 point, L = 1, 2 (Fig. 4) and L = 3, 4 (Fig. 5); - Σ(m) consists of 3 points, L = 1, 2 (Fig. 6) and L = 3, 4 (Fig. 7); - Σ(m) consists of 5 points, L = 1, 2 (Fig. 8) and L = 3, 4 (Fig. 9). As expected, the approximation becomes better with increasing degree L and more points in the subsets Σ(m). The use of only one node in Σ(m) reduces the approximation error by a factor 10?1 if L increases by 1. The cases of 3 and 5 points indicate, that enlarging the degree L of the polynomials by 1 gives a factor 10?2 for the approximation error. One should notice, that the plotted total error consists of two parts. Using (6.26, 6.25) we approximate the θ-function (2π)?1/2

m∈Z

e?(x?m)

2 /2

=1+2

∞ j=1

e?2π

2j2

cos 2πjx .

(6.31)

Hence, the plotted total error is the sum of the di?erence between (6.1) and (6.31) and the function 2

∞

e?2π

2j2

cos 2πjx ,

(6.32)

j=1

which is the saturation term obtained on the uniform grid. The error plots in Figure 7 for L = 4 and in Figure 9 show that the total error is already majorized by (6.32), which is shown by dashed lines.

26

-2*10-2

3*10-3

2*10-3

-2.8*10-2

1*10-3

-1

-0.5

0.5

1

-1

-0.5

0.5

1

right).

Figure 4: The graph of Θ(x) ? 1 when Σ(m) consists of 1 point, L = 1 (on the left) and L = 2 (on the

-2*10-4

5*10-5

-1 -0.5 0.5 1

-1

-4*10-4

-0.5

0.5

1

-5*10-5

right).

Figure 5: The graph of Θ(x) ? 1 when Σ(m) consists of 1 point, L = 3 (on the left) and L = 4 (on the

2*10-4

1*10-6

-1

-0.5

0.5

1

-1

-0.5 -1*10-6

0.5

1

-2*10-4

-2*10-6

-4*10-4

right).

Figure 6: The graph of Θ(x) ? 1 when Σ(m) consists of 3 points, L = 1 (on the left) and L = 2 (on the

8*10-9 4*10

-8

2*10-8

4*10-9

-1

-0.5 -2*10-8 -4*10-8

0.5

1 -1 -0.5 0.5 1

-4*10-9

right). The saturation term (6.32) is depicted by dashed lines.

Figure 7: The graph of Θ(x) ? 1 when Σ(m) consists of 3 points, L = 3 (on the left) and L = 4 (on the

27

4*10-5 1*10-7 2*10-5 -1 -1 -0.5 -2*10-5 -4*10-5 0.5 1 -1*10-7 -0.5 0.5 1

-2*10-7

right).

Figure 8: The graph of Θ(x) ? 1 when Σ(m) consists of 5 points, L = 1 (on the left) and L = 2 (on the

6*10-9 4*10-9 2*10-9

6*10-9 4*10-9 2*10-9

-1

-0.5 -2*10 -4*10

-9

0.5

1 -1

-0.5 -2*10

-9

0.5

1

-9

-4*10-9

-6*10-9

right). The saturation term (6.32) is depicted by dashed lines.

Figure 9: The graph of Θ(x) ? 1 when Σ(m) consists of 5 points, L = 3 (on the left) and L = 4 (on the

References

[1] M. D. Buhmann, N. Dyn, and D. Levin, On quasi interpolation by radial basis functions with scattered data. Constr. Appr. 11 (1995), 239–254. [2] C. de Boor, R. A. DeVore, and A. Ron, Approximation from shift–invariant subspaces of L2 (Rd ), Trans. AMS, 341 (1994), 787–806. [3] C. de Boor and A. Ron, Fourier analysis of the approximation power of principal shift-invariant spaces. Constr. Appr. 8 (1992), 427–462. [4] N. Dyn and A. Ron, Radial basis function approximation: from gridded centers to scattered centers. Proc. London Math. Soc. 71 (1995), 76–108. [5] M. M. Dzrbasyan and A. B. Tavadyan, On weighted uniform approximation by polynomials of several variables. Mat. Sb., N.S. 43 (85) (1957), 227–256. [6] T. Ivanov, V. Maz’ya and G. Schmidt, Boundary layer approximate approximations for the cubature of potentials in domains , Adv. Comp. Math. 10 (1999), 311–342. [7] K. Jetter and D. X. Zhou, Order of linear approximation from shift-invariant spaces. Constr. Appr. 11 (1995) 423–438. [8] V. Karlin and V. Maz’ya, Time-marching algorithms for non local evolution equations based upon “approximate approximations”. SIAM J. Sci. Comput. 18 (1997) 736–752.

28

[9] V. Maz’ya, A new approximation method and its applications to the calculation of volume potentials. Boundary point method. In 3. DFG-Kolloqium des DFGForschungsschwerpunktes “Randelementmethoden”, 1991. [10] V. Maz’ya, Approximate Approximations, in: The Mathematics of Finite Elements and Applications. Highlights 1993, J.R. Whiteman (ed.), Wiley & Sons, Chichester 1994. [11] V. Maz’ya and V. Karlin, Semi-analytic time marching algorithms for semi-linear parabolic equations. BIT 34 (1994), 129–147. [12] V. Maz’ya and G. Schmidt, “Approximate Approximations” and the cubature of potentials. Rend. Mat. Acc. Lincei 6 (1995), 161–184. [13] V. Maz’ya and G. Schmidt, On approximate approximation using Gaussian kernels. IMA J. of Numer. Anal. 16 (1996), 13–29. [14] V. Maz’ya and G. Schmidt, Construction of basis functions for high order approximate approximations. Mathematical Aspects of boundary elements methods (Palaiseau, 1998). Chapman & Hall/CRC Res. Notes Math., 414, 2000, 191–202. [15] V. Maz’ya and G. Schmidt, Approximate wavelets and the approximation of pseudodi?erential operators. App. Comp. Harm. Anal. 6 (1999), 287–313. [16] V. Maz’ya and G. Schmidt, On quasi-interpolation with non-uniformly distributed centers on domains and manifolds. J. Appr. Th. 110 (2001), 125–145. [17] V. Maz’ya, G. Schmidt and W. Wendland, On the computation of multi-dimensional single layer harmonic potentials via approximate approximations. Calcolo 40 (2003), 33– 53. [18] H. N. Mhaskar, Approximation Theory and Neural Networks. Wavelet and allied topics, 2001, 247–289. [19] M. J. D. Powell, The theory of radial basis functions in 1990, in: Advances in numerical analysis. Vol. 2: Wavelets, subdivision algorithms, and radial basis functions, W. Light (ed.), Clarendon Press, Oxford, 1992, 105–210 . [20] R. Schaback and Z. M. Wu, Construction Techniques for Highly Accurate QuasiInterpolation Operators, J. of Appr. Th. 91 (1997), 320-331 [21] G. Schmidt, On approximate approximations and their applications. In The Maz’ya Anniversary collection, v.1, Operator theory: Advances and Applications, v.109, 1999, 111–138. [22] E. M. Stein and G. Weiss, Introduction to Fourier analysis on Euclidean spaces. Princeton University press, 1971. [23] G. N. Watson, A Treatise on the Theory of Bessel Functions. Cambridge University Press, 1922. [24] Z. M. Wu and J. P. Liu, Generalized Strang-Fix condition for scattered data quasiinterpolation. Adv. Comp. Math. 23 (2005), 201–214

29

赞助商链接

更多相关文档:

更多相关标签:

相关文档

- 3D surface reconstruction from scattered data using
- Mining Approximate Frequent Itemset from Noisy Data
- Hierarchical splatting of scattered data
- Creating surfaces from scattered data using radial basis functions
- Adaptive thinning for bivariate scattered data
- Notes on Scattered-Data Radial-Function Interpolation
- Abstract Scattered Data Interpolation Using an Alternate Differential Equation Interpolant
- Extracting Skeletal Curves From 3D Scattered Data
- Reconstruction of Multivariate Functions from Scattered Data
- Reconstruction of kinematic surfaces from scattered data
- GUIDELINES ON SECURING PUBLIC WEB SERVERS
- Performance Considerations for Mobile Web Services
- 基于MATLAB实现二维delaunay三角剖分
- Modeling In-Network Processing and Aggregation in Sensor Networks
- Adaptive thinning for bivariate scattered data

文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com