# 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
*ck*2(
*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