## The Bisection Method

Supposeisa continuous function on some intervalwithandofopposite sign. By the intermediate value theorem, there issuchthatForsimplicity, let's assume there exists only one root inasshown.

Bisection gives a simple and robustmethod for bracketing the rootThealgorithm works as follows:

Take the midpointasa first guess and calculateIfandare

of opposite sign then the root lies inthe interval(Conversely,ifhasthe opposite

sign tothenthe root lies in the interval)

This procedure can be repeatediteratively, e.g. taking a second guessfrom

the example above.

At each iteration we halve the size ofthe intervalthatcontains the rootandafter n

iterations of the procedure we havereduced the uncertainty indownto,

Example: The functionhasa root in the intervalsinceandTheactual root is of course

0.00000 | 0.00000 | 0.00000 | 0.00000 | 0.00000 | 0.00000 | 0.00000 |

1.00000 | 0.00000 | 6.00000 | 3.00000 | 3.50000 | 3.00000 | 1.58600 |

2.00000 | 0.00000 | 3.00000 | 1.50000 | 0.12500 | 1.50000 | 0.08600 |

3.00000 | 0.00000 | 1.50000 | 0.75000 | -0.71900 | 0.75000 | 0.66400 |

4.00000 | 0.75000 | 1.50000 | 1.12500 | -0.36700 | 0.37500 | 0.28900 |

5.00000 | 1.12500 | 1.50000 | 1.31250 | -0.13900 | 0.18750 | 0.10200 |

6.00000 | 1.31250 | 1.50000 | 1.40625 | -0.01100 | 0.09375 | 0.00800 |

In the table,andisthe exact absolute error.

Advantages of the method

i. provided the function is continuouson an intervalwithbisectionis

guaranteed to work.

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

Disadvantages of the method :

i. the method is slow to converge.

ii. the errors inandindonot necessarily decrease between iterations. Note that,

in the example aboveiscloser to(andcloserto 0) than the next 3 iterates.

Also, no advantage is taken ofintermediate good approximations.