Optimization Online


Linearizing the Method of Conjugate Gradients

Serge Gratton(gratton***at***cerfacs.fr)
David Titley-Peloquin(dtitleyp***at***enseeiht.fr)
Philippe Toint(philippe.toint***at***fundp.ac.be)
Jean Tshimanga Ilunga(jtshimanga***at***serviware.com)

Abstract: 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.

Keywords: Conjugate Gradients Algorithm, Lanczos Algorithm, Perturbation Analysis, Linearization, Automatic Differentiation

Category 1: Applications -- Science and Engineering (Basic Sciences Applications )

Category 2: Nonlinear Optimization (Unconstrained Optimization )


Download: [PDF]

Entry Submitted: 09/09/2012
Entry Accepted: 09/09/2012
Entry Last Modified: 09/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society