# Stopping rule

Let $I$ denote a fixed (continuous) linear functional on $C [ a , b ]$. For the numerical approximation of $I$ most often so-called quadrature formulas $Q _ { n }$ are used (cf. also Quadrature formula). These are linear functionals of type

\begin{equation} \tag{a1} Q _ { n } [ f ] = \sum _ { v = 1 } ^ { n } a _ { v , n } f ( x _ { v , n } ), \end{equation} The numbers $a _ { v,n}$ are called the weights of $Q _ { n }$, while the numbers $x _ { v , n }$ are the so-called nodes of $Q _ { n }$. The remainder term of the quadrature formula $Q _ { n }$ is the linear functional $R_n$ defined by

\begin{equation} \tag{a2} R _ { n } = I - Q _ { n } \end{equation}

In order to stop a procedure $( Q _ { n_i } [ f ] ) _ { i = 1,2 , \ldots }$, in practice one has to decide whether $R _ { n } [ f ]$ is less than a prescribed tolerance or not. Most of the numerical software packages compute exit criteria using functionals $S _ { m }$ of the same type as $Q _ { n }$, i.e.

\begin{equation} \tag{a3} S _ { m } [ f ] = \sum _ { v = 1 } ^ { m } b _ { v , m } f ( y_{v , m} ), \end{equation}

\begin{equation*} \{ x _ { 1 , n} , \dots , x _ { n , n} \} \subseteq \{ y _ { 1 , m} , \dots , y _ { m , m} \}, \end{equation*}

where $b _ { v , m } \in \bf R$, $y _ { 1 , m} < \ldots < y _ { m , m }$, 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). Of course, one "hopes" that for $f$ one has the inequality (a4)

Since the middle of the 1960s, many new and sophisticated algorithms for the numerical approximation of functionals $I$, in particular for numerical integration (cf. Integration, numerical), have been developed. See [a2], [a4], [a11], [a13] and [a3], [a5], [a9]. Most of these automatic algorithms use one or several estimates for $R_n$ of the type (a4), which often are obtained by the help of a further quadrature formula $Q_l ^ { B }$:

\begin{equation} \tag{a5} | R - n [ f ] | \leq \gamma | Q _ { l } ^ { B } [ f ] - Q _ { n } [ f ] |. \end{equation}

Here the values of $\gamma$ are determined by asymptotic properties of $R_n$, respectively $R _ { l } ^ { B }$, as well as by numerical experience (cf. e.g. [a1], [a7], [a10]). For the latter, different testing techniques are used, see e.g. [a4], [a6], [a12], [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 $S _ { m }$, for which such inequalities are valid, may give some hints for practical application.

In particular, let

\begin{equation*} A _ { s } ^ { + } = \left\{ \begin{array} { l l } { f : } & { f \in A _ { s } } \\ & { f ^ { ( s ) } \text { has no change of } \operatorname { sign } \operatorname { in } ( a , b ) } \end{array} \right\}. \end{equation*}

A functional $S _ { m }$ of type (a3) is called a Peano stopping functional for the quadrature formula $Q _ { n }$ if (a4) holds for every $f \in A _ { s } ^ { + }$. There are several results for this type of stopping functionals which are based on Peano kernel theory; for a survey see [a8].

How to Cite This Entry:
Stopping rule. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Stopping_rule&oldid=50743
This article was adapted from an original article by K.-J. FÃ¶rster (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article