Worse than Bisection???!!!!
|
01-26-2014, 02:36 PM
(This post was last modified: 01-26-2014 02:37 PM by Namir.)
Post: #1
|
|||
|
|||
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: 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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
RE: Worse than Bisection???!!!! | |||
01-28-2014, 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. |
|||
07-17-2014, 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))/(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
|
|||
|
|||
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: 1 Guest(s)