×

Computation of Gauss-type quadrature formulas. (English) Zbl 0980.65021

This paper surveys methods of computing formulas from recursion coefficients and methods of obtaining recursion coefficients and their modification for Gauss-type formulas. The discussion includes obtaining recursion coefficients via quadrature and from modified moments. A main tool for obtaining Gauss-type quadratures is to establish the recursion coefficients for the system of orthogonal polynomials that are generated by the quadrature formula itself.
Radau, Lobatto, anti-Gaussian, and Kronrod are Gauss-type quadratures briefly discussed in the present context. W. Gautschi’s ORTHOPOL [ACM Trans. Math. Software 20, No. 1, 21-62 (1994; Zbl 0888.65013)] and other relevant software packages are mentioned. The paper concludes with existence and accuracy questions in connection with three-term and two-term coefficients. Almost 50 references reflect the present state of the art.

MSC:

65D32 Numerical quadrature and cubature formulas
41A55 Approximate quadratures

Citations:

Zbl 0888.65013

Software:

ORTHPOL; GQRAT; EXTEND
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ammar, G. S.; Calvetti, D.; Reichel, L., Computation of Gauss-Kronrod quadrature rules with non-positive weights, Elec. Trans. Numer. Anal., 9, 26-38 (1999) · Zbl 0954.65017
[2] Beckermann, B.; Bourreau, E., How to choose modified moments?, J. Comput. Appl. Math., 98, 81-98 (1998) · Zbl 0935.65011
[3] Calvetti, D.; Golub, G. H.; Gragg, W. B.; Reichel, L., Computation of Gauss-Kronrod quadrature rules, Math. Comput., 69, 1035-1052 (2000) · Zbl 0947.65022
[4] Cuppen, J. J.M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 36, 177-195 (1981) · Zbl 0431.65022
[5] de Boor, C.; Golub, G. H., The numerically stable reconstruction of a Jacobi matrix from spectral data, Linear Algebra Appl., 21, 245-260 (1978) · Zbl 0388.15010
[6] I.S. Dhillon, A new \(O(n^2)\) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, Ph.D. Thesis, University of California, Berkeley, 1997.; I.S. Dhillon, A new \(O(n^2)\) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, Ph.D. Thesis, University of California, Berkeley, 1997.
[7] Fernando, K. V.; Parlett, B. N., Accurate singular values and differential quotient-difference algorithms, Numer. Math., 67, 191-229 (1994) · Zbl 0814.65036
[8] Fischer, H.-J., On the condition of orthogonal polynomials via modified moments, Z. Anal. Anwendungen, 15, 223-244 (1996) · Zbl 0840.42018
[9] Fischer, H.-J., Explicit calculation of some polynomials introduced by W. Gautschi, Z. Anal. Anwendungen, 17, 963-977 (1998) · Zbl 0933.42015
[10] Fischer, H.-J., On generating orthogonal polynomials for discrete measures, Z. Anal. Anwendungen, 17, 183-205 (1998) · Zbl 0901.42017
[11] Gates, K.; Gragg, W. B., Notes on TQR algorithms, J. Comput. Appl. Math., 86, 195-203 (1997) · Zbl 0892.65023
[12] Gautschi, W., Construction of Gauss-Christoffel quadrature formulae, Math. Comput., 22, 251-270 (1968) · Zbl 0187.10603
[13] W. Gautschi, A survey of Gauss-Christoffel quadrature formulae, in: P.L. Butzer, F. Fehér (Eds.), E.B. Christoffel: The Influence of his Work on Mathematics and the Physical Sciences, Birkhäuser, Basel, 1981, pp. 72-147.; W. Gautschi, A survey of Gauss-Christoffel quadrature formulae, in: P.L. Butzer, F. Fehér (Eds.), E.B. Christoffel: The Influence of his Work on Mathematics and the Physical Sciences, Birkhäuser, Basel, 1981, pp. 72-147. · Zbl 0479.65001
[14] Gautschi, W., On generating orthogonal polynomials, SIAM J. Sci. Statist. Comput., 3, 289-317 (1982) · Zbl 0482.65011
[15] Gautschi, W., How and how not to check Gaussian quadrature formulae, BIT, 23, 209-216 (1983) · Zbl 0518.65007
[16] W. Gautschi, Questions of numerical condition related to polynomials, in: G.H. Golub (Ed.), Studies in Numerical Analysis, Math. Assoc. Amer. 1984, pp. 140-177.; W. Gautschi, Questions of numerical condition related to polynomials, in: G.H. Golub (Ed.), Studies in Numerical Analysis, Math. Assoc. Amer. 1984, pp. 140-177. · Zbl 0584.65020
[17] Gautschi, W., On the sensitivity of orthogonal polynomials to perturbations in the moments, Numer. Math., 48, 369-382 (1986) · Zbl 0613.65014
[18] Gautschi, W., Gauss-Kronrod quadrature – a survey, (Milovanović, G. V., Numerical Methods and Approximation Theory III (1987), University of Niš), 39-66
[19] Gautschi, W., Gauss-type quadrature rules for rational functions, (Brass, H.; Hämmerlin, G., Numerical Integration IV. Numerical Integration IV, International Series of Numerical Mathematics, Vol. 112 (1993), Birkhäuser: Birkhäuser Basel), 111-130 · Zbl 0802.65019
[20] Gautschi, W., Algorithm 726: ORTHPOL - a package of routines for generating orthogonal polynomials and Gauss-type quadrature rules, ACM Trans. Math. Software, 20, 21-62 (1994) · Zbl 0888.65013
[21] Golub, G. H., Some modified matrix eigenvalue problems, SIAM Rev., 15, 318-334 (1973) · Zbl 0254.65027
[22] Golub, G. H.; Kautsky, J., Calculation of Gauss quadratures with multiple free and fixed knots, Math. Comp., 41, 147-163 (1983) · Zbl 0525.65010
[23] Golub, G. H.; Welsch, J. H., Calculation of Gauss quadrature rules, Math. Comp., 23, 221-230 (1969) · Zbl 0179.21901
[24] Gragg, W. B.; Harrod, W. J., The numerically stable reconstruction of Jacobi matrices from spectral data, Numer. Math., 44, 317-335 (1984) · Zbl 0556.65027
[25] Gu, M.; Eisenstat, S. C., A divide-and-conquer algorithm for the bidiagonal svd, SIAM J. Matrix Anal. Appl., 16, 79-92 (1995) · Zbl 0821.65019
[26] Kautsky, J.; Elhay, S., Gauss quadratures and Jacobi matrices for weight functions not of one sign, Math. Comp., 43, 543-550 (1984) · Zbl 0556.65012
[27] Kautsky, J.; Golub, G. H., On the calculation of Jacobi matrices, Linear Algebra Appl., 52/53, 439-455 (1983) · Zbl 0512.65030
[28] Kronrod, A. S., Nodes and Weights of Quadrature Formulas (1965), Consultants Bureau: Consultants Bureau New York · Zbl 0154.18501
[29] Laurie, D. P., Stratified sequences of nested integration formulas, Quaest. Math., 15, 365-384 (1992) · Zbl 0788.65025
[30] Laurie, D. P., Anti-Gaussian quadrature formulas, Math. Comp., 65, 739-747 (1996) · Zbl 0843.41020
[31] Laurie, D. P., Calculation of Gauss-Kronrod quadrature formulas, Math. Comp., 66, 1133-1145 (1997) · Zbl 0870.65018
[32] Laurie, D. P., Accurate recovery of recursion coefficients from Gaussian quadrature formulas, J. Comput. Appl. Math., 112, 165-180 (1999) · Zbl 0942.65022
[33] Laurie, D. P., Questions related to Gaussian quadrature formulas and two-term recursions, (Gautschi, W.; Golub, G. H.; Opfer, G., Computation and Application of Orthogonal Polynomials. Computation and Application of Orthogonal Polynomials, International Series of Numerical Mathematics, Vol. 133 (1999), Birkhäuser: Birkhäuser Basel), 133-144 · Zbl 0944.41017
[34] S. Lewanowicz, Construction of a recurrence relation for modified moments, Technical Report, Institute of Computer Science, Wroclaw University, 1977.; S. Lewanowicz, Construction of a recurrence relation for modified moments, Technical Report, Institute of Computer Science, Wroclaw University, 1977. · Zbl 0437.65095
[35] Parlett, B. N., The Symmetric Eigenvalue Problem (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0431.65016
[36] B.N. Parlett, The new qd algorithms, in: A. Iserles (Ed.), Acta Numerica 1995, Cambridge University Press, Cambridge, 1995, pp. 459-491.; B.N. Parlett, The new qd algorithms, in: A. Iserles (Ed.), Acta Numerica 1995, Cambridge University Press, Cambridge, 1995, pp. 459-491. · Zbl 0835.65059
[37] Parlett, B. N.; Dhillon, I. S., Fernando’s solution to Wilkinson’s problem: an application of double factorization, Linear Algebra Appl., 267, 247-279 (1997) · Zbl 0886.65033
[38] Patterson, T. N.L., The optimal addition of points to quadrature formulae, Math. Comp., 22, 847-856 (1968) · Zbl 0172.19304
[39] Patterson, T. N.L., On some Gauss and Lobatto based quadrature formulae, Math. Comp., 22, 877-881 (1968) · Zbl 0172.19303
[40] Patterson, T. N.L., Algorithm 672: generation of interpolatory quadrature rules of the highest degree of precision with pre-assigned nodes for general weight-functions, ACM Trans. Math. Software, 15, 2, 137-143 (1989) · Zbl 0900.65048
[41] Reichel, L., Fast QR decomposition of Vandermonde-like matrices and polynomial least squares approximation, SIAM J. Matrix Anal. Appl., 12, 552-564 (1991) · Zbl 0739.65024
[42] Reichel, L., Construction of polynomials that are orthogonal with respect to a discrete bilinear form, Adv. Comput. Math., 1, 241-258 (1993) · Zbl 0824.65007
[43] Rutishauser, H., Der Quotienten-Differenzen-Algorithmus (1957), Birkhäuser: Birkhäuser Basel · Zbl 0077.11103
[44] H. Rutishauser, On Jacobi rotation patterns, in: Experimental Arithmetic, High Speed Computation and Mathematics, American Mathematical Society, Providence, RI, 1963, pp. 219-239.; H. Rutishauser, On Jacobi rotation patterns, in: Experimental Arithmetic, High Speed Computation and Mathematics, American Mathematical Society, Providence, RI, 1963, pp. 219-239.
[45] Sack, R. A.; Donovan, A. F., An algorithm for Gaussian quadrature given modified moments, Numer. Math., 18, 465-478 (1972) · Zbl 0221.65041
[46] Salzer, H. E., A recurrence scheme for converting from one orthogonal expansion into another, Comm. ACM, 16, 705-707 (1973) · Zbl 0269.65010
[47] Stroud, A. H.; Secrest, D., Gaussian Quadrature Formulas (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0156.17002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.