Does conjugate gradient compute A inverse?

No. It builds an approximate solution through matrix-vector products and vector operations.

Must A be explicitly stored?

No, provided an appropriate operator computes its action accurately and satisfies the required structure.

Is it the same as gradient descent?

No. Its directions combine residual information to exploit conjugacy for the quadratic problem.

AI Glossary / Mathematics and optimization / Advanced

Conjugate gradient

Definition

Conjugate gradient is an iterative method for solving a linear system Ax = b when A is symmetric positive definite in the real-valued setting. It builds search directions that are conjugate with respect to A, allowing progress through a sequence of increasingly rich approximation spaces without explicitly computing the matrix inverse.

What it means

The method is especially useful for large systems where multiplying a vector by A is practical but storing or computing a full factorization is costly. It can work with an operator that computes matrix-vector products, rather than requiring every matrix entry to be stored.

Conjugate directions satisfy p_i transpose A p_j = 0 for different directions. This is orthogonality measured through A, not necessarily ordinary perpendicularity. The linear method is related to minimizing the strictly convex quadratic one-half x transpose A x minus b transpose x.

How it works

Start with an estimate x_0 and residual r_0 = b − Ax_0. Set the first search direction p_0 equal to r_0. At each step, use alpha = (r transpose r)/(p transpose A p), update x to x + alpha p, and update the residual to r − alpha Ap.

If the residual has not met the stopping criterion, calculate beta as the new squared residual norm divided by the old one. The next direction is the new residual plus beta times the preceding direction. Matrix-vector products, inner products and vector updates drive the computation.

In exact arithmetic, the standard method reaches the solution in at most n iterations for an n-dimensional positive-definite system. Floating-point arithmetic can disrupt conjugacy, so practical solvers use tolerances and monitor convergence. Preconditioning can improve the effective conditioning, but its construction and application also cost time.

Three practical examples

1. Scientific simulation: solve a suitable positive-definite system arising from a discretized physical model. Sparse matrix-vector products can make each iteration manageable.

2. Regularized regression: solve a positive-definite linear system associated with a quadratic fitting objective. The matrix structure and conditioning still need checking; ordinary conjugate gradient is not a universal solver for every regression formulation.

3. Optimization subproblems: approximately solve an appropriate quadratic system inside a larger algorithm. The inner accuracy should be sufficient for the outer task rather than automatically pushed to machine precision.

Think of it this way

Imagine navigating a stretched bowl-shaped surface. Repeatedly following the steepest downhill direction can zigzag. Conjugate gradient combines new residual information with an earlier direction so that successive searches account for the bowl's geometry instead of simply repeating ordinary steepest-descent moves.

Worked example

Consider an original system with A = [[4, 1], [1, 3]] and b = (1, 2). The matrix is symmetric, its first leading principal minor is four, and its determinant is eleven, so it is positive definite.

Start from x_0 = (0, 0). Then r_0 = p_0 = (1, 2), and Ap_0 = (6, 7). The first step length is alpha_0 = 5/20 = 1/4. This gives x_1 = (1/4, 1/2) and r_1 = (−1/2, 1/4).

The new squared residual norm is 5/16, compared with the old value five. Thus beta_0 = 1/16, and p_1 = (−1/2, 1/4) + (1/16)(1, 2) = (−7/16, 3/8).

Multiplying gives Ap_1 = (−11/8, 11/16). Therefore p_0 transpose A p_1 = −11/8 + 2 × 11/16 = 0, explicitly confirming conjugacy. Their ordinary inner product is 5/16, so these directions are not ordinarily perpendicular.

The second step length is alpha_1 = 4/11. Updating gives x_2 = (1/11, 7/11). Direct substitution yields Ax_2 = (4/11 + 7/11, 1/11 + 21/11) = (1, 2), so the residual is exactly zero.

The two-step result was checked with exact rational arithmetic. It illustrates the finite-dimensional exact-arithmetic property, not a promise that large floating-point systems always terminate exactly or require only two iterations. In a practical application, the final residual should be interpreted alongside scaling and conditioning.

Illustrative case study

In a fictional simulation team, engineers replace a memory-intensive linear solve with conjugate gradient after confirming that the system has the required positive-definite structure. The first implementation reduces memory use but takes many iterations on poorly scaled instances.

They test a suitable preconditioner and compare total solve time, including its setup and application. They also check the residual against the original system instead of reporting only the number of iterations or the change between successive estimates.

The evaluation shows whether the revised solver meets the simulation's accuracy and resource requirements. Fewer iterations alone would not establish a better overall method if each preconditioned step became much more expensive.

Common misconceptions and mistakes

Ordinary linear conjugate gradient is not appropriate for every square matrix. Nonsymmetric or indefinite systems require suitable alternatives or carefully justified variants.

Conjugacy concerns search directions under the A inner product. It is not the same as taking complex conjugates, and the method's name does not mean every gradient vector is conjugate to every other one.

The at-most-n result assumes exact arithmetic. Rounding changes the practical behavior, especially for difficult conditioning.

A small residual does not always imply a proportionally small solution error. Conditioning connects the two. Also, nonlinear conjugate-gradient methods use related ideas but have different update and convergence considerations.

Business use

Conjugate gradient can reduce the resource cost of suitable large linear solves in simulation, estimation and optimization workflows. Assess memory, matrix-vector product cost, preconditioner cost and the accuracy needed by the surrounding application.

Document why the matrix assumptions hold and how convergence is checked. An iteration limit reached without the required accuracy should be reported as incomplete convergence, not converted into a successful result because an output vector exists.

Check your understanding

What is the first step length in the example?

Answer: One-quarter.

What distinguishes the two directions?

Answer: Their A-weighted inner product is zero, although their ordinary inner product is not.

What verifies the final solution?

Answer: Multiplying (1/11, 7/11) by A reproduces b exactly.

Related terms

Residual
Preconditioning
Condition number
Symmetric positive-definite matrix
Krylov subspace
quadratic optimization
nonlinear conjugate gradient

Learn next

Reproduce both iterations with exact fractions, then repeat using finite precision. Compare residual norms and solution errors for a more poorly conditioned positive-definite matrix, with and without a suitable preconditioner.

Residual

Sources

Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, 1994: https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf

SciPy, conjugate-gradient solver requirements and convergence interface: https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.cg.html

The rational-arithmetic example and simulation case are original illustrations.

Previous: Conjoint analysis Next: Conjugate prior