View source for Quadrature formula of highest algebraic accuracy

<!--
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

$$ \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 [[#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====
<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>