9.4 Newton-Raphson Method Using Derivative 365 Equation (9.4.6)says that Newton-Raphson converges quadratically (cf.equa- tion 9.2.3).Near a root,the number of significant digits approximately doubles with each step.This very strong convergence property makes Newton-Raphson the method of choice for any function whose derivative can be evaluated efficiently,and whose derivative is continuous and nonzero in the neighborhood of a root Even where Newton-Raphson is rejected for the early stages of convergence (because of its poor global convergence properties),it is very common to"polish up"a root with one or two steps of Newton-Raphson,which can multiply by two or four its number of significant figures! For an efficient realization of Newton-Raphson the user provides a routine that 81 evaluates both f(z)and its first derivative f'()at the point z.The Newton-Raphson formula can also be applied using a numerical difference to approximate the true local derivative, f'(x)≈f+)-fa) (9.4.7) dr This is not,however,a recommended procedure for the following reasons:(i)You are doing two function evaluations per step,so at best the superlinear order of convergence will be only v2.(ii)If you take dz too small you will be wiped out by roundoff,while if you take it too large your order of convergence will be only 墨会d的将 Press. linear,no better than using the initial evaluation f'(ro)for all subsequent steps. Therefore,Newton-Raphson with numerical derivatives is(in one dimension)always dominated by the secant method of 89.2.(In multidimensions,where there is a paucity of available methods,Newton-Raphson with numerical derivatives must be taken more seriously.See $89.6-9.7.) The following function calls a user supplied function funcd(x,fn,df)which supplies the function value as fn and the derivative as df.We have included input bounds on the root simply to be consistent with previous root-finding routines: Newton does not adjust bounds,and works only on local information at the point 是 x.The bounds are used only to pick the midpoint as the first guess,and to reject the solution if it wanders outside of the bounds 10621 #include <math.h> #define JMAX 20 Set to maximum number of iterations. Fuunrggoleioh Numerical Recipes 43106 float rtnewt(void (*funcd)(float,float *float *)float x1,float x2 float xacc) Using the Newton-Raphson method,find the root of a function known to lie in the interval (outside [x1,x2.The root rtnewt will be refined until its accuracy is known within +xacc.funcd is a user-supplied routine that returns both the function value and the first derivative of the North Software. function at the point x. f void nrerror(char error_text []) int i; float df,dx,f,rtn; rtn=0.5*(x1+x2): Initial guess. for (j=1;j<=JMAX;j++){ (*funcd)(rtn,&f,&df) dx=f/df; rtn -dx; 1f((x1-rtn)*(rtn-x2)<0.0) nrerror("Jumped out of brackets in rtnewt");9.4 Newton-Raphson Method Using Derivative 365 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). Equation (9.4.6) says that Newton-Raphson converges quadratically (cf. equa￾tion 9.2.3). Near a root, the number of significant digits approximately doubles with each step. This very strong convergence property makes Newton-Raphson the method of choice for any function whose derivative can be evaluated efficiently, and whose derivative is continuous and nonzero in the neighborhood of a root. Even where Newton-Raphson is rejected for the early stages of convergence (because of its poor global convergence properties), it is very common to “polish up” a root with one or two steps of Newton-Raphson, which can multiply by two or four its number of significant figures! For an efficient realization of Newton-Raphson the user provides a routine that evaluates both f(x) and its first derivative f
(x) at the point x. The Newton-Raphson formula can also be applied using a numerical difference to approximate the true local derivative, f
(x) ≈ f(x + dx) − f(x) dx . (9.4.7) This is not, however, a recommended procedure for the following reasons: (i) You are doing two function evaluations per step, so at best the superlinear order of convergence will be only √2. (ii) If you take dx too small you will be wiped out by roundoff, while if you take it too large your order of convergence will be only linear, no better than using the initial evaluation f
(x0) for all subsequent steps. Therefore, Newton-Raphson with numerical derivatives is (in one dimension) always dominated by the secant method of §9.2. (In multidimensions, where there is a paucity of available methods, Newton-Raphson with numerical derivatives must be taken more seriously. See §§9.6–9.7.) The following function calls a user supplied function funcd(x,fn,df) which supplies the function value as fn and the derivative as df. We have included input bounds on the root simply to be consistent with previous root-finding routines: Newton does not adjust bounds, and works only on local information at the point x. The bounds are used only to pick the midpoint as the first guess, and to reject the solution if it wanders outside of the bounds. #include <math.h> #define JMAX 20 Set to maximum number of iterations. float rtnewt(void (*funcd)(float, float *, float *), float x1, float x2, float xacc) Using the Newton-Raphson method, find the root of a function known to lie in the interval [x1, x2]. The root rtnewt will be refined until its accuracy is known within ±xacc. funcd is a user-supplied routine that returns both the function value and the first derivative of the function at the point x. { void nrerror(char error_text[]); int j; float df,dx,f,rtn; rtn=0.5*(x1+x2); Initial guess. for (j=1;j<=JMAX;j++) { (*funcd)(rtn,&f,&df); dx=f/df; rtn -= dx; if ((x1-rtn)*(rtn-x2) < 0.0) nrerror("Jumped out of brackets in rtnewt");