Given: x_low lower bound on minimum x_high upper bound on minimum x_tol tolerance for convergence in x and a procedure to evaluate f(x). Evaluate f_low = f(x_low) and f_high = f(x_high) Set iteration counter = 1; set x(1) = x_low, x(4) = x_high f(1) = f_low, f(4) = f_high ! Iteration loop Do (until converged) calculate length of interval: L = x(4) - x(1) if iteration 1 or we kept the left hand sub-intervals from previous iteration, then set x(2) = x(1) + 0.381966 L; calculate f(2) = f(x(2)) end if if iteration 1 or we kept the right hand sub-intervals from previous iteration, then set x(3) = x(4) - 0.381966 L; calculate f(3) = f(x(3)) end if find point i with minimum f(i); set i_min = i with min f(i) ! i_min is best point so far if L is smaller than xtol declare convergence otherwise if i_min is 1 or 2 then keep the left two sub-intervals (set a flag) end if if i_min is 3 or 4 then keep the right two sub-intervals (set a flag) end if if keeping the left sub-intervals copy point 3 to point 4; copy point 2 to point 3 if keeping the right sub-intervals copy point 2 to point 1; copy point 3 to point 2 ! `copy' means copy both x and f values. ! It is important to copy the points ! in the stated order. end if if we have convergence x_opt = x(i_min); f_opt = f(i_min) ! solves the problem exit from the iteration loop end if end doYou will need a flag (integer or logical variable) to indicate whether the left or right sub-intervals are being kept.
Remark: The three equal interval and (to some extent) the four-equal interval methods are easier to implement.
For 3 interval copy only the points adjacent to i_min to x(1), f(1) and x(4), f(4). This sets up the next iteration, but we must always do two function evaluations at the head of the loop at
x(2) = x(1) + 0.333333 L; x(3) = x(4) - 0.333333 L
4 interval has 5 points in the current range. Provided i_min is an interior point (not x(1) or x(5)), copy point i_min to point 3, and the adjacent points to new bound points 1 and 5. At each iteration do two function evaluations at the head of the loop at
x(2) = x(1) + 0.25 L; x(4) = x(5) - 0.25 LAt iteration 1 also evaluate f at x(3) = 0.5 ( x(1) + x(5) ).
Return to Section 5.3.2
Return to Section 5.3 Index
Return to Section 5 Index
Course Organiser Last modified: Tue Aug 25 12:08:46 BST