Improved Error Bounds for Underdetermined System Solvers
Demmel, James W.
Higham, Nicholas J.
Technical Report Identifier: CSD-90-587
August 13, 1990
Abstract: The minimal 2-norm solution to an undetermined system Ax = b of full rank can be computed using a QR factorization of A^T in two different ways. One requires storage and re-use of the orthogonal matrix Q while the method of semi-normal equations does not. Existing error analyses show that both methods produce computed solutions whose normwise relative error is bounded to first order by ck2(A)u, where c is a constant depending on the dimensions of A, k2(A) = ||A^+||2||A||2 is the 2-norm condition number, and u is the unit roundoff. We show that these error bounds can be strengthened by replacing k2(A) by the potentially much smaller quantity cond2(A) = |||A^+||.|A|||2, which is invariant under row scaling of A. We also show that cond2(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 cond-infinity(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 equalibration are explained.