Interactive Educational Modules in
Scientific Computing

Adaptive Quadrature

This module demonstrates adaptive quadrature for approximating the integral of a function of one variable over a given interval. Adaptive quadrature is a numerical integration procedure in which the interval of integration is recursively subdivided until an error tolerance is met for the approximate integral on each subinterval. The error estimate for a given subinterval is based on the difference between two different quadrature rules applied on the subinterval. The two quadrature rules used in this module are the midpoint and trapezoid rules. The number of subdivisions required to converge to within a given tolerance depends on the nature of the integrand function. In particular, a region where the integrand function has an abrupt change, sharp peak, cusp, or discontinuity will require many more subdivisions (and hence function evaluations) than a region where the integrand function is well behaved.

The user first selects an integrand function from the menu provided. The sample integrand functions are listed in rough order of difficulty, from easiest to hardest. The successive steps of the adaptive quadrature algorithm are then executed by clicking Next or the highlighted current step. The recursion tree can be traversed in depth-first or breadth-first order, or in any other order the user may choose.

Calculate evaluates the midpoint rule, M, and trapezoid rule, T, for the current subinterval, as well as the magnitude of their difference, and displays the results below the graph of the function. If the two quadrature rules differ by less than the selected tolerance, or if the subinterval width falls below some minimum allowed value, then that subinterval is declared “completed”. The desired convergence tolerance is specified as an order of magnitude. For example, selecting −2 means that the tolerance used is 10−2. The partial sum Q of results over all subintervals completed thus far is displayed, along with the correct value of the integral I for comparison.

During the Select Interval step, the next uncompleted subinterval to be processed, chosen by default in either depth-first (leftmost first) or breadth-first (widest first) order depending on the option selected, is highlighted in green. Any specific subinterval can be selected for processing, however, by clicking on the desired subinterval, which is then highlighted. At any point during the algorithm, or when the algorithm is finished, the user may Reset to start over.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 8.3.6, especially Figure 8.4 and Algorithm 8.1.

Developers: Evan VanderZee and Michael Heath