View source for Gauss-Kronrod quadrature formula

A [[Quadrature formula of highest algebraic accuracy|quadrature formula of highest algebraic accuracy]] 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/g/g120/g120030/g1200301.png" /></td> </tr></table>

<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/g/g120/g120030/g1200302.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200303.png" /> are fixed, being the nodes of the [[Gauss quadrature formula|Gauss quadrature formula]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200304.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200305.png" /> is a weight function (see [[Quadrature formula|Quadrature formula]]). Depending on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200306.png" />, its algebraic accuracy is at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200307.png" />, but may be higher (see [[Quadrature formula of highest algebraic accuracy|Quadrature formula of highest algebraic accuracy]]). For the special case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200308.png" />, which is most important for practical calculations, the algebraic accuracy is precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g1200309.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003010.png" /> is even and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003011.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003012.png" /> is odd [[#References|[a7]]].

The pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003013.png" /> 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|Adaptive quadrature]]). Gauss–Kronrod formulas are implemented in the numerical software package QUADPACK [[#References|[a6]]], and they are presently (1998) the standard method in most numerical libraries.

The nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003014.png" /> of the Gauss–Kronrod formula are the zeros of the Stieltjes polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003015.png" />, which satisfies

<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/g/g120/g120030/g12003016.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003017.png" /> is the system of [[Orthogonal polynomials|orthogonal polynomials]] with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003018.png" /> (cf. also [[Stieltjes polynomials|Stieltjes polynomials]]). An iteration of these ideas leads to a nested sequence of Kronrod–Patterson formulas (cf. [[Kronrod–Patterson quadrature formula|Kronrod–Patterson quadrature formula]]).

For several special cases of weight functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003019.png" />, the Stieltjes polynomials have real roots inside <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003020.png" /> which interlace with the zeros of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003021.png" />. In particular, this is known for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003022.png" />, and in this case also the weights <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003024.png" /> of the Gauss–Kronrod formulas are positive. These facts are not necessarily true in general, see [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]] for surveys. The nodes and weights of Gauss–Kronrod formulas for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g120/g120030/g12003025.png" /> are distributed very regularly (see also [[Stieltjes polynomials|Stieltjes polynomials]] for asymptotic formulas and inequalities).

Error bounds for Gauss–Kronrod formulas have been given in [[#References|[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|Gauss quadrature formula]]) which use the same number of nodes (see [[#References|[a2]]]). Cf. also [[Stopping rule|Stopping rule]] for practical error estimation with the Gauss and other quadrature formulas.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.J. Davis,   P. Rabinowitz,   "Methods of numerical integration" , Acad. Press  (1984)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Ehrich,   "Error bounds for Gauss–Kronrod quadrature formulas"  ''Math. Comput.'' , '''62'''  (1994)  pp. 295–304</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  W. Gautschi,   "Gauss–Kronrod quadrature — a survey"  G.V. Milovanović (ed.) , ''Numer. Meth. and Approx. Th.'' , '''III''' , Nis  (1988)  pp. 39–66</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  G. Monegato,   "Stieltjes polynomials and related quadrature rules"  ''SIAM Review'' , '''24'''  (1982)  pp. 137–158</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R. Piessens,   et al.,   "QUADPACK: a subroutine package in automatic integration" , Springer  (1983)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  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)</TD></TR></table>