7
$\begingroup$

Reading an implementation of the golden section search, I came across the following termination test:

$$| a - d | < \varepsilon ( |b| + |c| )$$

where $a < b < c < d$ are four points at which the function has been probed and $\varepsilon$ is a user-provided tolerance. Why is this a good termination criterion? If I take a function and an initial bracket and translate them along the abscissa, the algorithm should probe the function in the same fashion, but this test will terminate the runs at different iterations...

Cheers!

$\endgroup$
8
$\begingroup$

$|b|+|c|$ has the same order of magnitude as the extrema. Therefore, however many significant digits you have in $|b|+|c|$ is as accurately as you can calculate the location of the extrema. By ensuring your bracket is some fraction of this, you are ensuring you have a reachable condition while still getting as much accuracy as you can.

For example, let's say that your extrema is at $10^9$ and you are working in single precision. With 7 sig. figs. in single precision, you can only hope to get an answer to within $100$ of the actual value (single precision simply doesn't have the accuracy to do any better). In this case you would have to set your error tolerance (the r.h.s. of the inequality) to at least $100$ or your algorithm would never converge. In another case you could have a function with an extrema at $10^{-3}$. If you used the parameters from the last run, you would find a number somwhere between -100 and 100, and be nowhere close.

However, if you set epsilon to $10^{-7}$, you will measure your extrema to an accuracy of about $100$ in the first case and an accuracy of about $10^{-10}$ in the second case before convergence. This is using the exact same parameters in both cases.

This is a work around for when you have unknown locations of extrema in floating point arithmetic. If you had arbitrary precision, or knew the approximate location of the solution you could set a fixed error bound and the algorithm would work perfectly well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.