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