Asymptotic behavior of automatic quadrature (Q1336481)

The authors examine the asymptotic complexity of computing an exact real representation of a definite integral by using an automatic integration routine. The complexity cost used in this analysis is the number \(N\) of function evaluations in real exact arithmetic seen as a function of the number \(E\) of exact decimal digits in the result. In Section 1 (Introduction) an abstract of the work is presented. In Section 2 (Preliminaries) the authors give the main notations, the basic assumptions, the classes of integrands taken into consideration, the number of evaluations and the form for the presentation of quadrature algorithms. In Section 3 (Nonadaptive quadrature schemes) the nonadaptive automatic quadrature for Clenshaw-Curtis formulas, panel rules and double exponential quadrature are considered. In Section 4 (Global adaptive quadrature schemes) the authors study global adaptive quadrature, based on the composition of a fixed rule. They also derive explicit expressions for the constants associated to the asymptotic cost of the panel nonadaptive algorithm and global adaptive algorithm. In Section 5 (Double-adaptive quadrature schemes) a double- adaptive quadrature and triple-adaptive quadrature, which achieve outstanding performances, are introduced. Finally, in Section 6 (Conclusion) the complexity bounds are summarized. In the Appendix some auxiliary results are given.