Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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