IMPROVED ERROR-BOUNDS FOR UNDERDETERMINED SYSTEM SOLVERS

The minimal 2-norm solution to an underdetermined system Ax = b of full rank can be computed using a QR factorization of A(T) in two different ways. One method requires storage and reuse of the orthogonal matrix Q, while the method of seminormal equations does not. Existing error analyses show that both methods produce computed solutions whose normwise relative error is bounded to first order by ckappa2(A)u, where c is a constant depending on the dimensions of A, kappa2(A) = \\A+\\2\\A\\2 is the 2-norm condition number, and u is the unit roundoff. It is shown that these error bounds can be strengthened by replacing kappa2(A) by the potentially much smaller quantity cond2(A) = \\ \A+\.\A\ \\2, which is invariant under row scaling of A. It is also shown 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 oil 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 equilibration are explained.