Conjugate Gradient Solver

Introduction: Conjugate Gradient for SPD Linear Systems

Conjugate gradient (CG) solves a large linear system $Ax=b$ when $A$ is symmetric and positive definite. Direct methods such as Gaussian elimination can require substantial computation and memory, whereas CG improves an approximate solution iteratively without forming a matrix factorization. That makes the method particularly useful for sparse systems produced by partial-differential-equation discretizations in engineering and physics.

Core Idea: Conjugate Gradient as Quadratic Minimization

For a symmetric positive-definite system, conjugate gradient treats the solve as minimization of the quadratic function $f\left(x\right)=\frac{1}{2}{x}^{T}Ax-b^{T}x$. Beginning with an initial guess, CG moves through conjugate directions so that each step removes an error component independently under the $A$-inner product. The residual vector $r$ determines those directions, and each update minimizes the quadratic along the current direction. In exact arithmetic, CG reaches the solution in at most $n$ steps for an $n$-dimensional system; finite-precision arithmetic can alter that behavior.

Conjugate Gradient Update Formulas

In a conjugate gradient iteration, the residual is $r^{\left(k\right)}=b-A{x}^{\left(k\right)}$, and the method chooses a search direction $p_k$. The step size ${\alpha }_k$ is

Formula: α_k = (r^(k) r^(k)) / (p_k A p_k)

${\alpha }_k=\frac{r^{\left(k\right)}{r}^{\left(k\right)}}{p_{k}A{p}_k}$

For this conjugate gradient update, the new approximation is $x^{(k+1)}=x^{\left(k\right)}+{\alpha }_k{p}_k$. The residual is then updated, and the coefficient ${\beta }_k$ makes the next search direction conjugate:

Formula: β_k = (r^(k+1) r^(k+1)) / (r^(k) r^(k))

${\beta }_k=\frac{r^{(k+1)}{r}^{(k+1)}}{r^{\left(k\right)}{r}^{\left(k\right)}}$

The next conjugate gradient direction is $p_{k+1}=r^{(k+1)}+{\beta }_k{p}_k$. Repeating these updates drives the approximation toward the solution while retaining conjugacy among the search directions.

Conjugate Gradient 2×2 Example

This small conjugate gradient example solves $\left[\begin{array}{cc}4& 1\\ 1& 3\end{array}\right]$$x$ $=$ $\left[\begin{array}{c}1\\ 2\end{array}\right]$. With the zero vector as the starting guess, the initial residual is $b$ and $p_0$ equals that residual. CG updates the guess and residual from the calculated ${\alpha }_0$; in exact arithmetic this two-dimensional SPD system is solved within two iterations. The solution is approximately $\left(0.0909,,,0.6364\right)$, which agrees with the exact solution.

How to Use This Conjugate Gradient Calculator

This conjugate gradient calculator accepts every displayed coefficient of the matrix and the corresponding right-hand-side entries. To solve a 2×2 system, leave all entries in the third row and third column, including $b_3$, blank; otherwise, provide all entries for a 3×3 system. Enter the number of CG iterations and press Solve. The script begins at the zero vector and displays the final approximation to six decimal places. It does not test whether the supplied matrix is symmetric positive definite, so a matrix outside that class can fail to converge or produce an unsuitable result.

For a reliable CG calculation, enter matching off-diagonal coefficients when the matrix is intended to be symmetric: the value for $a_{12}$ should equal the value for $a_{21}$, with the same check applying to the third-row and third-column pairs in a 3×3 system. The iteration count is not a tolerance setting. It simply determines how many update cycles the calculator attempts before reporting its current approximation. Comparing results from successive iteration counts can help reveal whether the approximation has stabilized for the entered system.

Advantages of Conjugate Gradient for SPD Systems

Conjugate gradient is valuable for large, sparse, symmetric positive-definite systems because each iteration mainly uses matrix-vector products and vector operations. That pattern avoids the storage cost of a dense factorization when most matrix entries are zero. Scientific-computing applications include finite-element analysis, fluid models, and optimization problems whose linear systems meet the SPD requirement. The algorithm also connects linear algebra directly to quadratic optimization: minimizing the quadratic produces the system solution.

Using this CG calculator makes the dependence on the matrix and iteration count concrete. Try a symmetric positive-definite matrix, compare short and longer runs, and observe how the displayed approximation changes. Difficultly conditioned systems can require more iterations; preconditioning can improve convergence in larger implementations, but this calculator does not apply a preconditioner.

Conjugate gradient remains a central numerical-linear-algebra technique because it combines a compact iteration with strong behavior on its intended class of systems. Exploring the iterations here provides context for related Krylov-subspace methods, multigrid methods, and optimization algorithms used in computational science. In this small calculator, the reported vector is useful for inspecting the iteration itself rather than for replacing the diagnostic checks used in production numerical software. A changing result after additional iterations can indicate that the requested solve has not yet settled, while an invalid matrix can make the usual CG interpretation unavailable.

Step-by-Step Conjugate Gradient Worked Example

This worked conjugate gradient example uses the 3×3 SPD system

$\left[\begin{array}{ccc}4& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$ $x$ $=$ $\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right]$.

For this CG solve, the zero initial vector makes the initial residual equal to $b$, so the first search direction is $p_0=b$. The first step size is ${\alpha }_0=\frac{1}{3}$, giving $x_1=0.3333,0,0.3333$. Further residual and direction updates follow the formulas above. In exact arithmetic, the three-dimensional SPD system converges within three iterations to $0.3333,-0.3333,0.6667$, illustrating how CG builds the solution through successive conjugate directions.

Conjugate Gradient Comparison With Other Solvers

This comparison places conjugate gradient among common linear-system solvers. CG is designed for sparse SPD matrices, while direct elimination is often preferable for small dense systems.

Although CG can scale well, it depends on positive definiteness and symmetry; it is not the appropriate method for indefinite or nonsymmetric systems. Preconditioners, including incomplete Cholesky approaches, can reduce iteration counts but require setup beyond this calculator’s implementation.

Conjugate Gradient Calculator Limitations and Assumptions

This conjugate gradient calculator omits preconditioning, adaptive stopping criteria, and positive-definiteness checks. Round-off error can weaken conjugacy over long runs, and production solvers may use techniques such as restarting or re-orthogonalization. The calculator uses the coefficients exactly as entered, so you must enter a symmetric matrix for the standard CG assumptions to apply. For nonsymmetric systems, methods such as biconjugate gradient or GMRES may be more appropriate.

The displayed result is the iterate after the requested number of steps, not an independently verified exact solution. In particular, the calculator does not display a residual norm or stop automatically when a user-selected accuracy goal has been met. Check the matrix, right-hand-side vector, and iteration count before relying on an approximation. For a 3×3 solve, all third-row and third-column entries must be supplied; leaving that entire group blank selects the 2×2 calculation instead.

Related Linear-System Calculators

For a direct comparison with conjugate gradient, try the Gauss-Seidel Calculator or the Gaussian Elimination Calculator. These solvers highlight why the matrix’s size, sparsity, and structure matter when choosing a numerical method.