Conjugate gradient

Conjugate gradient methods are well suited for solving both linear and non-linear systems of equations.

Linear conjugate gradient method

The linear system of equations can be expressed like this:

     $Ax = b$

where $x$ is the vector of variables, and $A$ is the matrix of coefficients (weights).

The problem of solving this system of linear equations is equivalent to the problem of minimizing the residual. For convenience we can also transform it into a problem of minimizing a convex quadratic function:

     $\phi(x) = \frac{1}{2}x^{T}Ax - b^{T}x$

From here we can see that the

The performance of linear conjugate gradient methods is dependent on distribution of eigenvalues of the coefficient matrix, and thus it can be improved by applying matrix preconditioning.