# Conjugate gradient method of Golub and van Loan

(Difference between revisions)
 Revision as of 05:34, 14 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Revision as of 08:15, 14 September 2005 (view source)Zxaar (Talk | contribs) Newer edit → Line 12: Line 12: === Algorithm === === Algorithm === + ---- - Allocate temperary vectors p,z,q
+ :  Allocate temperary vectors p,z,q
- Allocate temerary reals rho_0, rho_1 , alpha, beta
+ :  Allocate temerary reals rho_0, rho_1 , alpha, beta
- + :
- r := b - A[itex]\bullet[/itex]x
+ :  r := b - A[itex]\bullet[/itex]x
- for i := 1 step 1 until max_itr do + :
- solve (M[itex]\bullet[/itex]z = r )
+ :  for i := 1 step 1 until max_itr do - beta := rho_0 / rho_1
+ ::    solve (M[itex]\bullet[/itex]z = r )
- p := z + beta[itex]\bullet[/itex]p
+ ::      beta := rho_0 / rho_1
- q := A[itex]\bullet[/itex]p
+ ::      p := z + beta[itex]\bullet[/itex]p
- alpha = rho_0 / ( p[itex]\bullet[/itex]q  )
+ ::      q := A[itex]\bullet[/itex]p
- x := x + alpha[itex]\bullet[/itex]p
+ ::      alpha = rho_0 / ( p[itex]\bullet[/itex]q  )
- r := r - alpha[itex]\bullet[/itex]q
+ ::      x := x + alpha[itex]\bullet[/itex]p
- rho_1 = rho_0
+ ::      r := r - alpha[itex]\bullet[/itex]q
- end (i-loop) + ::      rho_1 = rho_0
- + :  end (i-loop) - deallocate all temp memory
+ :
- return TRUE
+ :  deallocate all temp memory
- + :  return TRUE
+ ----

## Conjugate gradient method

Conjugate gradient method could be summarized as follows

### System of equation

For the given system of equation
Ax = b ;
b = source vector
x = solution variable for which we seek the solution
A = coefficient matrix

M = the precondioning matrix constructued by matrix A

### Algorithm

Allocate temperary vectors p,z,q
Allocate temerary reals rho_0, rho_1 , alpha, beta

r := b - A$\bullet$x

for i := 1 step 1 until max_itr do
solve (M$\bullet$z = r )
beta := rho_0 / rho_1
p := z + beta$\bullet$p
q := A$\bullet$p
alpha = rho_0 / ( p$\bullet$q )
x := x + alpha$\bullet$p
r := r - alpha$\bullet$q
rho_1 = rho_0
end (i-loop)

deallocate all temp memory
return TRUE

## Reference

Ferziger, J.H. and Peric, M. 2002. "Computational Methods for Fluid Dynamics", 3rd rev. ed., Springer-Verlag, Berlin.