Estimating the Attainable Accuracy of Recursively Computed ResidualMethods

Many conjugate gradient-like methods for solving linear systems $Ax=b$ use recursion formulas for updating residual vectors, instead of computing the residuals directly. For such methods it is shown that the difference between the actual residuals and the updated approximate residual vectors generated in finite precision arithmetic depends on the machine precision $\epsilon$ and on the maximum norm of an iterate divided by the norm of the true solution. It is often observed numerically, and can sometimes be proved, that the norms of the updated approximate residual vectors converge to zero, or, at least, become orders of magnitude smaller than the machine precision. In such cases, the actual residual norm reaches the level $\epsilon \| A \| \| x \|$ times the maximum ratio of the norm of an iterate to that of the true solution. Using exact arithmetic theory to bound the size of the iterates, we give a priori extimates of the size of the final residual for a number of algorithms