Thread: Golden Section Search--When to use it?

I have some x inside an interval say [a,b] where I know that my solution lies. Due to the nonlinearity of the problem solving it by traditional agorithms is not possible. I can evaluate each point inside the interval.

I wish to do a search applying the compostion of a few functions to points within the interval until I reached some value close enough to some Epsilon (haven't decided how close I need to be).

I've explored bisecting the interval until I reach the solution, but I was wondering if the Golden section search would be a better choice. Does this converge any faster or am I wasting my time exploring this method? Suggestions anyone?
Thanks,
just2peachy

This function is a composition of function that contains an absolute value, so not sure if derivative will exist.

I'm wondering if the Golden section search is only for unimodal data. If so then would the bisection search be faster in this case since I'm searching for a specific value along a strictly increasing or decreasing interval?

The numerical recipes in C book (http://www.nr.com) contains an extensive chapter on finding roots (chapter 9), with code for a variety of methods, as well as recommendations for shapes of curves where the different methods are likely to work better or worse. Have a look there.

Originally Posted by just2peachy

I have some x inside an interval say [a,b] where I know that my solution lies. Due to the nonlinearity of the problem solving it by traditional agorithms is not possible. I can evaluate each point inside the interval.

I wish to do a search applying the compostion of a few functions to points within the interval until I reached some value close enough to some Epsilon (haven't decided how close I need to be).

I've explored bisecting the interval until I reach the solution, but I was wondering if the Golden section search would be a better choice. Does this converge any faster or am I wasting my time exploring this method? Suggestions anyone?
Thanks,
just2peachy

The answer to your question is: "It depends."

The binary search method is guaranteed to find a real zero of a function on a given interval, assuming that the sign of the function value at one end of the interval is opposite from the sign at the other end (and assuming that the function value is finite on the interval and assuming that roundoff error does not interfere).

Other methods may be faster for some functions but may be slower and may not even converge for others.

If the characteristics of your function are such that it satisfies sufficiency requirements for a particular method, that method may be faster than the binary search, but maybe not.

Regards,

Dave