Worse than Bisection???!!!!

[Namir]

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:

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. :-)