Meshfree Cubature by Radial Basis Functions

(1)

Meshfree Cubature by Radial Basis Functions

S. D E M ARCHI ^a , A. S OMMARIVA ^b AND M. V IANELLO ^b

a

Department of Computer Science, University of Verona, ITALY

b

Department of Pure and Applied Mathematics, University of Padua, ITALY

Abstract We give a survey of some recent results on the construction of numerical cubature formulas from scattered samples of small/moderate size, by using interpolation with RBF (Radial Basis Functions). Error analysis and numerical tests with random points in the unit square have shown that Thin-Plate Splines and Wendland’s compactly supported RBF provide stable and reasonably accurate formulas. The method has then been extended to cubature by RBF on the sphere, and on arbitary (convex as well as nonconvex and even multiply connected) polygons by Thin- Plate Splines via Green’s formula.

1 The meshfree cubature problem

Given a scattered sample of size n, say

(X, f ) with X = {P

i

} = {(x

i

, y

i

)} ⊂ Ω , f = {f (P

i

)} , i = 1, . . . , n , where f is a given continuous function on a bivariate compact domain Ω ⊂ R

²

, we need to compute an approximate value of the integral

I(f ) = Z

Ω

f (P ) dP .

2 Numerical cubature by RBF

Fixed a suitable radial function φ : [0, +∞) → R, we can construct the RBF interpolant at the points {P

i

}

s(P ) :=

n

X

j=1

c

j

φ

j

(P ) + p

m

(P ) ≈ f (P ) , P = (x, y) ∈ Ω ,

s(P

i

) = f (P

i

), i = 1, . . . , n, where

• φ

j

(P ) = φ

j

(P ; δ) := φ(|P − P

j

|/δ), with δ scaling parameter

• p

m

(P ) = P

µ

k=1

b

k

π

k

(P ) polynomial of degree m (with {π

k

} ba- sis and µ dimension of the corresponding multivariate polynomial space), and p

m

≡ 0 in

positive definite

instances

The coefficients c = {c

j

} and b = {b

k

} are computed by solving the (pos- sibly) augmented system of dimension n + µ,

Ac + Bb = f , B

^T

b = 0 ,

where A = (a

ij

) = (φ

j

(P

i

)), B = (b

ik

) = (π

k

(P

i

)). Popular choices of RBF are (cf. [1, 3, 8]):

• Gaussians (G): φ(r) = exp (−r

²

)

• Duchon’s Thin-Plate Splines (TPS): φ(r) = r

²

log (r)

• Hardy’s MultiQuadrics (MQ): φ(r) = (1 + r

²

)

^1/2

• Inverse MultiQuadrics (IMQ): φ(r) = (1 + r

²

)

^−1/2

• C

²

Wendland’s compactly supported (W2): φ(r) = (1 − r)

⁴+

(4r + 1) Now, it is natural to approximate the integral I(f) as

I(f ) ≈ I(s) =

n

X

j=1

c

j

I(φ

j

) + I(p

m

) . (1)

• Cubature formula: (1) can be rewritten in the usual form of a weighted sum of the sample values. Considering for simplicity the positive definite case, by symmetry of A

I(f ) ≈ I(s) = hc, Ii = hA

⁻¹

f , Ii = hf , wi =

n

X

j=1

w

_j

f (P

_j

) , (2)

Aw = I , with I = {I(φ

j

)}

1≤j≤n

where h·, ·i is the scalar product in R

ⁿ

and I the vector of integrals on Ω of the radial basis functions.

2.1 Error Analysis

The error of the RBF cubature formula described above, in the presence of approximate values of the basis functions integrals, say ˜I ≈ I, can be estimated as

|I(f ) − h ˜ w , f i| ≤

meas(Ω) kf − sk∞

+ kA

⁻¹

k

2

kf k

2

kI − ˜Ik

2

(3)

= O(α(h)) + O

1 β(q)

kI − ˜Ik

2

, where

α(h) → 0 as h → 0, β(q) → 0 as q → 0 ,

h denoting the fill distance and q the separation distance of the scattered point set X. We have here an occurrence, in the cubature context, of the well-known

• “uncertainty principle” of RBF interpolation (cf. [4]): “There is no case known where the error and the sensitivity are both reasonably small”.

Indeed, the rates of α(h) and β(q) are both exponential for smooth RBF (G, MQ, IMQ), whereas they are both algebraic for less regular RBF (TPS, W2) (cf., e.g., [1, 4]). The situation seems hopeless with scattered data (where q h) and smooth RBF like the Gaussians, but numerical experiments have shown that (3) is by far an

overestimate.

3 Cubature on the unit square

For the Gaussians, we can easily compute the integrals {I(φ

j

)} by separa- tion of variables, via the ERF function. For the other RBF, to exploit radial symmetry we split the unit square into eight right triangles with common vertex in P

j

. Then we have to compute integrals of the form R

_T

φ

j

(P ) dP where T is a certain right triangle, say T = P

j

HM, with the right angle at H (sse the figure below).

P j

H M

Setting r

0

= |P

j

− H|, r

1

= |P

j

− M | and θ

^∗

the angle HP

j

M, and integrat- ing in polar coordinates, we get easily

Z

T

φ

j

(P ) dP = δ

²

Z

θ^∗

0

Ψ r

0

δ cos θ

dθ , (4)

where θ

^∗

= arccos (r

0

/r

1

), and Ψ is the following primitive

Ψ(ρ) = Z

ρ

0

φ(r)r dr , which can be computed analytically

• TPS: Ψ(ρ) =

^ρ₄⁴

log ρ −

¹₄

• MQ: Ψ(ρ) =

¹₃

(1 + ρ

²

)

^3/2

− 1

• IMQ: Ψ(ρ) = (1 + ρ

²

)

^−1/2

− 1

• W2: Ψ(ρ) = −

¹₇

(1 − ρ)

⁵₊

(4ρ

²

+

⁵₂

ρ +

¹₂

) +

₁₄¹

The integral on the r.h.s. of (4) can then be computed by means of

symbolic integrators, to avoid the bottleneck given by a large number of accurate

numerical quadratures.

3.1 Numerical results

RBF cubature by sets of n = 100 uniform random points in [0, 1]

²

. First:

spectral norm of the inverses of the collocation matrices and 1-norm of the computed weights vectors. Second and third: errors of RBF interpolation and RBF cubature of the function f(x, y) = exp (x − y) and of the well- known Franke test function (average values on 50 independent trials).

δ M Q IM Q G W2 T P S

0.1 1E+04 5E+03 1E+04 2E+02 9E+02 kA⁻¹k2 1 2E+16 6E+15 >E+17 5E+04 8E+03 10 >E+17 >E+17 >E+17 3E+07 1E+06 0.1 2E+00 2E+00 2E+00 3E-01 1E+00 k ˜wk1 1 8E+02 5E+02 1E+03 2E+00 1E+00 10 4E+06 1E+05 6E+02 2E+00 1E+00

exp(x − y) δ M Q IM Q G W2 T P S

0.1 6E-02 3E-01 5E-01 9E-01 4E-02 Eintp 1 3E-04 8E-04 8E-04 1E-01 2E-02 10 2E-03 7E-04 2E-03 2E-02 3E-02 0.1 6E-04 1E-02 8E-02 7E-01 5E-04

Ecub 1 2E-06 5E-06 1E-05 4E-03 2E-04

10 4E+00 6E-02 1E-03 1E-04 5E-04

Franke δ M Q IM Q G W2 T P S

0.1 5E-02 1E-01 5E-01 9E-01 6E-02 Eintp 1 1E+01 6E+00 3E+01 7E-02 7E-02 10 2E+01 8E+01 2E+01 7E-02 5E-02 0.1 2E-03 8E-03 1E-01 7E-01 3E-03

Ecub 1 2E-01 1E-01 4E-01 2E-03 5E-03

10 1E+04 3E+03 2E+01 2E-03 3E-03

A wide set of numerical experiments with several other test functions re- vealed that:

• As expected, the quality of interpolation and cubature depends strongly on the scaling parameter (except for the TPS, cf. e.g. [3]).

• The cubature error is always smaller than the interpolation error, as is natural.

• In some instances with smooth RBF, good results can be obtained even in presence of high condition numbers (namely with smooth integrands and accurate data)

• TPS and W2 generate the most reliable and robust RBF cubature formulas, which give acceptable results even on moderately large and/or noisy data sets.

• Meshfree cubature by TPS with random points gives much lower er- rors than MonteCarlo cubature (typically two orders of magnitude in the experiments with hundreds of points). This feature is impor- tant when sampling is very costly or even cannot be refined.

4 Cubature on polygons: TPS-Green

The core of the Green’s formula (cf. [2]) approach is given by computing Z

Ω

φ(|P − Q|/δ) dQ = Z

∂Ω

Z

φ(|P − Q|/δ) dx

dy , (5)

with P = (x, y), as a function of the point Q = (u, v). Working with TPS it is not restrictive to put δ = 1, and the x-primitive above is

Φ

Q

(P ) :=

Z

φ(|P − Q|) dx = 1 9 t

³

+ 2

3 tw

²

− 2

3 w

³

arctan t w

− 1

6 t(t

²

+ 3w

²

) log t

²

+ w

²

, t := u − x , w := v − y . Assume that Ω is a simply connected

polygon, with boundary described counterclockwise by a sequence of vertices Vj

= (ξ

j

, ν

j

), j = 1, . . . , p,

∂Ω = [V

₁

, V

₂

] ∪ [V

₂

, V

₃

] ∪ · · · ∪ [V

_p

, V

_p+1

] , V

_p+1

= V

₁

. Then by (5)

Z

Ω

φ(|P − Q|) dQ = X

∆νj6=0

Z

[Vj,Vj+1]

Φ

Q

(P ) dy .

Since v − y = at + b with a = −∆ν

j

/∆ξ

j

and b = ν

j

− v + (u − ξ

j

)∆ν

j

/∆ξ

j

along a side not parallel to the y-axis, the problem is eventually reduced to computing explicitly by symbolic integrators second level primitives like

Z

Φ

Q

(u − t, v − at − b) dt , Z

Φ

Q

(ξ, y) dy .

Extension to

multiply connected

polygons is immediate by describing clockwise the “holes” (cf. [6]).

4.1 Numerical results

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Errors of TPS-Green cubature of the three test functions f

1

(x, y) = exp (x − y), f

2

(x, y) = exp (5(x − y)), f

3

(x, y) = p(x − 0.5)

²

+ (y − 0.5)

²

, by n = 3000 uniform random points on the nonconvex polygon above.

subcells overlap f

1

f

2

f

3

speed-up

1 2E-07 3E-05 1E-06 1.0

4 0% 1E-06 8E-05 6E-06 6.8

10% 8E-08 2E-05 7E-07 5.8

9 0% 1E-06 4E-05 3E-06 12.2

10% 2E-07 3E-05 3E-07 11.1

16 0% 3E-06 4E-05 8E-06 18.5

10% 2E-07 1E-04 7E-08 16.2

• Note that by

splitting

the enclosing rectangle into non-overlapping subcells and by a modest interpolation overlap we can

improve effi- ciency

keeping or improving accuracy (no need to interface!).

5 Extensions and further studies

• In [7], the method has been extended to meshfree cubature on the sphere by RBF ans SBF (Spherical Basis Functions). Due to symmetry of the sphere, the integral I(φ

j

) is here independent of P

j

, and can be computed explicitly for the most usual RBF and SBF.

• The dependence of the cubature errors on the points distribution should be investigated, in particular on grids and lattices (the lat- ter also for comparison with Quasi-MonteCarlo).

• We have some encouraging results on the extension of TPS-Green cubature to other 2d domains, e.g. to disks and sectors.

• A more challenging problem is extension of RBF cubature to 3d do- mains, namely for meshfree integration on polyhedra by polyhar- monic splines via the divergence theorem.

References

[1] M.D. Buhmann, Radial Basis Functions: Theory and Implementation, Cambridge Mono- graphs on Appl. and Comput. Math., vol. 12, Cambridge University Press, 2003.

[2] G. Green, An Essay on the Application of Mathematical Analysis to the Theories of Electricity and Magnetism, Nottingham, 1828.

[3] A. Iske, Multiresolution Methods in Scattered Data Modelling, Lecture Notes in Comput.

Science and Eng., vol. 37, Springer, 2004.

[4] R. Schaback, Error estimates and condition numbers for radial basis function interpolation, Adv.

Comput. Math. 3 (1995), 251–264.

[5] A. Sommariva and M. Vianello, Numerical cubature on scattered data by radial basis func- tions, Computing 76 (2005), 295–310.

[6] A. Sommariva and M. Vianello, Meshless cubature by Green’s formula, Appl. Math. Com- put., in press (available online 28 August 2006).

[7] A. Sommariva and R. Womersley, Integration by RBF over the sphere, 2005, submitted.

[8] H. Wendland, Scattered Data Approximation, Cambridge Monographs on Appl. and Com- put. Math., vol. 17, Cambridge University Press, 2005.

Meshfree Cubature by Radial Basis Functions