Bisection Method (see ws1)

This method can be applied only when the zero of is 'bracketed' by two values and for which and have a different sign. The idea is then to halve the bracketing interval until the root is known as accurate as needed. We can describe the method in the following steps:

>

step 1: find and such that .

step 2: calculate .

step 3: if then we found the root else, if then else .

step 4: repeat from step 2 until with the 'tolerance' or the accuracy required.

>

A scheme like the one above is often called an 'algorithm' for the application of the numerical method. It can be illustrated in the following picture:

>

For a continuous function, this method will always provide a solution. But the root has to be bracketed to begin with and convergence is slow.

We can find an upper bound to the rate of convergence. The width of the interval changes as

> w[1]:=(b-a)/2;

> w[2]:=w[1]/2;

> w[3]:=w[2]/2;

or, for the -th interval:

> w[n]:=(b-a)/(2^n);

Let us choose the lower boundary of the interval as an approximation to the root, i.e. ,then the error in the approximation is always less then the width of the -th interval: , with the exact value of the root. Therefore,

> error:=abs(p-x[n])<(b-a)/(2^n);

This shows that the rate of convergence is of order . This must be considered as an upper bound to the error. The exact error may be considerably less!