Golden Section Search


GabrielZ
05-06-2011, 07:07 AM
I've got a quick question about section 10.2 in Numerical Recipes, "Golden Section Search".

In that section, I think, it is never explicitly stated whether the function needs to be continuous or not, in order for the method to work.

I have read up a little bit elsewhere on Golden Section Search, but almost all authors just say that the function is assumed to be smooth, or at least continuous. But I have never found any explanation as to why the function must be continuous/smooth.

It seems to me, actually, that the method works even with discontinuous functions.
(Note that I am not talking about finding the global minimum.)

Can you help me with this question?

Thanks a lot in advance.

Best regards,
Gabriel.

davekw7x
05-06-2011, 03:34 PM
...it is never explicitly stated whether the function needs to be continuous or not,...

In fact continuity is neither a necessary nor a sufficient condition for convergence of the general method.

Not necessary because:
None of the calculations (or the sequence of calculations) depends on continuity.

Not sufficient because:
If the function has two (or more) local minima on the given interval, there is no guarantee that the method will converge to the point where the smaller (smallest) one occurs.

So, one possible sufficient condition could go like this:
If a function is defined on an interval between two given end points and the function has exactly one local minimum in that interval, then the general method will converge.


Regards,

Dave

Footnote:
Depending on the specific function and depending on how "lucky" you are in selecting/guessing the initial end points, the method just might converge to the right answer even if the function jumps up and down lots of times inside the interval, so there is really no "if and only if" kind of condition for convergence of the method. Right?

GabrielZ
05-07-2011, 02:54 PM
In fact continuity is neither a necessary nor a sufficient condition for convergence of the general method.

Not necessary because:
None of the calculations (or the sequence of calculations) depends on continuity.


That is exactly what I was thinking.


Not sufficient because:
If the function has two (or more) local minima on the given interval, there is no guarantee that the method will converge to the point where the smaller (smallest) one occurs.


That is perfectly fine with me -- I just wanted to clarify things.

Thanks a lot for your clarifications!

Best regards,
Gabriel.