Gauss-Kronrod quadrature formula

A quadrature formula of highest algebraic accuracy of the type

\begin{equation*} \int _ { a } ^ { b } p ( x ) f ( x ) d x \approx Q _ { 2 n + 1 } ^ { G K } [ f ] = \end{equation*}

\begin{equation*} = \sum _ { \nu = 1 } ^ { n } \alpha _ { \nu } f ( x _ { \nu } ) + \sum _ { \mu = 1 } ^ { n + 1 } \beta _ { \mu } f ( \xi _ { \mu } ), \end{equation*}

where $x _ { 1 } , \ldots , x _ { n }$ are fixed, being the nodes of the Gauss quadrature formula $Q _ { n } ^ { G }$, and $p$ is a weight function (see Quadrature formula). Depending on $p$, its algebraic accuracy is at least $3 n + 1$, but may be higher (see Quadrature formula of highest algebraic accuracy). For the special case $p \equiv 1$, which is most important for practical calculations, the algebraic accuracy is precisely $3 n + 1$ if $n$ is even and $3 n + 2$ if $n$ is odd [a7].

The pair $( Q _ { n } ^ { G } , Q _ { 2n+1 } ^ { G K } )$ provides an efficient means for the approximate calculation of definite integrals with practical error estimate, and hence for adaptive numerical integration routines (cf. also Adaptive quadrature). Gauss–Kronrod formulas are implemented in the numerical software package QUADPACK [a6], and they are presently (1998) the standard method in most numerical libraries.

The nodes $\xi _ { 1 } , \dots , \xi _ { n + 1}$ of the Gauss–Kronrod formula are the zeros of the Stieltjes polynomial $E _ { n + 1}$, which satisfies

\begin{equation*} \int _ { - 1 } ^ { 1 } p ( x ) P _ { n } ( x ) E _ { n + 1 } ( x ) x ^ { k } d x = 0 , \quad k = 0 , \dots , n, \end{equation*}

where $\{ P _ { n } \}$ is the system of orthogonal polynomials with respect to $p$ (cf. also Stieltjes polynomials). An iteration of these ideas leads to a nested sequence of Kronrod–Patterson formulas (cf. Kronrod–Patterson quadrature formula).

For several special cases of weight functions $p$, the Stieltjes polynomials have real roots inside $[ a , b ]$ which interlace with the zeros of $P_n$. In particular, this is known for $p \equiv 1$, and in this case also the weights $\alpha _ { \nu }$ and $\beta _ { \mu }$ of the Gauss–Kronrod formulas are positive. These facts are not necessarily true in general, see [a3], [a4], [a5] for surveys. The nodes and weights of Gauss–Kronrod formulas for $p \equiv 1$ are distributed very regularly (see also Stieltjes polynomials for asymptotic formulas and inequalities).

Error bounds for Gauss–Kronrod formulas have been given in [a2]. It is known that for smooth (i.e. sufficiently often differentiable) functions, Gauss–Kronrod formulas are significantly inferior to the Gauss quadrature formulas (cf. Gauss quadrature formula) which use the same number of nodes (see [a2]). Cf. also Stopping rule for practical error estimation with the Gauss and other quadrature formulas.

References

[a1]	P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1984) (Edition: Second)
[a2]	S. Ehrich, "Error bounds for Gauss–Kronrod quadrature formulas" Math. Comput. , 62 (1994) pp. 295–304
[a3]	W. Gautschi, "Gauss–Kronrod quadrature — a survey" G.V. Milovanović (ed.) , Numer. Meth. and Approx. Th. , III , Nis (1988) pp. 39–66
[a4]	G. Monegato, "Stieltjes polynomials and related quadrature rules" SIAM Review , 24 (1982) pp. 137–158
[a5]	S.E. Notaris, "An overview of results on the existence and nonexistence and the error term of Gauss–Kronrod quadrature formulas" R.V.M. Zahar (ed.) , Approximation and Computation , Birkhäuser (1995) pp. 485–496
[a6]	R. Piessens, et al., "QUADPACK: a subroutine package in automatic integration" , Springer (1983)
[a7]	P. Rabinowitz, "The exact degree of precision of generalised Gauss–Kronrod integration rules" Math. Comput. , 35 (1980) pp. 1275–1283 (Corrigendum: Math. Comput. 46 (1986), 226)