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

[Thomas Klemm]

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

[Namir]

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

[Thomas Klemm]

(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.

[Dan W]

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.

[ttw]

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.

[Namir]

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.