INTERNATIONAL JOURNAL OF c © 2008 Institute for Scientific INFORMATION AND SYSTEMS SCIENCES Computing and Information Volume 4, Number 1, Pages 15–29 HARD CASES FOR CONJUGATE GRADIENT METHOD

Abstract. The Conjugate Gradient (CG) method is often used to solve a positive definite linear system Ax = b. This paper analyzes two hard cases for CG or any Krylov subspace type methods by either analytically finding the residual formulas or tightly bound the residuals from above and below, in contrast to existing results which only bound residuals from above. The analysis is based on a general framework to estimate CG and GMRES residuals for certain linear systems with normal A, and the framework may potentially be useful elsewhere