c10-5 (Numerical Recipes in C), страница 3

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).}Minimization or Maximization of Functions10.5 Direction Set (Powell’s) Methods in Multidimensions419normally be a significant addition to the overall computational burden, but we cannotdisguise its inelegance.#include "nrutil.h"#define TOL 2.0e-4Tolerance passed to brent.void linmin(float p[], float xi[], int n, float *fret, float (*func)(float []))Given an n-dimensional point p[1..n] and an n-dimensional direction xi[1..n], moves andresets p to where the function func(p) takes on a minimum along the direction xi from p,and replaces xi by the actual vector displacement that p was moved. Also returns as fretthe value of func at the returned location p.

This is actually all accomplished by calling theroutines mnbrak and brent.{float brent(float ax, float bx, float cx,float (*f)(float), float tol, float *xmin);float f1dim(float x);void mnbrak(float *ax, float *bx, float *cx, float *fa, float *fb,float *fc, float (*func)(float));int j;float xx,xmin,fx,fb,fa,bx,ax;ncom=n;Define the global variables.pcom=vector(1,n);xicom=vector(1,n);nrfunc=func;for (j=1;j<=n;j++) {pcom[j]=p[j];xicom[j]=xi[j];}ax=0.0;Initial guess for brackets.xx=1.0;mnbrak(&ax,&xx,&bx,&fa,&fx,&fb,f1dim);*fret=brent(ax,xx,bx,f1dim,TOL,&xmin);for (j=1;j<=n;j++) {Construct the vector results to return.xi[j] *= xmin;p[j] += xi[j];}free_vector(xicom,1,n);free_vector(pcom,1,n);}#include "nrutil.h"extern int ncom;Defined in linmin.extern float *pcom,*xicom,(*nrfunc)(float []);float f1dim(float x)Must accompany linmin.{int j;float f,*xt;xt=vector(1,ncom);for (j=1;j<=ncom;j++) xt[j]=pcom[j]+x*xicom[j];f=(*nrfunc)(xt);free_vector(xt,1,ncom);return f;}Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).int ncom;Global variables communicate with f1dim.float *pcom,*xicom,(*nrfunc)(float []);420Chapter 10.Minimization or Maximization of FunctionsCITED REFERENCES AND FURTHER READING:Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall), Chapter 7.

[1]10.6 Conjugate Gradient Methods inMultidimensionsWe consider now the case where you are able to calculate, at a given N dimensional point P, not just the value of a function f(P) but also the gradient(vector of first partial derivatives) ∇f(P).A rough counting argument will show how advantageous it is to use the gradientinformation: Suppose that the function f is roughly approximated as a quadraticform, as above in equation (10.5.1),f(x) ≈ c − b · x +1x·A·x2(10.6.1)Then the number of unknown parameters in f is equal to the number of freeparameters in A and b, which is 12 N (N + 1), which we see to be of order N 2 .Changing any one of these parameters can move the location of the minimum.Therefore, we should not expect to be able to find the minimum until we havecollected an equivalent information content, of order N 2 numbers.In the direction set methods of §10.5, we collected the necessary information bymaking on the order of N 2 separate line minimizations, each requiring “a few” (butsometimes a big few!) function evaluations.

Now, each evaluation of the gradientwill bring us N new components of information. If we use them wisely, we shouldneed to make only of order N separate line minimizations. That is in fact the casefor the algorithms in this section and the next.A factor of N improvement in computational speed is not necessarily implied.As a rough estimate, we might imagine that the calculation of each component ofthe gradient takes about as long as evaluating the function itself. In that case therewill be of order N 2 equivalent function evaluations both with and without gradientinformation.

Even if the advantage is not of order N , however, it is neverthelessquite substantial: (i) Each calculated component of the gradient will typically savenot just one function evaluation, but a number of them, equivalent to, say, a wholeline minimization. (ii) There is often a high degree of redundancy in the formulasfor the various components of a function’s gradient; when this is so, especially whenthere is also redundancy with the calculation of the function, then the calculation ofthe gradient may cost significantly less than N function evaluations.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), pp. 464–467.

[2]Jacobs, D.A.H. (ed.) 1977, The State of the Art in Numerical Analysis (London: AcademicPress), pp. 259–262..