Namespaces
Variants
Actions

Difference between revisions of "Gauss-Kronrod quadrature formula"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 25 formulas out of 25 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 25 formulas, 25 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
A [[Quadrature formula of highest algebraic accuracy|quadrature formula of highest algebraic accuracy]] of the type
 
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>
+
\begin{equation*} \int _ { a } ^ { b } p ( x ) f ( x ) d x \approx Q _ { 2 n + 1 } ^ { G K } [ f ] = \end{equation*}
  
<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>
+
\begin{equation*} = \sum _ { \nu = 1 } ^ { n } \alpha _ { \nu } f ( x _ { \nu } ) + \sum _ { \mu = 1 } ^ { n + 1 } \beta _ { \mu } f ( \xi _ { \mu } ), \end{equation*}
  
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]]].
+
where $x _ { 1 } , \ldots , x _ { n }$ are fixed, being the nodes of the [[Gauss quadrature formula|Gauss quadrature formula]] $Q _ { n } ^ { G }$, and $p$ is a weight function (see [[Quadrature formula|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|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 [[#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 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|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
+
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
  
<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>
+
\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 <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]]).
+
where $\{ P _ { n } \}$ is the system of [[Orthogonal polynomials|orthogonal polynomials]] with respect to $p$ (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).
+
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 [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]] for surveys. The nodes and weights of Gauss–Kronrod formulas for $p \equiv 1$ 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.
 
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====
 
====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>
+
<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>

Latest revision as of 16:57, 1 July 2020

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)
How to Cite This Entry:
Gauss-Kronrod quadrature formula. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Gauss-Kronrod_quadrature_formula&oldid=50208
This article was adapted from an original article by Sven Ehrich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article