Gauss–Kronrod quadrature formula

In numerical mathematics, the Gauss–Kronrod quadrature formula is a method for numerical integration (calculating approximate values of integrals). Gauss–Kronrod quadrature is a variant of Gaussian quadrature, in which the evaluation points are chosen so that an accurate approximation can be computed by re-using the information produced by the computation of a less accurate approximation. It is an example of what is called a nested quadrature rule: for the same set of function evaluation points, it has two quadrature rules, one higher order and one lower order (the latter called an embedded rule). The difference between these two approximations is used to estimate the calculational error of the integration.

These formulas are named after Alexander Kronrod, who invented them in the 1960s, and Carl Friedrich Gauss. Gauss–Kronrod quadrature is used in the QUADPACK library, the GNU Scientific Library, the NAG Numerical Libraries and R.^[1]

Description

The problem in numerical integration is to approximate definite integrals of the form

$\int_a^b f(x)\,dx.$

Such integrals can be approximated, for example, by n-point Gaussian quadrature

$\int_a^b f(x)\,dx \approx \sum_{i=1}^n w_i f(x_i).$

where w_i, x_i are the weights and points at which to evaluate the function f(x).

If the interval [a, b] is subdivided, the Gauss evaluation points of the new subintervals never coincide with the previous evaluation points (except at the midpoint for odd numbers of evaluation points), and thus the integrand must be evaluated at every point. Gauss–Kronrod formulas are extensions of the Gauss quadrature formulas generated by adding $n+1$ points to an $n$-point rule in such a way that the resulting rule is of order $2n+1$ (Laurie (1997, p. 1133); the corresponding Gauss rule is of order $2n-1$). These extra points are the zeros of Stieltjes polynomials. This allows for computing higher-order estimates while reusing the function values of a lower-order estimate. The difference between a Gauss quadrature rule and its Kronrod extension are often used as an estimate of the approximation error.

Example

A popular example combines a 7-point Gauss rule with a 15-point Kronrod rule (Kahaner, Moler & Nash 1989, §5.5). Because the Gauss points are incorporated into the Kronrod points, a total of only 15 function evaluations yields both a quadrature estimate and an error estimate.

(G7,K15) on [−1,1]

Gauss nodes		Weights
±0.94910 79123 42759	∗	0.12948 49661 68870
±0.74153 11855 99394	∗	0.27970 53914 89277
±0.40584 51513 77397	∗	0.38183 00505 05119
0.00000 00000 00000	∗	0.41795 91836 73469
Kronrod nodes		Weights
±0.99145 53711 20813		0.02293 53220 10529
±0.94910 79123 42759	∗	0.06309 20926 29979
±0.86486 44233 59769		0.10479 00103 22250
±0.74153 11855 99394	∗	0.14065 32597 15525
±0.58608 72354 67691		0.16900 47266 39267
±0.40584 51513 77397	∗	0.19035 05780 64785
±0.20778 49550 07898		0.20443 29400 75298
0.00000 00000 00000	∗	0.20948 21410 84728

The recommended error estimate is $(200 |G7 - K15|)^{1.5}$.

Patterson (1968) showed how to find further extensions of this type, Piessens (1974) and Monegato (1978) proposed improved algorithms, and finally the most efficient algorithm was proposed by Laurie (1997). Quadruple precision (34 decimal digits) coefficients for (G7, K15), (G10, K21), (G15,K31), (G20,K41) and others are computed and tabulated^[2]

See also

• Clenshaw–Curtis quadrature, another nested quadrature rule with similar accuracy

Notes

1. http://stat.ethz.ch/R-manual/R-patched/library/stats/html/integrate.html
2. Pavel Holoborodko (2011-11-07). "Gauss-Kronrod Quadrature Nodes and Weights". Retrieved 2016-01-15.

References

• Hazewinkel, Michiel, ed. (2001), "Gauss–Kronrod quadrature formula", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Kahaner, David; Moler, Cleve; Nash, Stephen (1989), Numerical Methods and Software, Prentice–Hall, ISBN 978-0-13-627258-8
• Kronrod, Aleksandr Semenovish (1965), Nodes and weights of quadrature formulas. Sixteen-place tables, New York: Consultants Bureau (Authorized translation from the Russian)
• Piessens, Robert; de Doncker-Kapenga, Elise; Überhuber, C. W.; Kahaner, D. K. (1983), QUADPACK, A subroutine package for automatic integration, Springer-Verlag, ISBN 978-3-540-12553-2 (Reference guide for QUADPACK)
• Patterson, T. N. L. (1968), "The Optimum Addition of Points to Quadrature Formulae", Math. Comput. (American Mathematical Society) 22 (104): 847–856 and C1–C11, doi:10.2307/2004583, JSTOR 2004583. Erratum in Math. Comput. 23: 892.
• Piessens, R; Branders, M (1974), "A Note on the Optimal Addition of Abscissas to Quadrature Formulas of Gauss and Lobatto", Mathematics of Computation, 28(125): 135–139
• Monegato, G (1978), "Some remarks on the construction of extended Gaussian quadrature rules", Mathematics of Computation, 32(141): 247–252
• Laurie, Dirk (1997), "Calculation of Gauss-Kronrod quadrature rules.", Mathematics of Computation of the American Mathematical Society 66 (219): 1133–1145

External links

• QUADPACK (part of SLATEC), source code . QUADPACK is a collection of algorithms, in Fortran, for numerical integration based on Gauss-Kronrod rules. SLATEC (at Netlib) is a large public domain library for numerical computing.
• ALGLIB source code in C#, C++, Delphi & Visual Basic