Quasi-Newton solution technique

ProductsAbaqus/Standard

A major contribution to the computational effort involved in nonlinear analysis is the solution of the nonlinear equations (Equation 1). In most cases Abaqus/Standard uses Newton's method to solve these equations, as described in Nonlinear solution methods in Abaqus/Standard. The principal advantage of Newton's method is its quadratic convergence rate when the approximation at iteration i is within the “radius of convergence”—that is, when the gradients defined by $K_{i}^{N M}$ provide an improvement to the solution. The method has two major disadvantages: the Jacobian matrix has to be calculated, and this same matrix has to be solved. The calculation of the Jacobian matrix is a problem because, in many important cases, it is difficult to derive the form of the matrix algebraically. The solution of the Jacobian is a problem because of the computational effort involved: as the problem size increases, the direct solution of the linear equations can dominate the entire computational effort.

There are a number of important nonlinear applications where the Jacobian is symmetric, is fairly well conditioned, and does not change greatly from one iteration to the next. Examples are implicit dynamic time integration with small time increments relative to the periods of the natural vibrations that participate in the response or small-displacement elastic-plastic analysis where the yielding is confined (such as occurs in many practical fracture mechanics applications). In such cases, especially when the problem is large, it can be less expensive to use an alternative to the Newton approach to the solution of the nonlinear equations. The “quasi-Newton” methods are such an approach; and Matthies and Strang (1979) have shown that, for systems of equations with a symmetric Jacobian matrix, the BFGS (Broyden, Fletcher, Goldfarb, Shanno) method can be written in a simple form that is especially effective on the computer and is successful in such applications. This method is implemented in Abaqus/Standard and is described in this section. The user must select this method explicitly: by default, Abaqus/Standard uses the standard Newton method.

The basis of quasi-Newton methods is to obtain a series of improved approximations to the Jacobian matrix, ${\tilde{K}}_{i}^{N M}$ , that satisfy the secant condition:

\begin{matrix} (1) & F^{N} (u_{i}^{M}) - F^{N} (u_{i - 1}^{M}) = {\tilde{K}}_{i}^{N M} (u_{i}^{M} - u_{i - 1}^{M}), \end{matrix}

so that ${\tilde{K}}_{i}^{N M}$ approaches $K_{i}^{N M}$ as the iterations proceed. Equation 1 is the basic quasi-Newton equation.

For convenience we define the change in the residual from one iteration to the next as

γ_{i}^{N} = F_{i}^{N} - F_{i - 1}^{N},

so that Equation 1 can be written

\begin{matrix} (2) & γ_{i}^{N} = {\tilde{K}}_{i}^{N M} c_{i}^{M}, \end{matrix}

where $c_{i}^{- M}$ is the correction to the solution from the previous iteration, defined in Nonlinear solution methods in Abaqus/Standard.

Matthies and Strang's implementation of the BFGS method is a computationally inexpensive method of creating a series of approximations to ${[{\tilde{K}}_{i}^{N M}]}^{- 1}$ that satisfy Equation 1 and retain the symmetry and positive definiteness of ${\tilde{K}}_{i}^{N M}$ . They accomplish this by updating ${[{\tilde{K}}_{i - 1}^{N M}]}^{- 1}$ to ${[{\tilde{K}}_{i}^{N M}]}^{- 1}$ using a “product plus increment” form:

\begin{matrix} (3) & {[{\tilde{K}}_{i}^{M N}]}^{- 1} = [I^{N L} - ρ_{i} c_{i}^{N} γ_{i}^{L}] {[{\tilde{K}}_{i - 1}^{P L}]}^{- 1} [I^{P M} - ρ_{i} γ_{i}^{P} c_{i}^{M}] + ρ_{i} c_{i}^{N} c_{i}^{M}, \end{matrix}

where

ρ_{i} = {(c_{i}^{M} γ_{i}^{M})}^{- 1} .

In the actual implementation of this version of the BFGS method, each ${[{\tilde{K}}_{i}^{M N}]}^{- 1}$ is not stored: rather, a “kernel” matrix, ${[{\tilde{K}}_{I}^{M N}]}^{- 1}$ , is used (as the decomposition of ${\tilde{K}}_{I}^{M N}$ ), and the update is accomplished by premultiplication of the kernel matrix by the terms

[I^{N L} - ρ_{j} c_{j}^{N} γ_{j}^{L}]

and postmultiplication of the kernel matrix by the terms

[I^{P M} - ρ_{j} γ_{j}^{P} c_{j}^{M}]

for $j = I + 1, I + 2, \dots i$ . Because of the form of these terms, the premultiplication and postmultiplication operations result in inner products of vectors and the scaling of vectors by constants: it is this organization that makes the method computationally attractive. However, too many such products ( $i - I$ being bigger than, say, 5–10) are not attractive, so usually a new kernel matrix is formed and stored after some iterations. In the Abaqus/Standard implementation the kernel is the actual Jacobian matrix $\partial F^{N} / \partial u^{M}$ . It is formed whenever a specified number of iterations have been done without obtaining a convergent solution; the default number of iterations is 8. Abaqus/Standard does not reform the kernel unless this value is exceeded, so the same kernel can be used for several increments if the BFGS updates are successful.

In general, the rate of convergence of the quasi-Newton method is slower than the quadratic rate of convergence of Newton's method, though faster than the linear rate of convergence of the modified Newton method.