9.3 Van Wiingaarden-Dekker-Brent Method 359 for (j=1;j<=MAXIT;j++){ xm=0.5*(x1+xh); fm=(*func)(xm); First of two function evaluations per it- s=sqrt(fm*fm-fl*fh); eration. if (s ==0.0)return ans; Xnew=xm+(xm-x1)*((f1>=fh?1.0:-1.0)*fm/s); Updating formula. if (fabs(xnew-ans)<=xacc)return ans; ans=xnew; fnew=(*func)(ans); Second of two function evaluations per if (fnew ==0.0)return ans; iteration. if (SIGN(fm,fnew)!fm){ Bookkeeping to keep the root bracketed X1=X; on next iteration. fl=fm; xh=ans; fh=fnew; else if (SIGN(fl,fnew)!=fl){ 19881992 xh=ans; fh=fnew; 1.800 else if (SIGN(fh,fnew)!fh){ xl=ans; 872 fl-fnew; Cambridge from NUMERICAL RECIPESI else nrerror("never get here."); if (fabs(xh-xl)<=xacc)return ans; nrerror("zriddr exceed maximum iterations"); else (North America server computer, sto make one paper University Press. IN C: THE if (fl==0.0)return x1; ART if (fh =0.0)return x2; nrerror("root must be bracketed in zriddr."); Programs return 0.0; Never get here. strictly proh to dir Copyright (C) CITED REFERENCES AND FURTHER READING: OF SCIENTIFIC COMPUTING(ISBN Ralston,A.,and Rabinowitz,P.1978,A First Course in Numerica/Analysis,2nd ed.(New York: 198819920 McGraw-Hill),88.3. Ostrowski,A.M.1966,Solutions of Equations and Systems of Equations,2nd ed.(New York: Academic Press),Chapter 12. Numerical Recipes 10-621 Ridders,C.J.F.1979,IEEE Transactions on Circuits and Systems,vol.CAS-26,pp.979-980.[1] 43108 (outside 9.3 Van Wijngaarden-Dekker-Brent Method North Software. Ame While secant and false position formally converge faster than bisection,one visit website finds in practice pathological functions for which bisection converges more rapidly. machine These can be choppy,discontinuous functions,or even smooth functions if the second derivative changes sharply near the root.Bisection always halves the interval, while secant and false position can sometimes spend many cycles slowly pulling distant bounds closer to a root.Ridders'method does a much better job,but it too can sometimes be fooled.Is there a way to combine superlinear convergence with the sureness of bisection?9.3 Van Wijngaarden–Dekker–Brent Method 359 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). for (j=1;j<=MAXIT;j++) { xm=0.5*(xl+xh); fm=(*func)(xm); First of two function evaluations per it￾s=sqrt(fm*fm-fl*fh); eration. if (s == 0.0) return ans; xnew=xm+(xm-xl)*((fl >= fh ? 1.0 : -1.0)*fm/s); Updating formula. if (fabs(xnew-ans) <= xacc) return ans; ans=xnew; fnew=(*func)(ans); Second of two function evaluations per if (fnew == 0.0) return ans; iteration. if (SIGN(fm,fnew) != fm) { Bookkeeping to keep the root bracketed xl=xm; on next iteration. fl=fm; xh=ans; fh=fnew; } else if (SIGN(fl,fnew) != fl) { xh=ans; fh=fnew; } else if (SIGN(fh,fnew) != fh) { xl=ans; fl=fnew; } else nrerror("never get here."); if (fabs(xh-xl) <= xacc) return ans; } nrerror("zriddr exceed maximum iterations"); } else { if (fl == 0.0) return x1; if (fh == 0.0) return x2; nrerror("root must be bracketed in zriddr."); } return 0.0; Never get here. } CITED REFERENCES AND FURTHER READING: Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed. (New York: McGraw-Hill), §8.3. Ostrowski, A.M. 1966, Solutions of Equations and Systems of Equations, 2nd ed. (New York: Academic Press), Chapter 12. Ridders, C.J.F. 1979, IEEE Transactions on Circuits and Systems, vol. CAS-26, pp. 979–980. [1] 9.3 Van Wijngaarden–Dekker–Brent Method While secant and false position formally converge faster than bisection, one finds in practice pathological functions for which bisection converges more rapidly. These can be choppy, discontinuous functions, or even smooth functions if the second derivative changes sharply near the root. Bisection always halves the interval, while secant and false position can sometimes spend many cycles slowly pulling distant bounds closer to a root. Ridders’ method does a much better job, but it too can sometimes be fooled. Is there a way to combine superlinear convergence with the sureness of bisection?