This is interval halving method for solving non-linear
equations. Beginning with an interval
[a0,b0]=[a,b]
where the solution is localized, this method creates series of intervals
[an,bn]
(n=0,1,2,...)
each being the half of the previous one, by moving only one interval
boundary at a time, so to keep the solution embraced, i.e.
x* ∈ [an,bn].
Criterion for solution localizing is that the function changes it's
sign at interval boundaries, i.e.
f(an)*f(bn) < 0.
The size of each interval can be calculated as:
bn-an=(b-a)/2n,
and it converges to zero when n->+oo.
Solution approximation is the midpoint of interval, i.e.
x(n)=(an+bn)/2
with error:
|x*-x(n)| <
(an+bn)/2 =
(b-a)/2n+1 < epsilon.