## The Bisection Method

Suppose isa continuous function on some interval with and of opposite sign. By the intermediate value theorem, there is suchthat For simplicity, let's assume there exists only one root in as shown. Bisection gives a simple and robust method for bracketing the root The algorithm works as follows:

Take the midpoint as a first guess and calculate If and are

of opposite sign then the root lies in the interval (Conversely,if has the opposite

sign to then the root lies in the interval )

This procedure can be repeated iteratively, e.g. taking a second guess from

the example above.

At each iteration we halve the size of the interval that contains the root and after n

iterations of the procedure we have reduced the uncertainty in down to, Example: The function has a root in the interval since and The actual root is of course 0 0 0 0 0 0 0 1 0 6 3 3.5 3 1.586 2 0 3 1.5 0.125 1.5 0.086 3 0 1.5 0.75 -0.719 0.75 0.664 4 0.75 1.5 1.125 -0.367 0.375 0.289 5 1.125 1.5 1.3125 -0.139 0.1875 0.102 6 1.3125 1.5 1.40625 -0.011 0.09375 0.008

In the table, and is the exact absolute error.

i. provided the function is continuous on an interval with bisection is

guaranteed to work.

ii. the number of iterations needed to achieve a specific accuracy is known in advance.

ii. the errors in and in do not necessarily decrease between iterations. Note that,
in the example above is closer to (and closer to 0) than the next 3 iterates. 