Symmetric Quadrature Rules on a Triangle - CORE

View metadata, citation and similar papers at core.ac.uk

brought to you by CORE

provided by Elsevier - Publisher Connector

PERGAMON

Computers and Mathematics with Applications

An International Journal

computers & mathematics

with applications

45 (2003) 1829-1840 locate/camwa

Symmetric Quadrature on a Triangle

Rules

S. WANDZURA+

HRL Laboratories 3011 Malibu Canyon Road Malibu, CA 90265, U.S.A.

H. XIAOt

Department of Computer Science, Yale University New Haven, CT 06520, U.S.A.

(Received and accepted May 200.2)

Abstract-we

present a class of quadrature rules on triangles in Wz which, somewhat similar

to Gaussian rules on intervals in W', have rapid convergence, positive weights, and symmetry. By a

scheme combining simple group theory and numerical optimization, we obtain quadrature rules of this

kind up to the order 30 on triangles. This scheme, essentially a formalization and generalization of

the approach used by Lyness and Jespersen over 25 years ago, can be easily extended to other regions

in 1R2and surfaces in higher dimensions, such as squares, spheres. We present example formulae and

relevant numerical results. @ 2003 Elsevier Science Ltd. All rights reserved.

Keywords-symmetric

quadrature, Triangle, Gaussian quadrature.

1. INTRODUCTION

Gaussian quadratures are a classical tool of numerical integration, and possess several desirable features such as positivity of weights, and an optimal number of nodes: an n-point Gaussian rule is exact for all polynomials of orders up to 2n - 1, and no n-point rule is exact for all polynomials of order 2n. In one dimension, since each quadrature node contributes two parameters (one as the coordinate, and the other as the weight), it is expected that an n-point quadrature rule can integrate exactly 2n functions (not, necessarily polynomials). Indeed, for many classesof functions including smooth functions and functions with end-point, singularities, such quadratures exist, (see, for example, [1,2]); when the functions to be integrated are polynomials, such integration rules are referred to as Gaussian quadratures.

Naturally, one would attempt to generalize the above theory to two-dimensional cases, and expect that an n-point quadrature in 2-d integrates 3n functions exactly. Obviously, an excellent upper bound for the number of quadrature nodes that is required to integrate exactly all

The authors thank Professor i. Rokhlin for his encouragement, advice, and support. tThe work of this author was supported in part by the Defense Advanced Research Projects Agency (DARPA) of the U.S. Department of Defense under Air Force Office of Scientific Research Contract No. F49620-91-C-0064, and in part by DAFtPA Contract No. MDA972-95-C-0021. $The work of this author was supported by DARPA/AFOSR under Grant F49620-97-1-0011.

08981221/03/S - see front matter @ 2003 Elsevier Science Ltd. All rights reserved. `M-et by AM-W PII: SO898-1221(03)00173-l

1830

S. WANDZURA AND H. XIAO

polynomials up to order n is given by tensor product rules; a lower bound is given by Stroud in [3] for triangles and other simplexes in llP. However, no general theory regarding the optimal number of quadrature nodes in two dimensions is known to the authors. In fact, the situation in two dimensions seems to be considerably more complex. While the interval is the only connected compact subset of R', regions of R2 come in an infinite variety of shapes, each with its own topological features. It seems likely that each shape should require a different set of quadrature formulae, and should have its own theories.

Since triangles are a standard tool for describing regions and surfaces in higher dimensions, and are one of the simplest forms in R2, quadratures for triangles have been studied in some detail. In particular, Lyness and Jespersen published a class of quadratures of moderate degree (up to order 12) on triangles over 25 years ago [4]. Their quadratures have many desirable properties of Gaussian quadratures in one dimension, such as rapid convergence, symmetry (or equivalently, invariance under a preselected finite group of linear transformations of the plane), and positivity of weights. Since then, several new quadratures of this type have been constructed (see [5]).

In this paper, we formalize the approach used in [4] by combining simple facts of group theory and straightforward numerical optimization, and develop a scheme for the construction of quadratures of relatively high orders. Since this scheme does not directly depend upon detailed geometry of the integration regions (rather, the geometric information is encapsulated in the corresponding symmetry groups as formulated below), it is easily extendable to other regions in R2, and to regions in higher dimensions.

The paper is organized as follows. In Section 2, we summarize elementary mathematical and numerical facts to be used in this paper. In Section 3, we develop the analytical apparatus for the numerical construction of quadratures on triangles. We summarize our numerical scheme in Section 4, and present results in Section 5. The last section contains discussions and conclusions.

2. MATHEMATICAL

AND NUMERICAL PRELIMINARIES

In this section, we collect the mathematical of the quadratures of this paper.

and numerical tools to be used in the construction

2.1. Symmetry Group of Equilateral

Triangles

We start with summarizing several elementary facts of the symmetry group of equilateral

triangles in R2.

As is well known, the symmetry group of an equilateral triangle-the

group of all orthogonal

linear transformations of the plane under which the equilateral triangle is invariant-is a reflection

group often referred to as 03 (see [6]). 03 has six elements, and has a two-dimensional matrix

representation shown below (see Table 1). Clearly, seen as orthogonal transformations of the

plane, matrices A, B, and C correspond to rotations by IT about the corresponding three medians

of the equilateral triangle (see Figure l), and matrices D and F correspond to clockwise rotations

about the center by 2~13 and 4~13, respectively.

Table 1. Two-dimensional

matrix representation

of D3 = {E, A, B, C, D, F}

Symmetric Quadrature Rules

1831

Figure 1. An equilateral triangle with the vertices (-l/2, a/2), (1, 0), and orbits.

(-l/2, -a/2),

The action of 03 separates points of the equilateral triangle into disjoint subsets. In particular,

denoting the equilateral triangle by T, and defining the orbit SC,,,) of an arbitrary point (5, y)

in T by the formula

SC,,,) = {g(x,v) 19 E 031,

(1)

we have

S(z,,, l-l S(u,v) = 07 if (x79) $ S(u,v),

(2)

and

T = u SW.

(3)

(w) ET

A quick inspection of the group D3 shows that each orbit of T assumes one of the three forms: the class one orbit which consists of one point (which, inevitably, is the center of the triangle); the class two orbit which consists of three points, one from each median; and the class three orbit which consists of six points, none of which can be on a median. In Figure 1, we show an equilateral triangle and two of its orbits. The points depicted by small circles are points from a class two orbit, and the points depicted by diamonds are points from a class three orbit.

2.2. Invariant Polynomials

of Equilateral

Triangles

Let p be any polynomial defined on an equilateral triangle and g an arbitrary element in D3. We define the polynomial gp (the image of p under the action of g) by the following formula:

(9P)(27Y) = P (9-l (2, Y,) .

(4)

Then, we say that p is an invariant polynomial with respect to 03 (or equivalently, p is 03 invariant) if for all g E D3,

(9P) (x7 Y) = P (x9 Y).

(5)

Let us refer to the set of all 03 invariant polynomials as I. Clearly, I is nonempty, since polynomials 1, z2 + y2, z3 - 3xy2 are elements of I. The structure of I is well known in invariant theory (see, for example, [7,8]); we summarize relevant results in the following theorem.

THEOREM 2.1. The set I is a finitely generated ring. Furthermore, of fundamental invariants that generate I.

{x2 + y2, x3 - 3xy2} is a set

1832

S. WANDZURA AND H. XIAO

2.3. Newton's Method Newton's method is a classical iterative technique used in solving equations of the form

F(x) = 0,

(6)

where F : Rn 4 R" is of the form

(7)

Newton's method has quadratic convergence when the initial approximation is sufficiently close to the solution, as summarized below in Theorem 2.2; when the initial point is not sufficiently close to the solution, the iteration may diverge.

DEFINITION

2.1. The Jacobian DF : B" + R" of the function F (see (7)) is defined by

1.-afl .. . -afl

ax1

ax,

1: DF(x) =

afn

afn

ZFl ... dz,

(8)

THEOREM 2.2. Suppose that F : W" 4 W" is continuously differentiable in a neighborhood nb( 0, 6 > 0, and integer N,,b 2 0, such that if

11x-0Eli< 6,

(12)

then

b`k+l -Eli < 6llxk -- ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download