An Attempt to Challenge the Bisection method for root findin



#8

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 root-bracketing 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^x-3*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.
2. The Random method outperformed the Bisection method only in 2% of the iterations. The maximum saving in iterations was 11. The average and std deviation in iterations saved were about 2.5 and 1.72 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


#9

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?)


#10

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 root-bracketing 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 root-bracketing interval).

#11

Quote:
(Or did I just mix up bisection with the Regula Falsi?)

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 x-interval [2; 10] the same way. So the next value is 7,33.

Dieter


#12

Reguli False has a little negative feature in that it does not intuitively shrink the root-bracketing interval like Bisection does. If you are using Reguli Falsi, you might as well switch to the tangent method. I believe the HP-34 Solve is based on the tangent method.

Namir


#13

Quote:
I believe the HP-34 Solve is based on the tangent method.

Since you say HP-34 and not WP-34 I think you refer to the HP-34C. As far as I know the 34C uses a modified secant method, i.e. a variation of the regula falsi. The WP-34s 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 x-axis. 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


#14

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.


- Pauli


Possibly Related Threads...
Thread Author Replies Views Last Post
  A fast Bernoulli Number method for the HP Prime Namir 16 703 11-22-2013, 04:46 PM
Last Post: Namir
  [HP Prime] Using n-root symbol and exponent problem uklo 7 366 11-11-2013, 01:39 AM
Last Post: Alberto Candel
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 355 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  HP PRIME - Bode and Black plots - first attempt dg1969 0 119 10-20-2013, 01:32 PM
Last Post: dg1969
  A brand new calculator benchmark: "middle square method seed test" Pier Aiello 25 894 09-13-2013, 01:58 PM
Last Post: Pier Aiello
  Cubic root (-8) = 2 ? Gilles Carpentier 37 1,252 08-12-2013, 10:26 PM
Last Post: jep2276
  Downhill Simplex Method (Nelder Mead) for WP-34S Marcel Samek 0 106 07-07-2013, 03:05 AM
Last Post: Marcel Samek
  Square Root Simplifier for HP39gII Mic 4 243 03-11-2013, 08:25 AM
Last Post: Eddie W. Shore
  Cube root on standard calculator Thomas Klemm 22 899 11-09-2012, 06:11 AM
Last Post: Pierre
  RPN HP39gII : An attempt to summarize our discusion Gilles Carpentier 18 600 07-27-2012, 06:44 PM
Last Post: Gilles Carpentier

Forum Jump: