Estimating the Attainable Accuracy of Recursively Computed Residual Methods
Author:
- Anne GreenbaumAGAnne Greenbaum
- 1 July 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 18 (3) , 535-551
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.
Keywords
This publication has 21 references indexed in Scilit:
- Relations between Galerkin and Norm-Minimizing Iterative Methods for Solving Linear SystemsSIAM Journal on Matrix Analysis and Applications, 1996
- A composite step bi-conjugate gradient algorithm for nonsymmetric linear systemsNumerical Algorithms, 1994
- An Implementation of the QMR Method Based on Coupled Two-Term RecurrencesSIAM Journal on Scientific Computing, 1994
- Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient ComputationsSIAM Journal on Matrix Analysis and Applications, 1992
- QMR: a quasi-minimal residual method for non-Hermitian linear systemsNumerische Mathematik, 1991
- Behavior of slightly perturbed Lanczos and conjugate-gradient recurrencesLinear Algebra and its Applications, 1989
- Numerical stability of descent methods for solving linear equationsNumerische Mathematik, 1984
- Bidiagonalization of Matrices and Solution of Linear EquationsSIAM Journal on Numerical Analysis, 1974
- The N‐Step Iteration ProceduresJournal of Mathematics and Physics, 1955
- Methods of conjugate gradients for solving linear systemsJournal of Research of the National Bureau of Standards, 1952