An iterative algorithm for solving non-linear equations. The equation to be solved is
Here, the setting is such that linear equations can be solved by direct methods and hence it is assumed that is not very large or that special structure is present that permits efficient sparse matrix factorizations. Having said that, however, note that Broyden's method can be effective on certain very large problems [a14] having dense and very large Jacobians.
The Newton method updates a current approximation to a solution by
When a method is specified in terms of the -notation, it is understood that the iteration follows the rule with playing the role of and that of . The classic local convergence theory for Newton's method, [a4], [a13], [a7] states that if the initial iterate is sufficiently near and is non-singular, then the Newton iteration converges -quadratically to . This means that
hence the number of significant figures roughly doubles with each iteration.
The cost of implementation in Newton's method is both in evaluations of functions and Jacobians and in the matrix factorization required to solve the equation for the Newton step
which is an implicit part of (a2). One way to reduce the cost of forming and factoring a Jacobian is to do this only for the initial iterate and amortize the cost over the entire iteration. The resulting method is called the chord method:
The chord method will converge rapidly, although not as rapidly as Newton's method, if the initial iterate is sufficiently near and is non-singular. The chord iterates satisfy
The convergence implied by (a6) is fast if is a very good approximation to , and in such a case the chord method is recommended. The chord iteration can be quite slow or diverge completely even in cases where is accurate enough for Newton's method to perform well and converge -quadratically.
Quasi-Newton methods (cf. also Quasi-Newton method) update both an approximation to and one to . The simplest of these is Broyden's method, [a1]. If and are the current approximations to the and , then, similarly to Newton's method and the chord method,
The approximate Jacobian is updated with a rank-one transformation
In (a8), and .
In the case of a scalar equation , and Broyden's method is the well-known secant method
The simple implementation from [a6], described below, is based directly on an approximation of the inverse of the Jacobian. The approach is based on a simple formula, [a8], [a9]. If is a non-singular -matrix and , then is invertible if and only if . In this case
The formula (a10) is called the Sherman–Morrison formula.
To start with, note that it can be assumed that . The reason for this is that if is a good approximation to , then one may equally well apply Broyden's method to with and use the identity matrix as an approximation to . One way to do this is to form and factor and replace by . In this way, just like the chord method, the computation and factorization of is amortized over the entire iteration, but one also gets the faster convergence and enhanced robustness of Broyden's method.
In the context of a sequence of Broyden updates , for one has
one sees that
Since the empty matrix product is the identity, (a11) is valid for .
Hence the action of on (i.e., the computation of the Broyden step) can be computed from the vectors at a cost of floating point operations. Moreover, the Broyden step for the following iteration is
Since the product
must also be computed as part of the computation of , one can combine the computation of and as follows:
The major weakness in this formulation is the need to store two new vectors with each non-linear iteration. This can be reduced to one, [a5], [a13], at the cost of a bit more complexity. This makes Broyden's method a good algorithm for very large problems if the product can be evaluated efficiently.
A completely different approach, [a4], is to perform a QR-factorization (cf. Matrix factorization; Triangular matrix) of and update the QR-factors. This is more costly than the approach proposed above, requiring the storage of a full -matrix and an upper triangular -matrix and more floating point arithmetic. However, this dense matrix approach has better theoretical stability properties, which may be important if an extremely large number of non-linear iterations will be needed.
|[a1]||C.G. Broyden, "A class of methods for solving nonlinear simultaneous equations" Math. Comp. , 19 (1965) pp. 577–593|
|[a2]||C.G. Broyden, J.E. Dennis, J.J. Moré, "On the local and superlinear convergence of quasi-Newton methods" J. Inst. Math. Appl. , 12 (1973) pp. 223–246|
|[a3]||J.E. Dennis, J.J. Moré, "Quasi-Newton methods, methods, motivation and theory" SIAM Review , 19 (1977) pp. 46–89|
|[a4]||J.E. Dennis, R.B. Schnabel, "Numerical Methods for Nonlinear Equations and Unconstrained Optimization" , Classics in Applied Math. : 16 , SIAM (Soc. Industrial Applied Math.) (1996)|
|[a5]||P. Deuflhard, R.W. Freund, A. Walter, "Fast Secant Methods for the Iterative Solution of Large Nonsymmetric Linear Systems" Impact of Computing in Science and Engineering , 2 (1990) pp. 244–276|
|[a6]||M.S. Engelman, G. Strang, K.J. Bathe, "The application of quasi-Newton methods in fluid mechanics" Internat. J. Numerical Methods Eng. , 17 (1981) pp. 707–718|
|[a7]||J.M. Ortega, W.C. Rheinboldt, "Iterative Solution of Nonlinear Equations in Several Variables" , Acad. Press (1970)|
|[a8]||J. Sherman, W.J. Morrison, "Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix (abstract)" Ann. Math. Stat. , 20 (1949) pp. 621|
|[a9]||J. Sherman, W.J. Morrison, "Adjustment of an inverse matrix corresponding to a change in one element of a given matrix" Ann. Math. Stat. , 21 (1950) pp. 124–127|
|[a10]||D.W. Decker, H.B. Keller, C.T. Kelley, "Convergence rates for Newton's method at singular points" SIAM J. Numer. Anal. , 20 (1983) pp. 296–314|
|[a11]||D.W. Decker, C.T. Kelley, "Sublinear convergence of the chord method at singular points" Numer. Math. , 42 (1983) pp. 147–154|
|[a12]||D.W. Decker, C.T. Kelley, "Broyden's method for a class of problems having singular Jacobian at the root" SIAM J. Numer. Anal. , 22 (1985) pp. 566–574|
|[a13]||C.T. Kelley, "Iterative Methods for Linear and Nonlinear Equations" , Frontiers in Appl. Math. : 16 , SIAM (Soc. Industrial Applied Math.) (1995)|
|[a14]||C.T. Kelley, E.W. Sachs, "A new proof of superlinear convergence for Broyden's method in Hilbert space" SIAM J. Optim. , 1 (1991) pp. 146–150|
Broyden method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Broyden_method&oldid=16772