An Attempt to Challenge the Bisection method for root findin  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: An Attempt to Challenge the Bisection method for root findin (/thread190495.html) 
An Attempt to Challenge the Bisection method for root findin  Namir  08132011 Early this morning I had a curios idea in my head. How do the following two modifications to the Bisection method stack up against the Bisection method for finding roots? 1. A Random Method where we select a point at random inside the rootbracketing interval. The selected point's function value determines which part of the interval [A,B] to keep in order to zoom in on the root. 2. A Hybrid method in which we alternate between a regular Bisection step that chooses the midpoint in interval [A,B] and random step that chooses at random a point inside [A, B]. I ran 100,000 iterations to find the zero in [3,4] for my function e^x3*x^2 = 0. The results are:
1. The hybrid method outperformed the Bisection method only in 5% of the iterations. The maximum saving in iterations was 10. The average and std deviation in iterations saved were about 2.0 and 1.26 iterations. The histogram for the savings in iterations for both methods looks like an exponential decay. So for now, the Bisection has done better than the above two suggested modifications. That was fun!! Namir
Re: An Attempt to Challenge the Bisection method for root findin  Marcus von Cube, Germany  08132011 It simply depends on how smooth your function is. The close the two points are the more the function between them looks like a straight line and bisection would give the exact result. (Or did I just mix up bisection with the Regula Falsi?)
Re: An Attempt to Challenge the Bisection method for root findin  Namir  08132011 The Bisection looks only at the sign of the functions' values. The Reguli Falsi uses the function values as weights to estimate the new guess inside the rootbracketing interval. I developed the Quartile algorithm a few years ago, which performs better than the Bisection. The new method compares the absolute values of the function to calculate the refined guess (also inside the rootbracketing interval).
Re: An Attempt to Challenge the Bisection method for root findin  Dieter  08142011 Quote: Yes. Bisection simply means that, if f(x=2) is > 0 and f(x=10) < 0, try x=6 next. The regula falsi (linear interpolation) uses a weighted average instead. If f(x=2) is 8 and f(x=10) is 4, i.e. "twice as close" to zero, the new estimate divides the xinterval [2; 10] the same way. So the next value is 7,33.
Dieter
Re: An Attempt to Challenge the Bisection method for root findin  Namir  08142011 Reguli False has a little negative feature in that it does not intuitively shrink the rootbracketing interval like Bisection does. If you are using Reguli Falsi, you might as well switch to the tangent method. I believe the HP34 Solve is based on the tangent method.
Namir
Re: An Attempt to Challenge the Bisection method for root findin  Dieter  08142011 Quote:Since you say HP34 and not WP34 I think you refer to the HP34C. As far as I know the 34C uses a modified secant method, i.e. a variation of the regula falsi. The WP34s uses Brent's algorithm where several methods are combined. I assume that "tangent method" refers to something like Newton's algorithm, i.e. place a tangent to the graph and find its intersection with the xaxis. Such a method requires just one initial guess, while HP Solve (just as the 34s) requires two guesses, preferably with opposite signs of the function result.
Dieter
Re: An Attempt to Challenge the Bisection method for root findin  Paul Dale  08142011 I'm pretty sure the 34C uses a modified secant method. It has checks for going too far and escaping a bracketing interval. The 34S uses Brent's method which fits a quadratic in the best case. it also has guards and interval bracketing in place.
