Accuracy of preconditioned CG-type methods for least squares problems

AbstractThe conjugate gradient method with IMGS, an incomplete modified version of Gram-Schmidt orthogonalization to obtain an incomplete orthogonal factorization preconditioner, applied to the normal equations (PCGLS) is often used as the basic iterative method to solve the linear least squares problems. In this paper, a detailed analysis is given for understanding the effect of rounding errors on IMGS and determining the accuracy of computed solutions of PCGLS with IMGS for linear least squares problems in finite precision. It is shown that for a consistent system, the difference between the true residuals and the updated approximate residual vectors generated depends on the machine precision ε, on the maximum growth in norm of the iterates over their initial values, the norm of the true solution, and the condition number of R which is affected by the drop set in incomplete Gram-Schmidt factorization. Similar results are obtained for the difference between the true and computed solution for inconsistent systems. Numerical tests are carried out to confirm the theoretical conclusions