362 Chapter 9.Root Finding and Nonlinear Sets of Equations 2 a=b: Move last best guess to a. fa-fb; if (fabs(d)>tol1) Evaluate new trial root. b+=d; else b+=SIGN(tol1,xm); fb=(*func)(b); nrerror("Maximum number of iterations exceeded in zbrent"); return 0.0; Never get here. 83g CITED REFERENCES AND FURTHER READING: Brent,R.P.1973,Algorithms for Minimization without Derivatives(Englewood Cliffs,NJ:Prentice- 11800 Hall),Chapters 3,4.[1] Forsythe,G.E.,Malcolm,M.A.,and Moler,C.B.1977,Computer Methods for Mathematical Computations (Englewood Cliffs,NJ:Prentice-Hall),87.2. 9.4 Newton-Raphson Method Using Derivative America Press. Perhaps the most celebrated ofall one-dimensional root-finding routines is New- ton's method,also called the Newton-Raphson method.This method is distinguished from the methods of previous sections by the fact that it requires the evaluation SCIENTIFIC( of both the function f(x),and the derivative f'(z),at arbitrary points x.The Newton-Raphson formula consists geometrically of extending the tangent line at a current pointri until it crosses zero,then setting the next guess to the abscissa of that zero-crossing(see Figure 9.4.1).Algebraically,the method derives from the familiar Taylor series expansion of a function in the neighborhood of a point, fe+)≈f回+fa5+"回+. (9.4.1) 2 Numerica 10621 For small enough values of 6,and for well-behaved functions,the terms beyond 43126 linear are unimportant,hence f(x+6)=0 implies 6s、x) (9.4.2) f'(x) North Newton-Raphson is not restricted to one dimension.The method readily generalizes to multiple dimensions,as we shall see in 89.6 and 89.7.below. Far from a root,where the higher-order terms in the series are important,the Newton-Raphson formula can give grossly inaccurate,meaningless corrections.For instance,the initial guess for the root might be so far from the true root as to let the search interval include a local maximum or minimum of the function.This can be death to the method (see Figure 9.4.2).If an iteration places a trial guess near such a local extremum,so that the first derivative nearly vanishes,then Newton- Raphson sends its solution off to limbo,with vanishingly small hope of recovery.362 Chapter 9. Root Finding and Nonlinear Sets of Equations Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). } a=b; Move last best guess to a. fa=fb; if (fabs(d) > tol1) Evaluate new trial root. b += d; else b += SIGN(tol1,xm); fb=(*func)(b); } nrerror("Maximum number of iterations exceeded in zbrent"); return 0.0; Never get here. } CITED REFERENCES AND FURTHER READING: Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: Prentice￾Hall), Chapters 3, 4. [1] Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for Mathematical Computations (Englewood Cliffs, NJ: Prentice-Hall), §7.2. 9.4 Newton-Raphson Method Using Derivative Perhaps the most celebrated of all one-dimensional root-finding routines is New￾ton’s method, also called the Newton-Raphson method. This method is distinguished from the methods of previous sections by the fact that it requires the evaluation of both the function f(x), and the derivative f
(x), at arbitrary points x. The Newton-Raphson formula consists geometrically of extending the tangent line at a current point xi until it crosses zero, then setting the next guess xi+1 to the abscissa of that zero-crossing (see Figure 9.4.1). Algebraically, the method derives from the familiar Taylor series expansion of a function in the neighborhood of a point, f(x + δ) ≈ f(x) + f
(x)δ + f

(x) 2 δ2 + .... (9.4.1) For small enough values of δ, and for well-behaved functions, the terms beyond linear are unimportant, hence f(x + δ)=0 implies δ = − f(x) f
(x) . (9.4.2) Newton-Raphson is not restricted to one dimension. The method readily generalizes to multiple dimensions, as we shall see in §9.6 and §9.7, below. Far from a root, where the higher-order terms in the series are important, the Newton-Raphson formula can give grossly inaccurate, meaningless corrections. For instance, the initial guess for the root might be so far from the true root as to let the search interval include a local maximum or minimum of the function. This can be death to the method (see Figure 9.4.2). If an iteration places a trial guess near such a local extremum, so that the first derivative nearly vanishes, then Newton￾Raphson sends its solution off to limbo, with vanishingly small hope of recovery