DIFFERENTIATING THE METHOD OF CONJUGATE GRADIENTS

作者：Gratton Serge^*; Titley Peloquin David; Toint Philippe; Ilunga Jean Tshimanga

来源：SIAM Journal on Matrix Analysis and Applications, 2014, 35(1): 110-126.

DOI：10.1137/120889848

• conjugate gradients algorithm
• Lanczos algorithm
• perturbation analysis
• linearization
• automatic differentiation

The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax = b, where A is an element of R-n (x) (n) is symmetric positive definite. Let x(k) denote the kth iterate of CG. This is a nonlinear differentiable function of b. In this paper we obtain expressions for J(k), the Jacobian matrix of xk with respect to b. We use these expressions to obtain bounds on parallel to J(k)parallel to(2), the spectral norm condition number of x(k), and discuss algorithms to compute or estimate J(k)v and J(k)(T)v for a given vector v.

• 出版日期2014