A review of error estimation in adaptive quadrature
---
paper_title: Comparison of several adaptive Newton-Cotes quadrature routines in evaluating definite integrals with peaked integrands

paper_content:

This report compares the performance of five different adaptive quadrature schemes, based on Newton-Cotes (2 N + 1) point rules ( N = 1, 2, 3, 4, 5), in approximating the set of definite integrals ∫ 1 -1 ( x 2 + p 2 ) -1 dx with relative accuracy e.
---
paper_title: Practical error estimation in numerical integration

paper_content:

Theoretical error estimates for quadrature rules involve quantities that are usually difficult if not impossible to obtain in practice. Various heuristics to obtain computable error estimates are compared by calculating their performance profiles on the Lyness family of integrands. Two sets of tests are used, corresponding to adaptive and single-rule quadrature. In the single rule case, Gaussian quadrature with error estimate provided by dropping one point from the formula performs best. In the adaptive case, the best heuristic is non-linear extrapolation based on Gaussian quadrature.
---
paper_title: Elementary Numerical Computing with Mathematica

paper_content:

Applications computational errors algorithms error error propagation floating-point computation positional number systems floating-point numbers rounding basic operations numerical instability other difficulties rootfinding roots bisection method Newton's method functional interaction secant method systems of linear equations matrices norms and sensitivity Gaussian elimination accuracy of partial pivoting linear equation solvers large sparse systems LU factorization interpolation Taylor's series big-oh notation existence and uniqueness Lagrange form inverse interpolation least squares approximation the least squares problem orthogonality the normal equations numerical differentiation and integration numerical differentiation simple quadrature rates Gaussian quadrature rules numerical error estimates global adaptive quadrature ordinary differential equators a single ODE Euler's method systems of ODE's Taylor series methods Runge-Kutta methods overview. Appendices: Getting started with Mathematica exact and approximate numerical calculations algebraic calculations lists defining functions procedural programming expressions defining rules how evaluation works delayed evaluation.
---
paper_title: Numerical analysis: an introduction

paper_content:

This is a text in numerical analysis which is taken to mean the branch of mathematics that develops and analyzes computational methods dealing with problems arising in classical analysis, approximations theory, the theory of equations, and ordinary differential equations. The topics in this book are presented with a view towards stressing basic principles and maintaining simplicity and teachability as far as possible. Topics that require a level of technicality that goes beyond the standard of simplicity imposed are referenced in bibliographic notes at the end of each chapter. This book does not cover numerical linear algebra, nor the numerical solution of partial differential equations, as the author takes the view that these are now separate disciplines. It is intended that the student has a good background in calculus and advanced calculus and some knowledge of linear algebra, complex analysis, and differential equations.
---
paper_title: Doubly Adaptive Quadrature Routines based on Newton-Cote Rules

paper_content:

In this paper we test two recently published Matlab codes, adaptsim and adaptlob, using both a Lyness–Kaganove test and a battery type of test. Furthermore we modify these two codes using sequences of null rules in the error estimator with the intention to increase the reliability for both codes. In addition two new Matlab codes applying a locally and a globally adaptive strategy respectively are developed. These two new codes turn out to have very good properties both with respect to reliability and efficiency. Both algorithms are using sequences of null rules in their local error estimators. These error estimators allow us both to test if we are in the region of asymptotic behavior and thus increase reliability and to take advantage of the degree of precision of the basic quadrature rule. The new codes compare favorably to the two recently published adaptive codes both when we use a Lyness–Kaganove testing technique and by using a battery test.
---
paper_title: Error estimation in automatic quadrature routines

paper_content:

A new algorithm for estimating the error in quadrature approximations is presented. Based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. These null rule approximations are then used to produce an estimate of the local error. The algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. In the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.
---
paper_title: Generating numerical algorithms using a computer algebra system

paper_content:

An useful application of computer algebra systems is the generation of algorithms for numerical computations. We have shown in Gander and Gruntz (SIAM Rev., 1999) how computer algebra can be used in teaching to derive numerical methods. In this paper we extend this work, using essentially the capability of computer algebra system to construct and manipulate the interpolating polynomial and to compute a series expansion of a function. We will automatically generate formulas for integration and differentiation with error terms and also generate multistep methods for integrating differential equations.
---
paper_title: Algorithm 868: Globally doubly adaptive quadrature—reliable Matlab codes

paper_content:

We discuss how to modify a recently published Matlab code, coteglob, so that the excellent performance this code demonstrates for low and intermediate accuracy requests is retained while the performance is improved for high accuracy requests. coteglob is a globally adaptive code using a 5 and 9 point pair of Newton-Cotes rules. Combining an extended sequence of rules using 5, 9, 17 and 33 points with a doubly adaptive bisection strategy is the main focus of the paper. We also discuss local versus global adaptivity and conclude that globally adaptive codes are to be preferred. Based on this we develop several new globally adaptive codes that all compare favorably both with coteglob, with Matlab's best currently available quadrature software quadl and the general purpose QUADPACK codes dqk15 and dqk21. We include the results from extensive testing using both a Lyness-Kaganove testing technique and a battery test.
---
paper_title: Algorithm 36 SNIFF: Efficient self-tuning algorithm for numerical integration

paper_content:

A new adaptive algorithm for the integration of analytic functions is presented. The algorithm processes the integration interval by generating local subintervals whose length is controlled through a feedback loop. Control is performed by means of a relation derived on an analytical basis and valid for an arbitrary integration rule: two different estimates of an integral are used to compute the interval length necessary to obtain an integral estimate with accuracy within the assigned error bounds. The implied method for local generation of subintervals and an effective assumption of error partition among subintervals give rise to an adaptive algorithm provided with an accurate and very efficient integration process.
---
paper_title: Doubly Adaptive Quadrature Routines based on Newton-Cote Rules

paper_content:

In this paper we test two recently published Matlab codes, adaptsim and adaptlob, using both a Lyness–Kaganove test and a battery type of test. Furthermore we modify these two codes using sequences of null rules in the error estimator with the intention to increase the reliability for both codes. In addition two new Matlab codes applying a locally and a globally adaptive strategy respectively are developed. These two new codes turn out to have very good properties both with respect to reliability and efficiency. Both algorithms are using sequences of null rules in their local error estimators. These error estimators allow us both to test if we are in the region of asymptotic behavior and thus increase reliability and to take advantage of the degree of precision of the basic quadrature rule. The new codes compare favorably to the two recently published adaptive codes both when we use a Lyness–Kaganove testing technique and by using a battery test.
---
paper_title: Symmetric Integration Rules for Hypercubes III. Construction of Integration Rules Using Null Rules

paper_content:

A new operator, which we term a "Null Rule" is defined. Its properties which are analogous to those of an integration rule are investigated. It is found to be useful in the construction of high-dimensional integration rules of moderate degree. A set of integration rules Wt(+ are derived which are more economical in the number of required function evaluations than the previously published 0(+) 1. Introduction. This part of this paper follows directly from Parts I and II (Lyness (1) and (2)). In Part I we introduced the n-dimensional basic rule (R (n) and the composite rule R('). These rules have hypercubic symmetry, that is, they are invariant under any rotation or reflection of the hypercube into itself. In Part II we defined and discussed the projection and extension of an n-dimensional rule of degree d, to form an n'-dimensional rule (n' 5 n) of degree d' and determined the relation between d and d'. In this part we exploit the formalism of Part II with a view to determining high- dimensional rules of moderate degree. As an intermediate step we define the "Null Rule" and determine some of its properties. We then use it as the basis of a re- cursive procedure. This procedure is used to determine a set of integration rules W+) and several other closely related sets.
---
paper_title: DQAINT: An Algorithm for Adaptive Quadrature Over a Collection of Finite Intervals

paper_content:

In this paper we describe a new one-dimensional general purpose algorithm for adaptive quadrature. This algorithm differs from the well known, and high quality, general purpose code DQAG (QUADPACK) [6] in a number of aspects: ::: ::: 1. ::: ::: Three different basic rules are offered: Gauss, Lobatto or Gauss-Kronrod as integration rules over each local interval, while DQAG offers Gauss-Kronrod rules (with a choice of the number of evaluation points). This choice of rules is based on the experience, [1], that Gauss rules are at least as effective as Gauss-Kronrod rules in this kind of software and that closed rules (Lobatto) are better for discontinuous problems. ::: ::: ::: ::: ::: 2. ::: ::: The local error estimation is based on a procedure developed in [1], and this procedure is principally the same for all three basic rules. A key element in this error estimation procedure is the null rules, first introduced in [5]. A rule is a null rule, N[f], iff it has at least one nonzero weight and the sum of the weights are zero A null rule is furthermore said to have degree d if it integrates to zero all polynomials of degree < d and fails to do so with f(x) = x d+1. The basic rule has degree of precision at least n while the null rules have degree of precision at most n - 1. In the code we use symmetric rules and a sequence of null rules of decreasing degrees n -1, n -2, …, which are either symmetric or anti-symmetric. We have chosen n = 20 and used a sequence of 8 (this number is based on heuristics) null rules of degrees 19, 18, …, 12. The null rules are combined into pairs to give 4 independent error estimates in order to create a reliable final local error estimate. Tests in [1] show that this error estimate is as reliable as the one implemented in QAG. The fact that the lowest degree null rule is as high as 12 (in [1] 8 symmetric null rules were used: lowest degree 5) makes the code more economic in regions where the function is smooth, without ruining the reliability. ::: ::: ::: ::: ::: 3. ::: ::: As the subdivision strategy a non-uniform 3-division has been implemented based on ideas and experience reported in [4]. In this procedure one attempts to focus on the difficulty in order to reduce the effort in the adaptive algorithm. Tests of the new code confirm the results reported in [4] that this technique does reduce the number of function evaluations when adaptability is important. ::: ::: ::: ::: ::: 4. ::: ::: The initial integration problem may consist of a collection of intervals. This way we allow the user to give information to the code about good subdivision points, but are still treating this as one quadrature problem. Thus the user gives only one error request for the whole problem. ::: ::: ::: ::: ::: 5. ::: ::: Simultaneous integration of the elements in a vector function is also allowed. This idea is not new (e. g. it has been implemented in [2, 3]) however no one-dimensional code has, to the author’s knowledge, such an option. We found it necessary to include some modifications of the global strategy because of this feature. This option should be used with care since simultaneous integration of several functions, with different behavior in the integration region, may increase the overall computation time. However, in many problems there may be a substantial gain in simultaneous integration. ::: ::: ::: ::: ::: 6. ::: ::: Finally, the code is designed to take advantage of shared memory parallel computers.
---
paper_title: PIECEWISE SMOOTH CHEBFUNS

paper_content:

Algorithms are described that make it possible to manipulate piecewise-smooth functions on real intervals numerically with close to machine precision. Break points are introduced in some such calculations at points determined by numerical root finding and in others by recursive subdivision or automatic edge detection. Functions are represented on each smooth subinterval by Chebyshev series or interpolants. The algorithms are implemented in object-oriented Matlab in an extension of the chebfun system, which was previously limited to smooth functions on [―1, 1].
---
paper_title: A method for numerical integration on an automatic computer

paper_content:

A new method for the numerical integration of a "well-behaved" function over a finite range of argument is described. It consists essentially of expanding the integrand in a series of Chebyshev polynomials, and integrating this series term by term. Illustrative examples are given, and the method is compared with the most commonly-used alternatives, namelySimpson's rule and the method ofGauss.
---
paper_title: Error estimation in automatic quadrature routines

paper_content:

A new algorithm for estimating the error in quadrature approximations is presented. Based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. These null rule approximations are then used to produce an estimate of the local error. The algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. In the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.
---
paper_title: Algorithm 868: Globally doubly adaptive quadrature—reliable Matlab codes

paper_content:

We discuss how to modify a recently published Matlab code, coteglob, so that the excellent performance this code demonstrates for low and intermediate accuracy requests is retained while the performance is improved for high accuracy requests. coteglob is a globally adaptive code using a 5 and 9 point pair of Newton-Cotes rules. Combining an extended sequence of rules using 5, 9, 17 and 33 points with a doubly adaptive bisection strategy is the main focus of the paper. We also discuss local versus global adaptivity and conclude that globally adaptive codes are to be preferred. Based on this we develop several new globally adaptive codes that all compare favorably both with coteglob, with Matlab's best currently available quadrature software quadl and the general purpose QUADPACK codes dqk15 and dqk21. We include the results from extensive testing using both a Lyness-Kaganove testing technique and a battery test.
---
paper_title: Interpolatory integration formulas for optimal composition

paper_content:

A set of symmetric, closed, interpolatory integration formulas on the interval [-1, 1] with positive weights and increasing degree of precision is introduced. These formulas, called recursive monotone stable (RMS) formulas, allow applying higher order or compound rules without wasting previously computed functional values. An exhaustive search shows the existence of 27 families of RMS formulas, stemming from the simple trapezoidal rule.
---
paper_title: On the use of Gauss quadrature in adaptive automatic integration schemes

paper_content:

The use of Kronrod's scheme for automatic adaptive integration is well known. In this paper we introduce Gauss integration rules combined with a new way of estimating the errors as basic rules in automatic adaptive integration schemes. On the basis of very limited numerical experiments it seems that our scheme may be as efficient and reliable as the Kronrod scheme.
---
paper_title: A Doubly Adaptive Integration Algorithm Using Stratified Rules

paper_content:

A doubly adaptive integration algorithm chooses between a higher order rule applied on the current subinterval or the subdivision of the interval. We describe one such algorithm using a stratified sequence of integration rules. We present a criterion to select the suitable strategy, depending on the type of integrand, using available information.
---
paper_title: An extended doubly-adaptive quadrature method based on the combination of the Ninomiya and the FLR schemes

paper_content:

An improvement is made to an automatic quadrature due to Ninomiya (J. Inf. Process. 3:162–170, 1980) of adaptive type based on the Newton–Cotes rule by incorporating a doubly-adaptive algorithm due to Favati, Lotti and Romani (ACM Trans. Math. Softw. 17:207–217, 1991; ACM Trans. Math. Softw. 17:218–232, 1991). We compare the present method in performance with some others by using various test problems including Kahaner’s ones (Computation of numerical quadrature formulas. In: Rice, J.R. (ed.) Mathematical Software, 229–259. Academic, Orlando, FL, 1971).
---
paper_title: Local error estimates in quadrature

paper_content:

A theoretical error estimate for quadrature formulas, which depends on four approximations of the integral, is derived. We obtain a bound, often sharper than the trivial one, which requires milder conditions to be satisfied than a similar result previously presented by Laurie. A selection of numerical tests with one-dimensional integrals is reported, to show how the error estimate works in practice.
---
paper_title: Vectorized adaptive quadrature in MATLAB

paper_content:

Adaptive quadrature codes process a collection of subintervals one at a time. We show how to process them all simultaneously and so exploit vectorization and the use of fast built-in functions and array operations that are so important to efficient computation in MATLAB. Using algebraic transformations we have made it just as easy for users to solve problems on infinite intervals and with moderate end point singularities as problems with finite intervals and smooth integrands. Piecewise-smooth integrands are handled effectively with breakpoints.
---
paper_title: Quadpack: A Subroutine Package for Automatic Integration

paper_content:

I. Introduction.- II. Theoretical Background.- 2.1. Automatic integration with QUADPACK.- 2.2. Integration methods.- 2.2.1. Quadrature sum.- 2.2.2. Construction of Gauss-type rules with preassigned abscissae.- 2.2.3. Modified Clenshaw-Curtis integration.- 2.2.4. Numerical quadrature and extrapolation.- III. Algorithm Descriptions.- 3.1. QUADPACK contents.- 3.2. Prototype of algorithm description.- 3.3. Algorithm schemes.- 3.4. Heuristics used in the algorithms.- IV. Guidelines for the use of Quadpack.- 4.1. General remarks.- 4.2. Decision tree for finite-range integration.- 4.3. Decision tree for infinite-range integration.- 4.4. Numerical examples.- 4.5. Sample programs illustrating the use of the QUADPACK integrators.- V. Special Applications of Quadpack.- 5.1. Two-dimensional integration.- 5.2. Hankel transform.- 5.3. Numerical inversion of the Laplace transform.- VI. Implementation Notes and Routine Listings.- 6.1. Implementation notes.- 6.2. Routine listings.- QNG.- QAG.- QAGE.- GAGS.- QAGP.- QAGI.- QAWO.- QAWF.- QAWFE.- QAWS.- QAWSE.- QAWC.- QAWCE.- QFOUR.- QK15.- QK21.- QK31.- QK41.- QK51.- QK61.- QK15I.- QK15W.- QEXT.- QSORT.- QC250.- QC25S.- QC25C.- QMOMO.- QCHEB.- QWGTO.- QWGTS.- QWGTC 29.- QMACO.- References.
---
paper_title: Interpolatory integration formulas for optimal composition

paper_content:

A set of symmetric, closed, interpolatory integration formulas on the interval [-1, 1] with positive weights and increasing degree of precision is introduced. These formulas, called recursive monotone stable (RMS) formulas, allow applying higher order or compound rules without wasting previously computed functional values. An exhaustive search shows the existence of 27 families of RMS formulas, stemming from the simple trapezoidal rule.
---
paper_title: Doubly Adaptive Quadrature Routines based on Newton-Cote Rules

paper_content:

In this paper we test two recently published Matlab codes, adaptsim and adaptlob, using both a Lyness–Kaganove test and a battery type of test. Furthermore we modify these two codes using sequences of null rules in the error estimator with the intention to increase the reliability for both codes. In addition two new Matlab codes applying a locally and a globally adaptive strategy respectively are developed. These two new codes turn out to have very good properties both with respect to reliability and efficiency. Both algorithms are using sequences of null rules in their local error estimators. These error estimators allow us both to test if we are in the region of asymptotic behavior and thus increase reliability and to take advantage of the degree of precision of the basic quadrature rule. The new codes compare favorably to the two recently published adaptive codes both when we use a Lyness–Kaganove testing technique and by using a battery test.
---
paper_title: On the use of Gauss quadrature in adaptive automatic integration schemes

paper_content:

The use of Kronrod's scheme for automatic adaptive integration is well known. In this paper we introduce Gauss integration rules combined with a new way of estimating the errors as basic rules in automatic adaptive integration schemes. On the basis of very limited numerical experiments it seems that our scheme may be as efficient and reliable as the Kronrod scheme.
---
paper_title: Algorithm 36 SNIFF: Efficient self-tuning algorithm for numerical integration

paper_content:

A new adaptive algorithm for the integration of analytic functions is presented. The algorithm processes the integration interval by generating local subintervals whose length is controlled through a feedback loop. Control is performed by means of a relation derived on an analytical basis and valid for an arbitrary integration rule: two different estimates of an integral are used to compute the interval length necessary to obtain an integral estimate with accuracy within the assigned error bounds. The implied method for local generation of subintervals and an effective assumption of error partition among subintervals give rise to an adaptive algorithm provided with an accurate and very efficient integration process.
---
paper_title: DQAINT: An Algorithm for Adaptive Quadrature Over a Collection of Finite Intervals

paper_content:

In this paper we describe a new one-dimensional general purpose algorithm for adaptive quadrature. This algorithm differs from the well known, and high quality, general purpose code DQAG (QUADPACK) [6] in a number of aspects: ::: ::: 1. ::: ::: Three different basic rules are offered: Gauss, Lobatto or Gauss-Kronrod as integration rules over each local interval, while DQAG offers Gauss-Kronrod rules (with a choice of the number of evaluation points). This choice of rules is based on the experience, [1], that Gauss rules are at least as effective as Gauss-Kronrod rules in this kind of software and that closed rules (Lobatto) are better for discontinuous problems. ::: ::: ::: ::: ::: 2. ::: ::: The local error estimation is based on a procedure developed in [1], and this procedure is principally the same for all three basic rules. A key element in this error estimation procedure is the null rules, first introduced in [5]. A rule is a null rule, N[f], iff it has at least one nonzero weight and the sum of the weights are zero A null rule is furthermore said to have degree d if it integrates to zero all polynomials of degree < d and fails to do so with f(x) = x d+1. The basic rule has degree of precision at least n while the null rules have degree of precision at most n - 1. In the code we use symmetric rules and a sequence of null rules of decreasing degrees n -1, n -2, …, which are either symmetric or anti-symmetric. We have chosen n = 20 and used a sequence of 8 (this number is based on heuristics) null rules of degrees 19, 18, …, 12. The null rules are combined into pairs to give 4 independent error estimates in order to create a reliable final local error estimate. Tests in [1] show that this error estimate is as reliable as the one implemented in QAG. The fact that the lowest degree null rule is as high as 12 (in [1] 8 symmetric null rules were used: lowest degree 5) makes the code more economic in regions where the function is smooth, without ruining the reliability. ::: ::: ::: ::: ::: 3. ::: ::: As the subdivision strategy a non-uniform 3-division has been implemented based on ideas and experience reported in [4]. In this procedure one attempts to focus on the difficulty in order to reduce the effort in the adaptive algorithm. Tests of the new code confirm the results reported in [4] that this technique does reduce the number of function evaluations when adaptability is important. ::: ::: ::: ::: ::: 4. ::: ::: The initial integration problem may consist of a collection of intervals. This way we allow the user to give information to the code about good subdivision points, but are still treating this as one quadrature problem. Thus the user gives only one error request for the whole problem. ::: ::: ::: ::: ::: 5. ::: ::: Simultaneous integration of the elements in a vector function is also allowed. This idea is not new (e. g. it has been implemented in [2, 3]) however no one-dimensional code has, to the author’s knowledge, such an option. We found it necessary to include some modifications of the global strategy because of this feature. This option should be used with care since simultaneous integration of several functions, with different behavior in the integration region, may increase the overall computation time. However, in many problems there may be a substantial gain in simultaneous integration. ::: ::: ::: ::: ::: 6. ::: ::: Finally, the code is designed to take advantage of shared memory parallel computers.
---
paper_title: Practical error estimation in numerical integration

paper_content:

Theoretical error estimates for quadrature rules involve quantities that are usually difficult if not impossible to obtain in practice. Various heuristics to obtain computable error estimates are compared by calculating their performance profiles on the Lyness family of integrands. Two sets of tests are used, corresponding to adaptive and single-rule quadrature. In the single rule case, Gaussian quadrature with error estimate provided by dropping one point from the formula performs best. In the adaptive case, the best heuristic is non-linear extrapolation based on Gaussian quadrature.
---
paper_title: An extended doubly-adaptive quadrature method based on the combination of the Ninomiya and the FLR schemes

paper_content:

An improvement is made to an automatic quadrature due to Ninomiya (J. Inf. Process. 3:162–170, 1980) of adaptive type based on the Newton–Cotes rule by incorporating a doubly-adaptive algorithm due to Favati, Lotti and Romani (ACM Trans. Math. Softw. 17:207–217, 1991; ACM Trans. Math. Softw. 17:218–232, 1991). We compare the present method in performance with some others by using various test problems including Kahaner’s ones (Computation of numerical quadrature formulas. In: Rice, J.R. (ed.) Mathematical Software, 229–259. Academic, Orlando, FL, 1971).
---
paper_title: Error estimation in automatic quadrature routines

paper_content:

A new algorithm for estimating the error in quadrature approximations is presented. Based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. These null rule approximations are then used to produce an estimate of the local error. The algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. In the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.
---
paper_title: Algorithm 868: Globally doubly adaptive quadrature—reliable Matlab codes

paper_content:

We discuss how to modify a recently published Matlab code, coteglob, so that the excellent performance this code demonstrates for low and intermediate accuracy requests is retained while the performance is improved for high accuracy requests. coteglob is a globally adaptive code using a 5 and 9 point pair of Newton-Cotes rules. Combining an extended sequence of rules using 5, 9, 17 and 33 points with a doubly adaptive bisection strategy is the main focus of the paper. We also discuss local versus global adaptivity and conclude that globally adaptive codes are to be preferred. Based on this we develop several new globally adaptive codes that all compare favorably both with coteglob, with Matlab's best currently available quadrature software quadl and the general purpose QUADPACK codes dqk15 and dqk21. We include the results from extensive testing using both a Lyness-Kaganove testing technique and a battery test.
---
paper_title: Quadpack: A Subroutine Package for Automatic Integration

paper_content:

I. Introduction.- II. Theoretical Background.- 2.1. Automatic integration with QUADPACK.- 2.2. Integration methods.- 2.2.1. Quadrature sum.- 2.2.2. Construction of Gauss-type rules with preassigned abscissae.- 2.2.3. Modified Clenshaw-Curtis integration.- 2.2.4. Numerical quadrature and extrapolation.- III. Algorithm Descriptions.- 3.1. QUADPACK contents.- 3.2. Prototype of algorithm description.- 3.3. Algorithm schemes.- 3.4. Heuristics used in the algorithms.- IV. Guidelines for the use of Quadpack.- 4.1. General remarks.- 4.2. Decision tree for finite-range integration.- 4.3. Decision tree for infinite-range integration.- 4.4. Numerical examples.- 4.5. Sample programs illustrating the use of the QUADPACK integrators.- V. Special Applications of Quadpack.- 5.1. Two-dimensional integration.- 5.2. Hankel transform.- 5.3. Numerical inversion of the Laplace transform.- VI. Implementation Notes and Routine Listings.- 6.1. Implementation notes.- 6.2. Routine listings.- QNG.- QAG.- QAGE.- GAGS.- QAGP.- QAGI.- QAWO.- QAWF.- QAWFE.- QAWS.- QAWSE.- QAWC.- QAWCE.- QFOUR.- QK15.- QK21.- QK31.- QK41.- QK51.- QK61.- QK15I.- QK15W.- QEXT.- QSORT.- QC250.- QC25S.- QC25C.- QMOMO.- QCHEB.- QWGTO.- QWGTS.- QWGTC 29.- QMACO.- References.
---
paper_title: CADRE: AN ALGORITHM FOR NUMERICAL QUADRATURE

paper_content:

Publisher Summary This chapter discusses the program CADRE—an algorithm for numerical quadrature. The program employs an adaptive scheme whereby CADRE is found as the sum of estimates for the integral of F ( x ) over suitably small subintervals of a given interval of integration. Starting with the interval of integration itself as the first such subinterval, the program attempts to find an acceptable estimate on a given subinterval by cautious Romberg extrapolation. If this attempt fails, the subinterval is divided into two subintervals of equal length. For the sake of economy, values of F ( x ), once calculated, are saved until they are successfully used in estimating the integral over some subinterval to which they belong. The program CADRE uses the composite trapezoid sum. For certain classes of integrands, the composite trapezoid sum exhibits a known and characteristic convergence behavior that the algorithm attempts to detect and to exploit through cautious extrapolation.
---
paper_title: A Doubly Adaptive Integration Algorithm Using Stratified Rules

paper_content:

A doubly adaptive integration algorithm chooses between a higher order rule applied on the current subinterval or the subdivision of the interval. We describe one such algorithm using a stratified sequence of integration rules. We present a criterion to select the suitable strategy, depending on the type of integrand, using available information.
---
paper_title: STRATIFIED SEQUENCES OF NESTED QUADRATURE FORMULAS

paper_content:

Abstract Adaptive quadrature algorithms have the property that their behaviour is tailored to the integrand. Such algorithms may be adaptive in two ways. Order adaptive: A nested sequence of quadrature rules, each more accurate than its predecessor, is applied. Examples of this approach are the methods of Romberg, Clenshaw and Curtis, and Patterson. Partition adaptive: A fixed quadrature rule is compounded by applying it on each subinterval of some partition of the quadrature interval. The partition is gradually built up by subdividing at each stage one of the current subintervals. Most of the QUADPACK algorithms are of this type. A quadrature algorithm that is adaptive in both ways is called doubly adaptive: At each stage, the selected subinterval is either subdivided, or a higher order quadrature rule is applied to it. Practical problems arise when a Patterson nested sequence is applied in a fully adaptive algorithm, because all quadrature points are reweighted, thus requiring storage of old function va...
---
paper_title: Exit criteria for Simpson’s compound rule

paper_content:

In many automated numerical algorithms, the calculations are stopped when the difference between two successive approximations is less than a preassigned tolerance. The dependability of this procedure for Simpson's compound rule has been investigated. Classes of functions have been determined for which the above criterion is (a) always valid, and (b) asymptotically valid. A new exit rule is proposed which appears to be less conservative than the standard technique.
---
paper_title: Local error estimates in quadrature

paper_content:

A theoretical error estimate for quadrature formulas, which depends on four approximations of the integral, is derived. We obtain a bound, often sharper than the trivial one, which requires milder conditions to be satisfied than a similar result previously presented by Laurie. A selection of numerical tests with one-dimensional integrals is reported, to show how the error estimate works in practice.
---
paper_title: Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants

paper_content:

We present two new adaptive quadrature routines. Both routines differ from previously published algorithms in many aspects, most significantly in how they represent the integrand, how they treat nonnumerical values of the integrand, how they deal with improper divergent integrals, and how they estimate the integration error. The main focus of these improvements is to increase the reliability of the algorithms without significantly impacting their efficiency. Both algorithms are implemented in MATLAB and tested using both the “families” suggested by Lyness and Kaganove and the battery test used by Gander and Gautschi and Kahaner. They are shown to be more reliable, albeit in some cases less efficient, than other commonly-used adaptive integrators.
---
paper_title: Numerical analysis: an introduction

paper_content:

This is a text in numerical analysis which is taken to mean the branch of mathematics that develops and analyzes computational methods dealing with problems arising in classical analysis, approximations theory, the theory of equations, and ordinary differential equations. The topics in this book are presented with a view towards stressing basic principles and maintaining simplicity and teachability as far as possible. Topics that require a level of technicality that goes beyond the standard of simplicity imposed are referenced in bibliographic notes at the end of each chapter. This book does not cover numerical linear algebra, nor the numerical solution of partial differential equations, as the author takes the view that these are now separate disciplines. It is intended that the student has a good background in calculus and advanced calculus and some knowledge of linear algebra, complex analysis, and differential equations.
---
paper_title: Solution of Vandermonde Systems of Equations

paper_content:

We obtain in this paper a considerable improvement over a method developed earlier by Ballester and Pereyra for the solution of systems of linear equations with Vandermonde matrices of coefficients. This is achieved by observing that a part of the earlier algorithm is equivalent to Newton's interpolation method. This allows also to produce a progressive algorithm which is significantly more efficient than previous available methods. Algol-60 programs and numerical results are included. Confluent Vandermonde systems are also briefly discussed.
---
paper_title: Efficient Construction, Update and Downdate Of The Coefficients Of Interpolants Based On Polynomials Satisfying A Three-Term Recurrence Relation

paper_content:

In this paper, we consider methods to compute the coefficients of interpolants relative to a basis of polynomials satisfying a three-term recurrence relation. Two new algorithms are presented: the first constructs the coefficients of the interpolation incrementally and can be used to update the coefficients whenever a nodes is added to or removed from the interpolation. The second algorithm, which constructs the interpolation coefficients by decomposing the Vandermonde-like matrix iteratively, can not be used to update or downdate an interpolation, yet is more numerically stable than the first algorithm and is more efficient when the coefficients of multiple interpolations are to be computed over the same set of nodes.
---
paper_title: Norm estimates for inverses of Vandermonde matrices

paper_content:

Formulas, or close two-sided estimates, are given for the norm of the inverse of a Vandermonde matrix when the constituent parameters are arranged in certain symmetric configurations in the complex plane. The effect of scaling the parameters is also investigated. Asymptotic estimates of the respective condition numbers are derived in special cases.
---
paper_title: Interpolatory integration formulas for optimal composition

paper_content:

A set of symmetric, closed, interpolatory integration formulas on the interval [-1, 1] with positive weights and increasing degree of precision is introduced. These formulas, called recursive monotone stable (RMS) formulas, allow applying higher order or compound rules without wasting previously computed functional values. An exhaustive search shows the existence of 27 families of RMS formulas, stemming from the simple trapezoidal rule.
---
paper_title: Comparison of several adaptive Newton-Cotes quadrature routines in evaluating definite integrals with peaked integrands

paper_content:

This report compares the performance of five different adaptive quadrature schemes, based on Newton-Cotes (2 N + 1) point rules ( N = 1, 2, 3, 4, 5), in approximating the set of definite integrals ∫ 1 -1 ( x 2 + p 2 ) -1 dx with relative accuracy e.
---
paper_title: Practical error estimation in numerical integration

paper_content:

Theoretical error estimates for quadrature rules involve quantities that are usually difficult if not impossible to obtain in practice. Various heuristics to obtain computable error estimates are compared by calculating their performance profiles on the Lyness family of integrands. Two sets of tests are used, corresponding to adaptive and single-rule quadrature. In the single rule case, Gaussian quadrature with error estimate provided by dropping one point from the formula performs best. In the adaptive case, the best heuristic is non-linear extrapolation based on Gaussian quadrature.
---
paper_title: Symmetric Integration Rules for Hypercubes III. Construction of Integration Rules Using Null Rules

paper_content:

A new operator, which we term a "Null Rule" is defined. Its properties which are analogous to those of an integration rule are investigated. It is found to be useful in the construction of high-dimensional integration rules of moderate degree. A set of integration rules Wt(+ are derived which are more economical in the number of required function evaluations than the previously published 0(+) 1. Introduction. This part of this paper follows directly from Parts I and II (Lyness (1) and (2)). In Part I we introduced the n-dimensional basic rule (R (n) and the composite rule R('). These rules have hypercubic symmetry, that is, they are invariant under any rotation or reflection of the hypercube into itself. In Part II we defined and discussed the projection and extension of an n-dimensional rule of degree d, to form an n'-dimensional rule (n' 5 n) of degree d' and determined the relation between d and d'. In this part we exploit the formalism of Part II with a view to determining high- dimensional rules of moderate degree. As an intermediate step we define the "Null Rule" and determine some of its properties. We then use it as the basis of a re- cursive procedure. This procedure is used to determine a set of integration rules W+) and several other closely related sets.
---
paper_title: Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants

paper_content:

We present two new adaptive quadrature routines. Both routines differ from previously published algorithms in many aspects, most significantly in how they represent the integrand, how they treat nonnumerical values of the integrand, how they deal with improper divergent integrals, and how they estimate the integration error. The main focus of these improvements is to increase the reliability of the algorithms without significantly impacting their efficiency. Both algorithms are implemented in MATLAB and tested using both the “families” suggested by Lyness and Kaganove and the battery test used by Gander and Gautschi and Kahaner. They are shown to be more reliable, albeit in some cases less efficient, than other commonly-used adaptive integrators.
---

Title: A Review of Error Estimation in Adaptive Quadrature

Section 1: INTRODUCTION
Description 1: This section should introduce the concept of adaptive quadrature, provide a historical context, outline the general approach of adaptive quadrature routines, detail the importance of error estimation, and present the objectives and structure of the review.

Section 2: LINEAR ERROR ESTIMATORS
Description 2: This section should explore various linear error estimators, define linear error estimation, discuss early linear error estimators, and detail significant examples such as Richardson extrapolation and methods based on equal degree rules.

Section 3: Finite Difference-Based Error Estimators
Description 3: This section should provide details on error estimators that use finite difference methods to estimate integration errors and discuss relevant algorithms and their historical context.

Section 4: Coefficient-Based Error Estimators
Description 4: This section should describe error estimators based on the coefficients of polynomial approximations of the integrand, including methods based on Chebyshev and Legendre polynomial coefficients.

Section 5: Gauss-Kronrod-Based Error Estimators
Description 5: This section should detail error estimators that utilize Gauss-Kronrod quadrature rules, explain their mechanisms, and provide examples and historical developments.

Section 6: Summary
Description 6: This section should summarize the different types of linear error estimators discussed, categorize them, and highlight their similarities and differences.

Section 7: NONLINEAR ERROR ESTIMATORS
Description 7: This section should introduce nonlinear error estimators, explain their principles, and discuss specific methods such as CADRE, modified exit procedures, and adaptive extrapolation algorithms.

Section 8: A NEW ERROR ESTIMATOR
Description 8: This section should present a new error estimator developed by the author, explaining its construction, theoretical foundation, and distinguishing features compared to other estimators.

Section 9: COMPARISON
Description 9: This section should compare the performance of different error estimation techniques, describe the methodology of tests, and present the results including the effectiveness and reliability of each estimator.

Section 10: CONCLUSIONS
Description 10: This section should conclude the review, summarizing the findings, discussing the relative strengths and weaknesses of different error estimation techniques, and suggesting potential future research directions.