Post Reply 
What Secrets the Bisection Method Hides?
05-31-2018, 11:40 PM
Post: #4
RE: What Secrets the Bisection Method Hides?
(05-31-2018 07:25 PM)Claudio L. Wrote:  
(05-31-2018 12:48 PM)Namir Wrote:  C = (w1 * A + w2 * B) / (w1 + w2)

The paper explores using different combinations of w1 and w2 and how most of these combinations can reduce the number of iterations needed to reach a refined guess for the root at a specific tolerance value.

Why did you choose w1+w2 as the parameter instead of w1/w2?

The equation transforms easily:

w2* ( w1/w2 * A + B ) / ( w2 * (1+w1/w2)) = ((w1/w2)*A+B) / (1+w1/w2)

Now this last expression reflects what you are doing much better: you fix the weight on one point to 1 (B in this case) and choose some ratio to determine the other weight (in your paper, you chose p=1+w1/w2 as the parameter and w1/w2= p-1). I think the w1/w2 ratio could give a better sense of calibration: when set to 1 it's the traditional bisection, and the point is at the center of A and B, when set to zero, it moves the "chosen" new point all the way to B, and any values in between will move it from the center to B progressively. Values >1 would move it in the opposite way, with +Inf moving it all the way to A.
The results would depend on the function you are studying, the "ideal" value, assuming the function is close to a straight line would be to use the magnitude of the functions at A and B as the parameters, effectively turning bisection into linear interpolation.

A final observation: it took me a while (not so clear on the paper) to visualize why it would be an improvement at all. Turns out your paper is apparently using a "fixed" ratio but it's not, since you are applying the weight of 1 to the point where the function has the smallest absolute value, so you are shifting the chosen point closer to that point, every time, effectively using a pair of ratios, not only one, and choosing the best of the two each time. The improvement to the method comes more from that decision than from the actual ratio you use.

The paper shows different cases for w1+w2 (using manual selection):

1) Sum is under 2. I just chose to assign 1 to one weight and calculate teh other weight as sum - 1. I could have used different numbers.
2) Sum is equal to 2, but w1 <> 1 and w2 <> 1.
3) Sum > 2 and w1 and w2 are selected to enhance the advantageous root-bracketing end.

Another approach is to use the absolute function values to calculate w1 and w2. So the paper shows two approaches.

You have total freedom to select w1 and w2 as long as it obeys:

C = (w1 * A + w2 * B) / (w1 + w2)

The relative values of w1 and w2 that you select will influence convergence rate, which of course greatly depends on the f(x) and the tolerance value for the refined guess for the root.

Namir
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: What Secrets the Bisection Method Hides? - Namir - 05-31-2018 11:40 PM



User(s) browsing this thread: 1 Guest(s)