Heath - Scientific Computing (523150), страница 47
Текст из файла (страница 47)
Moreover, these methods save on computational overhead by updating a factorization of the approximate Jacobian matrix at eachiteration (using techniques similar to the Sherman-Morrison formula) rather than refactoring it each time. Because of these two features, such methods are usually called secantupdating methods.These savings in computational overhead are not without their own cost, however, inthat secant updating methods generally have superlinear but not quadratic convergencerates. Nevertheless, there is often a net reduction in the overall cost of finding a solution,especially when the problem function and its derivatives are expensive to evaluate.5.3.4Broyden’s MethodOne of the simplest and most effective secant updating methods for solving nonlinear systems is Broyden’s method , which begins with an approximate Jacobian matrix and updatesit (or a factorization of it) at each iteration.
The initial Jacobian approximation B0 canbe taken as the correct Jacobian (or a finite difference approximation to it) at the startingpoint x0 , or, to avoid computing derivatives altogether, B0 can simply be initialized to bethe identity matrix I. The steps of the algorithm at iteration k are as follows:1.2.3.4.Solve Bk sk = −f (xk ) for sk .xk+1 = xk + sk .yk = f (xk+1 ) − f (xk ).Bk+1 = Bk + ((yk − Bk sk )sTk )/(sTk sk ).The motivation for the formula for Bk+1 is that it gives the least change to Bk subject tosatisfying the secant equationBk+1 (xk+1 − xk ) = f (xk+1 ) − f (xk ).In this way, the sequence of matrices Bk gains and maintains information about the behaviorof the function f along the various directions generated by the algorithm, without the needfor the function to be sampled purely for the purpose of obtaining derivative information.170CHAPTER 5.
NONLINEAR EQUATIONSUpdating Bk as just indicated would still leave one needing to solve a linear system ateach iteration at a cost of O(n3 ) arithmetic. Therefore, in practice a factorization of Bk isupdated instead of Bk directly, so that the total cost per iteration is only O(n2 ).Example 5.13 Broyden’s Method.
We illustrate Broyden’s method by again solvingthe nonlinear system of Example 5.12, x1 + 2x2 − 20f (x) ==.x21 + 4x22 − 40Again we let x0 = [ 12 ]T , so f (x0 ) = [ 313 ]T , and we let1B0 = Jf (x0 ) =22.16Solving the system1 2−3s =2 16 0−13−0.58 ]T , and hencegives s0 = [ −1.83−0.83x1 = x0 + s0 =,1.420f (x1 ) =,4.72−3y0 =.−8.28From the updating formula, we therefore haveB1 =12 20+16−2.34 01=−0.74−0.342.15.3Solving the systemgives s1 = [ 0.59120s1 =−0.34 15.3−4.72−0.30 ]T , and hence−0.24x2 = x1 + s1 =,1.1200f (x2 ) =,1.080y1 =.−3.64From the updating formula, we therefore have1B2 =−0.34 20+15.31.46 01=−0.731.12Iterations continue until convergence to the solution x∗ = [ 01 ]T .2.14.55.4.
SOFTWARE FOR NONLINEAR EQUATIONS5.3.5171Robust Newton-Like MethodsNewton’s method and its variants may fail to converge when started far from a solution.Unfortunately, in n dimensions there is no simple analogue of bisection in one dimensionthat can provide a fail-safe hybrid method. Nevertheless, safeguards can be taken that maysubstantially widen the region of convergence for Newton-like methods.The simplest of these precautions is the damped Newton method , in which the Newton(or Newton-like) step sk is computed as usual at each iteration, but then the new iterate istaken to bexk+1 = xk + αk sk ,where αk is a scalar parameter to be chosen.
The motivation is that far from a solutionthe full Newton step is likely to be unreliable—often much too large—and so αk can beadjusted to ensure that xk+1 is a better approximation to the solution than xk . One wayto enforce this condition is to monitor kf (xk )k2 and make sure that it decreases sufficientlywith each iteration. One might even minimize kf (xk + αk sk )k2 with respect to αk ateach iteration (see the discussion of line searches in Chapter 6).
Whatever the strategy forchoosing αk , when the iterates become close enough to a solution, the value αk = 1 shouldsuffice, and indeed the αk must approach 1 in order to maintain the usual convergence rate.Although this damping technique can improve the robustness of Newton-like methods, it isnot foolproof.
For example, there may be no value for αk that produces sufficient decrease,or the iterations may converge to a local minimum of kf (x)k2 such that the function valueis not 0.A somewhat more complicated but often more effective approach to making Newtonlike methods more robust is to maintain an estimate of the radius of a trust region withinwhich the Taylor series approximation, upon which Newton’s method is based, is sufficientlyaccurate for the resulting computed step to be reliable. By adjusting the size of the trustregion as necessary to constrain the stepsize, these methods can usually make progresstoward a solution even when started far away, yet still converge rapidly once near a solution,since the trust radius should then be large enough to permit full Newton steps to be taken.Again, however, the point to which such a method converges may be a local minimumof kf (x)k2 without being a solution of the equation f (x) = o.
Unlike damped Newtonmethods, trust region methods may modify the direction as well as the length of the Newtonstep when necessary, and hence they are generally more robust. See Section 6.3.3 for furtherdiscussion and a graphical illustration (Fig. 6.6).5.4Software for Nonlinear EquationsTable 5.1 is a list of some of the software available for solving general nonlinear equations.In the multidimensional case, we distinguish between routines that do or do not require theuser to supply derivatives for the functions, although in some cases the routines mentionedoffer both options.Software for solving a nonlinear equation f (x) = 0 typically requires the user to supplythe name of a routine that computes the value of the function f for any given value ofx.
The user must also supply absolute or relative error tolerances that are used in thestopping criterion for the iterative solution process. Additional input for one-dimensional172CHAPTER 5. NONLINEAR EQUATIONSTable 5.1: Software for nonlinear equationsOne-dimensionalMultidimensionalSourceNo derivativesNo derivatives DerivativesBrent [23]zeroFMMzeroinHSLnb01/nb02ns11IMSLzbrenneqbfneqnjDennis/Schnabel [57]nedrivernedriverKMNfzerosnsqesnsqeMATLABfzerofsolveMINPACK [182]hybrd1hybrj1NAGc05adfc05nbfc05pbfNAPACKrootquasiNRzbrentbroydnnewtNUMALzeroinquanewbndSLATECfzerosnsq/sosTOMSzero1(#631)brentm(#554)problems usually includes the endpoints of an interval in which the function has a changeof sign. Additional input for multidimensional problems includes the number of functionsand variables in the system and a starting guess for the solution, and may also include thename of a routine for computing the Jacobian of the function and the name of an array tobe used as workspace for storing the Jacobian or an approximation to it.
In addition to thesolution x, the output typically includes a status flag indicating any warnings or errors.For both single equations and systems, it is highly advisable to make a preliminary plot,or at least a rough sketch, of the function(s) involved to determine a good starting guessor bracketing interval. Some trial and error may be required to determine an initial guessfor which a zero finder converges, or finds the desired root in cases with more than onesolution.Some additional packages available for solving systems of nonlinear equations are basedon methods not covered in this book.
One such approach is homotopy methods or continuation methods. Such methods parameterize the problem space and then track a curvebetween a trivial problem instance and the actual problem to be solved. See Computer Problem 9.6 for an example of this approach, which can be especially useful for very difficultnonlinear problems for which a good starting guess for the solution is unavailable.
Softwareimplementing such methods includes fixpt(#555), dafne(#617), and hompack(#652), allavailable from TOMS. Yet another approach is generalized bisection, which is implementedin the routines chabis(#666) and intbis(#681) available from TOMS.Table 5.2 is a list of specialized software for finding all the zeros of a polynomial withreal or complex coefficients.5.5. HISTORICAL NOTES AND FURTHER READINGTable 5.2: Software for finding allSource RealHSLpa17IMSLzporc/zplrcMATLAB rootsNAGc02agfNAPACKNRzrhqrSLATEC rpzero/rpqr79TOMSrpoly(#493)5.5173the zeros of a polynomialComplexpa16zpoccrootsc02affczerozrootscpzero/cpqr79cpoly(#419)Historical Notes and Further ReadingMost of the methods we discussed for solving nonlinear equations in one dimension—including bisection, Newton, and secant—are quite venerable. Hybrid, safeguarded methodsfor one-dimensional problems, as popularized by Brent [23], are a relatively recent development.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
