Abstract
An iterative procedure is developed for reducing the rounding errors in the computed least squares solution to an overdetermined system of equationsAx =b, whereA is anm ×n matrix (m ≧n) of rankn. The method relies on computing accurate residuals to a certain augmented system of linear equations, by using double precision accumulation of inner products. To determine the corrections, two methods are given, based on a matrix decomposition ofA obtained either by orthogonal Householder transformations or by a modified Gram-Schmidt orthogonalization. It is shown that the rate of convergence in the iteration is independent of the right hand side,b, and depends linearly on the condition number, ℳ2135;(A), of the rectangular matrixA. The limiting accuracy achieved will be approximately the same as that obtained by a double precision factorization.
In a second part of this paper the case whenx is subject to linear constraints and/orA has rank less thann is covered. Here also ALGOL-programs embodying the derived algorithms will be given.
This is a preview of subscription content, log in via an institution to check access.
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.
Björck, Å.,Solving Linear Least Squares Problems by Gram-Schmidt Orthogonalization, BIT 7 (1967), 1–21.
Collatz, L.,Funktionalanalysis und Numerische Mathematik, Berlin: Springer-Verlag (1964).
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.
Martin, R. S., Peters, G. and Wilkinson, J. H.,Iterative Refinement of the Solution of a Positive Definite System of Equations, Num. Math. 8, (1966), 203–216.
Moler, C. B.,Iterative Refinement in Floating Point, J. Assoc. Comput. Mach. 14, (1967), 316–321.
Wilkinson, J. H.,Rounding Errors in Algebraic Processes, London: Her Majesty's Stationary Office; Englewood Cliffs, N.J.: Prentice-Hall 1963.
Wilkinson, J. H.,Error Analysis of Transformations Based on the Use of Matrices of the Form I-2ww T, Error in Digital Computations. Volume II. Rall, L. B. ed. New York: John Wiley (1965), 77–101.
Additional information
This work was sponsored by the Swedish Natural Science Research Council.
Rights and permissions
About this article
Cite this article
Björck, Å. Iterative refinement of linear least squares solutions I. BIT 7, 257–278 (1967). https://doi.org/10.1007/BF01939321
Issue Date:
DOI: https://doi.org/10.1007/BF01939321