×

zbMATH — the first resource for mathematics

Numerics of Gram-Schmidt orthogonalization. (English) Zbl 0801.65039
The paper surveys the numerical properties of the classical and the modified Gram-Schmidt (MGS) orthogonalization procedures. The key observation is the numerical equivalence of the modified Gram-Schmidt procedure to the Householder QR factorization of the matrix \(A\) augmented by an \(n \times n\) zero matrix on top. This result is used to derive bounds on the loss of orthogonality in MGS. A backward-stable algorithm based on MGS is developed. The use of reorthogonalization and iteration is also investigated. Block Gram-Schmidt algorithms are presented.

MSC:
65F25 Orthogonalization in numerical linear algebra
65F05 Direct numerical methods for linear systems and matrix inversion
Software:
ALGOL 60
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdelmalek, N.N., Roundoff error analysis for Gram-Schmidt method and solution of linear least squares problems, Bit, 11, 345-368, (1971) · Zbl 0236.65031
[2] Bauer, F.L., Elimination with weighted row combinations for solving linear equations and least squares problems, Numer. math., 7, 338-352, (1965) · Zbl 0142.11504
[3] Bienaymé, I.J., Remarques sur LES différences qui distinguent l’interpolation de M. Cauchy de la méthode des moindre carrés, et qui assurent la supériorité de cette méthode, C. R. acad. sci. Paris, 37, 5-13, (1853)
[4] Bischof, C.H., A block QR factorization algorithm using restricted pivoting, (), 248-256
[5] Björck, Å., Solving linear least squares problems by Gram-Schmidt orthogonalization, Bit, 7, 1-21, (1967) · Zbl 0183.17802
[6] Björck, Å.; Paige, C.C., Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm, SIAM J. matrix anal. appl., 13, 176-190, (1992) · Zbl 0747.65026
[7] Cauchy, A.L., Mémoire sur L’interpolation, (), 2, 5-17, (1837), Ser. 2
[8] Daniel, J.; Gragg, W.B.; Kaufman, L.; Stewart, G.W., Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. comp., 30, 772-795, (1976) · Zbl 0345.65021
[9] Farebrother, R.W., Linear least squares computations, (1988), Marcel Dekker New York · Zbl 0715.65027
[10] Gander, W., Algorithms for the QR-decomposition, Technical report 80-02, (1980), Angewandte Mathematik, ETH
[11] Golub, G.H.; Van Loan, C.F., Matrix computations, (1989), John Hopkins U.P Baltimore · Zbl 0733.65016
[12] Hoffman, W., Iterative algorithms for Gram-Schmidt orthogonalization, Computing, 41, 335-348, (1989) · Zbl 0667.65037
[13] Jalby, W.; Philippe, B., Stability analysis and improvement of the block Gram-Schmidt algorithm, SIAM J. sci. statist. comput., 12, 1058-1073, (1991) · Zbl 0734.65034
[14] Jordan, T.L., Experiments on error growth associated with some linear least-squares procedures, Math. comp., 22, 579-588, (1968) · Zbl 0162.46801
[15] Laplace, P.S., Théorie analytique des probabilités. premier supplément, (1816), Mme. Courcier, Paris
[16] Lawson, C.L.; Hanson, R.J., Solving least squares problems, (1974), Prentice-Hall Englewood Cliffs, N.J · Zbl 0185.40701
[17] Läuchli, P., Jordan-elimination und ausgleichung nach kleinsten quadraten, Numer. math., 3, 226-240, (1961) · Zbl 0117.10902
[18] Longley, J.W., Modified Gram-Schmidt process vs. classical Gram-Schmidt, Comm. statist. simulation comput. B10, 5, 517-527, (1981) · Zbl 0463.65026
[19] Malard, J., Block solvers for dense linear systems on local memory multi-processors, ()
[20] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, N.J · Zbl 0431.65016
[21] Peters, G.; Wilkinson, J.H., The least squares problem and pseudo-inverses, Comput. J., 13, 309-316, (1970) · Zbl 0195.44804
[22] Rice, J.R., Experiments on Gram-Schmidt orthogonalization, Math. comp., 20, 325-328, (1966) · Zbl 0228.65034
[23] Ruhe, A., Numerical aspects of Gram-Schmidt orthogonalization of vectors, Linear algebra appl., 52/53, 591-601, (1983) · Zbl 0515.65036
[24] Rutishauser, H., Description of algol 60, ()
[25] Schmidt, E., Über die auflösung linearer gleichungen mit unendlich vielen unbekannten, Rend. circ. mat. Palermo, 25, 1, 53-77, (1908) · JFM 39.0401.01
[26] Schreiber, R.; Van Loan, C.F., A storage efficient WY representation for products of Householder transformations, SIAM J. sci. statist. comput., 10, 53-57, (1989) · Zbl 0664.65025
[27] Wampler, R.H., A report on the accuracy of some widely used least squares computer programs, J. amer. statist. assoc., 65, 549-565, (1970) · Zbl 0196.22405
[28] Wampler, R.H., Solutions to weighted least squares problems by modified gram – schmidt with iterative refinement, ACM trans. math. software, 5, 457-465, (1979) · Zbl 0429.65033
[29] Wilkinson, J.H., Error analysis of transformations based on the use of matrices of the form I−2wwh, (), 77-101
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.