Worse than Bisection???!!!!
01-26-2014, 02:36 PM (This post was last modified: 01-26-2014 02:37 PM by Namir.)
Post: #1
 Namir Senior Member Posts: 867 Joined: Dec 2013
Worse than Bisection???!!!!
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. :-)
 « Next Oldest | Next Newest »

 Messages In This Thread Worse than Bisection???!!!! - Namir - 01-26-2014 02:36 PM RE: Worse than Bisection???!!!! - Thomas Klemm - 01-26-2014, 06:01 PM RE: Worse than Bisection???!!!! - Namir - 01-26-2014, 07:06 PM RE: Worse than Bisection???!!!! - Thomas Klemm - 01-26-2014, 10:53 PM RE: Worse than Bisection???!!!! - Dan W - 01-28-2014, 03:18 AM RE: Worse than Bisection???!!!! - ttw - 07-17-2014, 06:38 PM RE: Worse than Bisection???!!!! - Namir - 07-17-2014, 08:43 PM

User(s) browsing this thread: 1 Guest(s)