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

, 1990

http://www2.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},
    Year= {1990},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5233.html},
    Number= {UCB/CSD-90-587},
    Abstract= {The minimal 2-norm solution to an undetermined system <i>Ax</i> = <i>b</i> of full rank can be computed using a <i>QR</i> factorization of <i>A</i>^<i>T</i> in two different ways. One requires storage and re-use of the orthogonal matrix <i>Q</i> 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 <i>ck</i>2(<i>A</i>)<i>u</i>, where <i>c</i> is a constant depending on the dimensions of <i>A</i>, <i>k2</i>(<i>A</i>) = ||<i>A</i>^+||2||<i>A</i>||2 is the 2-norm condition number, and <i>u</i> is the unit roundoff. We show that these error bounds can be strengthened by replacing <i>k2</i>(<i>A</i>) by the potentially much smaller quantity cond2(<i>A</i>) = |||<i>A</i>^+||.|<i>A</i>|||2, which is invariant under row scaling of <i>A</i>. We also show that cond2(<i>A</i>) reflects the sensitivity of the minimum norm solution <i>x</i> to row-wise relative perturbations in the data <i>A</i> and <i>b</i>. For square linear systems <i>Ax</i> = <i>b</i> row equilibration is shown to endow solution methods based on <i>LU</i> or <i>QR</i> factorization of <i>A</i> with relative error bounds proportional to cond-infinity(<i>A</i>), just as when a <i>QR</i> factorization of <i>A</i>^<i>T</i> is used. The advantages of using fixed precision iterative refinement in this context instead of row equalibration are explained.},
}

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://www2.eecs.berkeley.edu/Pubs/TechRpts/1990/5233.html
%F Demmel:CSD-90-587