Conjugate Gradient Method (CG)⚓︎
Introduction to Conjugate Gradient Algorithm⚓︎
Algorithm
( Conjugate Gradient Method ):
Compute
For
- Step length:
; - Approximate solution:
; - Residual:
; - Improvement this step:
; - Search direction:
;
End
The most expensive part for computation of this algorithm is computing
Question
: How can we derive the CG method?
Derivation from Projection Method⚓︎
Perform the projection method with
where
Based on the requirement of Projection Method:
Since
where
Claim
: We can find (How to prove?):
Proof
:
Then:
End of proof.
Because:
We have:
Also:
Properties of Conjugate Gradient Method⚓︎
It can be proved that CG satisfies the following properties:
.
Note that for
In this way we prove the equivalence of formulas.