Bisection method
= Bisection method
{title2=$m_k=(a_k+b_k)/2$}
{wiki}
The <bisection method> finds a <zero of a function> by repeatedly halving a <root bracket>. Let $f$ be a real-valued <continuous function> on the <closed interval> $[a,b]$, with $a<b$. First check for endpoint <zeros of a function>; otherwise require strictly opposite signs at the endpoints. Evaluate the <midpoint> and retain the half with strictly opposite endpoint signs, stopping immediately if the <midpoint> is a <zero of a function>. The <intermediate value theorem> ensures that every retained <root bracket> still contains a <zero of a function>. This is the construction in MIT's root-finding notes.https://ocw.mit.edu/courses/18-330-introduction-to-numerical-analysis-spring-2012/5b325bfa56a599794c7196de926844b0_MIT18_330S12_Chapter4.pdf[Laurent Demanet, MIT 18.330, Chapter 4, §4.1, pp. 1–2, 2012]{ref}
For a worked <square root> calculation, use the <polynomial> $f(x)=x^2-2$ on $[1,2]$. Write $[a_k,b_k]$ for the <root bracket> after $k$ halvings, with $[a_0,b_0]=[1,2]$. The candidate evaluated during update $k$ is the old <midpoint> $m_{k-1}$:
$$
\begin{array}{c|c|r|c}
\text{update }k&\text{candidate }m_{k-1}&f(m_{k-1})&\text{retained }[a_k,b_k]\\\hline
1&1.5&0.25&[1,1.5]\\
2&1.25&-0.4375&[1.25,1.5]\\
3&1.375&-0.109375&[1.375,1.5]\\
4&1.4375&0.06640625&[1.375,1.4375]
\end{array}
$$
The initial <midpoint> is $m_0=1.5$. After four halvings the new <midpoint> is $m_4=1.40625$, and the <bisection error bound> is $|m_4-\sqrt2|\leq0.03125$. Its actual error is approximately $0.00796356237310$. The last tested candidate $m_3=1.4375$ and the reported <midpoint> $m_4$ are different points.
\Image[/bisection-root-brackets.png]
{title=Bisection of a square-root bracket: the graph and first four retained intervals}
The useful feature of the <bisection method> is that the retained width halves on every update, independently of the shape of the <function graph>. The <bisection error bound> therefore supplies an accuracy guarantee before the <zero of a function> is known. No <derivative> is needed, and a valid initial <root bracket> gives convergence without a close initial guess. This makes the <bisection method> a dependable fallback for the faster <Newton root-finding iteration>.