Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems
Åke Björck, Tommy Elfving, Zdeněk Strakoš · SIAM Journal on Matrix Analysis and Applications · 1998
{The conjugate gradient method applied to the normal equations A T Ax=A T b (CGLS) is often used for solving large sparse linear least squares problems. The mathematically equivalent algorithm LSQR based on the Lanczos bidiagonalization process is an often recommended alternative. In this paper, the achievable accuracy of different conjgate gradient and Lanczos methods in finite precision is studied. It is shown that an implementation of algorithm CGLS in which the residual s k =A T (b-Ax k ) of the normal equations is recurred will not in general achieve accurate solutions. The same conclusion holds for the method based on Lanczos bidiagonalization with starting vector A T b. For the preferred implementation of CGLS we bound the error ||r-r k || of the computed residual r k . Numerical tests are given that confirm a conjecture of backward stability. The achievable accuracy of LSQR is shown to be similar. The analysis essentially also covers the preconditioned case.