Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization
HTML articles powered by AMS MathViewer
- by J. W. Daniel, W. B. Gragg, L. Kaufman and G. W. Stewart PDF
- Math. Comp. 30 (1976), 772-795 Request permission
Abstract:
Numerically stable algorithms are given for updating the Gram-Schmidt QR factorization of an $m \times n$ matrix $A\;(m \geqslant n)$ when A is modified by a matrix of rank one, or when a row or column is inserted or deleted. The algorithms require $O(mn)$ operations per update, and are based on the use of elementary two-by-two reflection matrices and the Gram-Schmidt process with reorthogonalization. An error analysis of the reorthogonalization process provides rigorous justification for the corresponding ALGOL procedures.References
- George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
- P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505β535. MR 343558, DOI 10.1090/S0025-5718-1974-0343558-6
- Philip E. Gill, Walter Murray, and Michael A. Saunders, Methods for computing and modifying the $LDV$ factors of a matrix, Math. Comp. 29 (1975), no.Β 132, 1051β1077. MR 388754, DOI 10.1090/S0025-5718-1975-0388754-8
- W. B. Gragg and G. W. Stewart, A stable variant of the secant method for solving nonlinear equations, SIAM J. Numer. Anal. 13 (1976), no.Β 6, 889β903. MR 433856, DOI 10.1137/0713070
- Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
- Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
- Charles L. Lawson and Richard J. Hanson, Solving least squares problems, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. MR 0366019 HEINZ RUTISHAUSER, Handbook for Automatic Computation. Vol. 1/Part a: Description of ALGOL 60, Die Grundlehren der math. Wissenschaften, Band 135, Springer-Verlag, New York, 1967.
- G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
- J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Math. Comp. 30 (1976), 772-795
- MSC: Primary 65F25
- DOI: https://doi.org/10.1090/S0025-5718-1976-0431641-8
- MathSciNet review: 0431641