Improved Error Bounds for Underdetermined System Solvers
- 1 January 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 14 (1), 1-14
- https://doi.org/10.1137/0614001
Abstract
The minimal 2-norm solution to an underdetermined system $Ax = b$ of full rank can be computed using a QR factorization of $A^T $ in two different ways. One method requires storage and reuse of the orthogonal matrix Q, while the method of seminormal equations does not. Existing error analyses show that both methods produce computed solutions whose normwise relative error is bounded to first order by $c\kappa_2 ( A )u$, where c is a constant depending on the dimensions of A, $\kappa_2 ( A ) = \| A^ + \|_2 \| A \|_2 $ is the 2-norm condition number, and u is the unit roundoff. It is shown that these error bounds can be strengthened by replacing $\kappa_2(A)$ by the potentially much smaller quantity ${\operatorname{cond}}_2 ( A ) = \| \,| A^ + | \cdot | A |\, \|_2 $, which is invariant under row scaling of A. It is also shown that ${\operatorname{cond}}_2 ( A )$ reflects the sensitivity of the minimum norm solution x to row-wise relative perturbations in the data A and b. For square linear systems $Ax = b$ row equilibration is shown to endow solution methods based on LU or QR factorization of A with relative error bounds proportional to ${\operatorname{cond}}_\infty ( A )$, just as when a QR factorization of $A^T $ is used. The advantages of using fixed precision iterative refinement in this context instead of row equilibration are explained.
Keywords
This publication has 16 references indexed in Scilit:
- Algorithm 694ACM Transactions on Mathematical Software, 1991
- Experience with a Matrix Norm EstimatorSIAM Journal on Scientific and Statistical Computing, 1990
- Solving Sparse Linear Systems with Sparse Backward ErrorSIAM Journal on Matrix Analysis and Applications, 1989
- FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimationACM Transactions on Mathematical Software, 1988
- Stability analysis of the method of seminormal equations for linear least squares problemsLinear Algebra and its Applications, 1987
- Error analysis of an algorithm for solving an underdetermined linear systemNumerische Mathematik, 1985
- Condition EstimatesSIAM Journal on Scientific and Statistical Computing, 1984
- $l_2 $-Solutions to Underdetermined Linear SystemsSiam Review, 1976
- A numerically stable form of the simplex algorithmLinear Algebra and its Applications, 1973
- Zusammenfassender Bericht. Genauigkeitsfragen bei der Lösung linearer GleichungssystemeZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, 1966