Meshfree Cubature by Radial Basis Functions

Meshfree Cubature by Radial Basis Functions

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

b

Department of Computer Science, University of Verona, ITALY

c

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; cf., e.g., [?, ?, ?]). Error analysis and numerical tests with random points in the unit square have shown that Thin-Plate Splines and Wendland’s com- pactly supported RBF provide stable and reasonably accurate formulas (cf. [?]). The method has then been extended to cubature by RBF over the sphere (cf. [?]), and over arbitary (convex as well as nonconvex and even multiply connected) polygons by Thin-Plate Splines via Green’s formula (cf. [?]). In the latter case, we also show how to improve efficiency by a suitable domain decomposition technique.

1 The cubature problem

Given a scattered sample of size n, say

X = {P

i

} = {(x

i

, y

i

)} ⊂ Ω; , i = 1, . . . , n , and

f = {f (P

i

)}, i = 1, . . . , n , (1) of a given continuous function f on a multivariate compact set Ω ⊂ R

^N

(the closure of an open and bounded set), and that we need to compute an approximate value of the integral

I(f ) = Z

Ω

f(P ) dP . (2)

2 The Lebesgue constant of the Xu points

FIGURE1. Left: the distribution of N = 144 (deg n = 16) Xu-like points on Q. Right: the behavior of the Lebesgue constant of the Xu points up to degree n = 100.

T

HEOREM

1 Λ

^Xun

≤ 8

_π²

log n + 5

²

+

³₄

.

R

EMARK

. The Lebesgue constant of the Xu points has the same order of growth as the Padua points (the best known on Q, cf. [3]).

TABLE1.Lebesgue constants size of different nodal sets on Q: Morrow-Patterson (MP), Extended Morrow-Patterson (EMP), Padua points (PD), Xu points.

interp. pts. Λ34 Λ48 Λ62 Λ76

MP 649 1264 2082 3102

EMP 237 456 746 1106

PD 11 13 14 15

XU 10 12 13 14

3 Beyond the square: extensions

Consider a surjective map σ : Q → K , t = (t

1

, t

2

) 7→ x = (x

1

, x

2

) , with “inverse” σ

⁻¹

: K → Q , σ

⁻¹

(x) = t(x) ∈ ← − σ (x) , where t(x) denotes a point selected in some manner from the inverse image ← − σ (x). By interpolating the composition g = f ◦ σ at the Xu points in Q, we get a (in general) non-polynomial interpolation formula

L

^Xu_n

f(x) = L

^Xu_n

g(σ

⁻¹

(x)) , g = f ◦ σ , x ∈ K , Thus, f will be sampled at the Xu-like points K 3 x

r,s

= σ(z

r,s

) .

• Key feature: smoothness of the transformation σ.

3.1 Generalized rectangles

K = {x = (x

1

, x

2

) : a ≤ x

1

≤ b , φ(x

1

) ≤ x

2

≤ ψ(x

1

)} , φ and ψ being suitable functions.

FIGURE2.The distribution of N = 144 Xu-like points (deg n = 16) in two generalized sectors.

TABLE2.Xu-like interpolation errors of f(x1, x2) = sin (x²1+ x²2)on the generalized rectangles of Fig. 2.

n 8 16 24 32 40

N 40 144 312 544 840

K1 1E-2 2E-5 1E-8 4E-12 5E-14 K2 3E-2 2E-4 2E-6 4E-9 3E-11

3.2 Generalized sectors and starlike domains

•

Generalized sectors

K = {x = (ρ cos θ, ρ sin θ) : θ

1

≤ θ ≤ θ

2

, ρ

1

(θ) ≤ ρ ≤ ρ

2

(θ)} ,

• Starlike domains

K = {x = (ρ cos θ, ρ sin θ) : 0 ≤ θ ≤ 2 π , 0 ≤ ρ ≤ r(θ)}

= {x = (ρ cos θ, ρ sin θ) : 0 ≤ θ ≤ π , −r(θ + π) ≤ ρ ≤ r(θ)} .

FIGURE3. The distribution of N = 144 Xu-like points (deg n = 16) in the unit disk in polar (left) and starlike-polar (right) coordinates.

FIGURE4.The distribution of N = 144 Xu-like points (deg n = 16) in starlike-polar coordinates:

cardioid (left), four-leaf clover (right).

TABLE3.Xu-like interpolation errors of f(x1, x2) = cos (x1+ x2)on the unit disk in Cartesian, standard polar and “starlike polar” coordinates; n is the underlying polynomial degree, N = n(n + 2)/2the corresponding number of Xu-like interpolation points.

n 8 16 24 32 40

N 40 144 312 544 840

Cartesian 6E-2 2E-2 6E-3 3E-3 4E-3 polar 1E-1 3E-3 2E-5 1E-7 3E-10 starlike 1E-2 1E-5 4E-9 5E-13 2E-14

4 Surface compression from scattered data by

“interpolated interpolations”

We consider the problem of compressing a surface, given as a large scat- tered data set. This problem can be addressed in several ways, for example by multiresolution methods using splines or radial basis functions. Here we adopted

• Xu-like interpolation of a cubic Shepard-like interpolant (cf. [4]) The compression ratio obtained is

compr. ratio = 3 × numb. of scatt. pts.

numb. of Xu nodes ≈ 6 × numb. of scatt. pts.

n

²

,

where n is the underlying polynomial degree.

TABLE4. Compression errors (in sup-norm) for the Franke test function on [0, 1]², sampled at randomly generated point sets; last row and column: actual errors of the Xu and Shepard-like interpolants on the test function.

random pts. n = 16 n = 24 n = 32 n = 40 n = 48 “true” Shep.

5000 3E-2 2E-3 1E-4 7E-5 1E-4 2E-4

10000 3E-2 2E-3 1E-4 6E-5 4E-5 7E-5

20000 3E-2 2E-3 1E-4 1E-5 3E-5 3E-5

40000 3E-2 2E-3 1E-4 3E-6 8E-6 8E-6

“true” Xu 3E-2 2E-3 1E-4 3E-6 5E-8

TABLE5.The compression ratios corresponding to the example above.

random pts. n = 16 n = 24 n = 32 n = 40 n = 48

5000 104:1 48:1 28:1 18:1 13:1

10000 208:1 96:1 55:1 36:1 25:1

20000 416:1 192:1 110:1 71:1 50:1

40000 832:1 385:1 221:1 143:1 100:1

4.1 Compression of a Finite Element PDE solution

• Poisson equation with Dirichlet boundary conditions

 ∆f (x) = −10 , x ∈ Ω f(x) = 0 , x ∈ ∂Ω where Ω is the “lynx-eye” shaped domain in Fig. 5.

•

Finite Element

discretization on a Delaunay mesh with 81796 trian- gles and 41402 nodes.

• Xu-like interpolation of the Finite Element solution.

FIGURE5. Left: the distribution of N = 312 Xu-like points (deg n = 24) in the “lynx-eye”

shaped domain. Right: a detail of the Finite Element mesh in the domain above, near the internal boundary.

TABLE6. Compression errors (in the max-norm) for the Finite Element solution of the Poisson equation above.

mesh size n = 8 n = 12 n = 16 n = 20 n = 24 n = 28 n = 32

41402 1E-1 3E-2 1E-2 5E-3 2E-3 1E-3 1E-3

FIGURE6. Plot of the Xu-like interpolated solution (deg n = 24: compression ratio ≈ 400 : 1, compression error ≈ 2 · 10⁻³).

References

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

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

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

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

[4] A. Sommariva and M. Vianello, Meshless cubature by Green’s for- mula, 2006, submitted (preprint UNSW AMR06/10, available online at http://www.maths.unsw.edu.au/applied/apphome.html).

[5] A. Sommariva and R. Womersley, Integration by RBF over the sphere, 2005, submitted (preprint UNSW AMR05/17, available online at http://www.maths.unsw.edu.au/applied/apphome.html).

[6] H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, 2005.