Computer solution and perturbation analysis of generalized linear least squares problems

Author:
C. C. Paige

Journal:
Math. Comp. **33** (1979), 171-183

MSC:
Primary 65D10; Secondary 65F35

DOI:
https://doi.org/10.1090/S0025-5718-1979-0514817-3

MathSciNet review:
514817

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new formulation of the generalized linear least squares problem is given. This is based on some ideas in estimation and allows complete generality in that there are no restrictions on the matrices involved. The formulation leads directly to a numerical algorithm involving orthogonal decompositions for solving the problem. A perturbation analysis of the problem is obtained by using the new formulation and some of the decompositions used in the solution. A rounding error analysis is given to show that the algorithm is numerically stable.

**[1]**Ȧke Björck,*A uniform numerical method for linear estimation from general Gauss-Markoff models*, Compstat 1974 (Proc. Sympos. Computational Statist., Univ. Vienna, Vienna, 1974) Physica Verlag, Vienna, 1974, pp. 131–140. MR**0373173****[2]**Ȧke Björck,*Solving linear least squares problems by Gram-Schmidt orthogonalization*, Nordisk Tidskr. Informationsbehandling (BIT)**7**(1967), 1–21. MR**214275**, https://doi.org/10.1007/bf01934122**[3]**Ȧke Björck,*Iterative refinement of linear least squares solutions. I*, Nordisk Tidskr. Informationsbehandling (BIT)**7**(1967), 257–278. MR**233494**, https://doi.org/10.1007/bf01939321**[4]**Peter Businger and Gene H. Golub,*Handbook series linear algebra. Linear least squares solutions by Householder transformations*, Numer. Math.**7**(1965), 269–276. MR**176590**, https://doi.org/10.1007/BF01436084**[5]**A. K. Cline,*An elimination method for the solution of linear least squares problems*, SIAM J. Numer. Anal.**10**(1973), 283–289. MR**359294**, https://doi.org/10.1137/0710027**[6]**G. Golub,*Numerical methods for solving linear least squares problems*, Numer. Math.**7**(1965), 206–216. MR**181094**, https://doi.org/10.1007/BF01436075**[7]**G. H. Golub and C. Reinsch,*Handbook Series Linear Algebra: Singular value decomposition and least squares solutions*, Numer. Math.**14**(1970), no. 5, 403–420. MR**1553974**, https://doi.org/10.1007/BF02163027**[8]**Gene H. Golub and George P. H. Styan,*Numerical computations for univariate linear models*, J. Statist. Comput. Simulation**2**(1973), 253–274. MR**375649**, https://doi.org/10.1080/00949657308810051**[9]**G. H. Golub and J. H. Wilkinson,*Note on the iterative refinement of least squares solution*, Numer. Math.**9**(1966), 139–148. MR**212984**, https://doi.org/10.1007/BF02166032**[10]**Charles L. Lawson and Richard J. Hanson,*Solving least squares problems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. MR**0366019****[11]**G. PETERS & J. H. WILKINSON, "The least squares problem and pseudo-inverses,"*Comput. J.*, v. 13, 1970, pp. 309-316.**[12]**G. W. Stewart,*On the continuity of the generalized inverse*, SIAM J. Appl. Math.**17**(1969), 33–45. MR**245583**, https://doi.org/10.1137/0117004**[13]**G. W. Stewart,*On the perturbation of pseudo-inverses, projections and linear least squares problems*, SIAM Rev.**19**(1977), no. 4, 634–662. MR**461871**, https://doi.org/10.1137/1019104**[14]**G. GOLUB, V. KLEMA, & G. W. STEWART,*Rank Degeneracy and Least Squares Problems*, Stanford University Computer Science Report STAN-CS-76-559, August, 1976.**[15]**C. Radhakrishna Rao,*Linear statistical inference and its applications*, 2nd ed., John Wiley & Sons, New York-London-Sydney, 1973. Wiley Series in Probability and Mathematical Statistics. MR**0346957****[16]**G. A. F. Seber,*Linear regression analysis*, John Wiley & Sons, New York-London-Sydney, 1977. Wiley Series in Probability and Mathematical Statistics. MR**0436482****[17]**C. C. Paige and M. A. Saunders,*Least squares estimation of discrete linear dynamic systems using orthogonal transformations*, SIAM J. Numer. Anal.**14**(1977), no. 2, 180–193. MR**437197**, https://doi.org/10.1137/0714012**[18]**S. KOUROUKLIS,*Computing Weighted Linear Least Squares Solutions*, McGill University School of Computer Science, M.Sc. Project, May 1977.**[19]**G. W. Stewart,*Introduction to matrix computations*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Computer Science and Applied Mathematics. MR**0458818****[20]**A. van der Sluis,*Stability of the solutions of linear least squares problems*, Numer. Math.**23**(1974/75), 241–254. MR**373259**, https://doi.org/10.1007/BF01400307**[21]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[22]**Sven Hammarling,*A note on modifications to the Givens plane rotation*, J. Inst. Math. Appl.**13**(1974), 215–218. MR**343568****[23]**C. C. Paige,*Fast numerically stable computations for generalized linear least squares problems*, SIAM J. Numer. Anal.**16**(1979), no. 1, 165–171. MR**518691**, https://doi.org/10.1137/0716012**[24]**C. C. Paige,*Numerically stable computations for general univariate linear models*, Comm. Statist. B—Simulation Comput.**7**(1978), no. 5, 437–453. MR**516832**, https://doi.org/10.1080/03610917808812090

Retrieve articles in *Mathematics of Computation*
with MSC:
65D10,
65F35

Retrieve articles in all journals with MSC: 65D10, 65F35

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1979-0514817-3

Keywords:
Covariance matrices,
error analysis,
estimation of linear systems,
linear least squares,
matrix computations,
perturbation analysis,
regression analysis

Article copyright:
© Copyright 1979
American Mathematical Society