(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Minimal point cubatures of precision seven for symmetric planar regions"

L REPORT SECTION 
; GRADUATE SCHOOL" 
'.RLY. CALIFORNIA 93940 



NPS-53FE72021A 



NAVAL POSTGRADUATE SCHOOL 

Monterey, California 




MINIMAL POINT CUBATURES 

OF PRECISION SEVEN 

FOR SYMMETRIC PLANAR REGIONS 
by 

Richard Franke 
14 February 1972 



Approved for public release; distribution unlimited, 



FEDDOCS 

D 208.14/2: 

NPS-53FE72021A 



NAVAL POSTGRADUATE SCHOOL 
Monterey, California 



Rear Admiral A. S. Goodfellow M. U. Clauser 

Superintendent Provost 



Abstract: 

A method of constructing 12 point cubature formulas with polynomial precision 
seven is given for planar regions and weight functions which are symmetric in 
each variable. If the nodes are real the weights are positive. For any fully 
symmetric region, or any region which is the product of symmetric intervals, 
it is shown that infinitely many 12 point formulas exist, and that these formu- 
las use the minimum number of points. 



This task was supported by: Foundation Research Program 

Naval Postgraduate School 
Monterey, California 



R. E. Gaskell, Chairman \ C. E. Menneken 

Department of Mathematics Dean of Research Administration 



NPS-53FE72021A 
14 February 1972 



MINIMAL POINT CUBATURES OF PRECISION SEVEN 
FOR SYMMETRIC PLANAR REGIONS** 

Richard Franke* 

1. Introduction 

We are concerned with determining the minimum number of evaluation points 

required by certain cubature formulas of the form 



r n 

ywf= E 



(2) ^'A'k'^ 

and exhibiting such minimal point formulas. Here R is a region in n-space 
and w is a non-negative weight function. A formula (2) which is exact for all 
polynomials of degree <d, but not for all polynomials of degree d + 1 is said 
to have precision d. We assume the integral exists for all polynomials of 
degree < d. 

For arbitrary regions, Stroud [4,7] has shown that the minimum number 
of points required by a cubature formula of precision d is I L 2 J / 
We will be considering the case n = 2, d = 7, for which the presently known 
lower bound is the above, 10. Huelsman [2] has recently shown that for 
fully symmetric regions (i.e., (x,y) e R implies (±x,±y) c R and (±y,±x) e R) 
there are no ten point formulas. 

Stroud [6,7] has given a characterization of cubature formulas with pre- 
cision in terms of the evaluation points being zeros of polynomials which 

** This research was supported by the Foundation Research Program 

* Department of Mathematics, Naval Postgraduate School, Monterey, 

California 93 940 



have certain orthogonality properties. The important consequence of that 
characterization which we shall need is the following: 

Proposition 3 : Let there be given a formula of type (2), with precision 7 , for 
a region in the plane. Suppose that N < 15. Then the points y. , k = 1, . . . , N 
are zeros of 15-N linearly independent polynomials of degree 4, each of which 
is orthogonal, over R with respect tow, to all polynomials of degree ^3. 

In the remainder of the paper the following definitions and notation will 
be used. The function w will be assumed to be symmetric in x and y, 
i.e. , w(-x,y) = w(x,-y) = w(x,y) ^0. R will be assumed to be symmetric with 
respect to both axes. We will sometimes speak of a region R and intend this 
to include the associated weight function w. Q and Q. will denote polynom- 
ials of degree <3, and P. will be an orthogonal polynomial of degree 4, 

i.e. , P. is orthogonal to all Q, over R with respect to w. The five ortho- 

^ ^ r T,(m/4-m) m 4-m , _ n , . 

gonal polynomials of the form P =xy + Q ,m=0, l / ...,4 

are a basis for the vector space of orthogonal polynomials of degree 4. The 

integral Lw x y will be denoted by I . We note that if p or q is odd, 
./K pq 

I =0 and if p and q are both even, I > 0. 

pq pq 

4. Construction of Formulas 

The basic idea in constructing our formulas is to determine three linearly 
independent orthogonal polynomials of degree 4 which have 12 points as com- 
mon (finite) zeros. These 12 points will be the evaluation points, or nodes , 
in the formula. 

We digress to discuss the properties of the orthogonal polynomials for 



our special case. Due to the assumed symmetry of the region and weight 

function, the basis orthogonal polynomials mentioned earlier have the form 

D (4,0) 4 2 u 2 

P ' - x + a.x + by + c. 
4 4 4 

P (3,D 3 

P = x y + a 3 yx 



(5) 



In the above , a =- _ 

1 *22 



D (2,2) 2 2, 2 , . 2 

P v = x y + a 2 x + b 2 y + c 2 

p(l/3) 3 j 

P = xy + a xy 

D (0/4) 4 2 . 2 

P = y + V + V + C 

x 24 *42 

, a. = - ~ , and the remaining coefficients are 

3 x 22 



determined by the equations 



III 
20 02 00 




a. 

i 








III 
40 22 20 


« 


b i 


= - 


^^-i 


, i= 0,2,4 


-22 X 04 X 02- 




-°i- 




^ i,6-i - 1 





We will consider three orthogonal polynomials 

p p (l,3) p (3,l) . 2 2. 

P x = a 3 P " a i p = xy(a 3 y -a^) 

(6) P 2 = a 3 P (1/3) + ai P (3/1) = xy(a 3 y 2 + a^ 2 + 23^) 
P = p(4,0) +Ap (2,2) +Bp ( 0/ 4) 

4 2 2 4 2 2 

= x +Axy + By +Cx + Dy + E, 



where A and B are to be determined, and then C = a + Aa + Bb~, 

D = b. + Ab„ + Bb rt/ and E = c A + Ac„ + Bc n . The reason for considering such 
4 2 4 2 

polynomials is the following: 

Theorem 7 : Suppose the orthogonal polynomials (6) have 12 distinct, finite, 
common zeros. Then these points may be used as nodes in a cubature 
formula of precision 7 for R and w. 



Since the proof of the theorem requires some information about the loca- 
tion of the common zeros, we first investigate whether such polynomials can 
have 12 common zeros, and if so, how they are distributed. We note that 
the first two polynomials have xy in common. The other components of the 
first two have the points ( ± a , ± j3) in common , where a = V -a, / $ '- V -a. . 
Note that since a. , a_ < 0, these points are real. Now, we require that 
A and B be chosen so that the points (±a, ± 0) lie on P„ , i.e. , that 

(8) P 3 (a, 0) = P (4/0) (a, 0) + AP (2 ' 2) ( a , 0) + BP (0 ' 4) ( a , fl ) = 0. 

This could fail only if P (2/2) (a, 0) = P ( °' 4) (a/ 0) = 0, and P (4/0) (a, 0) ^ 0. 

(2 2) (0 4) 

Therefore we impose the restriction ft : If P v ' (a,/3) = P ' ( a, B) = 0, 

then P ' (a, 0) = 0. Condition (8) will generally leave one free parameter, 

although we won't know in general whether it can be taken as A, or B. Thus 

we will speak of "the parameter" in P . 

Now we consider the common zeros of xy and P„ , under condition (8). 
P (x,0) has four zeros, and if B ^ 0, P„(0,y) has four zeros. We want these 
to be distinct, to give us a total of 12 distinct common zeros. Therefore we 
now assume that the following restriction is satisfied: 

ft : For some value of the parameter in P_ , P_(x,0) and P,j(0,y) each have 
four distinct zeros. 

The author knows of no symmetric region for which restrictions ft. and ft„ 
are not satisfied, and conjectures that symmetry is sufficient to ensure that 
they are satisfied. The conditions can be expressed in terms of certain 
polynomial relations between the I being satisfied, or not satisfied. We 

pq 

note, however, that for certain values of the parameter, common zeros may 



be repeated, or infinite (e.g. , B = 0) . 

The 12 common zeros of the polynomials (6) then have the following form: 
(±a. ±8), (±x x , 0), (±x 2 , 0), (0, ± yi ), and (0, ±y 2 ), where x^ ^ , Y \ ty\ 
We are now prepared to prove Theorem 7 . 

Proof of Theorem 7: The zeros are symmetric, and we seek a formula such 
that the weights are also symmetric. The formula will have the form: 

(9) ^ Wf = A x L f (a, 8) + f (-a , fl) + f (a ,- fl) + f (-a . - fl) - 



+ A, 



+ A. 



Lf (x x , 0) + f (-x 1# 0) J+ A 3 Lf (x 2 , 0) + f (-x 2 , 0) J 
. f (0, Yl ) + f (0,-y^ J + A 5 L f (0,y 2 ) + f (0,-y 2 ) J 



Let us solve for A 1 , . . . , A by requiring that (9) is exact for the functions 

2 2 2 2 4 

1, x , y , x y , and y . The system of equations is: 



4A X 4- 2A 2 ♦ 2A 3 + 2A 4 + 2A 5 = l QQ 
4A 1« 2 + 2A 2 X 1 + 2A 3 X 2 =I 2 



4A l( 3 

4A l0 /S 

4 
4A l( 3 



+ 2A 4 y 2 + 2A s y 2 = I Q2 

= I 22 
+ 2A 4 y^ + 2A 5 y^ = I 



The coefficient matrix is non-singular since all 12 points cannot lie on 

2 2 2 2 4 

a polynomial of the form |j + i_lx + n y + n x y + \j. y . 

Now we must show that the resulting formula is exact for the remaining 

P q 
monomials of degree s7. If p or q is odd, it is exact for x y by symmetry, 

464224 , 6 ml .._,., 

so that leaves x , x , x y , x y , and y . The argument is identical to one 



sum is 



I wp 
in Stroud [5 J. We have / R 3 = by orthogonality, and the cubature 

also zero since all nodes lie on p . Because the formula is exact of 

2 2 2 2 4 4 

1, x , y , x y , y and P. , it must also be exact for x . Considering in 



2 2 

turn xy(p +p ), xy(p -p ), x p , and y P , one gets exactness for 

42246 ^6. + , , , . 

x y , x y , x , and y in the same fashion. ■ 

The above construction yields a family of cubature formulas of precision 
7 for a given region and weight function, the procedure failing only for a 
finite number of values of the parameter in P (under the assumption of &. 
and & ). For certain values of the parameter the nodes may be complex 
valued. It would be desirable for the nodes of the formula to be inside R. 
This is impossible in general, however. For example, f or R = [-1,1] x [-1,1], 
w = 1, no value of the parameter yields a formula with all nodes in the square. 
For B = 1 we obtain a previously known formula due to Mysovskih [3], which 
has four nodes outside the square. As B is varied, two of these nodes move 
toward (and into) the square, and two move away from it. There does exist a 
12 point formula for the square with all nodes in the interior [8]; however, 
it does not belong to our family. We will show how to construct it by a 
similar method in Section 2 0. 

An example to be given in the next section demonstrates that we may not 
be able to obtain a formula with all the nodes real. However, if the nodes 
are all real, we have the following result: 
Theorem 10: If the nodes of the cubature formula (9) are all real, the weights 

A.. , . . . , A are all positive. 

I 

22 
Proof: We see from the proof of Theorem 7 that A = — r—r- > 0. We show 

4 a 8 
that A > 0, the positivity of the remaining weights follows by the same method. 



Consider the polynomial Q = x 



2 2 2 2 2 2 

R (x -x ) - (a -x 9 )y J. All nodes except 



2 2 
(±x 1# 0) lie on Q. Since x x ^ x g and x^O, Qfr^O) = Q(-x,0) ^0. Q is 

/2 2 

wQ = 2 A Q (x. , 0) 

fr WQ2 
and A = -^ > 0. B 

2Q (x^O) 

We consider an example. Let R be the region bounded by the parabolas 

y=± (1-x ) with w = 1. Then I = , , , x £ — }„ ,". for p and q even. Either 

pq (p+l)i , p+2q+5 s 

2 
A or B may be used as the parameter in P ; let us speak in terms of B being 

the parameter. If B < 0, some of the nodes are complex. If B > 0, the nodes 

are all real and for a range including approximately the interval (.2,4.5) the 

nodes are all in the interior of the region. The value B = 1 is perhaps a 

natural one to consider, and yields a typical self-contained (i.e. , all nodes 

in the region) formula from the family. The formula is given approximately in 

Table 1. 

Points Weight 



(±.52223, ± 


.57937) 


.18495 


(±.43188,0) 




.31975 


(±.84421,0) 




.14894 


(0, ±.41243) 




.33700 


(0, ±.88401) 




.15775 



1 i i 2 

Table 1: R= j(x,y): -Uxsl, |y| < 1-x I, w = 1 

1 1 . Special Case : Fully Symmetric Regions 

When R and w are fully symmetric (f.s.) the above details are easier to 

consider by virtue of the fact the orthogonal polynomials are simplified. In 

particular, it is true that I*i =1 . Thus we have 

pq qp 

a. = b , b = a , c = c , b = a , and a = a in the polynomials (5). 



Also note that a = ft . 

We will require a number of inequalities between the integrals of the 
monomials. Most of these are obtained by application of the Schwarz in- 
equality. We will list those we need, and prove one to indicate the manner 
of proof. 

(12) 

(13) 

(14) 

(15) 

We will prove (14), since it is the most difficult. We give a preliminary 



X pq <I 2(p-r) / 2(q-s) X 2r2s 

(I 22 + I 40 )2<I 20 (I 60 + 3I 42 ) 

2 2 

I 42^ I 40" I 22^ < ^(fW ^42*2 0~W 

2I 20 <I 00 (I 40 +I 22 ) 



result: 



i 2 = 

22 



4 



2 2 

wx y 



/ f 2 2.2 ± 2j f 
<l J R wx y (x +y )J 



= 21 



/. 



w 



2 2 

x v 



2 2 
x y 
w 

R 2^ 2 
x +y 



42 •'R 2^ 2 

x +y 



Now we note that for any symmetric integrable function f , we may write 
e C I ! 

J wf = 4 J ,w(f( X/ y)+f(y,x)), where R' = | (x,y)eR: 0<y£xl. The above 



R "R 

inequality then becomes 

.2 



2 2 



^22. < 16/' 



I 



42 



2 2 

K x y 



. Now we have 



(I 40" I 22 ) - 4 



= 16 



f 4 4 2 2 

J DI w (x +y -2x y ) 



'R 



= 16 



J Rl w(x -y ) 



J /w (x -y ) M +Y ' / w(x -y ) 



/x z +y' 

<16\ v / Rl wfr Z -y*) W) // W ^ X? 2 ^j 

R* X Y 



2 2,2, 2 2, 



,, f , 6^ 6 4 2 2 4, f .22 4xV . 
= 16 J Rl w(x +y -x y -x y ). J Rl w(x +y - g y ) 

x +y 
" "OO-W^O" 16 ^ 22» 

« x +y 

22 

< (1 6 <f V a 2o-rr ) - 

42 
This is equivalent to (14). We note the strict inequalities appear because 
the Schwarz inequality is applied to functions such that the square of their 
quotient is not a constant. 

For f.s. regions the orthogonal polynomials (6) can be seen to become: 

2 2 
P l = a i xy ( y ~ x ) 

, v ,22 2, 

(16) P 2 = a 1 xy(y +x -2)3 ) 

4 2 2 4 2 2 
P = x +Ax y +By +Cx +Dy +E, 

6 T 

2 42 

where, as before, (3 = -a = - — , A and B satisfy 

22 

(17) P (4,0) (3,j8) + AP< 2 -' 2 >(j8,|8) + BP ( °' 4) (8,i3) = 0, 

and C = a„ + Aa n + Bb„ , D = b„ +Aa + Ba„ , and E = Ac + (1+ B) c,. 
4 2 4 42 4 2 4 

We first note that restriction ^ is satisfied automatically since P 
P (0,4) (x,y) = P (4 ' 0) (y /X ), hence P ( °' 4) (S,3) = implies P (4/0) (S,S) = 0. 
We consider the common zeros of the polynomials (16) with condition (17) 

to show that restriction ft 9 is also satisfied. 

4 2 

We haveP (x ,0) = x + (a +Aa +Bb )x + (Ac + (1+B)c ) where (17) is 

satisfied. For the zeros to be distinct we need (i) E = Ac + (1+B) c ^ 0, 

and (ii) C 2 -4E = (a 4 +Aa 2 +Bb 4 ) 2 -4 (Ac 2 + (1+B) c 4 ) ± 0. 

Case (i). Assume Ac + (1+B) c = for all values of the parameter in P . 



Condition (17) then yields c^ 2 ,2 \|3,j3) - c P (4, °'(8,j5) = 0. We first demon- 
strate that c„ and c. cannot be zero simultaneously. We have 

Ac 4 = I 40 (I 40 + I 22 ) - I 20 (I 00 +I 42 )and 

AC 2 = I 22 (I 40 + I 22 } ~ 2I 2 I 42' Where 

A = 2I 20- I 00 (I 40 +I 22 ) ' 
Then A (c 4 + o 2 ) = l£ + 21^1^ + 1^ - 1^ & + 31^) 



= (I 22 + I 4o ) -^o^eo^W^ 



by (13). 



(2 2) (4 0) 

We now show that c P v ' (j8,j3) - c ? P ' (3,8) cannot be zero. If it 

were, there would exist a non- trivial orthogonal polynomial of the form 

4 2 2 2 2 

P 4 = H n x + (j x y + |i x + \a y which is zero at (|3/j3). Thus the system 

of homogeneous equations P 4 (|3, £) = 0, J wP x y = for 

(p,q) = (0,0)/ (2,0), (0,2) must have a singular coefficient matrix. The 



determinant of the coefficient matrix is 







T 22 X 2 X 2 
X 42 X 40 *22 



42 42 



L 22 



40 



which expands to 

-^" (I - I ) 
2 u 22 4 0' 

22 



2 2 

I 42 (I 40 " W + (I 60 " W (I 22 " J 2oW 



Then by (12) and (14), the determinant is positive. 



10 



Case (ii) . Assume that 

2 
(18) (a 4 + Aa 2 + Bb 4 ) -4 [ Ac 2 + (1+B) c 4 ] = 0, when condition (17) 

(2 2) 

is satisfied. P ' (ft/j3) = requires B = -1, and A as the parameter. In 

s 2 

that instance we have (a. - b + Aa ) - 4Ac_ = which would require that 

(2 2) 2 2 

a = c = (a - b ) = 0. But a = c = implies P = x y , clearly an 

(2 2) 

impossibility. Thus we may suppose that P \B,fi) ^ 0. (Note: It is 

(2 2) 

possible for P ' (8/8) to be zero, but not, of course, under condition (18) ). 

pC4,0) 

Now we may write A = - (1 + B) , 9 \ = (1 + B) n. 

P U/ '(S,/3) 
Then (18) becomes 

[a 4 + (1+B) M a 2 + Bb 4 ] 2 -4 [ (1+B) ^ + (1+B) c 4 ] = 0. 

We write this as a quadratic in 1+B, obtaining 

(1+B) 2 [ M a 2 + b 4 ] 2 + (1+B) [2(a 4 -b 4 ) dia^b^) - r(nc 2 + cj ] + (a^) 2 = 0. 

(2 2) 

Thus, we must have |_ic_ + c = 0. But this is equivalent to c.P ' (8,8) 

- c_P ' (8,8) = 0, which was shown to be impossible in case (i). 
For the zeros of P~(0,y) to be distinct and finite we must have 

(iii) E i 

(iv) D 2 - 4BE t 

(v) B i 0. 
Case (iii) is case (i) , and case (iv) is similar to case (ii). Since 

P ( °' 4) (x,y) = P (4,0) (y,x), and in particular, P ( °' 4) (6,|3) = P (4 ' 0) ($ , 8) , we 

(2 2) 

can always take B ± 0. If P (j3,|3) = 0, we must take B = -1, however, 

assuming that P ' (8,8) i 0. In any case, restriction ^2 is satisfied. 

We have now completed the proof of the following theorem. 
Theorem 19 ; For all but a finite number of values of the parameter in P , 

11 



there is a corresponding 12 point cubature formula of precision 7 for any fully 
symmetric region R and weight function w. 

For f.s. regions it is desirable to have a f.s. formula. This would be 
obtained by taking B = 1, if that is possible. This construction would fail to 

yield a f.s. formula if any one of conditions (ii) - (iv) fail for B = 1, or if 

(2 2) 
P (Bid) ~ 0. We give an example where the latter occurs. 

Consider the family of f.s. polygonal regions with vertices at 

(±l,±l),(±t,0), and (0,±t), where t>0 is a parameter. Let w = 1 on R. The 

(2 2) 

I are polynomials in t, thus P ' (/9,j3) is a rational function of t. The 

(2 2) 

numerator of P ' (j3,8) (t) has a zero t f a .60584. For t = t n then, none of 

the formulas given by our construction is fully symmetric, as B = -1 for all 
of them. A representative formula is given in Table 2, and corresponds to 
A = 1. It is easy to see that all of the formulas we obtain for this region in- 
volve complex nodes. 

Points Weight 



(±.74553, ±. 


74553) 


.17834 


(±.32252,0) 




.79365 


(±.90057,0) 




.02390 


(0,±. 64198) 




.17769 


(0,±. 452431) 




-.14023 



i 

20. Alternate Construction: Fully Symmetric Regions 



Table 2: R= j(±x,±y), (±y,±x):0^yac^t +y(l-t ), t -.60584 ( , w = l. 



We now consider an alternate construction for f.s. regions which yields 
f.s. formulas, when it is successful. The spirit of the method is identical 

12 



to that of the previous method. We consider the following orthogonal poly- 
nomials: 

(21) P 2 = p< 4 .°>-p<°.4> = (x V)(x 2 + yV) 
P p (4.0) + Ap (2,2) + p (0,4) 

4 2 2 4 2 ? 

= x + Ax y + y + C(x + y ) + E, 

2 
where y = b -a , C = a + b. + Aa ? , E = 2c + Ac ? , and A is selected so 

that 

(22) P_(y,0) = 0. 

p(4,0) ( 0) + p (0,4) ( Q) 

We then have A = to o\ ^OLuJ ^ hence we must have 

p U/Z V,o) 

P (2/2) (y,0) ^ 0. 

If we assume condition (22) can be satisfied, the common zeros of the 
polynomials (21) are (±y, 0) , (0, ±y), (± 6, ± 6) , and (± t, ± t)/ where 6 and t 
are zeros of P.(x / x). If these fail to be distinct, or if P,-(x,x) has degree 2, 
the construction fails. 

We could, of course, allow another parameter in P , as we did pre- 
viously. This would probably ensure the existence of formulas of this type; 
however, our goal here was to attempt to construct a f.s. formula if the 
previous construction failed for B = 1. 

This formula for the region given previously (t = t_ e= .60584) is given 
in Table 3. It is not self-contained. 



13 



Points Weight 

(±.34308,±. 34308) .39246 

(±.77704, ±.77704) .13621 

(±.74916,0) .07716 

(0,±. 74916) .07716 



I 



Table3: R = j (±x,±y) , (±y ,±x):0sy£X£t +y(l-t ) ,t == . 60584 j , w= 1 

We noted previously that our original construction failed to give a self- 
contained formula for the square. The alternate construction yields a formula 
previously given by Tyler [8]. We hasten to note that the alternate construc- 
tion is not applicable to arbitrary symmetric regions. 

We point out an example of failure of the alternate procedure due to 
P (x,x) being of degree 2. Consider again the family of f.s. polygonal regions 
with vertices at (±1,±1), (#,0), (0,±t). For t = t =? 3 . 3 , we obtain A = -2 , 

and thus P (x,x) has but two distinct zeros, not the four required. Four of 

2 2 
the common zeros of y -x and P are at infinity. 

o 

2 3 . Minimal Point Formulas : Fully Symmetric Regions 

Theorem 24 : Let R and w be fully symmetric. Then any cubature formula of 

precision 7 for R and w uses at least 12 nodes. 

Proof: Proposition 4 assures us that any such formula must use at least 10 

points. Huelsman [2] shows that there are no 10 point formulas. Thus we 

need only to show that no 11 point formula exists. We assume the contrary: 

There exists a f.s. region for which an 11 point formula exists. Let the nodes 

be denoted by y , k = 1 , . . . , 11. 



14 



Now the v all lie on four linearly independent orthogonal polynomials 

of degree 4. Thus they lie on some non-trivial linear combination of any 

two of the basis polynomials (5). Hence, we deduce that the v, all lie on 

k 

(25) xy [\ x x + ^y + 3^^^)] 

2 2 

Thus each of the y lie on either the conic X,x + (j., y +a 1 (X-. + [~u) / or one 

of the axes. Now the y, must also lie on the polynomials 

^(4.0)^(2.2) 

(26> X 3 P (0 < 4) + M 3 P (2 - 2) . 

Note that these two need not be linearly independent, if all the v lie on 

(2 2) 

P . The polynomials (26) have at most two distinct common zeros on 

each of the x and y axes, for a total of four. 

2 2 

The remaining iA must then lie on the conic X-.X + |-i,y + a (X ,+|~i,) . 

(1 3) 

Two possibilities present themselves: (I) The y, all lie on one of P 

orP^ 3/1 ^, (II) the y do not all lie on either of P^ 1 ' 3 ' or P^ 3,1 \ 

2 
We consider case (I). Suppose at least seven of the v, lie on x + a . 

2 (4 o) (2 2) 

Now x + a and X 9 P ' + |~i 9 P ' have at most four finite common zeros, 

X La u 

2 
and this is not enough. If seven of the v lie on y + a , the argument is 

dual. 

For case (II), we have both X, and \i. non-zero. The v, lie on the 

following orthogonal polynomials: 

2 . 2 






P 1 =xy[X 1 x +M 1 y +a 1 (X 1 + i-Lj) ] 

p 2 =x 2 p (4 < 0) ^ 2 p (2 < 2) 

P3=X 3 P (0 < 4) ^ 3 P (2 ' 2) 

p 4 -x 4 p w '« + „ 4 p»-» 



15 



Now we note that the common zeros of P and P appear in symmetric 
pairs. Hence, they must have eight distinct common zeros of the form 
(±x ,±y ), { ± x ,±y ) , where none of these points lie on either axis, and 
at least seven are nodes in the formula. At least three of the points 

(±x ,±y ) lie on P . Since P ' is an even function of both x and y, and 

(3 1) 

P is an odd function of both x and y, we deduce that 

X 4 p(4/0)(x r Y l ) ± M 4 P (3/1) (^ r y 1 ) = 0. ThusX 4 P (4 ' 0) (x 1/ y 1 )=^P (3 ' 1) (x 1/ y 1 )=0 
Similarly we find that \ P ( ' (x ,y ) = n P ( ' '(x y ) = 0. Since not all 

(3 1) 

eight of the points lie on P , we must have \i. = 0. 

We now have established that the four linearly independent orthogonal 
polynomials are 

p 2 = p (2,2) 
p 3=p (0.4) 

P 4 =P (4 ' 0) • 
Since the v . lie on P. = P ' ' and P 3 = P ' , they are a subset of the 

common zeros of those two polynomials. The common zeros of P ' and 

t,(0/ 4 ) , ,. r>(4,0) „(0,4) , 2 2 W 2 L 2 2, _, 

P also lie on P -P = (x -y ) (x +y -y ). Thus eight zeros lie 

2 2 2 2 2 

on x -y and eight on x +y - y . Since we have four zeros on the axes, it is 

clear that they must be (0,±y), (±y,0), and these are each of multiplicity two 

as common zeros of P ' and P . Now P = xy [x +|a.y +(l+|_L)a ] is 

2 2 
zero at the above points. It is easily seen that the eight zeros on x -y can 

lie on P only if |_i = -1. 

16 



Then for all common zeros not on the axes, the ordinate and abscissa 

have the same absolute value. Thus the zeros of P ' (x,x) must be the 

(2 2) (4 0) 4 2 

same as those of P ' (x,x). We have P ' (x,x) = x + (a +b )x +c , 

(2 2) 4 2 

P ' (x,x) = x +2a x + c . Thus a + b = 2a_ and c = c ? . Consider- 

(2 2) 2 

ing the common zeros on the axes gives us P ' (x,0) = a ? x + o = 0, 

2 C 2 (0 4) / C 2 C 2 

or x = - — . Then P ' (V- — / 0) = - — b„ + c„ = 0, or c b /1 = c„a . 
a a a 4 4 2 4 4 2 

The previous condition o = c implies a ? = b , since we must have c -- 1 - 0. 



(4 0) / C 2 
a,, + b„ = 2a then gives a„ = b„ = a . The condition P v ' ( V - 7—, 0) = 

> 

. Since 



4 4 2 4 4 2 v a_ 

c„ z 



1 
gives us = -7- 

a 2 



L C 2 " a 2 a 4 C 2 + C 4 a 2 ] = aj [ C 2 " a 2 (a 4 " V j 



c. /0, we have c ? = a 9 (a* - b ), but a = b. gives the contradiction c = 0. 
Thus \d . jL -1 either, and we have completed the proof. 
2 7 . Special Case ; Symmetric Product Regions 

When R = [-a, a] x [-b,b] and w(x,y) = u(x)v(y) where u and v are even 
functions we can obtain the same results as for f.s. regions. We refer to 

these regions as symmetric product (s.p.) regions. 

^ . , , . , ,1 . ■. r^(m / 4-m) n . 

For s.p. regions the basis orthogonal polynomials, P , m=0,...,4, 

(k) 

are products of orthogonal polynomials in one variable. Thus if L (x) is the 

monic polynomial which is orthogonal to all polynomials of degree <k, over 

(k) 

[-a, a] with respect to u(x), and if M (y) is the corresponding polynomial 

for [-b,b] and v(y), then P (m ' 4 " m) = L (m) (x)M (4 ~ m) (y). It can be shown that 
the orthogonal polynomials P ' are of the form 



(4,0) ,2 2 W 2 2. 
P v = (x -x ) (x -x 4 ) 

P v = xy (x -x ) 



17 



_(2,2) ,2 2 W 2 2. 
P = (x -x 2 ) (y -v 2 ) 

P =xy(y -y ) 

_(0,4) ,2 2 W 2 2. 

P = (y -yj (y -y 4 ) . 



It is easy to show that the inequalities 

2 2 2 2 2 
< x. < x < x_ < x. < a and 
12 3 4 

2 2 2 2 2 
< y x < y 2 < y < y 4 < b are valid. 

In the case R is a s.p. region, the orthogonal polynomials correspond- 
ing to (6) are 

,22 2 2, 
Pj = -xy (x 3 y - y 3 x ) 

, » ,222222, 

(28) P 2 = -xy (x^y + y 3 x -2x 3 y 3 ) 

4 2 2 4 

P = x + Ax y + By 

- (x + x 4 - Ay 2 ) x - ( By x + By 4 + Ax 2 ) y 

, 2 2 , . 2 2 , ^ 2 2 
+ x 1 x 4 +Ax 2 y 2 + By 1 y 4 

with A and B chosen so as to satisfy 

(29) P 3 (a,/3) = (Xg - Xj)(x^ - x*) + A (x* - x^y* - y*) 

+ B(y* - y\) f% - x*) = 

where (a, 5) = teg/Yg) . 

The inequalities between the x. and y, assure we have restriction R. 
satisfied, with B as a parameter. Then 

A _ _ (X 3 " x l ) (X 3 ' X 4 } + B(y 3 ' y l } (y 3 I y 4 } 

(X 3 " X 2 } (y 3 ■ y 2 } 

We now consider the zeros of P,-(x,0) with B as a parameter. 

4,2 2 2, ,22 22 2 2. 

P 3 (x, 0) = x - (x l + x 4 + Ay 2 ) + (x 1 x 4 + Ax 2 y 2 + By^) , 

18 



2 2 2 2 2 2 

so if x-,x. + Ax_y_ + By,y.. 4 and 

14 2 2 14 

/ 2 2 2.2 „, 2 2 2 22, 

(x 1 + x 4 + Ay 2 ) - 4(x x x 4 + Ax 2 + By^ ) £ 

for some value of B, the zeros will be distinct. Substituting A in terms of 

B in the first gives us 



1 



(x 3- X 2 )(y 3- y 2 } 



,2 2 W 2 2. 2 2 ,2 2 W 2 2, 2 2 
(X 3 ' X 2 )(y 3 " Y 2 } X 1 X 4 " (X 3 " X 1 )(X 3 " X 4 ) X 2 y 2 



- B(y 3 " y l } (Y 3 " y 4> X 2 y 2 + By l y 4 (X 3 " X 2 } (y 3 " y 2 } 

» Z. L* \ * Li Li \ £* Li . L* Lt * * Lt La » Li Lt 

(x 3 " X 2 } (y 3" y 2 )X ! X 4 " (X 3 " X l> (X 3 " X 4 ) X 2 Y 2 



+ B 



(X 3 " X 2 } (y 3 " y 2 } 

(La \ / " ^ \ L, Lt . Li Li » » Li 

(y 3 " y l )(y 3" y 4 )x 2 y 2 + (x 3" X 2 )(y 3 



2. 2 2 
Y 2 } Y 1 Y 4 



(x 3" X 2 )(y 3" y 2 } 



Inspection of the above in the light of the inequalities between the x. 
and y. shows us that the coefficient of B is positive, hence the expression 
is non-zero for all but one value of B. 

Considering in a similar way the second expression, one finds that the 



coefficient of B is 



(y 3 ' y l' (y 3 " y 4> 



(x 3- X 2 )(y 3- y 2» 



7^0, hence the expression 



is zero for at most two values of B. 

The polynomial P~(0,y) must also have four distinct zeros, and similar 
consideration gives the result for all but a finite number of values of B. 
Thus we have proved the theorem now given. 



19 



Theorem 3 ; For all but a finite number of values of B, there is a correspond- 
ing 12 point cubature formula of precision 7 for any symmetric product 

region R and weight function w. 

2 
We consider an example. Let R = (-=°,<») x[-l,l] and w(x,y) = e 

Then , r 

X pq (q+l)2P- i (p/2)! 

for p and q both even. For B > 7.5 the formulas are self-contained. A typi- 
cal one, for B = 10, is given approximately in Table 4. 

Point Weight 

(±1.22475, ±.77460) .16412 

(±.75942,0) .54525 

(±2.27056,0) .01541 

(0,±. 55770) .69894 

(0,±. 97772) .18462 

-x 2 
Table 4: R =(-»,«) x [-1,1], w(x f y) = e 

31. Minimal Point Formulas : Symmetric Product Regions 

Theorem 32 : Let R be a symmetric product region. Then any cubature formula 
of precision 7 for R and w uses at least 12 points. 

Proof: The proof we are going to give here has a slightly different flavor than 
that given for f. s. regions. We do so because it is felt that the use of alge- 
braic geometry may be indicative of the type of proof which may be necessary 

(k) 

for more complex regions. We note that the only common zeros that L (x), 

(k) 
k = 1,2,3,4 can have are at the origin, and similarly for M (y) , k = 1,2 ,3 ,4, 

We need a preliminary result. 



20 



Proposition 33 : Let i(x) be a linear component of L (x) which is not x. 
Then the only orthogonal polynomials of degree 4 (over [-a, a] x [-b,b] 
with respect to u(x)v(y))which have £(x) as a component are multiples of 
L v '(x)M v '(y). 
Proof: Suppose that £(x)Q(x,y) is an orthogonal of degree 4, and that A(x*)=0, 

1 A 

Then(x-x*)Q(x /y )= T \ L (k) (x)M (4 " k) (y) , so £ X, L (k) (x*)M (4 " k) (y) = 0. 

k=0 K k=0 K 

(V) 

This is possible only if X,L V '(x*) = for k = 0, 1 , . . . ,4. Thus 

X = for k^m, and the proposition is established. We note the identical 

result holds in y. 

We have noted previously that no cubature formula of precision 7 can 

use fewer than ten points. For s.p. regions it is clear none can use ten, 

(2) (2) (4) 

since L (x)M (y) and L (x) have only eight common finite zeros. Thus 

we need only to show no s.p. region exists which has an 11 point formula. 

Assume the contrary, and let the nodes be y , k =1, . . . , 11. 

(4) (2) (2) (A) 

Proposition 34 : They do not all lie on L v / (x) / L v '(x)M v '(y), or M v '(y). 

(4) 
Proof: The argument is similar for all three; we consider L (x). At least 

(4) 

one linear component of L (x) must have ^3 of they, on it. Say 

(4) 
L (x) =£(x)Q(x) where 2*3 of they, lie oni,(x). Because any polynomial of 

degree four on which all the y lie must be an orthogonal polynomial, and 

because there are at least two linearly independent 0(x,y) passing through 

the ^8 y not oni(x), we have two linearly independent orthogonal poly- 

nomials of the f orm i (x) Q (x , y) . This contradicts Proposition 33. 



21 



Now we are assured that the v lie on four linearly independent ortho- 
gonal polynomials of the form 

? 1 = L {4) ^)+X 1 L {2) (x)M {2) (y) 
P 2 = L (3) (x)M (1) (y) +X 2 L (2) (x)M (2) (y) 
P 3 = L (1) (x)M (3) (y) +X 3 L (2) (x)M (2) (y) 
P 4 = M (4) (y)+X 4 L (2) (x)M (2) (y), 

where X and \. are non-zero. 

(3) (1) 2 2 

Suppose the v all lie on L (x)M (y) = xy(x -x ) . We know that not 

more than two of the v could lie on either of x ± x , since if > 3 were on 

x + x (say), there are ^2 linearly independent Q such that each of the 

(x + x )Q is an orthogonal polynomial. This is not possible by Proposition 33 

Thus there are at most four of they, not on xy. Then we see that there are 

^2 linearly independent orthogonal polynomials of the form xyQ 9 , where Q 9 

is of degree 2, on which all they lie. This follows because there are s2 

linearly independent Q passing through four points. We must have 

4 
xyQ 2 = E M m L (m) (x)M (m) (y). Ifx=0, 

(4} m= ° (2) (2) (A) 

we have |^M l '(y) + |^L V ; (0)M V y (y) + u L l ' (0) =0. 

This is possible only if |j = p_ = |i . = 0. Thus the two linearly independent 
xyQ are I/ 3 '(x)M (1 '(y) and L^'(x)M^ 3 '(y) f so if they all lie on one of 
L (3 ^(x)M (1 '(y) or L (1 '(x)M (3 '(y) , they lie on both. We must have nodes off 
the axes, and these can only be (± x , ± y ). The polynomials P. and P. 
can have at most two zeros on the y and x axes, respectively. Thus we can- 
not obtain 11 common zeros for P, , P„ . P„ , and P„. 

1 2 3 4 

22 



The remaining possibility is that both \ and \ are non-zero. Then 
the v k all lie on X^ - X^ = xy [A^-x 2 ) - X 2 (y 2 -y 2 ) ]. If v lies on 
the x-axis, we have v. = (±x ,0), since ±x are the only zeros of P (x,0). 
Likewise (0,±y_) are the only zeros of P on the y-axis. But then 

P 1 (±x 2 ,0) = L (4) (±x 2 ) + X 1 L (2) (±x 2 )M (2) (0) = L (4) (x 2 ) } 0. Similarly 

(4) 
p (0,±y ) = M (y_) ^ 0. Hence there can be no nodes on the axes. But 

2 2 2 2 

then they must all lie on X»(x - x ) - \„(y - y_). This is impossible since 

not all of the nodes of the formula can lie on a polynomial of degree ^3. 



35 . Conclusions 

It is known that the minimum number of points required by a cubature 
formula of specified precision depends on the region. We have exhibited 
12 point formulas for f.s. and s.p. regions, which have precision 7, and 
shown this to be the minimum number of points possible. This answers affir- 
matively a conjecture by Stroud [7, Section 3. 16] that certain known 12 point 
cubatures of precision 7 are minimal point rules. In an earlier section the 
author conjectured the result holds for arbitrary symmetric regions as well. 

The author knows of no region for which a 10 point or 11 point formula 
exists, and it would be interesting to know if there is one. Likewise, we 
mig-ht ask: Is there a planar region for which the minimal number of points 
for a formula of precision 7 is greater than 12? The author conjectures that 
the triangular region may be a candidate. See [1] for some computations on 
this problem. A proof similar to the above does not seem likely, however. 

23 



The extension of the above approach to other regions, especially in 
more dimensions, and other degrees of precision, does not appear to be 

straightforward. The present analysis was made possible by the rather 

tj — . 
— +1 

of which the nodes must be common zeros. For example, for fully symmetric 

planar regions, the author would conjecture that the minimum number of 

points for formulas of precision 9 would be 20. However, we could be sure 

the nodes would lie on at most one polynomial of degree 5. The author has 

found a 20 point formula for the square, the nodes actually being common 

zeros of two orthogonal polynomials of degree 5 [1]. 



24 



Bibliography 



1. Richard Franke, "Obtaining Cubatures for Rectangles and other Planar 
Regions by Using Orthogonal Polynomials", Math. Comp. 25 (1971) 
pp 803-818 

2. C. B. Huelsman, III, "Near Minimum Quadrature Formulas over Fully 
Symmetric Planar Regions", USAF/AFSC/AFWL TR AFWL-7 1-162 , 

Air Force Weapons Lab, Kirtland AFB, NM, 1971 

3. LP. Mysovskih, "On the Construction of Cubature Formulas for the 
Simplest Domains", USSR Comput. Math, and Math. Phys., 4 (1964) 
pp 1-18 

4. A. H. Stroud, "Quadrature Methods for Functions of More than One 
Variable" in Numerical Properties of Functions of More than One 
Independent Variable , H. C. Thacker, Jr., etal., New York Academy 
Sc. V 86, 1960, pp 776-791 

5. A. H. Stroud, "Integration Formulas and Orthogonal Polynomials", 
SIAM J. Numer. Anal. 4 (1967), pp 381-389 

6. A. H. Stroud, "Integration Formulas and Orthogonal Polynomials II", 
SIAM J. Numer. Anal. 7 (1970), pp 271-276 

7. A. H. Stroud, Approximate Calculation of Multiple Integrals , 
Prentice-Hall, Inc., Englewood Cliffs, N. J., 1971 

8. G. W. Tyler, "Numerical Integration of Functions of Several Variables", 
Canadian J. of Math., 5 (1953), pp 393-412 



25 



Distribution List 

No. of copies 

Defense Documentation Center 12 

Cameron Station 
Alexandria, Virginia 22314 

Library 2 

Naval Postgraduate School 
Monterey, California 

Dean of Research Administration 1 

Naval Postgraduate School 
Monterey, California 

Professor Richard Frank e 5 

Department of Mathematics 
Naval Postgraduate School 
Monterey, California 

Professor Craig Comstock 5 

Department of Mathematics 
Naval Postgraduate School 
Monterey, California 

Professor David A. Ault 1 

Department of Mathematics 
Naval Postgraduate School 
Monterey, California 

Professor Robert E. Gaskell 1 

Chairman, Department of Mathematics 
Naval Postgraduate School 
Monterey, California 

Professor R. E. Barnhill 1 

Department of Mathematics 

University of Utah 

Salt Lake City, Utah 84112 

Professor A. H. Stroud 1 

Department of Mathematics 
Texas A & M University 
College Station, Texas 77843 

Professor D. Mangeron 1 

Department of Mathematics 
University of Alberta 
Edmonton, Alberta, Canada 



26 



No. of copies 



Dr. Richard Lau 1 

Office of Naval Research 
Pasadena, California 

Dr. Leila Bram 1 

Director, Mathematics Program 
Office of Naval Research 
Arlington, Virginia 22217 

Professor Frank Lether 1 

Department of Mathematics 
University of Georgia 
Athens, Georgia 3 0601 

Dr. Seymour Haber 1 

Numerical Analysis Section 
National Bureau of Standards 
Washington, D. C. 2 0234 

Dr. M. Wayne Wilson 1 

Dr. Peter Hirsch 1 

International Business Machines, Inc. 
P. O. Box 13 69 
Houston, Texas 77001 

Dr. O. G. Johnson 1 

International Mathematical and Statistical Libraries, Inc. 
6200 Hillcroft, Suite 510 
Houston, Texas 77036 

Dr. David Kahaner 1 

Los Alamos Scientific Laboratory 
Los Alamos, New Mexico 87544 

Mr. Duane Stevenson 1 

Kaman Nuclear 

1700 Garden of the Gods Road 

Colorado Springs, Colorado 80907 

Mr. Loren Shannon 1 

CIBAR, Inc. 

Colorado Springs, Colorado 80907 

Captain C. B. Huelsman, III 1 

Air Force Weapons Laboratory 

Kirtland Air Force Base, New Mexico 87117 

Mr. Arnold Lent 1 

Electronic Data Processing 
Bell Aerospace Company 
Buffalo, New York 1424 

27 



UNCLASSIFIED 



Security Clarification 



■•wd'm.ww^i 



DOCUMENT CONTROL DATA -R&D 



(Sacurlty clatalflcatlon ol (lilt, body ol abalract and Indixlnj annotation wuat ba antarad whan lha ovartfll taport la claaalllad) 



I ORIGINATING ACTIVITY (Corporate authot) 

Naval Postgraduate School 
Monterey, California 



2a. REPORT IICURITV CLASSIFICATION 



UNCLASSIFIED 



2b. OROUP 



■^3 



} REPORT TITH 



Minimal Point Cubatures of Precision Seven for Symmetric Planar Regions 



4. DESCRIPTIVE NOTKI (Typ* of taport and,lr.clualva da fa) 



Technical Report, 1972 



I AUTHOR(S) (fltit r^rr.a, taidula Initial, lait ntma) 



Franke, Richard 



• REPORT DATE 



14 February 1972 



70. TOTAL NO. OP PAOII 



32 



76. NO. OP REPS 



»•. CONTRACT OR GRANT NO. 



b. PROJECT NO. 



*a. ORIGINATOR'* REPORT NUMIERIS) 



NPS-53FE72021A 



Bfc. OTHER REPORT NO(S) (Any olhat nuwbata that may ba attlgnad 
thla tapott) 



10. DISTRIBUTION STATEMENT 



Approved for public release; distribution unlimited. 



II. SUPPLEMENTARY NOTES 



12. SPONSORING MILITARY ACTIVITY 

Foundation Research Program 
Naval Postgraduate School 



IS. ABSTRACT 



A method of constructing 12 point cubature formulas with polynomial pre- 
cision seven is given for planar regions and weight functions which are 
symmetric in each variable. If the nodes are real the weights are positive. 
For any fully symmetric region, or any region which is the product of 
symmetric intervals, it is shown that infinitely many 12 point formulas exist, 
and that these formulas use the minimum number of points. 



.'£?.. 1473 (I>ACI " 

•/N eioi-eo7-«on 



28 



UNCLASSIFIED 



4-11441 



UNCLASSIFIED 



S« -.-iiriix Classification 



ki« wo noi 



Minimal point cubature 
Cubature 
Planar region 
Polynomial precision 
Orthogonal polynomials 
Symmetric region 



DD ,'«r..1473 <back. 



S/N 0101 -807-6a21 



29 



UNCLASSIFIED 



Security Classification 






U144132 



DUDLEY KNOX LIBRARY - RESEARCH REPORTS 



5 6853 01057993 1 



UU412