Tuesday, 23 August 2011

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
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.


  1. Hi Chris,

    Can you let me know how to integrate MathJax2 into blogger? It would be nice to write maths in a post, using it.


  2. I'll send you an e-mail it's a bit fiddly and I'm
    not sure I've got it quite right I can't use inline equations so thats why say the delta in the above post appears on a separate line. Better than nothing though

  3. Chris,

    You were spot on about the MST121 TMA04 Calculus section. Tut, Tut, Tut! I think the O.U have been very naughty there. They have mixed in some awful double angle formula manipulations, into the final required answer.

    I managed to solve it but it took 4hrs of graft and loads of algebra tricks, for just 4 marks. I'm sure I haven't answered it in the shortest way possible; but I can't see much alternative as it is not obvious on how to proceed.

    It just seems like a gross over complication that isn't really justified, in my opinion. Goodness knows what they are thinking in a level 1 course!