Newton with Line Search Algorithm

From OpenSeesWiki
Revision as of 22:21, 3 March 2010 by Fmk (talk | contribs)
Jump to navigation Jump to search



This command is used to construct a NewtonLineSearch algorithm object which is introduces line search to the Newton-Raphson algorithm to solve the nonlinear residual equation. Line search increases the effectiveness of the Newton method when convergence is slow due to roughness of the residual. The command is of the following form:

algorithm NewtonLineSearch <-type $typeSearch> <-tol $tol> <-maxIter $maxIter> <-minEta $minEta> <-maxEta $maxEta>


$typeSearch line search algorithm. optional default is InitialInterpoled. valid types are:
Bisection, Secant, RegulaFalsi, InitialInterpolated
$tol tolerance for search. optional, defeulat = 0.8
$maxIter max num of iterations to try. optional, default = 10
$minEta a min <math>\eta\!</math> value. optional, default = 0.1
$maxEta a max <math>\eta\!</math> value. optional, default = 10.0


NOTES:


REFERENCES:

M.A. Crisfield, "Nonlinear Finite Element Analysis of Solids and Structures", Vol(1), Wiley

THEORY:

The rationale behin line search is that:

  • the direction <math>\Delta U\,\!</math> found by the Newton method is often a good direction, but the step size <math>\parallel\Delta U\parallel</math> is not.
  • It is cheaper to compute the residual for several points along <math>\Delta U\,\!</math> rather than form and factor a new system Jacobian

In NewtonLineSearch the regular Newton-Raphson method is used to compute the <math>\Delta U\,\!</math>, but the update that is used is modified. The modified update is:

<math> U_{n+1} = U_n + \eta \Delta U\,\!</math>


The different line search algorithms use different root finding methods to obtain <math>\eta\,\!</math>:

<math> s0 = \Delta U R(U_n),\!</math>
<math> s = \Delta U R(U_{n} + \eta \Delta U)\,\!</math>


InterpolatedLineSearch:

while (<math>R(U_{n} + \eta_{n+1}) \!</math> > $tol && count < $maxIter} {

<math> \eta_{n+1} = \frac{\eta_n *s0}{s0 -s_{n+1}} ,\!</math>

}


ReguaFalsi Line Search:

while (<math>R(U_{n} + \eta_{n+1})\!</math> > $tol && count < $maxIter} {

<math> \eta_{n+1} = \eta_U - \frac{s_U*(\eta_L-\eta_U)}{s_L-S_U} ,\!</math>
if <math> s_{n+1} * s_L < 0 \Rightarrow \eta_U = \eta_{n+1}, s_U = s_{n+1},\!</math>
if <math> s_{n+1} * s_U < 0 \Rightarrow \eta_L = \eta_{n+1}, s_L = s_{n+1},\!</math>

}

Bisection Line Search:

while (<math>R(U_{n} + \eta_{n+1})\!</math> > $tol && count < $maxIter} {

<math> \eta_{n+1} = \frac{\eta_L - \eta_U}{2.0} ,\!</math>
if <math> s_{n+1} * s_L < 0 \Rightarrow \eta_U = \eta_{n+1}, s_U = s_{n+1},\!</math>
if <math> s_{n+1} * s_U < 0 \Rightarrow \eta_L = \eta_{n+1}, s_L = s_{n+1},\!</math>

}

Secant Line Search:

while (<math>R(U_{n} + \eta_{n+1})\!</math> > $tol && count < $maxIter} {

<math> \eta_{n+1} = \eta_j - \frac{s_j*(\eta_{j-1}-\eta_j)}{s_{j-1}-S_j} ,\!</math>
if <math> s_{n+1} * s_L < 0 \Rightarrow \eta_U = \eta_{n+1}, s_U = s_{n+1},\!</math>
if <math> s_{n+1} * s_U < 0 \Rightarrow \eta_L = \eta_{n+1}, s_L = s_{n+1},\!</math>

}

Code Developed by: fmk

Retrieved from "https://opensees.ist.berkeley.edu/wiki/index.php?title=Newton_with_Line_Search_Algorithm&oldid=2778"