Namespaces
Variants
Actions

Difference between revisions of "Quadrature formula of highest algebraic accuracy"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (gather refs)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
q0761901.png
 +
$#A+1 = 82 n = 0
 +
$#C+1 = 82 : ~/encyclopedia/old_files/data/Q076/Q.0706190 Quadrature formula of highest algebraic accuracy
 +
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 of the type
 
A formula of the type
  
<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/q/q076/q076190/q0761901.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\int\limits _ { a } ^ { b }
 +
p ( x) f ( x)  dx  \approx \
 +
\sum _ {j = 1 } ^ { N }  C _ {j} f ( x _ {j} ),
 +
$$
  
where the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761902.png" /> is assumed to be non-negative on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761903.png" />, where the integrals
+
where the weight function $  p ( x) $
 +
is assumed to be non-negative on $  [ a, b] $,
 +
where the integrals
  
<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/q/q076/q076190/q0761904.png" /></td> </tr></table>
+
$$
 +
\mu _ {k}  = \
 +
\int\limits _ { a } ^ { b }  p ( x) x  ^ {k}  dx,\ \
 +
k = 0, 1 \dots
 +
$$
  
exist and where, moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761905.png" />. The nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761906.png" /> of formula (1) are the roots of a polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761907.png" /> orthogonal on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761908.png" /> with the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q0761909.png" />, and the weights are defined by the condition that (1) be an interpolatory formula. A quadrature formula of this type has algebraic accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619010.png" />, i.e. it is exact for all algebraic polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619011.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619012.png" /> and is not exact for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619013.png" />; it is known as a quadrature formula of Gaussian type.
+
exist and where, moreover, $  \mu _ {0} > 0 $.  
 +
The nodes $  x _ {j} $
 +
of formula (1) are the roots of a polynomial of degree $  N $
 +
orthogonal on $  [ a, b] $
 +
with the weight function $  p ( x) $,  
 +
and the weights are defined by the condition that (1) be an interpolatory formula. A quadrature formula of this type has algebraic accuracy $  2N - 1 $,  
 +
i.e. it is exact for all algebraic polynomials $  f ( x) $
 +
of degree $  \leq  2N - 1 $
 +
and is not exact for $  x  ^ {2N} $;  
 +
it is known as a quadrature formula of Gaussian type.
  
 
This concept can be generalized as follows. Consider the quadrature formula
 
This concept can be generalized as follows. Consider the 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/q/q076/q076190/q07619014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 
+
\int\limits _ { a } ^ { b }
with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619015.png" /> nodes, where the nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619016.png" /> are pre-assigned (fixed) while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619017.png" /> are so chosen that (2) be a quadrature formula of highest algebraic accuracy. Let
+
p ( x) f ( x) dx  \approx \
 
+
\sum _ {j = 1 } ^ { m }  A _ {j} f ( a _ {j} ) +
<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/q/q076/q076190/q07619018.png" /></td> </tr></table>
+
\sum _ {j = 1 } ^ { n }  C _ {j} f ( x _ {j} )
 
+
$$
Formula (2) is exact for all polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619019.png" /> if and only if it is an interpolatory quadrature formula and the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619020.png" /> is orthogonal on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619021.png" /> with the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619022.png" /> to all polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619023.png" />. This reduces the question of the existence of a quadrature formula that is exact for all polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619024.png" /> to the problem of determining a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619025.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619026.png" /> that is orthogonal on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619027.png" /> with the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619028.png" />, and to examining the properties of its roots. If the roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619029.png" /> are real, simple, lie in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619030.png" />, and none of them is one of the fixed nodes, the required quadrature formula exists. If, moreover,
 
 
 
<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/q/q076/q076190/q07619031.png" /></td> </tr></table>
 
 
 
then the algebraic accuracy of the formula is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619032.png" />.
 
  
Under the above assumptions concerning the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619033.png" />, a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619034.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619035.png" />, orthogonal on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619036.png" /> with the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619037.png" />, is defined uniquely (up to a non-zero constant factor) in the following special cases.
+
with  $  N = m + n $
 +
nodes, where the nodes  $  a _ {1} \dots a _ {m} $
 +
are pre-assigned (fixed) while  $  x _ {1} \dots x _ {n} $
 +
are so chosen that (2) be a quadrature formula of highest algebraic accuracy. Let
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619039.png" /> is arbitrary. The single fixed node is an end-point of the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619040.png" />, with the only condition that it be finite.
+
$$
 +
\sigma ( x) = \
 +
\prod _ {j = 1 } ^ { m }  ( x - a _ {j} ),\ \
 +
\omega ( x)  = \
 +
\prod _ {j = 1 } ^ { n }  ( x - x _ {j} ).
 +
$$
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619042.png" /> is arbitrary. The two fixed nodes are the end-points of the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619043.png" />, provided they are finite.
+
Formula (2) is exact for all polynomials of degree  $  \leq  m + 2n - 1 $
 +
if and only if it is an interpolatory quadrature formula and the polynomial  $  \omega ( x) $
 +
is orthogonal on  $  [ a, b] $
 +
with the weight function  $  \sigma ( x) p ( x) $
 +
to all polynomials of degree  $  \leq  n - 1 $.  
 +
This reduces the question of the existence of a quadrature formula that is exact for all polynomials of degree  $  \leq  2n - 1 $
 +
to the problem of determining a polynomial  $  \omega ( x) $
 +
of degree  $  n $
 +
that is orthogonal on  $  [ a, b] $
 +
with the weight function  $  \sigma ( x) p ( x) $,
 +
and to examining the properties of its roots. If the roots of  $  \omega ( x) $
 +
are real, simple, lie in  $  [ a, b] $,  
 +
and none of them is one of the fixed nodes, the required quadrature formula exists. If, moreover,
  
3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619044.png" /> is arbitrary, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619045.png" />. The fixed nodes are the roots of a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619046.png" /> that is orthogonal on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619047.png" /> with the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619048.png" />.
+
$$
 +
\int\limits _ { a } ^ { b }  p ( x) \sigma ( x) \omega  ^ {2} ( x) dx  \neq  0,
 +
$$
  
In cases 1) and 2), the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619049.png" /> is orthogonal relative to the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619050.png" />, which is of fixed sign on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619051.png" />, and therefore its roots are real, simple, lie inside <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619052.png" />, and are consequently distinct from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619053.png" />. The quadrature formula (2) exists, its coefficients are positive and its algebraic accuracy is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619054.png" />. Quadrature formulas corresponding to the cases 1) and 2) are called Markov formulas.
+
then the algebraic accuracy of the formula is $  m + 2n - 1 $.
  
In case 3), the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619055.png" /> changes sign on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619056.png" /> and this complicates the inspection of the roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619057.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619059.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619060.png" />, then the roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619061.png" /> lie inside <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619062.png" /> and separate the roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619063.png" />: Between any two consecutive roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619064.png" /> there is exactly one root of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619065.png" /> (see [[#References|[2]]]). With this weight function, the quadrature formula (2) exists and is exact for all polynomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619066.png" />; however, one cannot state that its algebraic accuracy is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619067.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619069.png" /> the nodes and the coefficients of the quadrature formula can be specified explicitly (see [[#References|[3]]]); the algebraic accuracy in the former case is increased to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619070.png" />, and in the second case to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619071.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619072.png" /> and the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619073.png" />, the nodes and the coefficients have been computed for the quadrature formula (2) (with fixed nodes of type 3)) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619074.png" /> (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619075.png" /> varying from 1 to 40 with step 1) (see [[#References|[4]]]); the algebraic accuracy is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619076.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619077.png" /> is even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619078.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619079.png" /> is odd. A quadrature formula (2) with fixed nodes of type 3) also exists for the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619080.png" /> and the weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619081.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/q/q076/q076190/q07619082.png" />, and the nodes and the coefficients can be explicitly specified (see [[#References|[3]]]).
+
Under the above assumptions concerning the weight function $  p ( x) $,  
 +
a polynomial  $  \omega ( x) $
 +
of degree $  n $,  
 +
orthogonal on  $  [ a, b] $
 +
with the weight function  $  \sigma ( x) p ( x) $,
 +
is defined uniquely (up to a non-zero constant factor) in the following special cases.
  
====References====
+
1)  $ m = 1 $,  
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.I. Krylov,  "Approximate calculation of integrals" , Macmillan  (1962(Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  G. Szegö,  "Ueber gewisse orthogonale Polynome, die zu einer oszillierenden Belegungsfunktion gehören"  ''Math. Ann.'' , '''110''' :  4  (1934) pp. 501–513</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.P Mysovskikh,   "A special case of quadrature formulas containing pre-assigned nodes" ''Izv. Akad. Nauk BelorussSSR. Ser. Fiz.-Tekhn. Navuk'' , '''4''' (1964) pp. 125–127  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.S. Kronrod,  "Nodes and weights of quadrature formulas" , Consultants Bureau  (1965)  (Translated from Russian)</TD></TR></table>
+
$ n $
 +
is arbitrary. The single fixed node is an end-point of the interval $ [ a, b] $,
 +
with the only condition that it be finite.
  
 +
2)  $  m = 2 $,
 +
$  n $
 +
is arbitrary. The two fixed nodes are the end-points of the interval  $  [ a, b] $,
 +
provided they are finite.
  
 +
3)  $  m $
 +
is arbitrary,  $  n = m + 1 $.
 +
The fixed nodes are the roots of a polynomial  $  P _ {m} ( x) $
 +
that is orthogonal on  $  [ a, b] $
 +
with the weight function  $  p ( x) $.
  
====Comments====
+
In cases 1) and 2), the polynomial  $  \omega ( x) $
 +
is orthogonal relative to the weight function  $  \sigma ( x) p ( x) $,
 +
which is of fixed sign on  $  [ a, b] $,
 +
and therefore its roots are real, simple, lie inside  $  ( a, b) $,
 +
and are consequently distinct from  $  a, b $.
 +
The quadrature formula (2) exists, its coefficients are positive and its algebraic accuracy is  $  m + 2n - 1 $.
 +
Quadrature formulas corresponding to the cases 1) and 2) are called Markov formulas.
  
 +
In case 3), the weight function  $  \sigma ( x) p ( x) $
 +
changes sign on  $  [ a, b] $
 +
and this complicates the inspection of the roots of  $  \omega ( x) $.
 +
If  $  [ a, b] = [- 1, 1] $
 +
and  $  p ( x) = ( 1 - x  ^ {2} )  ^  \alpha  $,
 +
where  $  - 1/2 < \alpha \leq  3/2 $,
 +
then the roots of  $  \omega ( x) $
 +
lie inside  $  (- 1, 1) $
 +
and separate the roots of  $  P _ {m} ( x) $:
 +
Between any two consecutive roots of  $  \omega ( x) $
 +
there is exactly one root of  $  P _ {m} ( x) $(
 +
see [[#References|[2]]]). With this weight function, the quadrature formula (2) exists and is exact for all polynomials of degree  $  \leq  3m + 1 $;
 +
however, one cannot state that its algebraic accuracy is  $  3m + 1 $.
 +
For  $  \alpha = - 1/2 $
 +
and  $  \alpha = 1/2 $
 +
the nodes and the coefficients of the quadrature formula can be specified explicitly (see [[#References|[3]]]); the algebraic accuracy in the former case is increased to  $  4m - 1 $,
 +
and in the second case to  $  4m + 1 $.
 +
For  $  p ( x) = 1 $
 +
and the interval  $  [ 0, 1] $,
 +
the nodes and the coefficients have been computed for the quadrature formula (2) (with fixed nodes of type 3)) for  $  m = 1 ( 1) 40 $(
 +
i.e.  $  m $
 +
varying from 1 to 40 with step 1) (see [[#References|[4]]]); the algebraic accuracy is  $  3m + 1 $
 +
if  $  m $
 +
is even and  $  3m + 2 $
 +
if  $  m $
 +
is odd. A quadrature formula (2) with fixed nodes of type 3) also exists for the interval  $  [- 1, 1] $
 +
and the weight function  $  ( 1 - x)  ^  \alpha  ( 1 + x) ^ {- \alpha } $
 +
for  $  \alpha = \pm  1/2 $,
 +
and the nodes and the coefficients can be explicitly specified (see [[#References|[3]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,  P. Rabinowitz,   "Methods of numerical integration" , Acad. Press  (1975)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.I. Krylov, "Approximate calculation of integrals" , Macmillan  (1962)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  G. Szegö, "Ueber gewisse orthogonale Polynome, die zu einer oszillierenden Belegungsfunktion gehören"  ''Math. Ann.'' , '''110''' :  4  (1934)  pp. 501–513</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  I.P Mysovskikh, "A special case of quadrature formulas containing pre-assigned nodes"  ''Izv. Akad. Nauk BelorussSSR. Ser. Fiz.-Tekhn. Navuk'' , '''4'''  (1964)  pp. 125–127  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  A.S. Kronrod, "Nodes and weights of quadrature formulas" , Consultants Bureau  (1965)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,  P. Rabinowitz, "Methods of numerical integration" , Acad. Press  (1975)</TD></TR>
 +
</table>

Latest revision as of 08:05, 9 February 2024


A formula of the type

$$ \tag{1 } \int\limits _ { a } ^ { b } p ( x) f ( x) dx \approx \ \sum _ {j = 1 } ^ { N } C _ {j} f ( x _ {j} ), $$

where the weight function $ p ( x) $ is assumed to be non-negative on $ [ a, b] $, where the integrals

$$ \mu _ {k} = \ \int\limits _ { a } ^ { b } p ( x) x ^ {k} dx,\ \ k = 0, 1 \dots $$

exist and where, moreover, $ \mu _ {0} > 0 $. The nodes $ x _ {j} $ of formula (1) are the roots of a polynomial of degree $ N $ orthogonal on $ [ a, b] $ with the weight function $ p ( x) $, and the weights are defined by the condition that (1) be an interpolatory formula. A quadrature formula of this type has algebraic accuracy $ 2N - 1 $, i.e. it is exact for all algebraic polynomials $ f ( x) $ of degree $ \leq 2N - 1 $ and is not exact for $ x ^ {2N} $; it is known as a quadrature formula of Gaussian type.

This concept can be generalized as follows. Consider the quadrature formula

$$ \tag{2 } \int\limits _ { a } ^ { b } p ( x) f ( x) dx \approx \ \sum _ {j = 1 } ^ { m } A _ {j} f ( a _ {j} ) + \sum _ {j = 1 } ^ { n } C _ {j} f ( x _ {j} ) $$

with $ N = m + n $ nodes, where the nodes $ a _ {1} \dots a _ {m} $ are pre-assigned (fixed) while $ x _ {1} \dots x _ {n} $ are so chosen that (2) be a quadrature formula of highest algebraic accuracy. Let

$$ \sigma ( x) = \ \prod _ {j = 1 } ^ { m } ( x - a _ {j} ),\ \ \omega ( x) = \ \prod _ {j = 1 } ^ { n } ( x - x _ {j} ). $$

Formula (2) is exact for all polynomials of degree $ \leq m + 2n - 1 $ if and only if it is an interpolatory quadrature formula and the polynomial $ \omega ( x) $ is orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $ to all polynomials of degree $ \leq n - 1 $. This reduces the question of the existence of a quadrature formula that is exact for all polynomials of degree $ \leq 2n - 1 $ to the problem of determining a polynomial $ \omega ( x) $ of degree $ n $ that is orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $, and to examining the properties of its roots. If the roots of $ \omega ( x) $ are real, simple, lie in $ [ a, b] $, and none of them is one of the fixed nodes, the required quadrature formula exists. If, moreover,

$$ \int\limits _ { a } ^ { b } p ( x) \sigma ( x) \omega ^ {2} ( x) dx \neq 0, $$

then the algebraic accuracy of the formula is $ m + 2n - 1 $.

Under the above assumptions concerning the weight function $ p ( x) $, a polynomial $ \omega ( x) $ of degree $ n $, orthogonal on $ [ a, b] $ with the weight function $ \sigma ( x) p ( x) $, is defined uniquely (up to a non-zero constant factor) in the following special cases.

1) $ m = 1 $, $ n $ is arbitrary. The single fixed node is an end-point of the interval $ [ a, b] $, with the only condition that it be finite.

2) $ m = 2 $, $ n $ is arbitrary. The two fixed nodes are the end-points of the interval $ [ a, b] $, provided they are finite.

3) $ m $ is arbitrary, $ n = m + 1 $. The fixed nodes are the roots of a polynomial $ P _ {m} ( x) $ that is orthogonal on $ [ a, b] $ with the weight function $ p ( x) $.

In cases 1) and 2), the polynomial $ \omega ( x) $ is orthogonal relative to the weight function $ \sigma ( x) p ( x) $, which is of fixed sign on $ [ a, b] $, and therefore its roots are real, simple, lie inside $ ( a, b) $, and are consequently distinct from $ a, b $. The quadrature formula (2) exists, its coefficients are positive and its algebraic accuracy is $ m + 2n - 1 $. Quadrature formulas corresponding to the cases 1) and 2) are called Markov formulas.

In case 3), the weight function $ \sigma ( x) p ( x) $ changes sign on $ [ a, b] $ and this complicates the inspection of the roots of $ \omega ( x) $. If $ [ a, b] = [- 1, 1] $ and $ p ( x) = ( 1 - x ^ {2} ) ^ \alpha $, where $ - 1/2 < \alpha \leq 3/2 $, then the roots of $ \omega ( x) $ lie inside $ (- 1, 1) $ and separate the roots of $ P _ {m} ( x) $: Between any two consecutive roots of $ \omega ( x) $ there is exactly one root of $ P _ {m} ( x) $( see [2]). With this weight function, the quadrature formula (2) exists and is exact for all polynomials of degree $ \leq 3m + 1 $; however, one cannot state that its algebraic accuracy is $ 3m + 1 $. For $ \alpha = - 1/2 $ and $ \alpha = 1/2 $ the nodes and the coefficients of the quadrature formula can be specified explicitly (see [3]); the algebraic accuracy in the former case is increased to $ 4m - 1 $, and in the second case to $ 4m + 1 $. For $ p ( x) = 1 $ and the interval $ [ 0, 1] $, the nodes and the coefficients have been computed for the quadrature formula (2) (with fixed nodes of type 3)) for $ m = 1 ( 1) 40 $( i.e. $ m $ varying from 1 to 40 with step 1) (see [4]); the algebraic accuracy is $ 3m + 1 $ if $ m $ is even and $ 3m + 2 $ if $ m $ is odd. A quadrature formula (2) with fixed nodes of type 3) also exists for the interval $ [- 1, 1] $ and the weight function $ ( 1 - x) ^ \alpha ( 1 + x) ^ {- \alpha } $ for $ \alpha = \pm 1/2 $, and the nodes and the coefficients can be explicitly specified (see [3]).

References

[1] V.I. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[2] G. Szegö, "Ueber gewisse orthogonale Polynome, die zu einer oszillierenden Belegungsfunktion gehören" Math. Ann. , 110 : 4 (1934) pp. 501–513
[3] I.P Mysovskikh, "A special case of quadrature formulas containing pre-assigned nodes" Izv. Akad. Nauk BelorussSSR. Ser. Fiz.-Tekhn. Navuk , 4 (1964) pp. 125–127 (In Russian)
[4] A.S. Kronrod, "Nodes and weights of quadrature formulas" , Consultants Bureau (1965) (Translated from Russian)
[a1] P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1975)
How to Cite This Entry:
Quadrature formula of highest algebraic accuracy. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Quadrature_formula_of_highest_algebraic_accuracy&oldid=11862
This article was adapted from an original article by I.P. Mysovskikh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article