Conjugate Gradient Method
Conjugate Gradient Method for Linear Systems · Also known as: CG method, Krylov subspace method
The Conjugate Gradient (CG) Method is an iterative algorithm for solving large sparse symmetric positive-definite linear systems Ax = b, developed by Hestenes and Stiefel in 1952. It is one of the most widely used iterative solvers in scientific computing because it converges in at most n iterations for an n × n matrix and typically requires far fewer.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use CG for large sparse symmetric positive-definite systems where storing the full matrix is infeasible. Ideal for discretized PDEs and eigenvalue problems. For non-symmetric systems, use GMRES or BiCG. Not suitable for dense matrices where direct factorization (LU, Cholesky) is more efficient.
Strengths & limitations
- Converges in at most n iterations for n × n matrices (theoretical bound often met in practice)
- Memory efficient: requires only O(n) storage for vectors, not O(n²) for the matrix
- Convergence rate depends on condition number; preconditioning can dramatically accelerate convergence
- Parallelizes well; matrix-vector products dominate computation and scale across processors
- Requires symmetric positive-definite matrices; variants (MINRES, GMRES) needed for other cases
- Sensitive to round-off errors in finite precision; loss of orthogonality can slow convergence
- Without good preconditioning, ill-conditioned systems (large condition numbers) converge slowly
- Only suitable for linear systems; nonlinear problems require other approaches
Frequently asked
What does conjugacy mean and why is it important?
Two vectors p_i and p_j are conjugate with respect to A if p_i^T A p_j = 0. This ensures each search direction minimizes the error in its own subspace, preventing redundant iterations and guaranteeing finite convergence.
Why is preconditioning so critical for CG?
CG's convergence rate is O(√κ), where κ is the condition number of A. Preconditioning solves an equivalent problem with lower condition number, often reducing iterations from O(κ) to O(√κ). For ill-conditioned systems, preconditioner choice is as important as CG itself.
When should I use CG versus direct factorization (LU)?
For small dense systems (n < 5000), direct methods are faster and more stable. For large sparse systems, CG and preconditioned CG are superior: O(n²) or O(n^1.5) iterations times O(nnz) cost per iteration beats O(n³) dense factorization. Memory also favors CG.
How do I detect loss of orthogonality in finite precision?
Compute true residual r = b - Ax periodically, not just the recurrence relation. If ||r_true|| >> ||r_recurrence||, orthogonality is lost; restart CG or use reorthogonalization.
Sources
- Hestenes, M. R., & Stiefel, E. (1952). Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 409–436. DOI: 10.6028/jres.049.044 ↗
- Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM. DOI: 10.1137/1.9780898718003 ↗
- Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer. DOI: 10.1007/978-0-387-40065-5 ↗
How to cite this page
ScholarGate. (2026, June 3). Conjugate Gradient Method for Linear Systems. ScholarGate. https://scholargate.app/en/numerical-methods/conjugate-gradient-method
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
Compare side by side →