Linearizing the Method of Conjugate Gradients

The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations $Ax=b$, where $A\in\Re^{n\times n}$ is symmetric positive definite. Let $x_k$ denote the $k$--th iterate of CG. In this paper we obtain an expression for $J_k$, the Jacobian matrix of $x_k$ with respect to $b$. We use this expression to obtain computable bounds on the spectral norm condition number of $x_k$, and to design algorithms to compute or estimate $J_kv$ and $J_k^Tv$ 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.