2.1 Bisection Method

Identify an interval $[a, b]$ such that either a or b overshoots the mark while the other undershoots it.
Calculate the midpoint, m, of the identified interval.
If a and m both overshoot or both undershoot the mark, the desired value lies in $[m, b]$ .
If b and m both overshoot or both undershoot the mark, the desired value lies in $[a, m]$ .
Return to step 2 using the newly identified interval.

Error Analysis

if $m_{j}$ is a midpoint for any given $j$ then

| m_{j} - p | \leq \frac{b - a}{2^{j}}

Taking $p_{n} = \frac{b - a}{2^{n}}$ $⟨ p_{n} ⟩ \to 0$ we have

\lim_{n \to \infty} \frac{| \frac{b - a}{2^{n + 1}} - 0 |}{{| \frac{b - a}{2^{n}} - 0 |}^{α}} = \lim_{n \to \infty} \frac{2^{α n}}{2^{n + 1}} \cdot | b - a |^{1 - α} = \frac{1}{2} | b - a |^{1 - α} \cdot \lim_{n \to \infty} 2^{(α - 1) n}

which converges to a real $λ > 0$ for $α = 1$ so the bisection method has a linear order of convergence
Clearly has rate of convergence of $O (\frac{1}{2 n^{}})$