Conjugate Gradient
The conjugate gradient method solves symmetric positive-definite Ax=b, converging in n steps (in exact arithmetic) using A-conjugate directions.
Purpose
To solve large sparse symmetric positive-definite linear systems efficiently and iteratively.
Mechanism
It searches along A-conjugate (not orthogonal) directions, each step optimal within the Krylov subspace. It needs no explicit A, only matrix-vector products. Preconditioned CG accelerates convergence. Complexity O(√κ log(1/ε)).
Use cases
- Large-scale linear solving
- Optimization algorithms
- Scientific computing