[solved] advanced "divide & conquer" like method



  • Hi,
    I am looking for a advanced / extended "divide & conquer" like algorithm for my problem.
    I have a function which take a double X and return a double Y. Now I need to know the value of X to receive Y=0. This must be done by iterate multiple values of X. There is no way to perform a analytic study, couse the function differs by previous user input.
    By manipulating X in one direction, Y is also moving in one direction (could be positiv or negative but always in one direction). There are no gaps / singularity effect or something like that.
    My suggestion was to calculate Y two times, see the direction "where to move" and then raise or lower X till Y is 0 (approx). But this seems to be very time consuming, and I hope there is a way to speed it up by "intelligent guessing".

    Thanks,
    Nobody-86



  • Take a reasonably big stride. If you're too far, go back half. If you're not far enough, go the double distance untill you are at or past your target. Then, determine in which half of the range you can find your answer, and iteratively half the remaining range until you're close enough to your answer. Note that you may never find the exact answer due to the nature of doubles.



  • There probably is a better way to do this then guessing input values.

    @
    There is no way to perform a analytic study, couse the function differs by previous user input.
    @

    If this is true then the output is random unless you mean that the input 'formula' (?) changes between calculations.

    I think there are some good math libraries that could help with this kind of thing.


  • Moderators

    If your function is continuous and only changes in one direction, then the Newton-Raphson Algorithm (http://en.wikipedia.org/wiki/Newton's_method ) is a good one.

    Google "root-finding" if you're interested in other algorithms



  • It's not a divide and counquer, it's just a search for zero.
    [quote]There is no way to perform a analytic study, couse the function differs by previous user input.[/quote]
    What does "differs by" mean?
    JKSH, all the op has is some unknown black box, mapping input to output, luckily monotonic, while Newton's method requires knowing of function's derivative as well. http://en.wikipedia.org/wiki/Secant_method would be applicable.


  • Moderators

    [quote author="bipll" date="1364640642"]JKSH, all the op has is some unknown black box, mapping input to output, luckily monotonic, while Newton's method requires knowing of function's derivative as well. http://en.wikipedia.org/wiki/Secant_method would be applicable.[/quote]Ah, you're right. The Secant method approximates the derivative function, while the Newton-Raphson uses the analytical derivative function



  • Hi,

    bq. If this is true then the output is random unless you mean that the input ‘formula’ (?) changes between calculations.

    Ok, you got me. It is not true. Actually it is (theoretical) possible to get 'n' equations for 'n' unknown values ('n' depends on users input). But these equations are very hard to set up (I give up for n>3). Solving is even harder.

    bq. What does “differs by“ mean?

    Ah, my mistake, it should be "depends". English is (obvious) not my native language ;-).

    bq. http://en.wikipedia.org/wiki/Secant_method would be applicable.

    Yeah, this is pretty usefull, and I guess it is a bit faster than my try. But it also says:

    bq. As can be seen from the recurrence relation, the secant method requires two initial values, x0 and x1, which should ideally be chosen to lie close to the root.

    Same problem here, I have to guess the values x0 and x1.


  • Moderators

    [quote author="Nobody-86" date="1365174274"]
    bq. http://en.wikipedia.org/wiki/Secant_method would be applicable.

    Yeah, this is pretty usefull, and I guess it is a bit faster than my try. But it also says:

    bq. As can be seen from the recurrence relation, the secant method requires two initial values, x0 and x1, which should ideally be chosen to lie close to the root.

    Same problem here, I have to guess the values x0 and x1.[/quote]Your initial guesses are important in 2 cases:

    If the function has a discontinuity, a bad initial guess might prevent the algorithm from ever finding an answer

    If your function has multiple values of X which give Y=0 (i.e. the function changes directions), then your initial guess will influence which 'X' is found

    Since your function is continuous and only changes in one direction, it's not important to guess x0 and x1 accurately. Just pick any 2 numbers (e.g. 0 and 1), and the algorithm will find your answer quite quickly.



  • Hi there,

    I implemented the secant method in my program, and it works perfect for my case. In most cases less then three iterations are needed to find the root with a error of 1e-9, which is more then enough.

    <- solved, close.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.