Abstract
A general analysis of the condition of the linear least squares problem is given. The influence of rounding errors is studied in detail for a modified version of the Gram-Schmidt orthogonalization to obtain a factorizationA=QR of a givenm×n matrixA, whereR is upper triangular andQ T Q=I. Letx be the vector which minimizes ‖b−Ax‖2 andr=b−Ax. It is shown that if inner-products are accumulated in double precision then the errors in the computedx andr are less than the errors resulting from some simultaneous initial perturbation δA, δb such that
No reorthogonalization is needed and the result is independent of the pivoting strategy used.
Similar content being viewed by others
References
Bauer, F. L.,Elimination with Weighted Row Combinations for Solving Linear Equations and Least Squares Problems, Num. Math. 7 (1965), 338–352.
Golub, G. H.,Numerical Methods for Solving Linear Least Squares Problems, Num. Math. 7 (1965), 206–216.
Golub, G. H. and Wilkinson, J. H.,Note on the Iterative Refinement of Least Squares Solution, Num. Math. 9 (1966), 139–148.
Householder, A. S.,The Theory of Matrices in Numerical Analysis, New York: Blaisdell 1964.
Rice, J. R.,Experiments on Gram-Schmidt Orthogonalization, Math. Comp. 20 (1966), 325–328.
Wilkinson, J. H.,Rounding Errors in Algebraic Processes, London: H.M.S.O. 1963.
Wilkinson, J. H.:The Algebraic Eigenvalue Problem, Oxford: Clarendon Press 1965.
Åslund, N.,A Data Processing System for Spectra of Diatomic Molecules, Arkiv Fysik 30 (1965), 377–396.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Björck, Å. Solving linear least squares problems by Gram-Schmidt orthogonalization. BIT 7, 1–21 (1967). https://doi.org/10.1007/BF01934122
Issue Date:
DOI: https://doi.org/10.1007/BF01934122