Estimating the Attainable Accuracy of Recursively Computed Residual Methods

Abstract

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 estimates of the size of the final residual for a number of algorithms.

Locations

• SIAM Journal on Matrix Analysis and Applications - View
• eCommons (Cornell University) - View - PDF