Previous Index Next
Page 18
(previous) (Page 000018) (next)
 
18

where dr=gO-r and E is a matrix whose components are

aévtOtal(r)/ariarj . Since grad Vtotal(ro) is zero by definition,
one obtains an equation for 5;

6r = —F_l(r)grad V(E) (21)
This method, called the Newton—Raphson method, yields the minimum in
one step, provided the higher terms in the Taylor series are neg—
ligible, which is approximately true for points near the minimum

of any well behaved function. Therefore, starting near the minimum,
a few iterations of Equation (21) converge progressively to the
minimum. Such a convergence is called "quadratic convergence"
since for a quadratic function the higher terms are precisely zero
and the exact minimum is reached by Equation (21) in one step.
There are however difficulties with this algorithm. First, when

E is far away from the minimum the method may be unstable, namely

6; derived by Equation (21) may move r away from minimum. Second,
the inverse of g does not exist if E is singular, so that}?—1 in
Equation (21) must be replaced by 'E+,the "generalized inverse”
matrix . Third, when Vtotal is a function of a great number of
variables, as is the case for Vtotal of biological macromolecules,
the calculation, storage and manipulation of the matrix F becomes
technically unmanageable. “

To overcome these difficulties, new methods have been developed
which combine the advantages of the steepest descent and the Newton-
Raphson methods but avoid their pitfalls. Such methods are both
stable and fast converging. Among these the most suitable for
energy calculations in'molecular biology is the so called “conjugate
gradient" methodl7. Its great advantage is that like the steepest
descent method its requirements for computer memory space is pro—
portional to the number cm? variables (3n.for a molecules of n
atoms), while other methods, like the Newton—Raphson, require
memory space proportional to the square of the number of variables.
We shall explain here the basic ideas behind the "conjugate gradient"
method, while skipping the mathematical details. '

The method starts at the first iteration like the steepest
descent, by a "line search" along the direction of the gradient.
At the second, third, or in general at the i'th iteration, the new
direction of the line search is determined by a linear combination
of the gradient at the present point (i) and the direction of line
search at the previous point (1-1). The coefficients of the linear
combination are chosen, very cleverly,such that if the function to
be minimized is quadratic to a good approximation then two major
goals are achieved: 1) Each new direction of search is linearly
independent of all previous directions of search. 2) The minimum
along the direction of the line search at each iteration is also
the minimum of the function in the whole subspace spanned by all

Previous Index Next