Golden Section Search--When to use it?

This is a discussion on Golden Section Search--When to use it? within the C++ Programming forums, part of the General Programming Boards category; I have some x inside an interval say [a,b] where I know that my solution lies. Due to the nonlinearity ...

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    17

    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

  2. #2
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    If the function is derivable you should try newton-raphson's method.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #3
    Registered User
    Join Date
    Oct 2004
    Posts
    17
    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?

  4. #4
    Registered User
    Join Date
    Oct 2004
    Posts
    26
    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.

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Maths For Game Programming?
    By kolliash in forum Game Programming
    Replies: 13
    Last Post: 09-18-2008, 11:53 AM
  2. In need of guidance
    By ajdspud in forum C++ Programming
    Replies: 5
    Last Post: 09-10-2006, 01:43 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21