More on the Bisection Method

Error analysis and convergence for bisection method

Ok here is a basic summary of the error analysis associated with the bisection method. Let $$\delta$$ be the required tolerance and let $$e_{n}$$ be the error after the nth iteration.
Then as the bisection method  reduces the error by 1/2 at each iteration  interval, we have the basic recurrence relation $$e_{n+1}=\frac{1}{2}e_{n}$$



As this is linearly dependent  on the previous error the convergence is linear (unlike Newton Rhapshon) and can be comparatively slow to higher order methods as hopefully I will be able to show when I consider the Newton Rhapshon method.

So in terms of the original error e = |a-b|  (where a and b) are the points of the original interval, we have after n iterations
$$e_{n+1}=\frac{|a-b|}{2^n}$$    (2)
Now if $$\delta$$  is the desired tolerance then we can use equation 2 to get an estimate of how many iterations it will take to reach the tolerance call this N. So we have
$$\delta > \frac{|a-b|}{2^N}$$
Rearranging gives
$$2^N >\frac{|a-b|}{\delta}$$
Taking logarithms (it doesn't matter which)
gives$$N log2 > log|a-b| - log{\delta}$$ or
$$N>log|a-b|-log{\delta}$$
So if |a-b| = 1 say and $$\delta=0.5 . 10^{-5}$$
then $$N >\frac{log1-log{\delta}}{log2}$$
or N > 17.6

Hence the number of iterations it takes to converge to less than $$\delta$$  is 18.
I checked this for various intervals and amazingly it worked each time.
I love the way in this method it's the interval that determines the convergence it has nothing to do with the function at all. Simple and Brilliant.