|An Attempt to Challenge the Bisection method for root findin|
Message #1 Posted by Namir on 13 Aug 2011, 12:18 p.m.
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!!