A Metalgorithm for Adaptive Quadrature
John R. Rice · Journal of the ACM · 1975
The few adaptive quadrature algorithms that have appeared are significantly superior to traditional numerical integration algorithms The concept of metalgorithm is introduced to provide a framework for the systematic study of the range of interesting adaptive quadrature algorithms A principal result is that there are from i to 10 million potentially interesting and distinct algorithms This is followed by a considerable development of metalgorithm analysis.In partmular, theorems about the convergence properties of various classes of algorithms are established which theoretically show the experimentally observed superiority of these algorithms.Roughly, these theorems state.(a) for "well-behaved" integrands adaptive algorithms are just as efficient and effective as traditional algorithms of a "comparable" nature, (b) adaptive algorithms are equally effective for "badly behaved" integrands where traditional ones are ineffective The final part of the paper introduces the concept of a characteristic length and its role is illustrated in an analyms of three concrete realizations of the metalgorithm, including the algorithms CADRE and SQUANK KEY WORDS AND PHRASES' quadrature, numerical Integration, adaptive quadrature, quadrature convergence, numerical integration convergence, numermal integration programs, quadrature data structures, algorithm classes, algorithm analyms, algorithm components CR CATEGORIES' 3.62, 5.16, 5.29 IntroductwnThe quadrature problem for a given function f(x) is to estimate the value of If = f'0f(x) dx.Traditional quadrature formulas give estimates of the form N Q~f = ~ w~f(xd for some suitably chosen weights w, and abscissas x,.Adaptive quadrature uses some algorithm to choose the abscissas and weights during the computation and thus is to dynamically adapt its estimate to the particular properties of the integrand f(x).A number of adaptive quadrature algorithms have appeared in the literature [2,6,8,9] and there is some basis [3,5] to believe that they are significantly superior to traditional quadrature formulas.As shown later, the few algorithms that have appeared only scratch the surface of the possibilities, and one purpose of this paper is to systematically study the range of interesting adaptive quadrature algorithms.The concept of metalgorithm is introduced for this purpose; the word means a framework or theory to study algorithms.Webster's relevant definition of the prefix "met" is "discipline designed to deal critically with the original one."