View source for Adaptive quadrature

It is a common task to compute an approximate value of an [[Integral|integral]], the simplest case being

<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/a/a110/a110310/a1103101.png" /></td> </tr></table>

If the integrand <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103102.png" /> is given by a Fortran-like expression, then one can use symbolic methods, interval-methods or numerical methods. If the integrand <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103103.png" /> is given by function values, only numerical methods of the form

<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/a/a110/a110310/a1103104.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

can be used. A method (a1) is called non-adaptive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103105.png" /> and the knots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103106.png" /> are fixed in advance and do not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103107.png" />. One might hope that it is possible to learn about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103108.png" /> during the computation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a1103109.png" /> in such a way that one can choose the next knot <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031010.png" /> suitably to reduce the error. Therefore, one studies adaptive methods, where the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031011.png" /> depends on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031012.png" /> and the choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031013.png" /> may depend on the already computed function values. In [[Mathematical statistics|mathematical statistics]], adaptive information is known as sequential design and non-adaptive information as non-sequential design.

The use of adaptive algorithms is widespread. Often these methods are based on a way to estimate the error in different subintervals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031014.png" />. One then adds new knots in those intervals where a high error is expected. See [[#References|[a1]]], [[#References|[a2]]], [[#References|[a4]]], [[#References|[a6]]] for detailed information concerning these strategies.

A non-adaptive method provides an immediate decomposition for parallel computation. If adaptive information is superior to non-adaptive information, then an analysis of the trade-off between using adaptive or non-adaptive information on a parallel computer should be carried out.

To prove any bounds for the error <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031015.png" />, one must have some a priori knowledge concerning <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031016.png" />, such as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031017.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031018.png" /> is a class of integrable functions. Without such assumptions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031019.png" />, the error of any method (a1) can be arbitrarily large. Much is known concerning the power of adaption; [[#References|[a5]]] contains known results as well as new results of the authors. See also the survey [[#References|[a3]]]. One can study the worst case as well as the average case and errors for randomized (Monte-Carlo) methods (cf. also [[Monte-Carlo method|Monte-Carlo method]]). It may happen that adaption does not help in the worst-case setting but helps significantly with respect to other settings.

Under certain assumptions, adaptive methods are not better than non-adaptive ones. N.S. Bakhvalov (1971) proved, see [[#References|[a3]]], [[#References|[a5]]], that adaption does not help in the worst-case setting if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110310/a11031020.png" /> is a symmetric and convex set of functions. For some other natural classes adaption helps significantly. In particular, adaption significantly helps for certain classes of functions with singularities. The power of adaption depends critically on a priori knowledge concerning the problem being studied; even a seemingly small change in the assumptions can lead to a different answer.

====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">  A.R. Krommer,   C.W. Ueberhuber,   "Numerical integration on advanced computer systems" , ''Lecture Notes in Computer Science'' , '''848''' , Springer  (1994)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Novak,   "On the power of adaption"  ''J. Complexity'' , '''12'''  (1196)  pp. 199–237</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Piessens,   E. de Doncker-Kapenga,   C.W. Überhuber,   D.K. Kahaner,   "Quadpack" , Springer  (1983)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  J.F. Traub,   G.W. Wasilkowski,   H. Woźniakowski,   "Information-based complexity" , Acad. Press  (1988)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D. Zwillinger,   "Handbook of integration" , Jones and Bartlett  (1992)</TD></TR></table>