Namespaces
Variants
Actions

Difference between revisions of "Cubature formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
c0272101.png
 +
$#A+1 = 224 n = 0
 +
$#C+1 = 224 : ~/encyclopedia/old_files/data/C027/C.0207210 Cubature formula
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A formula for the approximate calculation of multiple integrals of the form
 
A formula for the approximate calculation of multiple integrals of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272101.png" /></td> </tr></table>
+
$$
 +
I ( f  )  = \
 +
\int\limits _  \Omega
 +
p ( x) f ( x)  dx.
 +
$$
 +
 
 +
The integration is performed over a set  $  \Omega $
 +
in the Euclidean space  $  \mathbf R  ^ {n} $,
 +
$  x = ( x _ {1} \dots x _ {n} ) $.
 +
A cubature formula is an approximate equality
 +
 
 +
$$ \tag{1 }
 +
I ( f  )  \cong \
 +
\sum _ {j = 1 } ^ { N }
 +
C _ {j} f ( x  ^ {(} j) ).
 +
$$
  
The integration is performed over a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272102.png" /> in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272104.png" />. A cubature formula is an approximate equality
+
The integrand is written as the product of two functions: the first,  $  p ( x) $,
 +
is assumed to be fixed for each specific cubature formula and is known as a weight function; the second,  $  f ( x) $,
 +
is assumed to belong to some fairly broad class of functions, e.g. continuous functions such that the integral  $  I ( f  ) $
 +
exists. The sum on the right-hand side of (1) is called a cubature sum; the points  $  x  ^ {(} j) $
 +
are known as the interpolation points (knots, nodes) of the formula, and the numbers  $  C _ {j} $
 +
as its coefficients. Usually  $  x  ^ {(} j) \in \Omega $,
 +
though this condition is not necessary. In order to compute the integral  $  I ( f  ) $
 +
via formula (1), one need only calculate the cubature sum. If  $  n = 1 $
 +
formula (1) and the sum on its right-hand side are known as a quadrature formula and sum (see [[Quadrature formula|Quadrature formula]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272105.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
Let  $  \alpha = ( \alpha _ {1} \dots \alpha _ {n} ) $
 +
be a multi-index, where the  $  \alpha _ {i} $
 +
are non-negative integers; let  $  | \alpha | = \alpha _ {1} + \dots + \alpha _ {n} $;  
 +
and let  $  x  ^  \alpha  = x _ {1} ^ {\alpha _ {1} } \dots x _ {n} ^ {\alpha _ {n} } $
 +
be a monomial of degree  $  | \alpha | $
 +
in  $  n $
 +
variables; let
  
The integrand is written as the product of two functions: the first, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272106.png" />, is assumed to be fixed for each specific cubature formula and is known as a weight function; the second, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272107.png" />, is assumed to belong to some fairly broad class of functions, e.g. continuous functions such that the integral <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272108.png" /> exists. The sum on the right-hand side of (1) is called a cubature sum; the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c0272109.png" /> are known as the interpolation points (knots, nodes) of the formula, and the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721010.png" /> as its coefficients. Usually <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721011.png" />, though this condition is not necessary. In order to compute the integral <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721012.png" /> via formula (1), one need only calculate the cubature sum. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721013.png" /> formula (1) and the sum on its right-hand side are known as a quadrature formula and sum (see [[Quadrature formula|Quadrature formula]]).
+
$$
 +
\mu  = \
 +
M ( n, m) = \
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721014.png" /> be a multi-index, where the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721015.png" /> are non-negative integers; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721016.png" />; and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721017.png" /> be a monomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721018.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721019.png" /> variables; let
+
\frac{( n + m)! }{n!m! }
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721020.png" /></td> </tr></table>
+
$$
  
be the number of monomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721021.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721022.png" /> variables; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721024.png" /> be an ordering of all monomials such that monomials of lower degree have lower subscript while the monomials of equal degree have been ordered arbitrarily, e.g. in lexicographical order. In this enumeration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721025.png" />, and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721027.png" />, include all monomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721028.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721029.png" /> be a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721030.png" />. The set of points in the complex space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721031.png" /> satisfying the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721032.png" /> is known as an algebraic hypersurface of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721033.png" />.
+
be the number of monomials of degree at most $  m $
 +
in $  n $
 +
variables; let $  \phi _ {j} ( x) $,
 +
$  j = 1, 2 \dots $
 +
be an ordering of all monomials such that monomials of lower degree have lower subscript while the monomials of equal degree have been ordered arbitrarily, e.g. in lexicographical order. In this enumeration $  \phi _ {1} ( x) = 1 $,  
 +
and the $  \phi _ {j} ( x) $,  
 +
$  j = 1 \dots \mu $,  
 +
include all monomials of degree at most $  m $.  
 +
Let $  \phi ( x) $
 +
be a polynomial of degree $  m $.  
 +
The set of points in the complex space $  \mathbf C  ^ {n} $
 +
satisfying the equation $  \phi ( x) = 0 $
 +
is known as an algebraic hypersurface of degree $  m $.
  
One way to construct cubature formulas is based on algebraic interpolation. The points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721035.png" />, are so chosen that they do not lie on any algebraic hypersurface of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721036.png" /> or, equivalently, they are chosen such that the Vandermonde matrix
+
One way to construct cubature formulas is based on algebraic interpolation. The points $  x  ^ {(} j) \in \Omega $,  
 +
$  j = 1 \dots \mu $,  
 +
are so chosen that they do not lie on any algebraic hypersurface of degree $  m $
 +
or, equivalently, they are chosen such that the Vandermonde matrix
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721037.png" /></td> </tr></table>
+
$$
 +
= \
 +
[ \phi _ {1} ( x  ^ {(} j) ) \dots \phi _  \mu  ( x  ^ {(} j) )] _ {j = 1 }  ^  \mu
 +
$$
  
is non-singular. The Lagrange interpolation polynomial for a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721038.png" /> with knots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721039.png" /> has the form
+
is non-singular. The Lagrange interpolation polynomial for a function $  f ( x) $
 +
with knots $  x  ^ {(} j) $
 +
has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721040.png" /></td> </tr></table>
+
$$
 +
{\mathcal P} ( x)  = \
 +
\sum _ {j = 1 } ^  \mu 
 +
{\mathcal L} _ {j} ( x) f ( x  ^ {(} j) ),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721041.png" /> is the polynomial of the influence of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721042.png" />-th knot: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721043.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721044.png" /> is the Kronecker symbol). Multiplying the approximate equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721045.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721046.png" /> and integrating over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721047.png" /> leads to a cubature formula of type (1) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721048.png" /> and
+
where $  {\mathcal L} _ {j} ( x) $
 +
is the polynomial of the influence of the $  j $-
 +
th knot: $  {\mathcal L} _ {j} ( x  ^ {(} i) ) = \delta _ {ij} $(
 +
$  \delta _ {ij} $
 +
is the Kronecker symbol). Multiplying the approximate equality $  f ( x) \cong {\mathcal P} ( x) $
 +
by $  p ( x) $
 +
and integrating over $  \Omega $
 +
leads to a cubature formula of type (1) with $  N = \mu $
 +
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721049.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
C _ {j}  = I ( {\mathcal L} _ {j} ),\ \
 +
j = 1 \dots \mu .
 +
$$
  
The existence of the integrals (2) is equivalent to the existence of the moments of the weight function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721050.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721051.png" />. Here and below it is assumed that the required moments of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721052.png" /> exist. A cubature formula (1) which has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721053.png" /> knots not contained in any algebraic hypersurface of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721054.png" /> and with coefficients defined by (2), is called an interpolatory cubature formula. Formula (1) has the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721056.png" />-property if it is an exact equality whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721057.png" /> is a polynomial of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721058.png" />; an interpolatory cubature formula has the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721059.png" />-property. A cubature formula (1) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721060.png" /> knots which has the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721061.png" />-property is an interpolatory formula if and only if the matrix
+
The existence of the integrals (2) is equivalent to the existence of the moments of the weight function, $  p _ {i} = I ( \phi _ {i} ) $,  
 +
$  i = 1 \dots \mu $.  
 +
Here and below it is assumed that the required moments of $  p ( x) $
 +
exist. A cubature formula (1) which has $  N = \mu $
 +
knots not contained in any algebraic hypersurface of degree $  m $
 +
and with coefficients defined by (2), is called an interpolatory cubature formula. Formula (1) has the $  m $-
 +
property if it is an exact equality whenever $  f ( x) $
 +
is a polynomial of degree at most $  m $;  
 +
an interpolatory cubature formula has the $  m $-
 +
property. A cubature formula (1) with $  N \leq  \mu $
 +
knots which has the $  m $-
 +
property is an interpolatory formula if and only if the matrix
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721062.png" /></td> </tr></table>
+
$$
 +
[ \phi _ {1} ( x  ^ {(} j) ) \dots \phi _  \mu  ( x  ^ {(} j) ) ] _ {j = 1 }  ^ {N}
 +
$$
  
has rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721063.png" />. This condition holds when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721064.png" />, so that a quadrature formula with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721065.png" /> knots that has the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721066.png" />-property is an interpolatory formula. The actual construction of an interpolatory cubature formula reduces to a selection of the knots and a calculation of the coefficients. The coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721067.png" /> are determined by the linear algebraic system of equations
+
has rank $  N $.  
 +
This condition holds when $  n = 1 $,  
 +
so that a quadrature formula with $  N \leq  m + 1 $
 +
knots that has the $  m $-
 +
property is an interpolatory formula. The actual construction of an interpolatory cubature formula reduces to a selection of the knots and a calculation of the coefficients. The coefficients $  C _ {j} $
 +
are determined by the linear algebraic system of equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721068.png" /></td> </tr></table>
+
$$
 +
\sum _ {j = 1 } ^  \mu 
 +
C _ {j} \phi _ {i} ( x  ^ {(} j) )  = p _ {i} ,\ \
 +
i = 1 \dots \mu ,
 +
$$
  
which is simply the mathematical expression of the statement that (1) (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721069.png" />) is exact for all monomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721070.png" />. The matrix of this system is precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721071.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721072.png" />).
+
which is simply the mathematical expression of the statement that (1) (with $  N = \mu $)  
 +
is exact for all monomials of degree at most $  m $.  
 +
The matrix of this system is precisely $  V ^ { \prime } $(
 +
= V  ^ {T} $).
  
Now suppose it is necessary to construct a cubature formula (1) with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721073.png" />-property, but with less than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721074.png" /> knots. Since this cannot be done by merely selecting the coefficients, not only the coefficients but also the knots are unknowns in (1), giving <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721075.png" /> unknowns in total. Since the cubature formula must have the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721076.png" />-property, one obtains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721077.png" /> equations
+
Now suppose it is necessary to construct a cubature formula (1) with the $  m $-
 +
property, but with less than $  \mu $
 +
knots. Since this cannot be done by merely selecting the coefficients, not only the coefficients but also the knots are unknowns in (1), giving $  N ( n + 1) $
 +
unknowns in total. Since the cubature formula must have the $  m $-
 +
property, one obtains $  \mu $
 +
equations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721078.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
\sum _ {j = 1 } ^ { N }
 +
C _ {j} \phi _ {i} ( x  ^ {(} j) )  = p _ {i} ,\ \
 +
i = 1 \dots \mu .
 +
$$
  
It is natural to require the number of unknowns to coincide with the number of equations: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721079.png" />. This equation gives a tentative estimate of the number of knots. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721080.png" /> is not an integer, one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721081.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721082.png" /> denotes the integer part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721083.png" />. A cubature formula with this number of knots need not always exist. If it does exist, its number of knots is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721084.png" /> times the number of knots of an interpolatory cubature formula. In that case, however, the knots themselves and the coefficients are determined by the non-linear system of equations (3). In the method of undetermined parameters, one constructs a cubature formula by trying to give it a form that will simplify the system (3). This can be done when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721086.png" /> have symmetries. The positions of the knots are taken compatible with the symmetry of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721087.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721088.png" />, and in that case symmetric knots are assigned the same coefficients. The simplification of the system (3) involves a certain risk: While the original system (3) may be solvable, the simplified system need not be.
+
It is natural to require the number of unknowns to coincide with the number of equations: $  N ( n + 1) = \mu $.  
 +
This equation gives a tentative estimate of the number of knots. If $  N = \mu /( n + 1) $
 +
is not an integer, one puts $  N = [ \mu /( n + 1)] + 1 $,  
 +
where $  [ \mu / ( n + 1)] $
 +
denotes the integer part of $  \mu /( n + 1) $.  
 +
A cubature formula with this number of knots need not always exist. If it does exist, its number of knots is $  1/( n + 1) $
 +
times the number of knots of an interpolatory cubature formula. In that case, however, the knots themselves and the coefficients are determined by the non-linear system of equations (3). In the method of undetermined parameters, one constructs a cubature formula by trying to give it a form that will simplify the system (3). This can be done when $  \Omega $
 +
and $  p ( x) $
 +
have symmetries. The positions of the knots are taken compatible with the symmetry of $  \Omega $
 +
and $  p ( x) $,  
 +
and in that case symmetric knots are assigned the same coefficients. The simplification of the system (3) involves a certain risk: While the original system (3) may be solvable, the simplified system need not be.
  
Example. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721089.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721090.png" />. One is asked to construct a cubature formula with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721091.png" />-property; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721092.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721093.png" />, and 12 knots. The knots are located as follows. The first group of knots consists of the intersection points of the circle of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721094.png" />, centred at the origin, with the coordinate axes. The second group consists of the intersection points of the circle of radius <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721095.png" />, also centred at the origin, with the straight lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721096.png" />. The third group is constructed similarly, with radius denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721097.png" />. The coefficients assigned to knots of the same group are identical and are denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721098.png" /> for knots of the first, second and third group, respectively. This choice of knots and coefficients implies that the cubature formula will be exact for monomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c02721099.png" /> in which at least one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210100.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210101.png" /> is odd. For the cubature formula to possess the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210102.png" />-property, it will suffice to ensure that it is exact for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210103.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210104.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210105.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210108.png" />. This yields a non-linear system of six equations in the six unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210109.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210110.png" />. Solving this system, one obtains a cubature formula with positive coefficients and with knots lying in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210111.png" />.
+
Example. Let $  \Omega = K _ {2} = \{ - 1 \leq  x _ {1} , x _ {2} \leq  1 \} $,
 +
$  p ( x _ {1} , x _ {2} ) = 1 $.  
 +
One is asked to construct a cubature formula with the $  7 $-
 +
property; $  n = 2 $,
 +
$  \mu = M ( 2, 7) = 36 $,  
 +
and 12 knots. The knots are located as follows. The first group of knots consists of the intersection points of the circle of radius $  a $,  
 +
centred at the origin, with the coordinate axes. The second group consists of the intersection points of the circle of radius $  b $,  
 +
also centred at the origin, with the straight lines $  x _ {1} = \pm  x _ {2} $.  
 +
The third group is constructed similarly, with radius denoted by c $.  
 +
The coefficients assigned to knots of the same group are identical and are denoted by $  A, B, C $
 +
for knots of the first, second and third group, respectively. This choice of knots and coefficients implies that the cubature formula will be exact for monomials $  x _ {1}  ^ {i} x _ {2}  ^ {j} $
 +
in which at least one of $  i $
 +
or $  j $
 +
is odd. For the cubature formula to possess the $  7 $-
 +
property, it will suffice to ensure that it is exact for $  1 $,  
 +
$  x _ {1}  ^ {2} $,  
 +
$  x _ {1}  ^ {4} $,  
 +
$  x _ {1}  ^ {2} x _ {2}  ^ {2} $,  
 +
$  x _ {1}  ^ {6} $,  
 +
$  x _ {1}  ^ {4} x _ {2}  ^ {2} $.  
 +
This yields a non-linear system of six equations in the six unknowns $  a, b, c $,
 +
$  A, B, C $.  
 +
Solving this system, one obtains a cubature formula with positive coefficients and with knots lying in $  K _ {2} $.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210112.png" /> be a finite subgroup of the group of orthogonal transformations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210113.png" /> of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210114.png" /> which leave the origin fixed. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210115.png" /> and a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210116.png" /> are said to be invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210117.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210118.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210119.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210120.png" /> and any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210121.png" />. The set of points of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210122.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210123.png" /> is a fixed point of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210124.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210125.png" /> runs through all elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210126.png" />, is known as the orbit containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210127.png" />. A cubature formula (1) is said to be invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210128.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210129.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210130.png" /> are invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210131.png" /> and if the set of knots is a union of orbits, with knots belonging to the same orbit being assigned identical coefficients. Examples of sets invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210132.png" /> are the entire space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210133.png" />, and any ball or sphere centred at the origin; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210134.png" /> is the group of transformations of a regular polyhedron <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210135.png" /> onto itself, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210136.png" /> is also invariant. Thus, one can speak of invariant cubature formulas when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210137.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210138.png" />, a ball, a sphere, a cube or any regular polyhedron, and when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210139.png" /> is any function invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210140.png" />, e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210141.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210142.png" />.
+
Let $  G $
 +
be a finite subgroup of the group of orthogonal transformations $  \textrm{ O } ( n) $
 +
of the space $  \mathbf R  ^ {n} $
 +
which leave the origin fixed. A set $  \Omega $
 +
and a function $  p ( x) $
 +
are said to be invariant under $  G $
 +
if $  g ( \Omega ) = \Omega $
 +
and $  p ( g ( x)) = p ( x) $
 +
for $  x \in \Omega $
 +
and any $  g \in G $.  
 +
The set of points of the form $  ga $,  
 +
where $  a $
 +
is a fixed point of $  \mathbf R  ^ {n} $
 +
and $  g $
 +
runs through all elements of $  G $,  
 +
is known as the orbit containing $  a $.  
 +
A cubature formula (1) is said to be invariant under $  G $
 +
if $  \Omega $
 +
and $  p ( x) $
 +
are invariant under $  G $
 +
and if the set of knots is a union of orbits, with knots belonging to the same orbit being assigned identical coefficients. Examples of sets invariant under $  G $
 +
are the entire space $  \mathbf R  ^ {n} $,  
 +
and any ball or sphere centred at the origin; if $  G $
 +
is the group of transformations of a regular polyhedron $  U $
 +
onto itself, then $  U $
 +
is also invariant. Thus, one can speak of invariant cubature formulas when $  \Omega $
 +
is $  \mathbf R  ^ {n} $,  
 +
a ball, a sphere, a cube or any regular polyhedron, and when $  p ( x) $
 +
is any function invariant under $  G $,  
 +
e.g. $  p ( r) $,  
 +
where $  r = \sqrt {x _ {1}  ^ {2} + \dots + x _ {n}  ^ {2} } $.
  
Theorem 1) A cubature formula which is invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210143.png" /> possesses the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210144.png" />-property if and only if it is exact for all polynomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210145.png" /> which are invariant under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210146.png" /> (see [[#References|[5]]]). The method of undetermined coefficients may be defined as the method of constructing invariant cubature formulas possessing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210147.png" />-property. In the above example, the role of the group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210148.png" /> may be played by the symmetry group of the square. Theorem 1 is of essential importance in the construction of invariant cubature formulas.
+
Theorem 1) A cubature formula which is invariant under $  G $
 +
possesses the $  m $-
 +
property if and only if it is exact for all polynomials of degree at most $  m $
 +
which are invariant under $  G $(
 +
see [[#References|[5]]]). The method of undetermined coefficients may be defined as the method of constructing invariant cubature formulas possessing the $  m $-
 +
property. In the above example, the role of the group $  G $
 +
may be played by the symmetry group of the square. Theorem 1 is of essential importance in the construction of invariant cubature formulas.
  
For simple domains of integration, such as a cube, a simplex, a ball, or a sphere, and for the weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210149.png" />, one can construct cubature formulas by repeatedly using quadrature formulas. For example, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210150.png" /> is the cube, one may use the Gauss quadrature formula with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210151.png" /> knots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210152.png" /> and coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210153.png" /> to obtain a cubature formula
+
For simple domains of integration, such as a cube, a simplex, a ball, or a sphere, and for the weight $  p ( x) = 1 $,  
 +
one can construct cubature formulas by repeatedly using quadrature formulas. For example, when $  \Omega = K _ {n} = \{ {- 1 \leq  x _ {i} \leq  1 } : {i = 1 \dots n } \} $
 +
is the cube, one may use the Gauss quadrature formula with $  k $
 +
knots $  t _ {i} $
 +
and coefficients $  A _ {i} $
 +
to obtain a cubature formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210154.png" /></td> </tr></table>
+
$$
 +
\int\limits _ {K _ {n} }
 +
f ( x)  dx  \cong \
 +
\sum _ {i _ {1} \dots i _ {n} = 1 } ^ { k }
 +
A _ {i _ {1}  } \dots A _ {i _ {n}  }
 +
f ( t _ {i _ {1}  } \dots t _ {i _ {n}  } )
 +
$$
  
with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210155.png" /> knots; this is exact for all monomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210156.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210157.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210158.png" />, and in particular for all polynomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210159.png" />. The number of knots of such cubature formulas increases rapidly, a fact which limits their applicability.
+
with $  k  ^ {n} $
 +
knots; this is exact for all monomials $  x  ^  \alpha  $
 +
such that 0 \leq  \alpha _ {i} \leq  2k - 1 $,  
 +
$  i = 1 \dots n $,  
 +
and in particular for all polynomials of degree at most $  2k - 1 $.  
 +
The number of knots of such cubature formulas increases rapidly, a fact which limits their applicability.
  
 
Throughout the sequel it will be assumed that the weight function is of fixed sign, say
 
Throughout the sequel it will be assumed that the weight function is of fixed sign, say
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210160.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
p ( x)  \geq  0 \ \
 +
\mathop{\rm in}  \Omega \ \
 +
\textrm{ and } \ \
 +
p _ {1}  > 0.
 +
$$
  
 
The fact that the coefficients of a cubature formula with such a weight function are positive, is a valuable property of the formula.
 
The fact that the coefficients of a cubature formula with such a weight function are positive, is a valuable property of the formula.
  
Theorem 2) If the domain of integration <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210161.png" /> is closed and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210162.png" /> satisfies (4), there exists an interpolatory cubature formula (1) possessing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210163.png" />-property, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210164.png" />, with positive coefficients and with knots in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210165.png" />. The question of actually constructing such a formula is as yet open.
+
Theorem 2) If the domain of integration $  \Omega $
 +
is closed and $  p ( x) $
 +
satisfies (4), there exists an interpolatory cubature formula (1) possessing the $  m $-
 +
property, $  N \leq  \mu $,  
 +
with positive coefficients and with knots in $  \Omega $.  
 +
The question of actually constructing such a formula is as yet open.
  
Theorem 3) If a cubature formula with a weight satisfying (4) has real knots and coefficients and possesses the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210166.png" />-property, then at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210167.png" /> of its coefficients are positive, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210168.png" /> is the integer part of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210169.png" />. Under the assumptions of Theorem 3, the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210170.png" /> is a lower bound for the number of knots:
+
Theorem 3) If a cubature formula with a weight satisfying (4) has real knots and coefficients and possesses the $  m $-
 +
property, then at least $  \lambda = M ( n, l) $
 +
of its coefficients are positive, where $  l = [ m/2] $
 +
is the integer part of $  m/2 $.  
 +
Under the assumptions of Theorem 3, the number $  \lambda $
 +
is a lower bound for the number of knots:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210171.png" /></td> </tr></table>
+
$$
 +
N  \geq  \lambda .
 +
$$
  
This inequality remains valid without the assumption that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210172.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210173.png" /> are real.
+
This inequality remains valid without the assumption that $  x  ^ {(} j) $
 +
and $  C _ {j} $
 +
are real.
  
Regarding cubature formulas with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210174.png" />-property, one is particularly interested in those having a minimum number of knots. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210175.png" /> it is easy to find such formulas for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210176.png" />, arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210177.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210178.png" />; the minimum number of knots is precisely the lower bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210179.png" />: It is equal to 1 in the first case, and to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210180.png" /> in the second. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210181.png" />, the minimum number of knots depends on the domain and the weight. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210182.png" />, the domain is centrally symmetric, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210183.png" />, the number of knots is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210184.png" />; for a simplex and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210185.png" />, it is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210186.png" />.
+
Regarding cubature formulas with the $  m $-
 +
property, one is particularly interested in those having a minimum number of knots. When $  m = 1, 2 $
 +
it is easy to find such formulas for any $  n $,  
 +
arbitrary $  \Omega $
 +
and $  p ( x) \geq  0 $;  
 +
the minimum number of knots is precisely the lower bound $  \lambda $:  
 +
It is equal to 1 in the first case, and to $  n + 1 $
 +
in the second. When $  m \geq  3 $,  
 +
the minimum number of knots depends on the domain and the weight. For example, if $  m = 3 $,  
 +
the domain is centrally symmetric, and if $  p ( x) = 1 $,  
 +
the number of knots is $  2n $;  
 +
for a simplex and $  p ( x) = 1 $,  
 +
it is $  n + 2 $.
  
 
By virtue of (4),
 
By virtue of (4),
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210187.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{5 }
 +
( \phi , \psi )  = \
 +
I ( \phi \overline \psi \; )
 +
$$
  
is a scalar product in the space of polynomials. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210188.png" /> be the vector space of polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210189.png" /> which are orthogonal in the sense of (5) to all polynomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210190.png" />. This space has dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210191.png" /> — the number of monomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210192.png" />. Polynomials in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210193.png" /> are called orthogonal polynomials for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210194.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210195.png" />.
+
is a scalar product in the space of polynomials. Let $  {\mathcal P} _ {k} $
 +
be the vector space of polynomials of degree $  k $
 +
which are orthogonal in the sense of (5) to all polynomials of degree at most $  k - 1 $.  
 +
This space has dimension $  M ( n - 1, k) $—  
 +
the number of monomials of degree $  k $.  
 +
Polynomials in $  {\mathcal P} _ {k} $
 +
are called orthogonal polynomials for $  \Omega $
 +
and $  p ( x) $.
  
Theorem 4) There exists a cubature formula (1) possessing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210196.png" />-property and having <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210197.png" /> knots (the lower bound) if and only if the knots are the common roots of all orthogonal polynomials for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210198.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210199.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210200.png" />.
+
Theorem 4) There exists a cubature formula (1) possessing the $  ( 2k - 1) $-
 +
property and having $  N = M ( n, k - 1) $
 +
knots (the lower bound) if and only if the knots are the common roots of all orthogonal polynomials for $  \Omega $
 +
and $  p ( x) $
 +
of degree $  k $.
  
Theorem 5) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210201.png" /> orthogonal polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210202.png" /> have <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210203.png" /> finite and pairwise distinct common roots, these roots can be chosen as knots for a cubature formula (1) possessing the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210204.png" />-property.
+
Theorem 5) If $  n $
 +
orthogonal polynomials of degree $  k $
 +
have $  k  ^ {n} $
 +
finite and pairwise distinct common roots, these roots can be chosen as knots for a cubature formula (1) possessing the $  ( 2k - 1) $-
 +
property.
  
The error of a cubature formula (1) in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210205.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210206.png" /> is bounded is defined by
+
The error of a cubature formula (1) in which $  p ( x) = 1 $
 +
and $  \Omega $
 +
is bounded is defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210207.png" /></td> </tr></table>
+
$$
 +
l ( f  )  = \
 +
\int\limits _  \Omega  f ( x)  dx -
 +
\sum _ {j = 1 } ^ { N }
 +
C _ {j} f ( x  ^ {(} j) ).
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210208.png" /> be a Banach space of functions such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210209.png" /> is a linear functional on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210210.png" />. The norm of the functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210211.png" /> characterizes the quality of a given cubature formula for all functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210212.png" />. Another approach to the construction of cubature formulas is based on minimizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210213.png" /> as a function of the knots and the coefficients of the (unknown) cubature formula (with only the number of knots fixed). Implementation of this approach, however, involves difficulties even for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210214.png" />. Important results for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210215.png" /> have been obtained by S.L. Sobolev [[#References|[4]]]. The question of minimizing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210216.png" /> as a function of the coefficients for a given set of knots has been solved completely; the problem of choosing the knots is based on the assumption that they form a parallelepipedal grid and that the minimization depends exclusively on the parameters of this grid. The space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210217.png" />, in particular, may be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210218.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210219.png" />, and in that case the desired cubature formula is assumed to be exact for all polynomials of degree at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210220.png" />.
+
Let $  B $
 +
be a Banach space of functions such that $  l ( f  ) $
 +
is a linear functional on $  B $.  
 +
The norm of the functional $  \| l \| = \sup _ {\| f \| = 1 }  l ( f  ) $
 +
characterizes the quality of a given cubature formula for all functions of $  B $.  
 +
Another approach to the construction of cubature formulas is based on minimizing $  \| l \| $
 +
as a function of the knots and the coefficients of the (unknown) cubature formula (with only the number of knots fixed). Implementation of this approach, however, involves difficulties even for $  n = 1 $.  
 +
Important results for any $  n \geq  2 $
 +
have been obtained by S.L. Sobolev [[#References|[4]]]. The question of minimizing $  \| l \| $
 +
as a function of the coefficients for a given set of knots has been solved completely; the problem of choosing the knots is based on the assumption that they form a parallelepipedal grid and that the minimization depends exclusively on the parameters of this grid. The space $  B $,  
 +
in particular, may be $  L _ {2}  ^ {m} ( \mathbf R  ^ {n} ) $,  
 +
where $  m > n/2 $,  
 +
and in that case the desired cubature formula is assumed to be exact for all polynomials of degree at most $  m - 1 $.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.M. Krylov,  "Approximate calculation of integrals" , Macmillan  (1962)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.I. Krylov,  L.T. Shul'gina,  "Handbook on numerical integration" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.H. Stroud,  "Approximate calculation of multiple integrals" , Prentice-Hall  (1971)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.L. Sobolev,  "Introduction to the theory of cubature formulas" , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  S.L. Sobolev,  "Formulas for mechanical cubature on the surface of a sphere"  ''Sibirsk. Mat. Zh.'' , '''3''' :  5  (1962)  pp. 769–796  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  I.P. Mysovskikh,  "Interpolatory cubature formulas" , Moscow  (1981)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.M. Krylov,  "Approximate calculation of integrals" , Macmillan  (1962)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.I. Krylov,  L.T. Shul'gina,  "Handbook on numerical integration" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.H. Stroud,  "Approximate calculation of multiple integrals" , Prentice-Hall  (1971)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S.L. Sobolev,  "Introduction to the theory of cubature formulas" , Moscow  (1974)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  S.L. Sobolev,  "Formulas for mechanical cubature on the surface of a sphere"  ''Sibirsk. Mat. Zh.'' , '''3''' :  5  (1962)  pp. 769–796  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  I.P. Mysovskikh,  "Interpolatory cubature formulas" , Moscow  (1981)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
The polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210221.png" /> "of the influence of the j-th knot"  (i.e. defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210222.png" />) is also called the basic Lagrangian (for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210223.png" />).
+
The polynomial  $  {\mathcal L} _ {j} ( x) $"
 +
of the influence of the j-th knot"  (i.e. defined by $  {\mathcal L} _ {j} ( x  ^ {(} i) ) = \delta _ {ij} $)  
 +
is also called the basic Lagrangian (for $  x  ^ {(} j) $).
  
The  "m-property"  is also known in Western literature as the degree of precision; i.e. a cubature formula has the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210224.png" />-property if it has degree of precision <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c027/c027210/c027210225.png" />.
+
The  "m-property"  is also known in Western literature as the degree of precision; i.e. a cubature formula has the $  m $-
 +
property if it has degree of precision $  m $.
  
 
Reference [[#References|[a1]]] is both an excellent introduction as well as an advanced treatment of cubature formulas.
 
Reference [[#References|[a1]]] is both an excellent introduction as well as an advanced treatment of cubature formulas.

Revision as of 17:31, 5 June 2020


A formula for the approximate calculation of multiple integrals of the form

$$ I ( f ) = \ \int\limits _ \Omega p ( x) f ( x) dx. $$

The integration is performed over a set $ \Omega $ in the Euclidean space $ \mathbf R ^ {n} $, $ x = ( x _ {1} \dots x _ {n} ) $. A cubature formula is an approximate equality

$$ \tag{1 } I ( f ) \cong \ \sum _ {j = 1 } ^ { N } C _ {j} f ( x ^ {(} j) ). $$

The integrand is written as the product of two functions: the first, $ p ( x) $, is assumed to be fixed for each specific cubature formula and is known as a weight function; the second, $ f ( x) $, is assumed to belong to some fairly broad class of functions, e.g. continuous functions such that the integral $ I ( f ) $ exists. The sum on the right-hand side of (1) is called a cubature sum; the points $ x ^ {(} j) $ are known as the interpolation points (knots, nodes) of the formula, and the numbers $ C _ {j} $ as its coefficients. Usually $ x ^ {(} j) \in \Omega $, though this condition is not necessary. In order to compute the integral $ I ( f ) $ via formula (1), one need only calculate the cubature sum. If $ n = 1 $ formula (1) and the sum on its right-hand side are known as a quadrature formula and sum (see Quadrature formula).

Let $ \alpha = ( \alpha _ {1} \dots \alpha _ {n} ) $ be a multi-index, where the $ \alpha _ {i} $ are non-negative integers; let $ | \alpha | = \alpha _ {1} + \dots + \alpha _ {n} $; and let $ x ^ \alpha = x _ {1} ^ {\alpha _ {1} } \dots x _ {n} ^ {\alpha _ {n} } $ be a monomial of degree $ | \alpha | $ in $ n $ variables; let

$$ \mu = \ M ( n, m) = \ \frac{( n + m)! }{n!m! } $$

be the number of monomials of degree at most $ m $ in $ n $ variables; let $ \phi _ {j} ( x) $, $ j = 1, 2 \dots $ be an ordering of all monomials such that monomials of lower degree have lower subscript while the monomials of equal degree have been ordered arbitrarily, e.g. in lexicographical order. In this enumeration $ \phi _ {1} ( x) = 1 $, and the $ \phi _ {j} ( x) $, $ j = 1 \dots \mu $, include all monomials of degree at most $ m $. Let $ \phi ( x) $ be a polynomial of degree $ m $. The set of points in the complex space $ \mathbf C ^ {n} $ satisfying the equation $ \phi ( x) = 0 $ is known as an algebraic hypersurface of degree $ m $.

One way to construct cubature formulas is based on algebraic interpolation. The points $ x ^ {(} j) \in \Omega $, $ j = 1 \dots \mu $, are so chosen that they do not lie on any algebraic hypersurface of degree $ m $ or, equivalently, they are chosen such that the Vandermonde matrix

$$ V = \ [ \phi _ {1} ( x ^ {(} j) ) \dots \phi _ \mu ( x ^ {(} j) )] _ {j = 1 } ^ \mu $$

is non-singular. The Lagrange interpolation polynomial for a function $ f ( x) $ with knots $ x ^ {(} j) $ has the form

$$ {\mathcal P} ( x) = \ \sum _ {j = 1 } ^ \mu {\mathcal L} _ {j} ( x) f ( x ^ {(} j) ), $$

where $ {\mathcal L} _ {j} ( x) $ is the polynomial of the influence of the $ j $- th knot: $ {\mathcal L} _ {j} ( x ^ {(} i) ) = \delta _ {ij} $( $ \delta _ {ij} $ is the Kronecker symbol). Multiplying the approximate equality $ f ( x) \cong {\mathcal P} ( x) $ by $ p ( x) $ and integrating over $ \Omega $ leads to a cubature formula of type (1) with $ N = \mu $ and

$$ \tag{2 } C _ {j} = I ( {\mathcal L} _ {j} ),\ \ j = 1 \dots \mu . $$

The existence of the integrals (2) is equivalent to the existence of the moments of the weight function, $ p _ {i} = I ( \phi _ {i} ) $, $ i = 1 \dots \mu $. Here and below it is assumed that the required moments of $ p ( x) $ exist. A cubature formula (1) which has $ N = \mu $ knots not contained in any algebraic hypersurface of degree $ m $ and with coefficients defined by (2), is called an interpolatory cubature formula. Formula (1) has the $ m $- property if it is an exact equality whenever $ f ( x) $ is a polynomial of degree at most $ m $; an interpolatory cubature formula has the $ m $- property. A cubature formula (1) with $ N \leq \mu $ knots which has the $ m $- property is an interpolatory formula if and only if the matrix

$$ [ \phi _ {1} ( x ^ {(} j) ) \dots \phi _ \mu ( x ^ {(} j) ) ] _ {j = 1 } ^ {N} $$

has rank $ N $. This condition holds when $ n = 1 $, so that a quadrature formula with $ N \leq m + 1 $ knots that has the $ m $- property is an interpolatory formula. The actual construction of an interpolatory cubature formula reduces to a selection of the knots and a calculation of the coefficients. The coefficients $ C _ {j} $ are determined by the linear algebraic system of equations

$$ \sum _ {j = 1 } ^ \mu C _ {j} \phi _ {i} ( x ^ {(} j) ) = p _ {i} ,\ \ i = 1 \dots \mu , $$

which is simply the mathematical expression of the statement that (1) (with $ N = \mu $) is exact for all monomials of degree at most $ m $. The matrix of this system is precisely $ V ^ { \prime } $( $ = V ^ {T} $).

Now suppose it is necessary to construct a cubature formula (1) with the $ m $- property, but with less than $ \mu $ knots. Since this cannot be done by merely selecting the coefficients, not only the coefficients but also the knots are unknowns in (1), giving $ N ( n + 1) $ unknowns in total. Since the cubature formula must have the $ m $- property, one obtains $ \mu $ equations

$$ \tag{3 } \sum _ {j = 1 } ^ { N } C _ {j} \phi _ {i} ( x ^ {(} j) ) = p _ {i} ,\ \ i = 1 \dots \mu . $$

It is natural to require the number of unknowns to coincide with the number of equations: $ N ( n + 1) = \mu $. This equation gives a tentative estimate of the number of knots. If $ N = \mu /( n + 1) $ is not an integer, one puts $ N = [ \mu /( n + 1)] + 1 $, where $ [ \mu / ( n + 1)] $ denotes the integer part of $ \mu /( n + 1) $. A cubature formula with this number of knots need not always exist. If it does exist, its number of knots is $ 1/( n + 1) $ times the number of knots of an interpolatory cubature formula. In that case, however, the knots themselves and the coefficients are determined by the non-linear system of equations (3). In the method of undetermined parameters, one constructs a cubature formula by trying to give it a form that will simplify the system (3). This can be done when $ \Omega $ and $ p ( x) $ have symmetries. The positions of the knots are taken compatible with the symmetry of $ \Omega $ and $ p ( x) $, and in that case symmetric knots are assigned the same coefficients. The simplification of the system (3) involves a certain risk: While the original system (3) may be solvable, the simplified system need not be.

Example. Let $ \Omega = K _ {2} = \{ - 1 \leq x _ {1} , x _ {2} \leq 1 \} $, $ p ( x _ {1} , x _ {2} ) = 1 $. One is asked to construct a cubature formula with the $ 7 $- property; $ n = 2 $, $ \mu = M ( 2, 7) = 36 $, and 12 knots. The knots are located as follows. The first group of knots consists of the intersection points of the circle of radius $ a $, centred at the origin, with the coordinate axes. The second group consists of the intersection points of the circle of radius $ b $, also centred at the origin, with the straight lines $ x _ {1} = \pm x _ {2} $. The third group is constructed similarly, with radius denoted by $ c $. The coefficients assigned to knots of the same group are identical and are denoted by $ A, B, C $ for knots of the first, second and third group, respectively. This choice of knots and coefficients implies that the cubature formula will be exact for monomials $ x _ {1} ^ {i} x _ {2} ^ {j} $ in which at least one of $ i $ or $ j $ is odd. For the cubature formula to possess the $ 7 $- property, it will suffice to ensure that it is exact for $ 1 $, $ x _ {1} ^ {2} $, $ x _ {1} ^ {4} $, $ x _ {1} ^ {2} x _ {2} ^ {2} $, $ x _ {1} ^ {6} $, $ x _ {1} ^ {4} x _ {2} ^ {2} $. This yields a non-linear system of six equations in the six unknowns $ a, b, c $, $ A, B, C $. Solving this system, one obtains a cubature formula with positive coefficients and with knots lying in $ K _ {2} $.

Let $ G $ be a finite subgroup of the group of orthogonal transformations $ \textrm{ O } ( n) $ of the space $ \mathbf R ^ {n} $ which leave the origin fixed. A set $ \Omega $ and a function $ p ( x) $ are said to be invariant under $ G $ if $ g ( \Omega ) = \Omega $ and $ p ( g ( x)) = p ( x) $ for $ x \in \Omega $ and any $ g \in G $. The set of points of the form $ ga $, where $ a $ is a fixed point of $ \mathbf R ^ {n} $ and $ g $ runs through all elements of $ G $, is known as the orbit containing $ a $. A cubature formula (1) is said to be invariant under $ G $ if $ \Omega $ and $ p ( x) $ are invariant under $ G $ and if the set of knots is a union of orbits, with knots belonging to the same orbit being assigned identical coefficients. Examples of sets invariant under $ G $ are the entire space $ \mathbf R ^ {n} $, and any ball or sphere centred at the origin; if $ G $ is the group of transformations of a regular polyhedron $ U $ onto itself, then $ U $ is also invariant. Thus, one can speak of invariant cubature formulas when $ \Omega $ is $ \mathbf R ^ {n} $, a ball, a sphere, a cube or any regular polyhedron, and when $ p ( x) $ is any function invariant under $ G $, e.g. $ p ( r) $, where $ r = \sqrt {x _ {1} ^ {2} + \dots + x _ {n} ^ {2} } $.

Theorem 1) A cubature formula which is invariant under $ G $ possesses the $ m $- property if and only if it is exact for all polynomials of degree at most $ m $ which are invariant under $ G $( see [5]). The method of undetermined coefficients may be defined as the method of constructing invariant cubature formulas possessing the $ m $- property. In the above example, the role of the group $ G $ may be played by the symmetry group of the square. Theorem 1 is of essential importance in the construction of invariant cubature formulas.

For simple domains of integration, such as a cube, a simplex, a ball, or a sphere, and for the weight $ p ( x) = 1 $, one can construct cubature formulas by repeatedly using quadrature formulas. For example, when $ \Omega = K _ {n} = \{ {- 1 \leq x _ {i} \leq 1 } : {i = 1 \dots n } \} $ is the cube, one may use the Gauss quadrature formula with $ k $ knots $ t _ {i} $ and coefficients $ A _ {i} $ to obtain a cubature formula

$$ \int\limits _ {K _ {n} } f ( x) dx \cong \ \sum _ {i _ {1} \dots i _ {n} = 1 } ^ { k } A _ {i _ {1} } \dots A _ {i _ {n} } f ( t _ {i _ {1} } \dots t _ {i _ {n} } ) $$

with $ k ^ {n} $ knots; this is exact for all monomials $ x ^ \alpha $ such that $ 0 \leq \alpha _ {i} \leq 2k - 1 $, $ i = 1 \dots n $, and in particular for all polynomials of degree at most $ 2k - 1 $. The number of knots of such cubature formulas increases rapidly, a fact which limits their applicability.

Throughout the sequel it will be assumed that the weight function is of fixed sign, say

$$ \tag{4 } p ( x) \geq 0 \ \ \mathop{\rm in} \Omega \ \ \textrm{ and } \ \ p _ {1} > 0. $$

The fact that the coefficients of a cubature formula with such a weight function are positive, is a valuable property of the formula.

Theorem 2) If the domain of integration $ \Omega $ is closed and $ p ( x) $ satisfies (4), there exists an interpolatory cubature formula (1) possessing the $ m $- property, $ N \leq \mu $, with positive coefficients and with knots in $ \Omega $. The question of actually constructing such a formula is as yet open.

Theorem 3) If a cubature formula with a weight satisfying (4) has real knots and coefficients and possesses the $ m $- property, then at least $ \lambda = M ( n, l) $ of its coefficients are positive, where $ l = [ m/2] $ is the integer part of $ m/2 $. Under the assumptions of Theorem 3, the number $ \lambda $ is a lower bound for the number of knots:

$$ N \geq \lambda . $$

This inequality remains valid without the assumption that $ x ^ {(} j) $ and $ C _ {j} $ are real.

Regarding cubature formulas with the $ m $- property, one is particularly interested in those having a minimum number of knots. When $ m = 1, 2 $ it is easy to find such formulas for any $ n $, arbitrary $ \Omega $ and $ p ( x) \geq 0 $; the minimum number of knots is precisely the lower bound $ \lambda $: It is equal to 1 in the first case, and to $ n + 1 $ in the second. When $ m \geq 3 $, the minimum number of knots depends on the domain and the weight. For example, if $ m = 3 $, the domain is centrally symmetric, and if $ p ( x) = 1 $, the number of knots is $ 2n $; for a simplex and $ p ( x) = 1 $, it is $ n + 2 $.

By virtue of (4),

$$ \tag{5 } ( \phi , \psi ) = \ I ( \phi \overline \psi \; ) $$

is a scalar product in the space of polynomials. Let $ {\mathcal P} _ {k} $ be the vector space of polynomials of degree $ k $ which are orthogonal in the sense of (5) to all polynomials of degree at most $ k - 1 $. This space has dimension $ M ( n - 1, k) $— the number of monomials of degree $ k $. Polynomials in $ {\mathcal P} _ {k} $ are called orthogonal polynomials for $ \Omega $ and $ p ( x) $.

Theorem 4) There exists a cubature formula (1) possessing the $ ( 2k - 1) $- property and having $ N = M ( n, k - 1) $ knots (the lower bound) if and only if the knots are the common roots of all orthogonal polynomials for $ \Omega $ and $ p ( x) $ of degree $ k $.

Theorem 5) If $ n $ orthogonal polynomials of degree $ k $ have $ k ^ {n} $ finite and pairwise distinct common roots, these roots can be chosen as knots for a cubature formula (1) possessing the $ ( 2k - 1) $- property.

The error of a cubature formula (1) in which $ p ( x) = 1 $ and $ \Omega $ is bounded is defined by

$$ l ( f ) = \ \int\limits _ \Omega f ( x) dx - \sum _ {j = 1 } ^ { N } C _ {j} f ( x ^ {(} j) ). $$

Let $ B $ be a Banach space of functions such that $ l ( f ) $ is a linear functional on $ B $. The norm of the functional $ \| l \| = \sup _ {\| f \| = 1 } l ( f ) $ characterizes the quality of a given cubature formula for all functions of $ B $. Another approach to the construction of cubature formulas is based on minimizing $ \| l \| $ as a function of the knots and the coefficients of the (unknown) cubature formula (with only the number of knots fixed). Implementation of this approach, however, involves difficulties even for $ n = 1 $. Important results for any $ n \geq 2 $ have been obtained by S.L. Sobolev [4]. The question of minimizing $ \| l \| $ as a function of the coefficients for a given set of knots has been solved completely; the problem of choosing the knots is based on the assumption that they form a parallelepipedal grid and that the minimization depends exclusively on the parameters of this grid. The space $ B $, in particular, may be $ L _ {2} ^ {m} ( \mathbf R ^ {n} ) $, where $ m > n/2 $, and in that case the desired cubature formula is assumed to be exact for all polynomials of degree at most $ m - 1 $.

References

[1] N.M. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[2] V.I. Krylov, L.T. Shul'gina, "Handbook on numerical integration" , Moscow (1966) (In Russian)
[3] A.H. Stroud, "Approximate calculation of multiple integrals" , Prentice-Hall (1971)
[4] S.L. Sobolev, "Introduction to the theory of cubature formulas" , Moscow (1974) (In Russian)
[5] S.L. Sobolev, "Formulas for mechanical cubature on the surface of a sphere" Sibirsk. Mat. Zh. , 3 : 5 (1962) pp. 769–796 (In Russian)
[6] I.P. Mysovskikh, "Interpolatory cubature formulas" , Moscow (1981) (In Russian)

Comments

The polynomial $ {\mathcal L} _ {j} ( x) $" of the influence of the j-th knot" (i.e. defined by $ {\mathcal L} _ {j} ( x ^ {(} i) ) = \delta _ {ij} $) is also called the basic Lagrangian (for $ x ^ {(} j) $).

The "m-property" is also known in Western literature as the degree of precision; i.e. a cubature formula has the $ m $- property if it has degree of precision $ m $.

Reference [a1] is both an excellent introduction as well as an advanced treatment of cubature formulas.

References

[a1] H. Engels, "Numerical quadrature and cubature" , Acad. Press (1980)
[a2] P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1984)
How to Cite This Entry:
Cubature formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cubature_formula&oldid=19012
This article was adapted from an original article by I.P. Mysovskikh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article