Abstract
The standard iterative refinement procedure for improving an approximate solution to the least squares problem min(x) parallel to b - Ax parallel to(2), where A is an element of R-mxn with m >= n has full rank, is based on solving the (m n) x (m n) augmented system with the aid of a QR factorization. In order to exploit multiprecision arithmetic, iterative refinement can be formulated to use three precisions, but the resulting algorithm converges only for a limited range of problems.
We build an iterative refinement algorithm called GMRES-LSIR, analogous to the GMRES-IR algorithm developed for linear systems [E. Carson and N.
J. Higham, SIAM T.
Set. Comput., 40 (2018), pp.
A817-A8471, that solves the augmented system using GMRES preconditioned by a matrix based on the computed QR factors. We explore two left preconditioners; the first has full off-diagonal blocks, and the second is block diagonal and can be applied in either left-sided or split form.
We prove that for a wide range of problems the first preconditioner yields backward and forward errors for the augmented system of order the working precision under suitable assumptions on the precisions and the problem conditioning. Our proof does not extend to the block diagonal preconditioner, but our numerical experiments show that with this preconditioner the algorithm performs about as well in practice.
The experiments also show that if we use MINRES in place of GMRES then the convergence is similar for sufficiently well conditioned problems but worse for the most ill conditioned ones.