348 Chapter 9.Root Finding and Nonlinear Sets of Equations will always converge,provided that the initial guess is good enough.Indeed one can even determine in advance the rate of convergence of most algorithms It cannot be overemphasized,however,how crucially success depends on having a good first guess for the solution,especially for multidimensional problems.This crucial beginning usually depends on analysis rather than numerics.Carefully crafted initial estimates reward you not only with reduced computational effort,but also with understanding and increased self-esteem.Hamming's motto,"the purpose of computing is insight,not numbers,"is particularly apt in the area of finding roots. You should repeat this motto aloud whenever your program converges,with ten-digit accuracy,to the wrong root of a problem,or whenever it fails to converge because there is actually no root,or because there is a root but your initial estimate was not sufficiently close to it. "This talk of insight is all very well,but what do I actually do?"For one- dimensional root finding,it is possible to give some straightforward answers:You should try to get some idea of what your function looks like before trying to find its roots.If you need to mass-produce roots for many different functions,then you should at least know what some typical members of the ensemble look like.Next. you should always bracket a root,that is,know that the function changes sign in an identified interval,before trying to converge to the root's value. 9 Finally (this is advice with which some daring souls might disagree,but we give it nonetheless)never let your iteration method get outside of the best bracketing bounds obtained at any stage.We will see below that some pedagogically important algorithms,such as secant method or Newton-Raphson,can violate this last constraint, and are thus not recommended unless certain fixups are implemented. A之台 Multiple roots,or very close roots,are a real problem,especially if the OF SCIENTIFIC multiplicity is an even number.In that case,there may be no readily apparent sign change in the function,so the notion of bracketing a root-and maintaining the bracket-becomes difficult.We are hard-liners:we nevertheless insist on bracketing a root,even if it takes the minimum-searching techniques of Chapter 10 to determine whether a tantalizing dip in the function really does cross zero or not. (You can easily modify the simple golden section routine of $10.1 to return early if it detects a sign change in the function.And,if the minimum of the function is exactly zero,then you have found a double root.) Numerica 10621 As usual,we want to discourage you from using routines as black boxes without understanding them.However,as a guide to beginners,here are some reasonable starting points: Brent's algorithm in 89.3 is the method of choice to find a bracketed root of a general one-dimensional function,when you cannot easily compute the function's derivative.Ridders'method (89.2)is concise,and a close North competitor. When you can compute the function's derivative,the routine rtsafe in 89.4,which combines the Newton-Raphson method with some bookkeep- ing on bounds,is recommended.Again,you must first bracket your root. Roots of polynomials are a special case.Laguerre's method,in 89.5, is recommended as a starting point.Beware:Some polynomials are ill-conditioned! Finally,for multidimensional problems,the only elementary method is Newton-Raphson (89.6),which works very well if you can supply a348 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). will always converge, provided that the initial guess is good enough. Indeed one can even determine in advance the rate of convergence of most algorithms. It cannot be overemphasized, however, how crucially success depends on having a good first guess for the solution, especially for multidimensional problems. This crucial beginning usually depends on analysis rather than numerics. Carefully crafted initial estimates reward you not only with reduced computational effort, but also with understanding and increased self-esteem. Hamming’s motto, “the purpose of computing is insight, not numbers,” is particularly apt in the area of finding roots. You should repeat this motto aloud whenever your program converges, with ten-digit accuracy, to the wrong root of a problem, or whenever it fails to converge because there is actually no root, or because there is a root but your initial estimate was not sufficiently close to it. “This talk of insight is all very well, but what do I actually do?” For one￾dimensional root finding, it is possible to give some straightforward answers: You should try to get some idea of what your function looks like before trying to find its roots. If you need to mass-produce roots for many different functions, then you should at least know what some typical members of the ensemble look like. Next, you should always bracket a root, that is, know that the function changes sign in an identified interval, before trying to converge to the root’s value. Finally (this is advice with which some daring souls might disagree, but we give it nonetheless) never let your iteration method get outside of the best bracketing bounds obtained at any stage. We will see below that some pedagogically important algorithms, such assecant method orNewton-Raphson,can violate this last constraint, and are thus not recommended unless certain fixups are implemented. Multiple roots, or very close roots, are a real problem, especially if the multiplicity is an even number. In that case, there may be no readily apparent sign change in the function, so the notion of bracketing a root — and maintaining the bracket — becomes difficult. We are hard-liners: we nevertheless insist on bracketing a root, even if it takes the minimum-searching techniques of Chapter 10 to determine whether a tantalizing dip in the function really does cross zero or not. (You can easily modify the simple golden section routine of §10.1 to return early if it detects a sign change in the function. And, if the minimum of the function is exactly zero, then you have found a double root.) As usual, we want to discourage you from using routines as black boxes without understanding them. However, as a guide to beginners, here are some reasonable starting points: • Brent’s algorithm in §9.3 is the method of choice to find a bracketed root of a general one-dimensional function, when you cannot easily compute the function’s derivative. Ridders’ method (§9.2) is concise, and a close competitor. • When you can compute the function’s derivative, the routine rtsafe in §9.4, which combines the Newton-Raphson method with some bookkeep￾ing on bounds, is recommended. Again, you must first bracket your root. • Roots of polynomials are a special case. Laguerre’s method, in §9.5, is recommended as a starting point. Beware: Some polynomials are ill-conditioned! • Finally, for multidimensional problems, the only elementary method is Newton-Raphson (§9.6), which works very well if you can supply a