November 13, 1967, revised July 12, 1968 | Gene H. Golub and John H. Welsch
This paper presents algorithms for computing Gauss quadrature rules. It shows that given the three-term recurrence relation for orthogonal polynomials generated by a weight function, the quadrature rule can be generated by computing the eigenvalues and first component of the orthonormal eigenvectors of a symmetric tridiagonal matrix. An algorithm is also presented for computing the three-term recurrence relation from the moments of the weight function.
The Gauss quadrature rule is exact for all polynomials of degree ≤ 2N - 1. The quadrature rule is determined by the eigenvalues and eigenvectors of a symmetric tridiagonal matrix derived from the three-term recurrence relation of the orthogonal polynomials. The Q-R algorithm is used to compute the eigenvalues and eigenvectors of the matrix. The algorithm proceeds by iteratively applying the Q-R algorithm to the matrix until it converges to the diagonal matrix of eigenvalues.
The paper also describes how to determine the three-term recurrence relation from the moments of the weight function. This is done by using the Cholesky decomposition of the moment matrix and then applying formulas to compute the recurrence coefficients.
The paper provides three ALGOL 60 procedures for performing the algorithms described. These procedures are used to compute the weights and abscissas of the quadrature rule. The procedures are tested on different machines and show that the GAUSSQUADRULE procedure is stable and accurate even for large N. The results are compared with existing tables for Gauss-Legendre and Gauss-Laguerre quadrature rules. The paper concludes with an acknowledgment of the helpful comments and derivation provided by Professor Walter Gautschi.This paper presents algorithms for computing Gauss quadrature rules. It shows that given the three-term recurrence relation for orthogonal polynomials generated by a weight function, the quadrature rule can be generated by computing the eigenvalues and first component of the orthonormal eigenvectors of a symmetric tridiagonal matrix. An algorithm is also presented for computing the three-term recurrence relation from the moments of the weight function.
The Gauss quadrature rule is exact for all polynomials of degree ≤ 2N - 1. The quadrature rule is determined by the eigenvalues and eigenvectors of a symmetric tridiagonal matrix derived from the three-term recurrence relation of the orthogonal polynomials. The Q-R algorithm is used to compute the eigenvalues and eigenvectors of the matrix. The algorithm proceeds by iteratively applying the Q-R algorithm to the matrix until it converges to the diagonal matrix of eigenvalues.
The paper also describes how to determine the three-term recurrence relation from the moments of the weight function. This is done by using the Cholesky decomposition of the moment matrix and then applying formulas to compute the recurrence coefficients.
The paper provides three ALGOL 60 procedures for performing the algorithms described. These procedures are used to compute the weights and abscissas of the quadrature rule. The procedures are tested on different machines and show that the GAUSSQUADRULE procedure is stable and accurate even for large N. The results are compared with existing tables for Gauss-Legendre and Gauss-Laguerre quadrature rules. The paper concludes with an acknowledgment of the helpful comments and derivation provided by Professor Walter Gautschi.