Conjugate gradient method

In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems. In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive-definite. The conjugate gradient method is often implemented as an iterative algorithm, applicable to sparse systems that are too large to be handled by a direct implementation or other direct methods such as the Cholesky decomposition. Large sparse systems often arise when numerically solving partial differential equations or optimization problems. The conjugate gradient method can also be used to solve unconstrained optimization problems such as energy minimization. It was mainly developed by Magnus Hestenes and Eduard Stiefel who programmed it on the Z4. The biconjugate gradient method provides a generalization to non-symmetric matrices. Various nonlinear conjugate gradient methods seek minima of nonlinear equations. Suppose we want to solve the system of linear equations for the vector x, where the known n × n matrix A is symmetric (i.e., AT = A), positive-definite (i.e. xTAx > 0 for all non-zero vectors x in Rn), and real, and b is known as well. We denote the unique solution of this system by x ∗ {displaystyle mathbf {x} _{*}} . We say that two non-zero vectors u and v are conjugate (with respect to A) if Since A is symmetric and positive-definite, the left-hand side defines an inner product Two vectors are conjugate if and only if they are orthogonal with respect to this inner product. Being conjugate is a symmetric relation: if u is conjugate to v, then v is conjugate to u. Suppose that is a set of n mutually conjugate vectors (with respect to A). Then P forms a basis for R n {displaystyle mathbb {R} ^{n}} , and we may express the solution x∗ of A x = b {displaystyle mathbf {Ax} =mathbf {b} } in this basis: