An Attempt to Challenge the Bisection method for root findin

[Namir]

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

[Marcus von Cube, Germany]

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

[Namir]

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

[Dieter]

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

[Namir]

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

[Dieter]

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

[Paul Dale]

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