Linearizing the Method of Conjugate Gradients
by S. Gratton, D. Titley-Peloquin, Ph. L. Toint, J. Tshimanga
Report NTR-15-2012 September 2012
The method of conjugate gradients (CG) is widely used for the iterative
solution of large sparse systems of equations Ax=b, where A is symmetric
positive definite. Let xk denote the k-th iterate of CG. In this paper we
obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We
use this expression to obtain computable bounds on the spectral norm condition
number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v
for a given vector v. We also discuss several applications in which these
ideas may be used. Numerical experiments are performed to illustrate the
theory.