01-26-2014, 02:36 PM
I thought that the Bisection method was the slowest root-seeking method for nonlinear functions. I set out, for the pure fun of it, to write an algorithm that can actually do worse!!! The proposed method starts at a point X and marches (in positive or negative steps) towards the targeted root. When the method detects that the function at the current value of X has changed sign, it switched the sign of the step value and reduces it by 2. Thus, the method (which I call Dancer) dances around the root until the search step falls below a tolerance value. The method is very much influenced by how close you choose the initial X to the root and by the initial step size. I did contemplate sub-steps to accelerate the march towards the root, but I was concerned that I would create problems when the nonlinear function has multiple roots that lie close to each other.
Here is the pseudo-code:
I implemented the above algorithm in Excel VBA, along with code for the Bisection method. The latter method did much better in all of the tests I conducted. The Dancer method took 30% to 100% more iterations to get the answer!!
Please no hate mail for this mediocre method. :-)
Here is the pseudo-code:
Code:
Give starting value X, Step dx, and tolerance value toler:
Fx2=f(x)
Repeat
Fx1=Fx2
x=x+dx
Fx2=f(X)
If Fx1*Fx2 < 0 Then
dx = -dx/2
End
Until Abs(dx) < toler
Return x
I implemented the above algorithm in Excel VBA, along with code for the Bisection method. The latter method did much better in all of the tests I conducted. The Dancer method took 30% to 100% more iterations to get the answer!!
Please no hate mail for this mediocre method. :-)