Solutions of Equations of One Variable With The Bisection Method

In this chapter we consider one of the most basic problems of numerical approximation, the root finding problem. This process involves finding a root, or solution, of an equation of the form $f(x)=0$. A root of this equation is also called a zero of the function $f$. This is one of the oldest known approximation problems, yet research continues in this area at the present time. 

The problem of finding an approximation to the root of an equation can be traced at least as far back as 1700 b.c. A cuneiform table in the Yale Babylonian Collection dating from that period gives a sexagesimal (base-60) number equivalent to $1.414222$ as an approximation to $\sqrt{2}$, a result that is accurate to within $10^{-5}$.

2.2 The Bisection Method

The first and most elementary technique we consider is the Bisection, or Binary Search, method. The Bisection method is used to determine, to any specified accuracy that your computer will permit, a solution to $f(x)=0$ on an interval $[a,b]$, provided that $f$ is continuous on the interval and that $f(a)$ and $f(b)$ are of opposite sign. Although the method will work for the case when more than one root is contained in the interval $[a,b]$, we assume for simplicity of our discussion that the root in this interval is unique.

To begin the Bisection method, set $a_{1}=a$ and $b_{1}=b$, as shown in Figure 2.1, and let $p_{1}$ be the midpoint of the interval $[a,b]$:

\[p_{1}=a_{1}+\frac{b_{1}-a_{1}}{2}\] if $f\left(p_{1}\right)=0$ then the root $p$ is given by $p=p_{1}$; if $f(p_{1})=0$, then $f(p_{1})$ has the same sign as either $f(a_{1})$ or $f(b_{1})$.

Figure 2.1

If $f(p_{1})$ and $f(a_{1})$ have the same sign,then $p$ is in the interval $(p_{1},b_{1})$, and we set\[a_{2}=p_{1\,\,\,}\text{and}\,\,\, b_{2}=b_{1}\] If, on the other hand, $f(p_{1})$ and $f(a_{1})$ have opposite signs, then $p$ is in the interval $(a_{1},p_{1})$, and we set\[a_{2}=a_{1}\,\,\,\,\text{and}\,\,\,\, b_{2}=p_{1}\] We reapply the process to the interval $[a_{2},b_{2}]$, and continue forming $[a_{3},b_{3}],[a_{4},b_{4}],....$ Each new interval will contain $p$ and have length one half of the length of the preceding interval.

[Bisection Method] An interval $[a_{n+1},b_{n+1}]$ containing an approximation to a root of $f(x)=0$ is constructed from an interval $[a_{n},b_{n}]$ containing the root by first letting\[p_{n}=a_{n}+\frac{b_{n}-a_{n}}{2}\] Then set $a_{n+1}=a_{n}$ and $b_{n+1}=p_{n}$ if $f(a_{n})f(p_{n})<0$, and $a_{n+1}=p_{n}$ and $b_{n+1}=b_{n}$ otherwise.

There are three stopping criteria commonly incorporated in the Bisection method. First, the method stops if one of the midpoints happens to coincide with the root. It also stops when the length of the search interval is less than some prescribed tol- erance we call $TOL$. The procedure also stops if the number of iterations exceeds a preset bound $N_{0}$ .

To start the Bisection method, an interval $[a,b]$ must be found with $f(a)\cdot f(b)<0$. At each step, the length of the interval known to contain a zero of $f$ is reduced by a factor of $2$. Since the midpoint $p_{1}$ must be within $(b-a)/2$ of the root $p$, and each succeeding iteration divides the interval under consideration by $2$, we have \[\left|p_{n}-p\right|\leq\frac{b-a}{2^{n}}\] As a consequence, it is easy to determine a bound for the number of iterations needed to ensure a given tolerance. If the root needs to be determined within the tolerance $TOL$, we need to determine the number of iterations, $n$, so that\[\frac{b-a}{2^{n}}<TOL\] Solving for $n$ in this inequality gives\[\frac{b-a}{TOL}<2^{n},\,\,\,\,\,\text{which implies that}\,\,\,\,\log_{2}\left(\frac{b-a}{TOL}\right)<n\]Since the number of required iterations to guarantee a given accuracy depends on the length of the initial interval $[a,b]$, we want to choose this interval as small as possible. For example, if $f(x)=2x^{3}-x^{2}+x-1$, we have both \[f\left(-4\right)\cdot f\left(4\right)<0\,\,\,\,\,\text{and}\,\,\,\,\, f\left(0\right)\cdot f\left(1\right)<0\] so the Bisection method could be used on either $[-4,4]$ or $[0,1]$. Starting the Bisection method on $[0,1]$ instead of $[-4,4]$ reduces by $3$ the number of iterations required to achieve a specified accuracy.