418 Chapter 10. Minimization or Maximization of Functions de1=0.0; Will be the biggest function decrease for(1=1;i<=n;i++)[ In each iteration,loop over all directions in the set. for (j=1;j<=n;j++)xit[j]=xi[j][i]; Copy the direction, fptt=(*fret); linmin(p,xit,n,fret,func); minimize along it, if (fptt-(*fret)>del){ and record it if it is the largest decrease del=fptt-(*fret); so far. ibig=i; 2 if (2.0*(fp-(*fret))<=ftol*(fabs(fp)+fabs(*fret))+TINY) free_vector(xit,1,n); lermination criterion free_vector(ptt,1,n); free_vector(pt,1,n); return; d 18881892 if (*iter =ITMAX)nrerror("powell exceeding maximum iterations."); for (j=1;j<=n;j++){ Construct the extrapolated point and the Cam NUMERICAL ptt[j]=2.0*p[j]-pt[j]; average direction moved.Save the xit[j]=p[j]-pt[j]; old starting point. pt[j]=p[j]; RECIPES fptt=(*func)(ptt); Function value at extrapolated point. it(fptt fp){ 入高 令 t=2.0*(fp-2.0*(*fret)+fptt)*SQR(fp-(*fret)-del)-del*SQR(fp-fptt); 1f(t<0.0)[ linmin(p,xit,n,fret,func); Move to the minimum of the new direc- Press. for (j=1;j<=n;j++){ tion,and save the new direction. xi[j][ibig]=xi[j][n]; xi[j][n]=xit[]; 22222 Back for another iteration. IENTIFIC MPUTING Implementation of Line Minimization 1920 (ISBN Make no mistake,there is a right way to implement linmin:It is to use 10.621 the methods of one-dimensional minimization described in $10.1-810.3,but to Numerica rewrite the programs of those sections so that their bookkeeping is done on vector- uction Recipes 43108 valued points P (all lying along a given direction n)rather than scalar-valued abscissas z.That straightforward task produces long routines densely populated with“for(k=1;k<=n;k++)”loops. We do not have space to include such routines in this book.Our linmin,which North Software. works just fine,is instead a kind of bookkeeping swindle.It constructs an"artificial" function of one variable called fidim,which is the value of your function,say, func,along the line going through the point p in the direction xi.linmin calls our familiar one-dimensional routines mnbrak($10.1)and brent ($10.3)and instructs them to minimize fidim.linmin communicates with f1dim"over the head"of mnbrak and brent,through global (external)variables.That is also how it passes to fidim a pointer to your user-supplied function. The only thing inefficient about linmin is this:Its use as an interface between a multidimensional minimization strategy and a one-dimensional minimization routine results in some unnecessary copying of vectors hither and yon.That should not418 Chapter 10. Minimization or Maximization of Functions 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). del=0.0; Will be the biggest function decrease. for (i=1;i<=n;i++) { In each iteration, loop over all directions in the set. for (j=1;j<=n;j++) xit[j]=xi[j][i]; Copy the direction, fptt=(*fret); linmin(p,xit,n,fret,func); minimize along it, if (fptt-(*fret) > del) { and record it if it is the largest decrease del=fptt-(*fret); so far. ibig=i; } } if (2.0*(fp-(*fret)) <= ftol*(fabs(fp)+fabs(*fret))+TINY) { free_vector(xit,1,n); Termination criterion. free_vector(ptt,1,n); free_vector(pt,1,n); return; } if (*iter == ITMAX) nrerror("powell exceeding maximum iterations."); for (j=1;j<=n;j++) { Construct the extrapolated point and the average direction moved. Save the old starting point. ptt[j]=2.0*p[j]-pt[j]; xit[j]=p[j]-pt[j]; pt[j]=p[j]; } fptt=(*func)(ptt); Function value at extrapolated point. if (fptt < fp) { t=2.0*(fp-2.0*(*fret)+fptt)*SQR(fp-(*fret)-del)-del*SQR(fp-fptt); if (t < 0.0) { linmin(p,xit,n,fret,func); Move to the minimum of the new direc￾for (j=1;j<=n;j++) { tion, and save the new direction. xi[j][ibig]=xi[j][n]; xi[j][n]=xit[j]; } } } } Back for another iteration. } Implementation of Line Minimization Make no mistake, there is a right way to implement linmin: It is to use the methods of one-dimensional minimization described in §10.1–§10.3, but to rewrite the programs of those sections so that their bookkeeping is done on vector￾valued points P (all lying along a given direction n) rather than scalar-valued abscissas x. That straightforward task produces long routines densely populated with “for(k=1;k<=n;k++)” loops. We do not have space to include such routines in this book. Our linmin, which works just fine, is instead a kind of bookkeeping swindle. It constructs an “artificial” function of one variable called f1dim, which is the value of your function, say, func, along the line going through the point p in the direction xi. linmin calls our familiar one-dimensional routines mnbrak (§10.1) and brent (§10.3) and instructs them to minimize f1dim. linmin communicates with f1dim “over the head” of mnbrak and brent, through global (external) variables. That is also how it passes to f1dim a pointer to your user-supplied function. The only thing inefficient about linmin is this: Its use as an interface between a multidimensional minimization strategy and a one-dimensional minimization routine results in some unnecessary copying of vectors hither and yon. That should not