(Difference between revisions)
 Revision as of 22:57, 17 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Latest revision as of 17:49, 26 August 2006 (view source)Nsoualem (Talk | contribs) (→External links) (4 intermediate revisions not shown) Line 2: Line 2: For the system of equations:
For the system of equations:
- :$AX = B$
+ :$A \cdot X = B$
The unpreconditioned conjugate gradient method constructs the '''i'''th iterate $x^{(k)}$  as an element of $x^{(k)} + span\left\{ {r^{(0)} ,...,A^{i - 1} r^{(0)} } \right\}$ so that  so that $\left( {x^{(0)} - \hat x} \right)^T A\left( {x^{(i)} - \hat x} \right)$  is minimized , where  ${\hat x}$ is the exact solution of $AX = B$.
The unpreconditioned conjugate gradient method constructs the '''i'''th iterate $x^{(k)}$  as an element of $x^{(k)} + span\left\{ {r^{(0)} ,...,A^{i - 1} r^{(0)} } \right\}$ so that  so that $\left( {x^{(0)} - \hat x} \right)^T A\left( {x^{(i)} - \hat x} \right)$  is minimized , where  ${\hat x}$ is the exact solution of $AX = B$.
This minimum is guaranteed to exist in general only if '''A''' is symmetric positive definite. The preconditioned version of these methods use a different subspace for constructing the iterates, but it satisfies the same minimization property over different subspace. It requires that the preconditioner '''M''' is symmetric and positive definite. This minimum is guaranteed to exist in general only if '''A''' is symmetric positive definite. The preconditioned version of these methods use a different subspace for constructing the iterates, but it satisfies the same minimization property over different subspace. It requires that the preconditioner '''M''' is symmetric and positive definite. + + ==External links== + * [http://www.math-linux.com/spip.php?article54 Conjugate Gradient Method] by N. Soualem. + * [http://www.math-linux.com/spip.php?article55 Preconditioned Conjugate Gradient Method] by N. Soualem. + ---- + Return to [[Numerical methods | Numerical Methods]]

## Basic Concept

For the system of equations: $A \cdot X = B$

The unpreconditioned conjugate gradient method constructs the ith iterate $x^{(k)}$ as an element of $x^{(k)} + span\left\{ {r^{(0)} ,...,A^{i - 1} r^{(0)} } \right\}$ so that so that $\left( {x^{(0)} - \hat x} \right)^T A\left( {x^{(i)} - \hat x} \right)$ is minimized , where ${\hat x}$ is the exact solution of $AX = B$.

This minimum is guaranteed to exist in general only if A is symmetric positive definite. The preconditioned version of these methods use a different subspace for constructing the iterates, but it satisfies the same minimization property over different subspace. It requires that the preconditioner M is symmetric and positive definite.