Bisection method

This article is about a root-finding algorithm. See all root-finding algorithms

Definition

The bisection method, also called the interval halving method, binary search method, and dichotomy method, is a root-finding algorithm.

Summary

Item	Value
Initial condition	works for a continuous function $f$ (or more generally, a function $f$ satisfying the intermediate value property) on an interval $[a,b]$ given that $f(a)$ and $f(b)$ have opposite signs.
Iterative step	At stage $i$, we know that $f$ has a root in an interval $[a_i,b_i]$. We test $f$ at $(a_i+b_i)/2$. We then define the new interval $[a_{i+1},b_{i+1}]$ as the left half $[a_i,(a_i+b_i)/2]$ if the signs of $f$ at $a_i$ and $(a_i+b_i)/2$ oppose one another, and as the right half otherwise.
Convergence rate	The size of the interval within which we are guaranteed to have a root halves at each step. The distance between the root and our "best guess" at any stage (say, the midpoint of the guaranteed interval) has an upper bound that halves at each step, so we have linear convergence.
Computational tools needed	Floating-point arithmetic to compute averages Ability to compute the value of a function at a point, or more minimalistically, determine whether the value is positive or negative.
Termination stage	We may terminate the algorithm based either on the size of the interval in the domain (i.e., we know that we are close to a root) or the closeness of the function value to zero. How we terminate depends on our goals.

Initial condition

The bisection method works for a continuous function $f$ (or more generally, a function $f$ satisfying the intermediate value property) on an interval $[a,b]$ given that $f(a)$ and $f(b)$ have opposite signs.

The bisection method can be used to find a root of a continuous function on a connected interval if we are able to locate two points in the domain of the function where it has opposite signs. We simply restrict the function to that domain and apply the method.

Iterative step

Let $a=a_0,b=b_0$.

At stage $i$ for $i$ a nonnegative integer.

Prior knowledge:

• $f(a_i)$ and $f(b_i)$ are both numerically distinguishable from zero (so they have defined signs, positive or negative) and they have opposite signs.
• Combining that with the fact that $f$ is a continuous function, the intermediate value theorem tells us that $f$ has a root on $[a_i,b_i]$.

Iterative step:

• Compute $f((a_i+b_i)/2)$.
• If it is equal to (or numerically indistinguishable from) zero, then return $(a_i+b_i)/2$ as the root and terminate the algorithm.
• If $f((a_i+b_i)/2)$ has sign opposite to $f(a_i)$ (and therefore the same as $f(b_i)$), then choose $a_{i+1}=a_i$ and $b_{i+1}=(a_i+b_i)/2$, so the new interval (for the next iteration) is $[a_{i+1},b_{i+1}]$ as the left half $[a_i,(a_i+b_i)/2]$.
• If $f((a_i+b_i)/2)$ has sign opposite to $f(b_i)$ (and therefore the same as $f(a_i)$), the nchoose $a_{i+1}=(a_i+b_i)/2$ and $b_{i+1}=b_i$, so the new interval (for the next iteration) is $[a_{i+1},b_{i+1}]$ as the left half $[(a_i+b_i)/2,b_i]$.

Convergence rate

At stage $i$, we can define our best guess $c_i$ as the midpoint $(a_i+b_i)/2$.

We can measure the convergence rate by looking at the size of the interval within which a root is guaranteed, and how this changes with time. We notice that the interval size halves at each stage, so that $|b_n-a_n|=|b-a|/2^n$. The distance between $c_i$ and the location of an actual root is bounded from above by half the interval length, so this also asymptotically halves with each iteration (at worst, and on average).

This is a form of linear convergence.

Computational tools needed

• We need to be able to compute halves of intervals. This is most easily done using floating-point binary arithmetic.
• We also need to be able to compute function values at particular points, and determine the signs of these values. Note that we do not care about computing the function value per se but we do need reliable information about its size.

Termination

Domain-based termination

We may terminate the algorithm when the size of the interval within which a root is guaranteed has fallen below a certain pre-specified length $\ell$. The number of steps for such termination can be predicted in advance as:

$\lceil {\log }_2(\frac{|b-a|}{\ell })\rceil$

At this stage, we may return the interval or the midpoint, depending on the desired format of the answer.

Output-based termination

We may terminate the algorithm once the value of the function at the midpoint is sufficiently close to zero.

The number of stages needed for such termination cannot be computed simply by knowing the length of the domain. However, if $f$ is differentiable and we have an upper bound $B$ on the magnitude of the derivative of $f$, then we know that if we are within $\epsilon /B$ distance of the root on the domain, the absolute value of the function value is at most $\epsilon$. We can therefore put an upper bound on the number of steps necessary.

Caveats

This finds only one root, not all roots

It's worth noting that this process finds only one root, not all roots. Consider, for instance, the function:

$f(x):=(x-1)(x-4)(x-5)$

on the interval $[0,6]$. This is negative at 0 and positive at 6. At the midpoint 3, it is positive, so our first iteration picks the left half of the interval, namely $[0,3]$.