Differentiating the method of conjugate gradients (Q2877081)

This paper introduces a first-order perturbation analysis of the conjugate gradient method, which is widely used for the iterative solution of a large sparse system of linear equations \(Ax=b\), where the matrix \(A\in \mathbb{R} ^{n\times n}\) is symmetric positive definite. The authors derive an expression for \(J_{k}\), the Jacobian of \(x_{k}\) with respect to \(b\), in terms of the matrices arising from the Lanczos algorithm and some additional polynomials. This allows to obtain bounds on the normwise relative error \( \left\| J_{k}-A^{-1}\right\| _{2}/\left\| A^{-1}\right\| _{2},\) as well as on \(\left\| J_{k}\right\| _{2}\), the spectral norm condition number of \(x_{k}\) \ with respect to the perturbation in \(b\). Furthermore, algorithms for computing \(J_{k}v\) and \(J_{k}^{T}v\) for a given vector \(v\) are discussed. Detailed numerical experiments are reported to illustrate the presented theoretical results.