Gauss-Kronrod quadrature formula
Encyclopedia
In numerical mathematics, the Gauss–Kronrod quadrature formula is a method for numerical integration
(calculating approximate values of integral
s). 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
.
Such integrals can be approximated, for example, by n-point Gaussian quadrature
where wi, xi 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
points to an 
-point rule in such a way that the resulting rule is of order 
. 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.
The recommended error estimate is
.
showed how to find further extensions of this type.
Numerical integration
In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations. This article focuses on calculation of...
(calculating approximate values of integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
s). Gauss–Kronrod quadrature is a variant of Gaussian quadrature
Gaussian quadrature
In numerical analysis, a quadrature rule is an approximation of the definite integral of a function, usually stated as a weighted sum of function values at specified points within the domain of integration....
, 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
Alexander Kronrod
Aleksandr Semenovich Kronrod was a Soviet mathematician and computer scientist, best known for the Gauss-Kronrod quadrature formula which he published in 1964. Earlier his computations informed theoretical physics...
, who invented them in the 1960s, and Carl Friedrich Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
. Gauss–Kronrod quadrature is used in the QUADPACK
QUADPACK
QUADPACK is a FORTRAN 77 library for numerical integration of one-dimensional functions. It was included in the SLATEC Common Mathematical Library and is therefore in the public domain. The individual subprograms are also available on netlib....
library, the GNU Scientific Library
GNU Scientific Library
In computing, the GNU Scientific Library is a software library written in the C programming language for numerical calculations in applied mathematics and science...
, the NAG Numerical Libraries
NAG Numerical Libraries
NAG Numerical Libraries is a software product sold by The Numerical Algorithms Group Ltd . The product is a software library of numerical analysis routines. It comprises a collection of 1500 mathematical and statistical algorithms. Areas covered include linear algebra, optimization, quadrature,...
and R
R (programming language)
R is a programming language and software environment for statistical computing and graphics. The R language is widely used among statisticians for developing statistical software, and R is widely used for statistical software development and data analysis....
.
Description
The problem in numerical integration is to approximate definite integrals of the formSuch integrals can be approximated, for example, by n-point Gaussian quadrature
Gaussian quadrature
In numerical analysis, a quadrature rule is an approximation of the definite integral of a function, usually stated as a weighted sum of function values at specified points within the domain of integration....
where wi, xi 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
points to an -point rule in such a way that the resulting rule is of order . These extra points are the zeros of Stieltjes polynomialsStieltjes polynomials
In mathematics, the Stieltjes polynomials En are polynomials associated to a family of orthogonal polynomials Pn. They are unrelated to the Stieltjes polynomial solutions of differential equations...
. 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 . 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.| 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
.showed how to find further extensions of this type.
External links
- QUADPACK (part of SLATEC), source code http://www.netlib.org/slatec/src. QUADPACK is a collection of algorithms, in FortranFortranFortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
, for numerical integration based on Gauss-Kronrod rules. SLATECSLATECSLATEC Common Mathematical Library is a FORTRAN 77 library of over 1400 general purpose mathematical and statistical routines. The code was developed at US Government research laboratories, and is in the public domain....
(at NetlibNetlibNetlib is a repository of software for scientific computing maintained by AT&T, Bell Laboratories, the University of Tennessee and Oak Ridge National Laboratory. Netlib comprises a large number of separate programs and libraries...
) is a large public domain library for numerical computing. - ALGLIB source code in C#, C++, Delphi & Visual Basic
- Arbitrary precision Gauss-Kronrod nodes & weights. Reference tables along with MATLAB program.