##
Accurate solution of weighted least squares by iterative methods

###
E. Bobrovnikova and S. Vavasis

We consider the weighted least-squares (WLS) problem
with a very ill-conditioned weight matrix. Weighted
least-squares problems arise in many applications including
linear programming, electrical networks, boundary
value problems, and structures. Because of roundoff
errors, standard iterative methods for solving a WLS
problem with ill-conditioned weights may not give the
correct answer. Indeed, the difference between the
true and computed solution (forward error) may be
large. We propose an iterative algorithm, called
MINRES-L, for solving WLS problems. The MINRES-L
method is the application of MINRES, a Krylov-space
method due to Paige and Saunders, to a certain
layered linear system. Using a simplified model of
the effects of roundoff error, we prove that MINRES-L
gives answers with small forward error. We present
computational experiments for some applications.
Argonne National Laboratory Preprint ANL/MCS-P644-0297

Contact: vavasis@mcs.anl.gov