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