## 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 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,andisthe exact absolute error.

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.