### Improved Error Bounds for Underdetermined System Solvers

**Authors:**

Demmel, James W.

Higham, Nicholas J.
**Technical Report Identifier:** CSD-90-587
**August 13, 1990**

CSD-90-587.pdf

**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 *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.