Find a Routine to Perform Iterations on Mathematica

[natski]

Hi all,

I am wondering if anyone knows of a routine to perform iterations on a computer which is both efficient and easy to implement in Mathematica. I basically have a single input, a, and a single output, b, which is computed through a black-box piece of code. I wish to create some kind of loop which finds the value of a needed to give b=0.

Any suggestions would be appreciated...

Natski

 

[HallsofIvy]

By "black box", you mean you do not know the function that connects a and b? I don't see any sure way of doing that: you have no reason to believe any a will give b=0!

 

[natski]

Hmm no it's not simple a black-box per say, but effectively it may as well be. The details are not important because the function takes several hundred lines of code to calculate b from a. However, given an appropriate guess value for a, I know that b is close to 0. I just need a routine to pin it down.

 

[ice109]

obviously run over an interval and plot the results. if that's too vague you could interpolate the points and look at the slope of the interpolant.

 

[Integral]

Find an interval where b<0 at one end point and b>0 at the other. Evaluate b at the midpoint of the interval. You now have a new interval which contains the zero. Repeat the process until you are as close to the zero as you want or need to be.

This is called the bisection method. With a bit of research you should be able to find more details. Other related methods include the secant method and regula falsi, or false point method. Check Wiki.

 

[natski]

Thanks a lot for that Integral... I was already using the bisection method actually, but didn't realize that this was its name. What I was looking for what a more efficient iteration method, so I will have a look at those others ones you suggested now.

Natski

 

[dodo]

Then again, "[URL method[/URL] could be a possibility. You could estimate the derivative of the black-box function by df = (f(a+h) - f(a)) / h, where h is relatively much more smaller than a (try with 3 or 4 orders of magnitude smaller). Then the next value for a would be given by a - f(a) / df.

That is, assuming the function looks "smooth enough", in the first place.

 

[CRGreathouse]

If you can't compute the derivative directly, you'd be best off using the secant method rather than a pseudo-Newton.

 

[ice109]

bisection method has to bracket the zero. Newton and secant don't but no one knows what the hell this blackbox function is. we have no idea that it's well behaved at all. i think it would be more productive to post the code and let us help you dissect it

 

[CRGreathouse]

i think it would be more productive to post the code and let us help you dissect it

Could be. I see it the opposite way -- the secant method is easy to code, so just run that and see if it solves it. If not, then you can (use bisection, post here, try a mixed method, etc.).

 

[ice109]

but no one knows what this "function" is? it could even be not single valued. you can't just say let's throw numerical analysis at it considering we have no idea what this thing is. what if it's just a random number generator.

 

[CRGreathouse]

but no one knows what this "function" is? it could even be not single valued. you can't just say let's throw numerical analysis at it considering we have no idea what this thing is. what if it's just a random number generator.

Sure, and if it's a random number generator then bisection will just give a random bitstring. The secant method would at least suggest that something's wrong.

On the other hand, if the function is reasonably well-behaved, then the secant method should give a testable answer fairly quickly.

Hmm, though; the OP did mention that he was using bisection before, so presumably there were problems (either in speed or in applicability). So perhaps you're right -- if it doesn't work with bisection there's precious little hope for secant.

 

[natski]

Hi again, the function is well behaved and single valued so there is no problems there. I should have said earlier that I was already aware of this fact and that iteration would definitely work, it was merely a matter of efficiency. Bisection works OK, but it's just a bit slow since it is a linear method, taking around 10-14 steps. I've applied secant and got much faster convergence so all is good, within 5 steps actually. I think a part of that improvement has come from improving my first guesses however. Secant is far more advantageous for my purposes, given good guesses, since should converge with an index of 1.6 rather than 1 for bisection, and also doesn't not require a bracketing of the solution.

 

[natski]

Note that there is an exhaustive list of routines at http://mathworld.wolfram.com/Root-FindingAlgorithm.html