Conjugate Gradient
Follow conjugate search directions to solve a positive-definite system and watch its residual disappear.
Free theory articleFollow conjugate search directions to solve a positive-definite system and watch its residual disappear.
Concept & interpretation
The Conjugate Gradient (CG) method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite (SPD). It is often used as an iterative algorithm for systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition.
Experiment
Open the Conjugate Gradient module to interact with this concept:
- Set A11 to 3, A12 to 1, and A22 to 2. Set b1 to 2 and b2 to 1.
- Set Updates to 1. The status will show "Finite iterate; not yet converged". The iterate is [5/9, 5/18] and the residual is [1/18, -1/9].
- Increase Updates to 2. The algorithm converges exactly to [3/5, 1/5] with a zero residual.
- Change A11 to 1, A12 to 2, and A22 to 1. This matrix is not positive-definite because its determinant is 1*1 - 2*2 = -3. The module will reject it and display "Outside SPD domain".
- Set b1 to 0 and b2 to 0 with an SPD matrix. The initial residual is zero, so the algorithm stops immediately without dividing by zero.