ExtendedSource checked

Conjugate Gradient

Solves large symmetric positive-definite linear systems with iterative search directions.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Advanced
Family: Iterative Linear Solver
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 7
Code example: Not ready
Visualization: Ready
Aliases: CG

Overview

Conjugate Gradient improves a solution along directions that avoid undoing previous progress.

Core Concepts

numeric approximationmatrix operationresidual updateobjective functioniterative linear solverconvergence checkerror control

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(k n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Conjugate Gradient when you need to build conjugate search directions.
Use it for sparse linear systems with inputs like symmetric positive-definite matrix.
Use it when an approximate numeric result is acceptable and the input assumptions are satisfied.
Use it when the Iterative Linear Solver tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when rounding error, ill-conditioning, or convergence failure would hide the real answer.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not approximate solution vector.

What It Does

Builds conjugate search directions
Minimizes the quadratic error of a linear system

Use Cases

Sparse linear systems
Physics simulation
Optimization subproblems

Inputs

Symmetric positive-definite matrix
Right-hand-side vector
Initial guess

Outputs

Approximate solution vector

Key Formulas (1)

Search update

x_next = x + α · direction

x_next = x + alpha * direction

Moves along a conjugate direction chosen to reduce the residual.

Pseudocode

1.Start with an initial residual
2.Choose the first search direction
3.Move along the direction by an optimal step
4.Update the residual
5.Build the next conjugate direction

Canonical Example

Input: equation = x^2 - 9 = 0 or matrix system Ax = b
Output: approximate numeric solution
Explanation: Conjugate Gradient: The method iteratively or algebraically approximates the requested mathematical result.

Implementation Notes

Keep the input contract explicit: Symmetric positive-definite matrix; Right-hand-side vector; Initial guess.
Use this step as the implementation spine: Start with an initial residual.
Then preserve the next state change: Choose the first search direction.
Prefer trusted numeric libraries for matrix operations once the concept is validated.
Use small examples with known answers to verify the numeric update before scaling up.

Common Pitfalls

Preconditioning can dramatically improve Conjugate Gradient convergence.
Ignoring singular or ill-conditioned inputs can produce unstable numeric results.
Stopping based only on iteration count instead of checking residual, tolerance, or error.
Returning approximate solution vector without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show search directions crossing a quadratic surface without repeating work.

Step 1 of 5: Start with an initial residual

conjugate-directions

Notes

Conjugate Gradient operates in O(k n) time and O(n) space within the Iterative Linear Solver family. Key governing relation: x_next = x + alpha * direction. Often compared with Jacobi Method and Gauss-Seidel Method.