Modified Newton methods matrix

The modified Newton methods evaluate the Hessian either analytically or by a numerical approximation in x and solve the linear system with a direct method that exploits matrix symmetry. 

The main difference between the modified Newton and quasi-Newton methods is in the evaluation of the Hessian the modified Newton methods approximate the matrix using local information in the neighborhood of xj the quasi-Newton methods update the matrix using gradient values evaluated at each iteration. 

The Gill-Murray modified Newton s method uses a Cholesky factorization of the Hessian matrix (Gill and Murray, 1974). The method is described in detail by Scales (1985). 

Newton variants are constructed by combining various strategies for the individual components above. These involve procedures for formulating Hk or Hk, dealing with structures of indefinite Hessians, and solving for the modified Newton search direction. For example, when Hk is approximated by finite differences, the discrete Newton subclass emerges.5 91-94 When Hk, or its inverse, is approximated by some modification of the previously constructed matrix (see later), QN methods are formed.95-110 When is nonzero, TN methods result,111-123 because the solution of the Newton system is truncated before completion. 

Numerical calculation has been carried out using a software interface which is based on the so-called "Method of lines" (14). Gear s backward difference formulas (15) are used for the time integration. A modified Newton s method with the internally generated Jacobian matrix is utilized to solve the nonlinear equations. ... 

Newton-type methods are very fast near the minimum. However, pure Newton methods can have serious convergence difficulties if the starting point is far from the minimum. Hence some modified form is nearly always required in practice. For least squares problems a Levenberg-Marquardt method is attractive, since it guarantees convergence by balancing steepest descent with Newton s method, and since the special structure of least squares problems allows for an easy approximation to the Hessian matrix. 

Methods that use the function gradient and Hessian belong to the Newton, modified Newton, and quasi-Newton method families. Some of these methods may also belong to the methods of conjugate directions category but, unlike previous methods, they explicitly use the Hessian matrix. 

Remark 1 Step 5 must still be specified. The matrix has been introduced to indicate that the matrix k is modified by a (low-rank) correction matrix. When step 5 is reset by a specific update formula, the quasi-Newton method is named after that update (for instance BFGS-method, DFP-method, Broyden-method,. ..). 

The simplest numerical method for a detailed geometrically and material nonlinear (GMN) analysis is the Newton-Raphson scheme (Crisfield 1979 Bathe 1995), which can be found in three forms (i) the full Newton-Raphson, which is the most accurate, but also the most time consuming, since the tangent stiffness of the structure has to be calculated and factorized within each iteration in the solution procedure (ii) the modified Newton-Raphson, which differs from the full Newton-Raphson in that the calculation and the factorization of the tangent stiffness matrix take place only in some iterations within each step, thus requiring in most cases a larger number of iterations per step but... 

The Newton-Raphson method may be computationally expensive in a multi dof problem because a new global stiffness matrix is used in each iterative step. In the Modified Newton-Raphson method, the same global stiffness matrix is used in all the iterative steps within an increment. This method requires more iterations to achieve convergence but each iteration is computed far more quickly. 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

The Newton-Raphson approach is another minimization method.f It is assumed that the energy surface near the minimum can be described by a quadratic function. In the Newton-Raphson procedure the second derivative or F matrix needs to be inverted and is then usedto determine the new atomic coordinates. F matrix inversion makes the Newton-Raphson method computationally demanding. Simplifying approximations for the F matrix inversion have been helpful. In the MM2 program, a modified block diagonal Newton-Raphson procedure is incorporated, whereas a full Newton-Raphson method is available in MM3 and MM4. The use of the full Newton-Raphson method is necessary for the calculation of vibrational spectra. Many commercially available packages offer a variety of methods for geometry optimization. 

---