Previous | Index | 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 |