The restriction under
which we operate is that and must have opposite signs --
one of them must be positive, the other negative. Then, because
f is continuous (we have to assume that), there must be a zero of
f somewhere in . Let c be the midpoint of
. Either c is the root, or the root lies in
or the root lies in .
Which happens? Well, we can evaluate
. If it is a zero (or at least if it is sufficiently small),
we have our root. If it is not zero, then
one pair of or have opposite signs.
Keep the half-interval with opposite signs. Repeat the process
until either f, evaluated at the midpoint of the interval,
is sufficiently small (less than a tolerance we must prescribe),
or the interval has been shrunk sufficiently small
(less than a second prescribed tolerance).
That is the bisection algorithm.