In numerical analysis, a quasi-Newton method is an iterative numerical method used either to find zeroes or to find local maxima and minima of functions via an iterative recurrence formula much like the one for Newton's method, except using approximations of the derivatives of the functions in place of exact derivatives. Newton's method requires the Jacobian matrix of all partial derivatives of a multivariate function when used to search for zeros or the Hessian matrix when used for finding extrema. Quasi-Newton methods, on the other hand, can be used when the Jacobian matrices or Hessian matrices are unavailable or are impractical to compute at every iteration. Some iterative methods that reduce to Newton's method, such as sequential quadratic programming, may also be considered quasi-Newton methods.
Search for zeros: root finding Newton's method to find zeroes of a function g {\displaystyle g} of multiple variables is given by x n + 1 = x n − [ J g ( x n ) ] − 1 g ( x n ) {\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})} , where [ J g ( x n ) ] − 1 {\displaystyle [J_{g}(x_{n})]^{-1}} is the right inverse of the Jacobian matrix J g ( x n ) {\displaystyle J_{g}(x_{n})} of g {\displaystyle g} evaluated for x n {\displaystyle x_{n}} . Strictly speaking, any method that replaces the exact Jacobian J g ( x n ) {\displaystyle J_{g}(x_{n})} with an approximation is a quasi-Newton method. For instance, the chord method (where J g ( x n ) {\displaystyle J_{g}(x_{n})} is replaced by J g ( x 0 ) {\displaystyle J_{g}(x_{0})} for all iterations) is a simple example. The methods given below for optimization refer to an important subclass of quasi-Newton methods, secant methods. Using methods developed to find extrema in order to find zeroes is not always a good idea, as the majority of the methods used to find extrema require that the matrix that is used is symmetrical. While this holds in the context of the search for extrema, it rarely holds when searching for zeroes. Broyden's "good" and "bad" methods are two methods commonly used to find extrema that can also be applied to find zeroes. Other methods that can be used are the column-updating method, the inverse column-updating method, the quasi-Newton least squares method and the quasi-Newton inverse least squares method. More recently quasi-Newton methods have been applied to find the solution of multiple coupled systems of equations (e.g. fluid–structure interaction problems or interaction problems in physics). They allow the solution to be found by solving each constituent system separately (which is simpler than the global system) in a cyclic, iterative fashion until the solution of the global system is found.
… excerpt ends here. Continue reading the full article.
