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

1983, Numerical Methods for Unconstrained Optimization andNonlinear Equations (Englewood Cliffs, NJ: Prentice-Hall).Polak, E. 1971, Computational Methods in Optimization (New York: Academic Press).Gill, P.E., Murray, W., and Wright, M.H. 1981, Practical Optimization (New York: Academic Press).Acton, F.S. 1970, Numerical Methods That Work; 1990, corrected edition (Washington: Mathematical Association of America), Chapter 17.Jacobs, D.A.H. (ed.) 1977, The State of the Art in Numerical Analysis (London: AcademicPress), Chapter III.1.Brent, R.P. 1973, Algorithms for Minimization without Derivatives (Englewood Cliffs, NJ: PrenticeHall).Dahlquist, G., and Bjorck, A. 1974, Numerical Methods (Englewood Cliffs, NJ: Prentice-Hall),Chapter 10.10.1 Golden Section Search in One DimensionRecall how the bisection method finds roots of functions in one dimension(§9.1): The root is supposed to have been bracketed in an interval (a, b).

Onethen evaluates the function at an intermediate point x and obtains a new, smallerbracketing interval, either (a, x) or (x, b). The process continues until the bracketinginterval is acceptably small. It is optimal to choose x to be the midpoint of (a, b)so that the decrease in the interval length is maximized when the function is asuncooperative as it can be, i.e., when the luck of the draw forces you to take thebigger bisected segment.There is a precise, though slightly subtle, translation of these considerations tothe minimization problem: What does it mean to bracket a minimum? A root of afunction is known to be bracketed by a pair of points, a and b, when the functionhas opposite sign at those two points.

A minimum, by contrast, is known to bebracketed only when there is a triplet of points, a < b < c (or c < b < a), such thatf(b) is less than both f(a) and f(c). In this case we know that the function (if itis nonsingular) has a minimum in the interval (a, c).The analog of bisection is to choose a new point x, either between a and b orbetween b and c. Suppose, to be specific, that we make the latter choice. Then weevaluate f(x).

If f(b) < f(x), then the new bracketing triplet of points is (a, b, x);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).one-dimensional sub-minimization. Turn to §10.6 for detailed discussionand implementation.• The second family goes under the names quasi-Newton or variable metricmethods, as typified by the Davidon-Fletcher-Powell (DFP) algorithm(sometimes referred to just as Fletcher-Powell) or the closely relatedBroyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.

These methodsrequire of order N 2 storage, require derivative calculations and onedimensional sub-minimization. Details are in §10.7..