Gauss–Legendre Quadrature
   HOME

TheInfoList



OR:

In
numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, Gauss–Legendre quadrature is a form of
Gaussian quadrature In numerical analysis, an -point Gaussian quadrature rule, named after Carl Friedrich Gauss, is a quadrature rule constructed to yield an exact result for polynomials of degree or less by a suitable choice of the nodes and weights for . Th ...
for approximating the
definite integral In mathematics, an integral is the continuous analog of a sum, which is used to calculate areas, volumes, and their generalizations. Integration, the process of computing an integral, is one of the two fundamental operations of calculus,Int ...
of a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...
. For integrating over the interval , the rule takes the form: :\int_^1 f(x)\,dx \approx \sum_^n w_i f(x_i) : where * ''n'' is the number of sample points used, * ''w''''i'' are quadrature weights, and * ''x''''i'' are the roots of the ''n''th
Legendre polynomial In mathematics, Legendre polynomials, named after Adrien-Marie Legendre (1782), are a system of complete and orthogonal polynomials with a wide number of mathematical properties and numerous applications. They can be defined in many ways, and t ...
. This choice of quadrature weights ''w''''i'' and quadrature nodes ''x''''i'' is the unique choice that allows the quadrature rule to integrate degree polynomials exactly. Many algorithms have been developed for computing Gauss–Legendre quadrature rules. The Golub–Welsch algorithm presented in 1969 reduces the computation of the nodes and weights to an
eigenvalue In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
problem which is solved by the
QR algorithm In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a Matrix (mathematics), matrix. The QR algorithm was developed in the late 1950s by John ...
. This algorithm was popular, but significantly more efficient algorithms exist. Algorithms based on the
Newton–Raphson method In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
are able to compute quadrature rules for significantly larger problem sizes. In 2014, Ignace Bogaert presented explicit asymptotic formulas for the Gauss–Legendre quadrature weights and nodes, which are accurate to within double-precision
machine epsilon Machine epsilon or machine precision is an upper bound on the relative approximation error due to rounding in floating point number systems. This value characterizes computer arithmetic in the field of numerical analysis, and by extension in the ...
for any choice of ''n'' ≥ 21. This allows for computation of nodes and weights for values of ''n'' exceeding one billion.


History

Carl Friedrich Gauss Johann Carl Friedrich Gauss (; ; ; 30 April 177723 February 1855) was a German mathematician, astronomer, geodesist, and physicist, who contributed to many fields in mathematics and science. He was director of the Göttingen Observatory and ...
was the first to derive the Gauss–Legendre quadrature rule, doing so by a calculation with
continued fraction A continued fraction is a mathematical expression that can be written as a fraction with a denominator that is a sum that contains another simple or continued fraction. Depending on whether this iteration terminates with a simple fraction or not, ...
s in 1814. He calculated the nodes and weights to 16 digits up to order ''n''=7 by hand.
Carl Gustav Jacob Jacobi Carl Gustav Jacob Jacobi (; ; 10 December 1804 – 18 February 1851) was a German mathematician who made fundamental contributions to elliptic functions, dynamics, differential equations, determinants and number theory. Biography Jacobi was ...
discovered the connection between the quadrature rule and the orthogonal family of
Legendre polynomials In mathematics, Legendre polynomials, named after Adrien-Marie Legendre (1782), are a system of complete and orthogonal polynomials with a wide number of mathematical properties and numerous applications. They can be defined in many ways, and t ...
. As there is no closed-form formula for the quadrature weights and nodes, for many decades people were only able to hand-compute them for small ''n'', and computing the quadrature had to be done by referencing tables containing the weight and node values. By 1942 these values were only known for up to ''n''=16.


Definition

For integrating ''f'' over 1,1/math> with Gauss–Legendre quadrature, the associated
orthogonal polynomials In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonal In mathematics, orthogonality (mathematics), orthogonality is the generalization of the geom ...
are
Legendre polynomials In mathematics, Legendre polynomials, named after Adrien-Marie Legendre (1782), are a system of complete and orthogonal polynomials with a wide number of mathematical properties and numerous applications. They can be defined in many ways, and t ...
, denoted by . With the -th polynomial normalized so that , the -th Gauss node, , is the -th root of and the weights are given by the formula : w_i = \frac. Some low-order quadrature rules are tabulated below for integrating over 1,1. For integrating over a general real interval ,b, a change of interval can be applied to convert the problem to one of integrating over 1,1/math>.


Algorithms


Newton–Raphson methods

Several researchers have developed algorithms for computing Gauss–Legendre quadrature nodes and weights based on the
Newton–Raphson method In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a ...
for finding roots of functions. Various optimizations for this specific problem are used. For instance, some methods compute \theta_i = \arccos x_i to avoid issues associated with clustering of the roots x_i near the ends of the interval -1 and 1 . Some methods utilize formulas to approximate the weights and then use a few iterations of Newton-Raphson to lower the error of the approximation to below machine precision.


Golub–Welsch

In 1969, Golub and Welsch published their method for computing Gaussian quadrature rules given the three term recurrence relation that the underlying orthogonal polynomials satisfy. They reduce the problem of computing the nodes of a Gaussian quadrature rule to the problem of finding the eigenvalues of a particular symmetric
tridiagonal matrix In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal below this), and the supradiagonal/upper diagonal (the first diagonal above the main ...
. The
QR algorithm In numerical linear algebra, the QR algorithm or QR iteration is an eigenvalue algorithm: that is, a procedure to calculate the eigenvalues and eigenvectors of a Matrix (mathematics), matrix. The QR algorithm was developed in the late 1950s by John ...
is used to find the eigenvalues of this matrix. By taking advantage of the symmetric tridiagonal structure, the eigenvalues can be computed in \mathcal O(n^2) time, as opposed to the \mathcal O(n^3) time expected for a generic eigenvalue problem.


Asymptotic formulas

Various methods have been developed that use approximate closed-form expressions to compute the nodes. As mentioned above, in some methods formulas are used as approximations to the nodes, after which some Newton-Raphson iterations are performed to refine the approximation. In a 2014 paper, Ignace Bogaert derives asymptotic formulas for the nodes that are exact up to machine precision for n \geq 21 and for the weights that are exact up to machine precision for n \geq 30 . This method does not require any Newton-Raphson iterations or evaluations of Bessel functions as other methods do. As shown in the paper, the method was able to compute the nodes at a problem size of one billion in 11 seconds. Since the nodes near the endpoints of 1,1 become very close to each other at this problem size, this method of computing the nodes is sufficient for essentially any practical application in double-precision floating point.


Higher precision

Johansson and Mezzarobba describe a strategy to compute Gauss–Legendre quadrature rules in
arbitrary-precision arithmetic In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple-precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are po ...
, allowing both small and large n. A rule of order n = 1000 with 1000 digits of precision can be calculated in around one second. Their method uses Newton–Raphson iteration together with several different techniques for evaluating Legendre polynomials. The algorithm also provides a certified error bound. Gil, Segura and Temme describe iterative methods with fourth order convergence for the computation of Gauss–Jacobi quadratures (and, in particular, Gauss–Legendre). The methods do not require a priori estimations of the nodes to guarantee its fourth-order convergence. Computations of quadrature rules with even millions of nodes and thousands of digits become possible in a typical laptop.


Comparison with other quadrature rules

Gauss–Legendre quadrature is optimal in a very narrow sense for computing integrals of a function ''f'' over , since no other quadrature rule integrates all degree polynomials exactly when using ''n'' sample points. However, this measure of accuracy is not generally a very useful one---polynomials are very simple to integrate and this argument does not by itself guarantee better accuracy on integrating other functions.
Clenshaw–Curtis quadrature Clenshaw–Curtis quadrature and Fejér quadrature are methods for numerical integration, or "quadrature", that are based on an expansion of the Integrand#Terminology and notation, integrand in terms of Chebyshev polynomials. Equivalently, they em ...
is based on approximating ''f'' by a polynomial interpolant at
Chebyshev nodes In numerical analysis, Chebyshev nodes (also called Chebyshev points or a Chebyshev grid) are a set of specific algebraic numbers used as nodes for polynomial interpolation and numerical integration. They are the Projection (linear algebra), pr ...
and integrates polynomials of degree up to ''n'' exactly when given ''n'' samples. Even though it does not integrate polynomials or other functions that are analytic in a large neighborhood of as well as Gauss–Legendre quadrature, Clenshaw–Curtis converges at approximately the same rate as Gauss–Legendre quadrature for most (non-analytic) integrands. Also, Clenshaw–Curtis shares the properties that Gauss–Legendre quadrature enjoys of convergence for all continuous integrands f and robustness to numerical rounding errors. Clenshaw–Curtis is straightforward to implement in \mathcal(n \log n) time by FFT-based methods. Newton–Cotes quadrature is based on approximating ''f'' by a polynomial interpolant at equally-spaced points in , and like Clenshaw–Curtis also integrates polynomials of degree up to ''n'' exactly when given ''n'' samples. However, it suffers from
Runge's phenomenon In the mathematical field of numerical analysis, Runge's phenomenon () is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation ...
as ''n'' increases; Newton–Cotes does not converge for some continuous integrands ''f'', and when it does converge it may suffer from numerical rounding errors. Thus, both Clenshaw–Curtis and Gauss–Legendre enjoy substantial benefits over Newton–Cotes for moderate to large ''n''.


References


Sources

* {{DEFAULTSORT:Gauss-Legendre quadrature Numerical integration