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: 828 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. :-)
01-26-2014, 06:01 PM
Post: #2
 Thomas Klemm Senior Member Posts: 1,768 Joined: Dec 2013
RE: Worse than Bisection???!!!!
A variant of this method using 10 instead of 2 is used to calculate the square root in HP-calculators. But of course it takes advantage of the fact that $$f(x_{n+1})$$ can be calculated easily based on $$f(x_{n})$$. Thus it's not a bad method per se.

Cheers
Thomas
01-26-2014, 07:06 PM
Post: #3
 Namir Senior Member Posts: 828 Joined: Dec 2013
RE: Worse than Bisection???!!!!
Thomas,

I guess you can use a factor of 10 instead of 2. The method just came to me as I was going to sleep two nights ago. It works, but it is sloooooooooooow.

namir
01-26-2014, 10:53 PM
Post: #4
 Thomas Klemm Senior Member Posts: 1,768 Joined: Dec 2013
RE: Worse than Bisection???!!!!
(01-26-2014 07:06 PM)Namir Wrote:  It works, but it is sloooooooooooow.
I guess Dave Cochran would like to have a talk with you.
01-28-2014, 03:18 AM
Post: #5
 Dan W Junior Member Posts: 4 Joined: Dec 2013
RE: Worse than Bisection???!!!!
Hi Namir

I've really enjoyed your explorations into root finding and integration. I've been using bisection or Newton's for years, and have a few Excel macros for it. So I may not implement this one.

As long as you are investigating convergence strategies, you might consider looking at Golden Section or Fibonacci series for reducing the bracketing interval and gaining significant digits.
07-17-2014, 06:38 PM
Post: #6
 ttw Member Posts: 255 Joined: Jun 2014
RE: Worse than Bisection???!!!!
Reguli Falsi with bracketing can be worse than bisection on many functions. It's like the Secant Method but keeps the root between estimates. One sets X2=(F(X1)-F(X0))/(X1-X0). If (for example) the function is sort of a curved L-shape and one point is above the X-axis near the upper leg and the other above the X-axis way out on the lower leg, the function will creep along chopping the interval a small amount at each time.

Using the Secant Method and switching to Bisection if the point falls outside works well in practice as it at worse becomes Bisection.
07-17-2014, 08:43 PM
Post: #7
 Namir Senior Member Posts: 828 Joined: Dec 2013
RE: Worse than Bisection???!!!!
Richard A Davis suggests in his new book Practical Numerical Methods for Chemical Engineers on page 187 the following remedies (which I am paraphrasing):

1) If a remains unchanged after two iterations use:

x = b - f(b)(a - b)/(f(b) - 0.5 f(a))

Otherwise, if b remains unchanged after two iterations use:

x = b - 0.5 f(b)(a-b)/(0.5 f(b) - f(a))

Where [a, b] is the root-bracketing interval for f(x) = 0.
 « Next Oldest | Next Newest »

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