Improved Error Bounds for Underdetermined System Solvers
James W. Demmel and Nicholas J. Higham
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-587
August 1990
http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-587.pdf
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.
BibTeX citation:
@techreport{Demmel:CSD-90-587,
Author = {Demmel, James W. and Higham, Nicholas J.},
Title = {Improved Error Bounds for Underdetermined System Solvers},
Institution = {EECS Department, University of California, Berkeley},
Year = {1990},
Month = {Aug},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5233.html},
Number = {UCB/CSD-90-587}
}
EndNote citation:
%0 Report %A Demmel, James W. %A Higham, Nicholas J. %T Improved Error Bounds for Underdetermined System Solvers %I EECS Department, University of California, Berkeley %D 1990 %@ UCB/CSD-90-587 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5233.html %F Demmel:CSD-90-587