+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Worse than Bisection???!!!! (/thread-526.html)
Worse than Bisection???!!!! - Namir - 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:
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 xI 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. :-)
RE: Worse than Bisection???!!!! - Thomas Klemm - 01-26-2014 06:01 PM
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
RE: Worse than Bisection???!!!! - Namir - 01-26-2014 07:06 PM
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
RE: Worse than Bisection???!!!! - Thomas Klemm - 01-26-2014 10:53 PM
(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.
RE: Worse than Bisection???!!!! - Dan W - 01-28-2014 03:18 AM
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.
RE: Worse than Bisection???!!!! - ttw - 07-17-2014 06:38 PM
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.
RE: Worse than Bisection???!!!! - Namir - 07-17-2014 08:43 PM
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.