$$
\definecolor{importantColor}{RGB}{255,0,0}
\definecolor{secondaryColor}{RGB}{255,0,255}
$$

- The bisection method is an algorithm that
*approximates*the location of an $$x$$-intercept (a root) of a Continuous function. - The bisection method depends on the Intermediate Value Theorem.
- The algorithm is
*iterative*. This means that the result from using it once will help us get a better result when we use the algorithm a second time.

Suppose $$f(x)$$ is continuous over $$[a,b]$$, and $$f(a)$$ and $$f(b)$$ have opposite signs (see the image below). Then, the Intermediate Value Theorem tells us that the function will achieve every value between $$f(a)$$ and $$f(b)$$ at least once somewhere in $$[a,b]$$.

Since $$f(a)$$ and $$f(b)$$ have opposite signs, then we know $$0$$ is somewhere in-between. So the IVT guarantees that somewhere in $$[a,b]$$ the function will equal 0 (again, see the image below).

We approximate the location of the root by finding the midpoint of the interval at $$x = \frac{a+b} 2$$ (see image below).

Suppose $$f(x)$$ is continuous over $$[a,b]$$ and the function values at the endpoints have different signs.

- Find the midpoint of $$[a,b]$$. Call it $$x_1$$.
- If $$f(x_1) = 0$$, we're done.
- If not, then $$x_1$$ is our first approximation to the root of the function . It has a maximum error of $$\frac 1 2$$ the length of the interval.

- Find a smaller interval where $$f(x)$$ has opposite signs at the endpoints. This new interval will either be $$[a,x_1]$$, or $$[x_1, b]$$.
- Using this smaller interval, repeat Steps 1 and 2 until the error is small enough.

Using the Bisection Method, find three approximations of the root of $$f(x) = \frac 1 4 x^2 -3$$. Determine the maximum error possible in using each approximation.

Step 1

Verify the Bisection Method can be used.

We first note that the function is continuous everywhere on it's domain.

Next, we pick an interval to work with. If we pick $$x = 2$$, we see that $$f(0) = -2 < 0$$ and if we pick $$x = 4$$ we see $$f(4) = 1 >0$$. So we can start with the interval $$[2,4]$$.

Step 2

Find the first approximation to the root and its associated error.

The first approximation to the root is the midpoint of our starting interval. In this case, the midpoint of $$[2,4]$$ is at $$x = 3$$.

Maximum Error: Since the root has to be between $$x =2$$ and $$x = 4$$, using $$x = 3$$ as an approximation for the root means the farthest away the root could possibly be is a distance of $$\pm1$$ unit (the plus/minus is because our approximation could be too big or too small).

In general, the maximum error in using a particular approximation is half the interval length.

Step 3

Use the midpoint to find a smaller interval so we can improve our approximation.

Notice that $$f(3) = \frac 1 4(3)^2 - 3 = -\frac 3 4 < 0$$. Updating our graph, we now have three points on it.

Examining this graph, we see that the root must lie between $$x=3$$ and $$x = 4$$. Consequently, this is our new interval.

Step 4

Find the second approximation and its associated error.

The midpoint of the interval $$[3,4]$$ is at $$x = \frac 7 2$$. This is the second approximation.

Max Error: Our interval has a length of 1 unit, so the maximum possible error in using $$x = \frac 7 2$$ as an approximation will be $$\pm 1/2$$ of a unit.

Our graph now looks like this:

Step 5

Find the next interval.

We note that $$f\left(\frac 7 2\right) = \frac 1 {16} > 0$$. Plotting this on our graph we see the following.

Examining this graph, we see that the root must lie between $$x = 3$$ and $$x = \frac 7 2$$. This becomes our next interval.

Step 6

Find the third approximation and its associated error.

The midpoint of the interval $$\left[3, \frac 7 2\right]$$ is at $$x = \frac{13} 4$$, as shown on the graph below. This is the next approximation.

Max Error: The interval has a length of $$1/2$$, so the maximum possible error is $$\pm1/4$$ of a unit.

Answer

The table below summarizes the approximations we found and their associated errors.

$$ \begin{array}{ccc} \mbox{Approximation} & x\mbox{-value} & \mbox{Possible Error}\\ \hline 1^{st} & x = 3 & \pm1\\[6pt] 2^{nd} & x = \frac 7 2 & \pm\frac 1 2\\[6pt] 3^{rd} & x = \frac{13} 4 & \pm\frac 1 4 \end{array} $$

Use the bisection method to approximate the solution to the equation below to within less than 0.1 of its real value. Assume $$x$$ is in radians.

$$\sin x = 6 - x$$

Step 1

Rewrite the equation so it is equal to 0.

$$ x - 6 + \sin x = 0 $$

The function we'll work with is $$f(x) = x - 6 + \sin x$$. Notice that the function is continuous everywhere.

Step 2

Find an initial interval to work with.

Setting up a table of values, we see the following.

$$ \begin{array}{cl} x & {f(x)}\\ \hline 0 & f(0) = -6\\ 1 & f(1) \approx -4.2\\ 2 & f(2) \approx -3.1\\ 3 & f(3) \approx -2.9\\ 4 & f(4) \approx -2.8\\ 5 & f(5) \approx -2\\ 6 & f(6) \approx -0.3\\ 7 & f(7) \approx 1.7\\ \end{array} $$

The first time we see a positive function value is at $$x = 7$$. So, we can use $$[6,7]$$ as the initial interval.

Step 3

Find the first approximation and its associated error.

$$ \begin{array}{ccc} \mbox{Interval} & \mbox{Midpoint} & \mbox{Max Error}\\ \hline [6, 7] & \blue{6.5} & \pm0.5 \end{array} $$

- 1st Approximation: $$x = 6.5$$
- Associated error: $$\pm 0.5$$ units.

Step 4

Find the 2nd interval. Use this new interval to determine the 2nd approximation. The first line of the table is included for completeness. The new work is on the second line.

$$ \begin{array}{cccc|cc} {\mbox{Finding the New Interval}}&&&& \mbox{Next Approximation}\\[6pt] f(\mbox{left}) & f(\mbox{mid}) & f(\mbox{right}) & \mbox{New Interval} & \mbox{Midpoint} & \mbox{Max Error}\\ \hline &&{\mbox{Starting Interval:}}& [6,7] & 6.5 & \pm0.5\\ f(\red 6)\approx-0.28 & f(\red{6.5})\approx 0.72 & f(7)\approx 1.66 & [6, 6.5] & \blue{6.25} & \pm0.25 \end{array} $$

- 2nd Interval: $$[6,6.5]$$
- 2nd Approximation: $$x = 6.25$$
- Associated Error: $$\pm0.25$$ units.

Step 5

Repeat Step 4 until the associated error is less than 0.1 units.

$$ {\mbox{Finding the 3rd Approximation}} \\ \\ \begin{array}{cccc|cc} &&{\mbox{Finding the New Interval}}&&&{\mbox{Next Approximation}} \\[8pt] f(\mbox{left}) & f(\mbox{mid}) & f(\mbox{right}) & \mbox{New Interval} & \mbox{Midpoint} & \mbox{Max Error}\\ \hline &&{\mbox{Starting Interval:}}& [6,7] & 6.5 & \pm0.5\\ f(6)\approx-0.28 & f(6.5)\approx 0.72 & f(7)\approx 1.66 & [6, 6.5] & 6.25 & \pm0.25\\ f(\red 6)\approx-0.28 & f(\red{6.25})\approx 0.22 & f(6.5)\approx 0.72 & [6,6.25] & \blue{6.125} & \pm0.125 \end{array} $$

- 3rd Interval: $$[6,6.25]$$
- 3rd Approximation: $$[6,6.125]$$
- Associated Error: $$\pm0.125$$ units.

$$ {\mbox{Finding the 4th Approximation}}\\[6pt] \\ \\ \begin{array}{cccc|cc} &&{\mbox{Finding the New Interval}}&&&{\mbox{Next Approximation}} \\[8pt] f(\mbox{left}) & f(\mbox{mid}) & f(\mbox{right}) & \mbox{New Interval} & \mbox{Midpoint} & \mbox{Max Error}\\ \hline &&{\mbox{Starting Interval:}}& [6,7] & 6.5 & \pm0.5\\ f(6)\approx-0.28 & f(6.5)\approx 0.72 & f(7)\approx 1.66 & [6, 6.5] & 6.25 & \pm0.25\\ f(6)\approx-0.28 & f(6.25)\approx 0.22 & f(6.5)\approx 0.72 & [6,6.25] & 6.125 & \pm0.125\\ f(6) \approx-0.28 & f(\red{6.125})\approx-0.03 & f(\red{6.25})\approx 0.22 & [6.125,6.25] & \blue{6.1875} & \pm0.0625 \end{array} $$

- 4th Interval: $$[6,6.25]$$
- 4th Approximation: $$[6,6.125]$$
- Associated Error: $$\pm0.125$$ units.

Answer

The solution to the equation is approximately $$6.1875$$. This approximation is accurate to within $$\pm 0.0625$$ units.

Find the third approximation from the bisection method to approximate the value of $$\sqrt[3] 2$$.

Step 1

Find (make) a non-linear function with a root at $$\sqrt[3] 2$$.

We are interested in knowing the approximate value of $$x = \sqrt[3] 2$$. We use this equation to build a non-linear function with a root at the appropriate value.

$$ \\ \begin{align*} x & = \sqrt[3] 2\\ x^3 & = 2\\ x^3 - 2 & = 0 \end{align*} \\ $$

We'll use the function $$f(x) = x^3 - 2$$. Notice that the function is continuous everywhere.

Step 2

Step 3

Setup and work through the table as in the previous example. The approximations are in blue. The new intervals are in red.

$$ \begin{array}{cccc|cc} &&{\mbox{Finding the New Interval}}&&{\mbox{Next Approximation}} \\[8pt] f(\mbox{left}) & f(\mbox{mid}) & f(\mbox{right}) & \mbox{New Interval} & \mbox{Midpoint} & \mbox{Max Error}\\ \hline &&{\mbox{Starting Interval:}}& [0,2] & \blue 1 & \pm 1\\ f(0)=-2 & f(\red 1) = -1 & f(\red 2) = 6 & [1, 2] & \blue{1.5} & \pm0.5\\ f(\red 1) = -1 & f(\red{1.5})\approx 1.4 & f(2)=6 & [1,1.5] & \blue{1.25} & \pm0.25 \end{array} $$

Answer

$$\sqrt[3] 2 \approx \blue{1.25}$$ with a possible error of $$\pm 0.25$$. (Even with only 3 approximations, we're pretty close! The calculator tells us $$\sqrt[3] 2 \approx 1.25992$$

We know the first approximation is within $$0.5(b-a)$$ of the actual value of the root. Similarly,

- the second approximation is within $$0.5^2(b-a)$$ of the actual value, and
- the third approximation is within $$0.5^3(b-a)$$ of the actual value.
- the fourth approximation is within $$0.5^4(b-a)$$ of the actual value.

In general, the $$n^{th}$$ approximation will be within $$0.5^n(b-a)$$ of the actual value. This allows us to determine ahead of time how many iterations are needed to achieve a desired degree of accuracy, as in the following example.

The function $$f(x) = x^4 - 5$$ has a positive root that is less than 3. If we started the bisection method with the interval $$[0,3]$$, how many iterations would it take before our approximation is within $$10^{-4}$$ of the actual value?

Step 1

Solve $$0.5^n(b-a)=0.01$$ for $$n$$ when $$a = 0$$ and $$b = 3$$

$$ \\ \begin{align*} 0.5^n(3 -0) & = 10^{-4}\\ 0.5^n(3) & = 10^{-4}\\ 0.5^n & = \frac{10^{-4}} 3\\[6pt] n\ln(0.5) & = \ln\left(\frac 1 {30000}\right)\\[6pt] -n\ln 2 & = -\ln(30000)\\[6pt] n & = \frac{\ln 30000}{\ln 2}\\[6pt] & \approx 14.87 \end{align*} \\ $$

We would need at least 15 iterations to ensure the accuracy desired.