Computational Physics - Department of Physics

192 6 Linear Algebra

The choice of relaxation factor is not necessarily easy, anddepends upon the properties of the
coefficient matrix. For symmetric, positive-definite matrices it can be proven that 0 <ω< 2
will lead to convergence, but we are generally interested infaster convergence rather than
just convergence.

6.6.4 Conjugate Gradient Method

The success of the Conjugate Gradient method for finding solutions of non-linear problems is
based on the theory for of conjugate gradients for linear systems of equations. It belongs to
the class of iterative methods for solving problems from linear algebra of the type

Aˆxˆ=bˆ.

In the iterative process we end up with a problem like

ˆr=bˆ−Aˆˆx,

whererˆis the so-called residual or error in the iterative process.
The residual is zero when we reach the minimum of the quadratic equation

P(xˆ) =^1

2

ˆxTAˆxˆ−xˆTbˆ,

with the constraint that the matrixAˆis positive definite and symmetric. If we search for a
minimum of the quantum mechanical variance, then the matrixAˆ, which is called the Hessian,
is given by the second-derivative of the variance. This quantity is always positive definite. If
we vary the energy, the Hessian may not always be positive definite.
In the Conjugate Gradient method we define so-called conjugate directions and two vectors
ˆsandˆtare said to be conjugate if
ˆsTAˆˆt= 0.

The philosophy of the Conjugate Gradient method is to perform searches in various conjugate
directions of our vectorsxˆiobeying the above criterion, namely

xˆTiAˆxˆj= 0.

Two vectors are conjugate if they are orthogonal with respect to this inner product. Being
conjugate is a symmetric relation: ifˆsis conjugate toˆt, thenˆtis conjugate toˆs.
An example is given by the eigenvectors of the matrix

vˆTiAˆvˆj=λvˆTiˆvj,

which is zero unlessi=j.
Assume now that we have a symmetric positive-definite matrixAˆ of sizen×n. At each
iterationi+ 1 we obtain the conjugate direction of a vector

xˆi+ 1 =xˆi+αipˆi.

We assume thatpˆiis a sequence ofnmutually conjugate directions. Then thepˆiform a basis
ofRnand we can expand the solutionAˆxˆ=bˆin this basis, namely

xˆ=

n

∑

i= 1

αipˆi.