Bisection method

For polynomials, more elaborate methods exist for testing the existence of a root in an interval (Descartes' rule of signs, Sturm's theorem, Budan's theorem). They allow extending the bisection method into efficient algorithms for finding all real roots of a polynomial; see Real-root isolation.

The method

The method is applicable for numerically solving the equation ${\displaystyle f(x)=0}$ for the real variable ${\displaystyle x}$, where ${\displaystyle f}$ is a continuous function defined on an interval ${\displaystyle [a,b]}$ and where ${\displaystyle f(a)}$ and ${\displaystyle f(b)}$ have opposite signs. In this case ${\displaystyle a}$ and ${\displaystyle b}$ are said to bracket a root since, by the intermediate value theorem, the continuous function ${\displaystyle f}$ must have at least one root in the interval ${\displaystyle (a,b)}$.

At each step the method divides the interval in two parts/halves by computing the midpoint ${\displaystyle c=(a+b)/2}$ of the interval and the value of the function ${\displaystyle f(c)}$ at that point. If ${\displaystyle c}$ itself is a root then the process has succeeded and stops. Otherwise, there are now only two possibilities: either ${\displaystyle f(a)}$ and ${\displaystyle f(c)}$ have opposite signs and bracket a root, or ${\displaystyle f(c)}$ and ${\displaystyle f(b)}$ have opposite signs and bracket a root. The method selects the subinterval that is guaranteed to be a bracket as the new interval to be used in the next step. In this way an interval that contains a zero of ${\displaystyle f}$ is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if ${\displaystyle f(c)=0}$ then ${\displaystyle c}$ may be taken as the solution and the process stops.

Otherwise, if ${\displaystyle f(a)}$ and ${\displaystyle f(c)}$ have the same signs,

• then the method sets ${\displaystyle a=c}$,
• else the method sets ${\displaystyle b=c}$.

In both cases, the new ${\displaystyle f(a)}$ and ${\displaystyle f(b)}$ have opposite signs, so the method may be applied to this smaller interval.

Once the process starts, the signs at the left and right ends of the interval remain the same for all iterations.

Stopping conditions

In order to determine when the iteration should stop, it is necessary to consider various possible stopping conditions with respect to a tolerance (${\displaystyle ϵ}$). Burden and Faires (2016) identify the three stopping conditions:

• Absolute tolerance: ${\displaystyle |p_N-p_{N-1}|<ϵ}$
• Relative tolerance: ${\displaystyle \left|\frac{p_N-p_{N-1}}{p_N}\right|<ϵ,}$ for ${\displaystyle p_N\ne 0}$
• ${\displaystyle |f(p_N)|<ϵ.}$

${\displaystyle |f(p_N)|<ϵ}$ does not give an accurate result to within ${\displaystyle ϵ}$ unless ${\displaystyle |f^{\prime }(p_N)|\ge 1}$. The other two possibilities represent different concepts: the absolute difference ${\displaystyle |c-a|\le 5\times {10}^{-t}}$ says that c and a are the same to ${\displaystyle t}$ decimal places, while the relative difference ${\displaystyle \left|\frac{c-a}{c}\right|\le 5\times {10}^{-t}}$ says that c and a are the same to ${\displaystyle t}$ significant figures. If nothing is known about the value of the root, then relative tolerance is the best stopping condition.

Iteration process

The input for the method is a continuous function ${\displaystyle f}$ and an interval ${\displaystyle [a,b]}$, such that the function values ${\displaystyle f(a)}$ and ${\displaystyle f(b)}$ are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:

1. Calculate ${\displaystyle c}$, the midpoint of the interval, ${\displaystyle c=\frac{a+b}{2}}$;
2. Calculate the function value at the midpoint, ${\displaystyle f(c)}$;
3. If ${\displaystyle f(c)=0}$, return c;
4. If convergence is satisfactory (that is, ${\displaystyle \left|c-a\right|\le 5\times {10}^{-t}|c|}$), return ${\displaystyle c}$;
5. Examine the sign of ${\displaystyle f(c)}$ and replace either ${\displaystyle a}$ or ${\displaystyle b}$ with ${\displaystyle c}$ so that there is a zero crossing within the new interval.

Example

Suppose that the bisection method is used to find a root of the polynomial

${\displaystyle f(x)=x^3-x-2.}$

First, two numbers ${\displaystyle a}$ and ${\displaystyle b}$ have to be found such that ${\displaystyle f(a)}$ and ${\displaystyle f(b)}$ have opposite signs. For the above function, ${\displaystyle a=1}$ and ${\displaystyle b=2}$ satisfy this criterion, as

${\displaystyle f(1)=(1{)}^3-(1)-2=-2}$

and

${\displaystyle f(2)=(2{)}^3-(2)-2=+4.}$

Because the function is continuous, there must be a root within the interval [1, 2]. Iterating the bisection method on this interval gives increasingly accurate approximations:

After 13 iterations, it becomes apparent that there is a convergence to about 1.521: a root for the polynomial.