University Maths Notes: Numerical Methods – The Bisection Method

Supposeis a continuous function on some intervalwithandof opposite sign. By the intermediate value theorem, there issuch thatFor simplicity, let's assume there exists only one root inas shown.

Bisection gives a simple and robust method for bracketing the rootThe algorithm works as follows:

Take the midpointas a first guess and calculateIfandare

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

sign tothen the root lies in the interval)

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

the example above.

At each iteration we halve the size of the intervalthat contains the rootand after n

iterations of the procedure we have reduced the uncertainty indown to,

Example: The functionhas a root in the intervalsinceandThe 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,andis the exact absolute error.

i. provided the function is continuous on an intervalwithbisection is

guaranteed to work.

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