Preconditioned conjugate gradient method: Difference between revisions

Revision as of 18:26, 11 April 2007

Revision as of 21:24, 14 May 2007

Line 3:

:<math>A x= b.\,</math>

where <math>A</math> is symmetric [positive definite]. If the [[matrix]] '<math>A'</math> is [[ill-conditioned]], i.e. it has a large [[condition number]] <math>\kappa(A)</math>, it is often useful to use a [[preconditioner|preconditioning matrix]] <math>P^{-1}</math> that is chosen such that <math>P^{-1} \approx A^{-1}</math> and solve the system

:<math> P^{-1}Ax = P^{-1}b,\,</math>

instead.

The simplest preconditioner is a diagonal matrix that has just the diagonal elements of of <math>A</math>. This is known as Jacobi preconditioning or diagonal scaling. Since diagonal matrices are trivial to invert and store in memory, a diagonal preconditioner is a good starting point. More sophisticated choices must trade-off the reduction in <math>\kappa(A)</math>, and hence faster convergence, with the time spent computing <math>P^{-1}</math>.

==External links==

* [http://www.math-linux.com/spip.php?article55 Preconditioned Conjugate Gradient] – math-linux.com

* [http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf] - conjugate gradient without the agonizing pain (Jonathon Richard Shewchuck)

[[Category:Numerical linear algebra]]

{{math-stub}}