408 Chapter 10. Minimization or Maximization of Functions du=(*df)(u); Now all the housekeeping,sigh. if (fu <fx){ if (u >x)a=x;else b=x; MOV3(v,fv,dv,w,fw,dw) MOV3(w,fw,dw,x,fx,dx) MOV3(x,fx,dx,u,fu,du) else if (u x)asu;else bsu; if (fu <fw l w =x){ MOV3(v,fv,dv,w,fw,dw) MOV3(w,fw,dw,u,fu,du) else if (fu fv Il v =x l v==w){ MOV3(v,fv,dv,u,fu,du) 83 granted for (including this one) 19881992 nrerror("Too many iterations in routine dbrent"); return 0.0; Never get here. 111800.872 NUMERICAL RECIPES (Nort CITED REFERENCES AND FURTHER READING: America server computer, University Press. 令 THE Acton,F.S.1970,Numerica/Methods That Work,1990,corrected edition (Washington:Mathe- to make one paper matical Association of America),pp.55;454-458.[1] ART Brent,R.P.1973,Algorithms for Minimization without Derivatives(Englewood Cliffs,NJ:Prentice- Hall),p.78. Programs OF SCIENTIFIC 10.4 Downhill Simplex Method in to dir Multidimensions st COMPUTING (ISBN 19891892 With this section we begin consideration of multidimensional minimization, that is,finding the minimum of a function of more than one independent variable. 10-621 This section stands apart from those which follow.however:All of the algorithms after this section will make explicit use of a one-dimensional minimization algorithm Fuurggoglrion 43108 as a part of their computational strategy.This section implements an entirely Numerical Recipes self-contained strategy,in which one-dimensional minimization does not figure. The downhill simplex method is due to Nelder and Mead [1].The method (outside requires only function evaluations,not derivatives.It is not very efficient in terms North Software. of the number of function evaluations that it requires.Powell's method (810.5)is almost surely faster in all likely applications.However,the downhill simplex method may frequently be the best method to use if the figure of merit is "get something working quickly"for a problem whose computational burden is small. machine The method has a geometrical naturalness about it which makes it delightful to describe or work through: A simplex is the geometrical figure consisting,in N dimensions,of N+1 points(or vertices)and all their interconnecting line segments,polygonal faces,etc. In two dimensions,a simplex is a triangle.In three dimensions it is a tetrahedron, not necessarily the regular tetrahedron.(The simplex method of linear programming,408 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). } } du=(*df)(u); Now all the housekeeping, sigh. if (fu <= fx) { if (u >= x) a=x; else b=x; MOV3(v,fv,dv, w,fw,dw) MOV3(w,fw,dw, x,fx,dx) MOV3(x,fx,dx, u,fu,du) } else { if (u < x) a=u; else b=u; if (fu <= fw || w == x) { MOV3(v,fv,dv, w,fw,dw) MOV3(w,fw,dw, u,fu,du) } else if (fu < fv || v == x || v == w) { MOV3(v,fv,dv, u,fu,du) } } } nrerror("Too many iterations in routine dbrent"); return 0.0; Never get here. } CITED REFERENCES AND FURTHER READING: Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathe￾matical Association of America), pp. 55; 454–458. [1] Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: Prentice￾Hall), p. 78. 10.4 Downhill Simplex Method in Multidimensions With this section we begin consideration of multidimensional minimization, that is, finding the minimum of a function of more than one independent variable. This section stands apart from those which follow, however: All of the algorithms after this section will make explicit use of a one-dimensional minimization algorithm as a part of their computational strategy. This section implements an entirely self-contained strategy, in which one-dimensional minimization does not figure. The downhill simplex method is due to Nelder and Mead [1]. The method requires only function evaluations, not derivatives. It is not very efficient in terms of the number of function evaluations that it requires. Powell’s method (§10.5) is almost surely faster in all likely applications. However, the downhill simplex method may frequently be the best method to use if the figure of merit is “get something working quickly” for a problem whose computational burden is small. The method has a geometrical naturalness about it which makes it delightful to describe or work through: A simplex is the geometrical figure consisting, in N dimensions, of N + 1 points (or vertices) and all their interconnecting line segments, polygonal faces, etc. In two dimensions, a simplex is a triangle. In three dimensions it is a tetrahedron, not necessarily the regular tetrahedron. (The simplex method of linear programming