The Bisection Method

Section 3.2 The Bisection Method

We saw the Bisection method in Example 2.2.4 to find the square root of 65, but can be extended to finding roots of any function. The idea is that if you can find two \(x\) values with function values that are different signs, and if the function is continuous, as we can see with Theorem 1.2.1, discussed below, there will be a root.

🔗

Example 3.2.1.

Show that the function \(f(x)=x^{3}+3\) has a root on \([-2,0]\text{.}\)

🔗

Solution.

We know that \(f\) is continuous on the interval \([-2,0]\) and \(f(-2)=-5\) and \(f(0)=3\text{,}\) and since this satisfies the Intermediate Value Theorem (Theorem 1.2.1), there must exist a number \(c\) such that \(f(c)=0\text{,}\) and this is the definition of a root.

🔗

Plotting the function above on the given interval:

🔗

Figure 3.2.2.

🔗

You can “see” that there is a root and the Intermediate Value Theorem assures that there is one there. Now, how to find it? We will see that the bisection method will start with an interval (with a guaranteed root), find the midpoint of the interval and then choose a new interval ensuring it has a root again. The following section shows this in detail.

🔗

Subsection 3.2.1 The Bisection Algorithm

The following in the formal bisection method.

🔗

Algorithm 3.2.3. Bisection Method.

Let \(f(x)\) be a function and \([a,b]\) be an interval \(a \lt b\text{,}\) such that \(f(a)f(b) \lt 0\text{.}\) The bisection method are the steps below to find the root \(p\) with tolerance \(\epsilon\text{.}\) That is if \(f(p)=0\text{,}\) then return \(p^{\star}\) such that \(|p-p^{\star}| \lt \epsilon\text{.}\)

🔗

Set \(a_{0}=a\text{,}\) \(b_{0}=b\) and \(n=0\text{.}\)
🔗

🔗
Let \(c_{n} = \frac{a_{n}+b_{n}}{2}\)
- If \(f(a_{n})f(c_{n}) \lt 0\text{,}\) then let \(a_{n+1}=a_{n}\text{,}\) \(b_{n+1}=c_{n}\text{.}\)
  🔗
  
  🔗
- else let \(a_{n+1}=c_{n}\text{,}\) \(b_{n+1}=b_{n}\text{.}\)
  🔗
  
  🔗
🔗
🔗
If \(b_{n+1}-a_{n+1} \lt \epsilon\text{,}\) then stop, return \((a_{n+1}+b_{n+1})/2\text{.}\) If not let \(n=n+1\) and return to step 2.
🔗

🔗

🔗

The following example applies the bisection method to find \(\sqrt{65}\text{.}\)

🔗

Example 3.2.4.

Use the bisection method to find \(\sqrt{65}\) using the function \(f(x)=x^{2}-65\) on the interval \([8,9]\) to 2 digits.

🔗

First, \(n=0\text{,}\) \(a_{0}=8\) and \(b_{0}=9\) and \(c_{0}=8.5\) is the midpoint of this interval.

🔗

Note that \(f(a_{0})=-1\text{,}\) \(f(b_{0})=16\) and \(f(c_{0})=7.25\text{.}\) Since \(f(a_{0})f(c_{0}) \lt 0\text{,}\) \(a_{1}=8\text{,}\) \(b_{1}=c_{0}=8.5\text{.}\) This is continued in the table:

🔗

Table 3.2.5. Table of interval Endpoints of the Bisection Method

🔗

\(n\)	\(a_{n}\)	\(f(a_{n})\)	\(b_{n}\)	\(f(b_{n})\)	\(c_{n}\)	\(f(c_n)\)
\(1\)	\(8\)	\(-1\)	\(9\)	\(16\)	\(8.5\)	\(7.25\)
\(2\)	\(8\)	\(-1\)	\(8.5\)	\(7.25\)	\(8.25\)	\(3.0625\)
\(3\)	\(8\)	\(-1\)	\(8.25\)	\(3.0625\)	\(8.125\)	\(1.015625\)
\(4\)	\(8\)	\(-1\)	\(8.125\)	\(1.015625\)	\(8.0625\)	\(0.00390625\)
\(5\)	\(8\)	\(-1\)	\(8.0625\)	\(0.00390625\)	\(8.03125\)	\(-0.49902343\)
\(6\)	\(8.03125\)	\(-0.49902343\)	\(8.0625\)	\(0.00390625\)	\(8.046875\)	\(-0.24780273\)
\(7\)	\(8.046875\)	\(-0.24780273\)	\(8.0625\)	\(0.00390625\)	\(8.0546875\)	\(-0.12200927\)
\(8\)	\(8.0546875\)	\(-0.12200927\)	\(8.0625\)	\(0.00390625\)	\(8.05859375\)	\(-0.05906677246\)

And at this point \(b_{8}-a_{8}=0.0078125 \lt 0.01\text{,}\) so we stop. Thus the approximation to \(\sqrt{65}\) is \(c_{8}=8.05859375\text{.}\)

🔗

Subsection 3.2.2 The Bisection Method with a Spreadsheet

The bisection method is fairly easy to perform with a simple handheld calculator, however it is tedious. Let’s begin by building a spreadsheet with the top row of the table in Example 3.2.4.

🔗

Table 3.2.6. Building a Spreadsheet for the Bisection Method

🔗

	A	B	C	D	E	F
1	\(a\)	\(f(a)\)	\(b\)	\(f(b)\)	\(c\)	\(f(c)\)
2	8	-1	9	16	8.5	7.25
3

where

🔗

the cell A2 has been entered as 8
🔗

🔗
the cell B2 has been entered as the formula: =a2*a2-65
🔗

🔗
the cell C2 has been entered as 9
🔗

🔗
the cell D2 has been entered as the formula: =c2*c2-65
🔗

🔗
the cell E2 has been entered as the formula: =0.5*(a2+c2)
🔗

🔗
the cell F2 has been entered as the formula: =e2*e2-65
🔗

🔗

🔗

Note that the formulas in cells B2, D2 and F2 are the functions of the cells to the left of each and the cell in E2 is the midpoint of A2 and C2.

🔗

The next step is to choose new values for the left and right endpoints in columns A and C. To do this, in cell A3 enter the formula: =IF(B3*F3 < 0;A3;E3) (note that some spreadsheets use commas in place of semicolons.) This formula will each choose the same left endpoint or the midpoint c to ensure that there is still a root between the two endpoints. For the same reason, enter =IF(D3*F3 > 0;E3;C3) in cell C3.

🔗

Lastly copy the cells from B2, D2, E2, and F2 into the ones in row 3. You may copy and paste or drag the lower-left corner of each cell. You should have a spreadsheet that looks like:

🔗

	A	B	C	D	E	F
1	\(a\)	\(f(a)\)	\(b\)	\(f(b)\)	\(p\)	\(f(p)\)
2	8	-1	9	16	8.5	7.25
3	8.00000	-1.00000	8.50000	7.25000	8.25000	3.06250

Lastly, if you selected all cells in the last line, click on the lower left corner and drag down to at least line 12, you will build up a table that looks like the table in Example 3.2.4.

🔗

Subsection 3.2.3 Graphical look at the Bisection

Let’s look at the last example graphically to understand the bisection method in a different way. First, the plot of \(f(x)=x^{2}-65\) is given below.

🔗

Figure 3.2.7.

🔗

Next, let’s plot the first few steps of bisection starting on the domain \([8,8.1]\text{.}\) (Note: this is different than above, but more clearly illustrates how bisection works. First, \(a_{0}=8\text{,}\) \(b_{0}=8.1\) and the midpoint is \(c_{0}=8.05\) and since \(f(c_{0}) \lt 0\) and \(f(a_{0}) \lt 0\text{,}\) then \(a_{1}=8.05\) and \(b_{1}=b_{0}=8.1\text{.}\)

🔗

Figure 3.2.8.

🔗

Continuing, \(c_{1}=8.075\) and to keep the root bracketed (such that \(f(a_{2})f(b_{2}) \lt 0\)), then \(a_{2}=8.05, b_{2}=c_{1}=8.075\text{.}\) This method continues until the root is found to a desired accuracy.

🔗

Subsection 3.2.4 Analysis of the Bisection Algorithm

We return to one of our main questions that arise in this area: how to we know that our sequence of points is converging to the correct answer. In short, we will answer this by analyzing the bisection method. The analysis can be summarized in the following theorem.

🔗

Theorem 3.2.9.

Let \(f\) be a continuous function on the closed interval \([a,b]\) with \(f(a)f(b) \lt 0\text{.}\) The bisection method generates a sequence \(\{p_{n}\}\) which converges to \(p\text{,}\) a root (where \(f(p)=0\) ) within \([a,b]\text{,}\) with the property that

\begin{equation} |p-p_{n}| \leq \frac{b-a}{2^{n}}\tag{3.2.1} \end{equation}

🔗

Proof.

The length of the interval \(\ell_{n} = b_{n}-a_{n}\) is halved in each step. That is

\begin{equation*} b_{n} - a_{n} = \frac{1}{2}(b_{n-1}-a_{n-1}) = \frac{1}{4}(b_{n-2}-a_{n-2}) = \cdots \frac{1}{2^{n}}(b_{0}-a_{0}) \end{equation*}

🔗

Since both \(p\) and \(p_{n}\) are in the interval \([a_{n},b_{n}]\text{,}\) thus

\begin{equation*} |p-p_{n}| \leq b_{n} - a_{n} = \frac{1}{2^{n}}(b_{0}-a_{0}) = \frac{b-a}{2^{n}} \end{equation*}

🔗

And using the squeeze theorem (Theorem 1.3.9)

\begin{equation*} \begin{aligned}\lim_{n \rightarrow \infty}|p - p_{n}| = \lim_{n \rightarrow \infty}\frac{1}{2^{n}}(b-a) = 0\end{aligned} \end{equation*}

so the sequence \(\{ p_{n} \}\) converges to \(p\text{.}\)

🔗

Subsection 3.2.5 Order and Rate of Convergence of the Bisection Method

Recall that an iterative method has rate \(O(\beta_{n})\) if

\begin{equation*} \begin{aligned}|p_{n}-p| \leq \lambda |\beta_{n}|\end{aligned} \end{equation*}

🔗

from (3.2.1), \(\beta_{n}=1/2^{n}\) and \(\lambda = (b-a)\text{,}\) so the bisection method converges with rate \(O(1/2^{n})\text{.}\)

🔗

It is a bit more difficult to calculate the order of convergence. Since there is not a simple formula for \(p_{n+1}\text{,}\) it is hard to show that

\begin{equation*} \begin{aligned}\lim_{n \rightarrow \infty}\frac{p_{n+1}- p}{|p_{n} - p|^{\alpha}}= \lambda\end{aligned} \end{equation*}

exists for some \(\alpha\) and \(\lambda\text{.}\)

🔗

Consider, instead, a linearly convergent sequence \(\{p_{n}\}\text{.}\) This means that

\begin{equation*} \lim_{n \rightarrow \infty}\frac{|p_{n+1}-p|}{|p_{n}-p|}= \lambda. \end{equation*}

🔗

For large \(n\text{,}\) this means that

\begin{equation*} \frac{|p_{n+1}-p|}{|p_{n} - p|}\approx \lambda \end{equation*}

\begin{equation*} \begin{aligned}|p_{n+1}- p| \amp \approx \lambda |p_{n} - p| \\ \amp \approx \lambda (\lambda |p_{n-1}- p|)\end{aligned} \end{equation*}

and extending this we can show that

\begin{equation*} |p_{n+1}- p| \approx \lambda^{n} |p_{1} -p|. \end{equation*}

🔗

Since

\begin{equation*} |p_{n+1}- p| \leq \frac{b-a}{2^{n+1}} \end{equation*}

we can say that the bisection is approximately linear with \(\lambda = 1/2\text{.}\)

🔗

Subsection 3.2.6 Stopping Conditions for the Bisection Method

We have shown above that the bisection method converges and Theorem 3.2.9 shows precisely the number of iterations needed to guarantee an error bound. There are three standard ways to determine when to stop:

🔗

The absolute error in the location of the root:

\begin{equation*} \begin{aligned}|p_{n}-p| \leq \frac{1}{2^{n}}(b_{0}-a_{0}) \leq \epsilon\end{aligned} \end{equation*}

🔗

🔗
The relative error in the location of the root:

\begin{equation*} \frac{|p_{n} -p|}{|p_{n}|}\leq \frac{1}{|p_{n}| 2^{n}}(b_{0}-a_{0}) \leq \epsilon. \end{equation*}

🔗

🔗
The root is reached within \(\epsilon\)

\begin{equation*} |f(p_{n})| \leq \epsilon \end{equation*}

🔗

🔗

🔗

Determination of which method often depends what you are looking for.

🔗

Example 3.2.10.

Consider the function \(f(x) = 10x^{3} - 2000\text{.}\) Perform the bisection method using the interval \([0,10]\) and using each stopping condition for \(\epsilon = 0.01\text{.}\) Report the number of steps needs for each.

🔗

Solution.

If we use the Bisection algorithm on this function for the given starting interval, we get the following table. From this we can see when the stopping condition is reached.

🔗

Table 3.2.11. TITLE

🔗

\(n\)	\(a\)	\(f(a)\)	\(b\)	\(f(b)\)	\(c\)	\(f(c)\)	abs. error	rel. error

\(0\)	\(0.00000\)	\(-2000.00\)	\(10.0000\)	\(8000.00\)	\(5.00000\)	\(-750.000\)	\(10.0000\)	\(2.00000\)
\(1\)	\(5.00000\)	\(-750.000\)	\(10.0000\)	\(8000.00\)	\(7.50000\)	\(2218.750\)	\(5.00000\)	\(0.66667\)
\(2\)	\(5.00000\)	\(-750.000\)	\(7.50000\)	\(2218.75\)	\(6.25000\)	\(441.4063\)	\(2.50000\)	\(0.40000\)
\(3\)	\(5.00000\)	\(-750.000\)	\(6.25000\)	\(441.406\)	\(5.62500\)	\(-220.21\)	\(1.25000\)	\(0.22222\)
\(4\)	\(5.62500\)	\(-220.215\)	\(6.25000\)	\(441.406\)	\(5.93750\)	\(93.20068\)	\(0.62500\)	\(0.10526\)
\(5\)	\(5.62500\)	\(-220.215\)	\(5.93750\)	\(93.2007\)	\(5.78125\)	\(-67.741\)	\(0.31250\)	\(0.05405\)
\(6\)	\(5.78125\)	\(-67.7414\)	\(5.93750\)	\(93.2007\)	\(5.85938\)	\(11.65676\)	\(0.15625\)	\(0.02667\)
\(7\)	\(5.78125\)	\(-67.7414\)	\(5.85938\)	\(11.6568\)	\(5.82031\)	\(-28.309\)	\(0.07813\)	\(0.01342\)
\(8\)	\(5.82031\)	\(-28.3088\)	\(5.85938\)	\(11.6568\)	\(5.83984\)	\(-8.39283\)	\(0.03906\)	\(0.00669\)
\(9\)	\(5.83984\)	\(-8.39283\)	\(5.85938\)	\(11.6568\)	\(5.84961\)	\(1.61523\)	\(0.01953\)	\(0.00334\)
\(10\)	\(5.83984\)	\(-8.39283\)	\(5.84961\)	\(1.61523\)	\(5.84473\)	\(-3.39298\)	\(0.00977\)	\(0.00167\)
\(11\)	\(5.84473\)	\(-3.39298\)	\(5.84961\)	\(1.61523\)	\(5.84717\)	\(-0.88992\)	\(0.00488\)	\(0.00084\)
\(12\)	\(5.84717\)	\(-0.88992\)	\(5.84961\)	\(1.61523\)	\(5.84839\)	\(0.36240\)	\(0.00244\)	\(0.00042\)
\(13\)	\(5.84717\)	\(-0.88992\)	\(5.84839\)	\(0.36240\)	\(5.84778\)	\(-0.26383\)	\(0.00122\)	\(0.00021\)
\(14\)	\(5.84778\)	\(-0.26383\)	\(5.84839\)	\(0.36240\)	\(5.84808\)	\(0.04927\)	\(0.00061\)	\(0.00010\)
\(15\)	\(5.84778\)	\(-0.26383\)	\(5.84808\)	\(0.04927\)	\(5.84793\)	\(-0.10728\)	\(0.00031\)	\(0.00005\)
\(16\)	\(5.84793\)	\(-0.10728\)	\(5.84808\)	\(0.04927\)	\(5.84801\)	\(-0.02901\)	\(0.00015\)	\(0.00003\)
\(17\)	\(5.84801\)	\(-0.02901\)	\(5.84808\)	\(0.04927\)	\(5.84805\)	\(0.01013\)	\(0.00008\)	\(0.00001\)
\(18\)	\(5.84801\)	\(-0.02901\)	\(5.84805\)	\(0.01013\)	\(5.84803\)	\(-0.00944\)	\(0.00004\)	\(0.00001\)
\(19\)	\(5.84803\)	\(-0.00944\)	\(5.84805\)	\(0.01013\)	\(5.84804\)	\(0.00034\)	\(0.00002\)	\(0.00000\)

The first stopping condition occurs when \(n=10\text{,}\) the second stopping condition occurs when \(n=8\) and the final condition occurs when \(n=18\text{.}\) Each are boxed above.

🔗

If we stop at different values of \(n\text{,}\) there is a different approximate root.

🔗

From the above example, one can see that using different stopping conditions give different results. A natural question to ask is which condition to use and of course the answer is it depends. If you need to ensure that you have reached a certain number of digits of accuracy, then 1) is good, and if you are just trying to find an answer that has a very small function value then 3) is good.

🔗

Prev Top Next