Title

Find the mid-point between a and b denoted c.

Calculate f(c) and check its sign.

Compare the sign of f(c) with f(b) and f(a).

f (c) < 0

f (c) > 0

Reassign a's value to c.

Reassign b's value to c.

Bisection is the simplest and most robust bracketing method. It is robust because bracketing, by definition, always ensures convergence to the root. We now consider the convergence of the bisection method. To do this consider the width of the bracket (

w_{n}

w_{n} = b_{n} - a_{n} = \frac{1}{2^{n}} (b_{0} - a_{0})

As the width is halved with each iteration. The error in the solution,

e_{n}

, at any point in the iteration is defined as the difference between the numerical and true solutions

e_{n} = x_{n} - x_{*}

Since

x_{n}

is the bisector, we know that

| e_{n} |

will be less than half the width of the bracket

m a x (| e_{n} |) = \frac{w_{n}}{2}

We know that this width will be the maximum possible difference between the numerical and true solutions. We can then substitute to find the maximum error

m a x (| e_{n} |) = \frac{w_{n}}{2} = \frac{b_{n} - a_{n}}{2} = \frac{1}{2^{n + 1}} (b_{0} - a_{0})

meaning the maximum error halves with each step

m a x (| e_{n + 1} |) = \frac{m a x (| e_{n} |}{2}