Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Extensions and applications of the Householder algorithm for solving linear least squares problems


Authors: Richard J. Hanson and Charles L. Lawson
Journal: Math. Comp. 23 (1969), 787-812
MSC: Primary 65.35
DOI: https://doi.org/10.1090/S0025-5718-1969-0258258-9
MathSciNet review: 0258258
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The mathematical and numerical least squares solution of a general linear system of equations is discussed.

Perturbation and differentiability theorems for pseudoinverses are given.

Computational procedures for calculating least squares solutions using orthonormal transformations, multiplying matrices by a matrix of orthonormal basis vectors for the null-space of a given matrix, sequential processing of data, and processing of block diagonal matrices form a partial list of numerical topics presented.


References [Enhancements On Off] (What's this?)

  • [1] P. Businger & G. Golub, ``Linear least squares solutions by Householder transformations,'' Numer. Math., v. 7, 1965, pp. 269-276. MR 31 #862. MR 0176590 (31:862)
  • [2] E. E. Osborne, ``On least squares solutions of linear equations,'' J. Assoc. Comput. Mach., v. 8, 1961, pp. 628-636. MR 24 #B2543. MR 0136510 (24:B2543)
  • [3] G. Forsythe & C. Moler, Computer Solution of Linear Algebraic Systems, Prentice-Hall, Englewood Cliffs, N. J., 1967. MR 36 #2306. MR 0219223 (36:2306)
  • [4] G. H. Golub & P. Businger, Least Squares, Singular Values and Matrix Approximations; An ALGOL Procedure for Computing the Singular Value Decomposition, Stanford Computer Sciences Department, Technical Report No. CS73, July 1967, (Mimo., 12 leaves).
  • [5] T. N. E. Greville, ``The pseudo-inverse of a rectangular or singular matrix and its application to the solution of systems of linear equations,'' SIAM Rev., v. 1, 1959, pp. 38-43. MR 21 #424. MR 0101615 (21:424)
  • [6] A. Ben-Israel, ``On error bounds for generalized inverses,'' SIAM J. Numer. Anal., v. 3, 1966, pp. 585-592. MR 35 #6344. MR 0215504 (35:6344)
  • [7] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, N. J., 1963. MR 28 #4661. MR 0161456 (28:4661)
  • [8] G. H. Golub & J. H. Wilkinson, ``Note on the iterative refinement of least squares solution,'' Numer. Math., v. 9, 1966, pp. 139-148. MR 35 #3849. MR 0212984 (35:3849)
  • [9] J. N. Franklin, Matrix Theory, Prentice-Hall, Englewood Cliffs, N. J., 1968. MR 0237517 (38:5798)
  • [10] G. W. Stewart III, ``On the continuity of the generalized inverse,'' SIAM J. Appl. Math., v. 17, 1969, pp. 33-45. MR 0245583 (39:6889)
  • [11] P. J. Davis, Orthonormalizing Codes in Numerical Analysis. Survey of Numerical Analysis, McGraw-Hill, New York, 1962, pp. 347-379. MR 25 #734. MR 0137278 (25:734)
  • [12] R. S. Martin, C. Reinsch & J. H. Wilkinson, ``Householder's tridiagonalization of a symmetric matrix,'' Numer. Math., v. 11, 1968, pp. 181-195. MR 1553959
  • [13] E. E. Osborne, ``Smallest least squares solutions of linear equations,'' J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., v. 2, 1965, pp. 300-307. MR 32 #4834. MR 0187382 (32:4834)
  • [14] T. L. Jordan, ``Experiments on error growth associated with some linear least-squares procedures,'' Math. Comp., v. 22, 1968, pp. 579-588. MR 37 #4947. MR 0229373 (37:4947)
  • [15] J. K. Reid, ``A note on the least squares solution of a band system of linear equations by Householder reductions,'' Comput. J., v. 10, 1967, pp. 188-189. MR 35 #5130. MR 0214279 (35:5130)
  • [16] A. Björck, ``Solving linear least squares problems by Gram-Schmidt orthogonalization,'' Nordisk Tidskr. Informations-Behandling, v. 7, 1967, pp. 1-21. MR 35 #5126. MR 0214275 (35:5126)
  • [17] V. Pereyra, ``Stabilizing Linear Least Squares Problems,'' Proceedings IFIP 68, p. 127, (1968).
  • [18] D. K. Faddeev, V. N. Kublamovskaya & V. N. Faddeeva, Sur Les Systèmes Linéaires Algébriques de Matrices Rectangulaires et Mal-Conditionnées, Programmation en Mathématiques Numériques, Editions Centre Nat. Recherche Sci., Paris, 1968, pp. 161-170. MR 37 #6017. MR 0230455 (37:6017)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65.35

Retrieve articles in all journals with MSC: 65.35


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1969-0258258-9
Keywords: Linear Least Squares, Linear Equations, Pseudoinverse Solution, Numerical Methods for Linear Equations, Orthogonal Methods for Linear Systems
Article copyright: © Copyright 1969 American Mathematical Society

American Mathematical Society