View source for Stopping rule

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202701.png" /> denote a fixed (continuous) [[Linear functional|linear functional]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202702.png" />. For the numerical approximation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202703.png" /> most often so-called quadrature formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202704.png" /> are used (cf. also [[Quadrature formula|Quadrature formula]]). These are linear functionals of 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/s/s120/s120270/s1202705.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</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/s/s120/s120270/s1202706.png" /></td> </tr></table>

The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202707.png" /> are called the weights of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202708.png" />, while the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s1202709.png" /> are the so-called nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027010.png" />. The remainder term of the quadrature formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027011.png" /> is the linear functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027012.png" /> defined by

<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/s/s120/s120270/s12027013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

In order to stop a procedure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027014.png" />, in practice one has to decide whether <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027015.png" /> is less than a prescribed tolerance or not. Most of the numerical software packages compute exit criteria using functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027016.png" /> of the same type as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027017.png" />, i.e.

<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/s/s120/s120270/s12027018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</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/s/s120/s120270/s12027019.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027021.png" />, and where the second condition in (a3) is given with regard to the computational complexity of the procedure (cf. also [[Algorithm, computational complexity of an|Algorithm, computational complexity of an]]). Of course, one  "hopes"  that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027022.png" /> one has the inequality

<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/s/s120/s120270/s12027023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>

Since the middle of the 1960s, many new and sophisticated algorithms for the numerical approximation of functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027024.png" />, in particular for numerical integration (cf. [[Integration, numerical|Integration, numerical]]), have been developed. See [[#References|[a2]]], [[#References|[a4]]], [[#References|[a11]]], [[#References|[a13]]] and [[#References|[a3]]], [[#References|[a5]]], [[#References|[a9]]]. Most of these automatic algorithms use one or several estimates for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027025.png" /> of the type (a4), which often are obtained by the help of a further quadrature formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027026.png" />:

<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/s/s120/s120270/s12027027.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a5)</td></tr></table>

Here the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027028.png" /> are determined by asymptotic properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027029.png" />, respectively <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027030.png" />, as well as by numerical experience (cf. e.g. [[#References|[a1]]], [[#References|[a7]]], [[#References|[a10]]]). For the latter, different testing techniques are used, see e.g. [[#References|[a4]]], [[#References|[a6]]], [[#References|[a12]]], [[#References|[a13]]]. Naturally, a mathematical proof that such estimates (a4), respectively (a5),  "almost"  hold is not realistic. However, mathematical results describing special classes of functions and special functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027031.png" />, for which such inequalities are valid, may give some hints for practical application.

In particular, let

<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/s/s120/s120270/s12027032.png" /></td> </tr></table>

A functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027033.png" /> of type (a3) is called a Peano stopping functional for the quadrature formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027034.png" /> if (a4) holds for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120270/s12027035.png" />. There are several results for this type of stopping functionals which are based on Peano kernel theory; for a survey see [[#References|[a8]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Berntsen,   T.O. Espelid,   "On the use of Gauss quadrature in adaptive automatic integration schemes"  ''BIT'' , '''24'''  (1989)  pp. 239–242</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Brass,   "Quadraturverfahren" , Vandenhoeck&amp;Ruprecht  (1977)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  "Numerical integration IV"  H. Brass (ed.)  G. Hämmerlin (ed.) , ''ISNM'' , Birkhäuser  (1994)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P.J. Davis,   P. Rabinowitz,   "Methods of numerical integration" , Acad. Press  (1983)  (Edition: Second)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T.O. Espelid,   A. Genz,   "Numerical integration - Recent developments, software and applications" , ''NATO ASI C: Math. Physical Sci.'' , '''357''' , Kluwer Acad. Publ.  (1992)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  P. Favati,   G. Lotti,   F. Romani,   "Testing automatic quadrature programs" , Calcolo  (1992)  pp. 169–193</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  K.-J. Förster,   "Über Monotonie und Fehlerkontrolle bei den Gregoryschen Quadraturverfahren"  ''ZAMM'' , '''67'''  (1987)  pp. 257–266</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  K.-J. Förster,   "A survey of stopping rules in quadrature based on Peano kernel methods"  ''Suppl. Rend. Circ. Mat. Palermo II'' , '''33'''  (1993)  pp. 311–330</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  "Numerical integration - Recent development, software and applications"  P. Keast (ed.)  G. Fairweather (ed.) , Reidel  (1987)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  D.P. Laurie,   "Stratified sequences of nested quadrature formulas"  ''Quaest. Math.'' , '''15'''  (1992)  pp. 365–384</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  J.N. Lyness,   "When not to use an automatic quadrature routine"  ''SIAM Review'' , '''25'''  (1983)  pp. 63–87</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  J.N. Lyness,   J.J. Kaganove,   "A technique for comparing automatic quadrature routines"  ''Comput. J.'' , '''20'''  (1977)  pp. 170–177</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  R. Piessens,   E. deDoncker-Kapenga,   C.W. Überhuber,   D.K. Kahaner,   "QUADPACK: a subroutine package for automatic integration" , ''Ser. Comput. Math.'' , '''1''' , Springer  (1982)</TD></TR></table>