Worse than Bisection???!!!!

01262014, 02:36 PM
(This post was last modified: 01262014 02:37 PM by Namir.)
Post: #1




Worse than Bisection???!!!!
I thought that the Bisection method was the slowest rootseeking 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 substeps 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 pseudocode: Code: Give starting value X, Step dx, and tolerance value toler: 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. :) 

01262014, 06:01 PM
Post: #2




RE: Worse than Bisection???!!!!
A variant of this method using 10 instead of 2 is used to calculate the square root in HPcalculators. 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 

01262014, 07:06 PM
Post: #3




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 

01262014, 10:53 PM
Post: #4




RE: Worse than Bisection???!!!!  
01282014, 03:18 AM
Post: #5




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. 

07172014, 06:38 PM
Post: #6




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))/(X1X0). If (for example) the function is sort of a curved Lshape and one point is above the Xaxis near the upper leg and the other above the Xaxis 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. 

07172014, 08:43 PM
Post: #7




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)(ab)/(0.5 f(b)  f(a)) Where [a, b] is the rootbracketing interval for f(x) = 0. 

« Next Oldest  Next Newest »

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