On Error Estimation in the Conjugate Gradient Method: Normwise Backward Error

Abstract

Using an idea of Duff and Vomel [BIT, 42 (2002), pp. 300-322 ] we suggest a simple algorithm that incrementally estimates the 2-norm of Jacobi matrices that are available during the conjugate gradient (CG) computations. The estimate can be used, e.g., in stopping criteria based on the normwise backward error.

A numerical experiment predicts that the estimate approximates the 2-norm of A with a sufficient accuracy.

Keywords

• conjugate gradients
• normwise backward error
• incremental norm estimation