x0=ax; At any given time we will keep track of four x3=cx; points, x0,x1,x2,x3. if (fabs(cx-bx) fabs(bx-ax)) { Make x0 to x1 the smaller segment, x1=bx; x2=bx+C*(cx-bx); and fill in the new point to be tried. } else { x2=bx; x1=bx-C*(bx-ax); } | 402 Chapter 10. Minimization or Maximization of Functions x0 ax x3 cx if fabs cx-bx fabs bx-ax x1 bx x2 bx C cx-bx else x2 bx x1 bx-C bx-ax f1 f x1 f2 f x2 At any given time we will keep track of four points x0 x1 x2 x3. Make x0 to x1 the smaller segment and fill in the new point to be tried. The initial function evaluations. Note that we never need to evaluate the function while fabs x3-x0 tol fabs x1 fabs x2 at the original endpoints. if f2 f1 SHFT3 x0 x1 x2 R x1 C x3 SHFT2 f1 f2 f x2 else SHFT3 x3 x2 x1 R x2 C x0 SHFT2 f2 f1 f x1 if f1 f2 xmin x1 return f1 else xmin x2 return f2 One possible outcome its housekeeping and a new function evaluation. The other outcome and its new function evaluation. Back to see if we are done. We are done. Output the best of the two current values. Parabolic Interpolation and Brent s Method in One Dimension We already tipped our hand about the desirability of parabolic interpolation in the previous section s mnbrak routine but it is now time to be more explicit. A golden section search is designed to handle in effect the worst possible case of function minimization with the uncooperative minimum hunted down and cornered like a scared rabbit. But why assume the worst If the function is nicely parabolic near to the minimum surely the generic case for sufficiently smooth functions then the parabola fitted through any three points ought to take us in a single leap to the minimum or at least very near to it see Figure . Since we want to find an abscissa rather than an ordinate the procedure is technically called inverse parabolic interpolation. The formula for the abscissa x that is the minimum of a parabola through three points f a f b and f c is x b 1 b a 2 f b f c b c 2 f b f a 2 b a f b f c b c f b f a as you can easily derive. This formula fails only if the three points are collinear in which case the denominator is zero minimum of the parabola is infinitely far Sample page from NUMERICAL RECIPES IN C THE ART OF
