Answers to exercises

Exercise 1

For example, we could define

\[ f(x) = \left\{ \begin{array}{ll} -1 & 0 \leq x < \frac{1}{2} \\ 1 & \frac{1}{2} \leq x \leq 1 \end{array} \right. \]

Exercise 2

As each successive $[a_n, b_n]$ has half the length of $[a_{n-1}, b_{n-1}]$, the interval $[a_n, b_n]$ is $\frac{1}{2^n}$ times the size of $[a_0, b_0]$. Thus $\frac{b_n - a_n}{b-a} = \frac{1}{2^n}$.

Exercise 3

Suppose that $f(a_0)$ is positive and $f(b_0)$ is negative. We will prove by induction that for all non-negative integers $n$, $f(a_n)$ is positive and $f(b_n)$ is negative. The claim is clearly for $n=0$. Now suppose the claim holds for $n=k$, so $f(a_k)>0$ and $f(b_k)<0$; we will prove the claim for $n=k+1$, showing that $f(a_{k+1})>0$ and $f(b_{k+1})<0$.

Bisecting $[a_k, b_k]$, we consider $f \left( \frac{a_k + b_k}{2} \right)$. If $f \left( \frac{a_k + b_k}{2} \right)$ is positive, then $[a_{k+1}, b_{k+1}] = \left[\frac{a_k + b_k}{2}, b_{k+1} \right]$, so $f(a_{k+1})>0$ and $f(b_{k+1})<0$ as claimed. Alternatively, if $f \left( \frac{a_k+b_k}{2} \right) < 0$, then $[a_{k+1}, b_{k+1}] = \left[ a_k, \frac{a_k + b_k}{2} \right]$, so $f(a_{k+1})>0$ and $f(b_{k+1})<0$ again. Either way, $f(a_{k+1})>0$ and $f(b_{k+1})< 0$. By induction, all $f(a_n)>0$ and all $f(b_n)<0$.

One can prove, by a similar method, that if $f(a_0)$ is negative and $f(b_0)$ is positive, then for all non-negative integers $n$, $f(a_n)$ is negative and $f(b_n)$ is positive.

Exercise 4

Let $f(x) = \ln x - 1$, so we solve $f(x) = 0$ using the bisection method with $[a_0, b_0] = [2,3]$. We tabulate the calculation as follows.

Step $n$	$a_n$	Sign of $f(a_n)$	$b_n$	Sign of $f(b_n)$	Midpoint $\frac{a_n + b_n}{2}$	Sign of $f \left( \frac{a_n + b_n}{2} \right)$
$0$	$2$	$-$	$3$	$+$	$\frac{5}{2} = 2.5$	$-$
$1$	$\frac{5}{2} = 2.5$	$-$	$3$	$+$	$\frac{11}{4}=2.75$	$+$
$2$	$\frac{5}{2}=2.5$	$-$	$\frac{11}{4}=2.75$	$+$	$\frac{21}{8}=2.625$	$-$
$3$	$\frac{21}{8}=2.625$	$-$	$\frac{11}{4}=2.75$	$+$	$\frac{43}{16}=2.6875$	$-$
$4$	$\frac{43}{16}=2.6875$	$-$	$\frac{11}{4}=2.75$	$+$	$\frac{87}{32}$	$+$
$5$	$\frac{43}{16}=2.6875$	$-$	$\frac{87}{32}=2.71875$	$+$	$\frac{173}{64}$	$-$
$6$	$\frac{173}{64}=2.703125$	$-$	$\frac{87}{32}=2.71875$	$+$

Thus $e \in \left[ \frac{173}{64}, \frac{87}{32} \right] = \left[ 2.703125, .71875 \right],$ and $e$ has been calculated to within an accuracy of $\frac{87}{32}-\frac{173}{64} = \frac{1}{64} = 0.015625 < 0.02.$

Exercise 5

There is just one solution. Let $f(x) = \cos x - x$. We note $f(0) = 1$ and $f(1) < 0$, so there is a solution in $[0,1]$. (One can check that for negative $x$, $f(x) > 0$, and for $x>1$, $f(x) < 0$.) Using the bisection method starting from $[a_0, b_0] = [0,1]$, after 7 iterations we arrive at $[a_7, b_7] = \left[ \frac{47}{64}, \frac{95}{128} \right] = [0.734375, 0.7421875]$, which has length $1/128 < 0.01$. To 6 decimal places the solution is $0.739085$.

Exercise 6

Letting $f(x) = 3x-1$, we apply the bisection method to solve $f(x) = 0$ starting from the interval $[0,1]$.

Step $n$	$a_n$	Sign of $f(a_n)$	$b_n$	Sign of $f(b_n)$	Midpoint $\frac{a_n + b_n}{2}$	Sign of $f \left( \frac{a_n + b_n}{2} \right)$
$0$	$0$	$-$	$1$	$+$	$\frac{1}{2} = 0.5$	$+$
$1$	$0$	$-$	$\frac{1}{2} = 0.5$	$+$	$\frac{1}{4}=0.25$	$-$
$2$	$\frac{1}{4}=0.25$	$-$	$\frac{1}{2} = 0.5$	$+$	$\frac{3}{8}=0.375$	$+ $
$3$	$\frac{1}{4}=0.25$	$-$	$\frac{3}{8}=0.375$	$+$	$\frac{5}{16}=0.3125$	$-$
$4$	$\frac{5}{16}=0.3125$	$-$	$\frac{3}{8}=0.375$	$+$	$\frac{11}{32}=0.34375$	$+$
$5$	$\frac{5}{16}=0.3125$	$-$	$\frac{11}{32}=0.34375$	$+$	$\frac{21}{64}=0.328125$	$-$
$6$	$\frac{21}{64}=0.328125$	$-$	$\frac{11}{32}=0.34375$	$+$	$\frac{43}{128}=0.3359375$	$+$
$7$	$\frac{21}{64}=0.328125$	$-$	$\frac{43}{128}=0.3359375$	$+$	$\frac{85}{256}=0.33203125$	$-$
$8$	$\frac{85}{256}=0.33203125$	$-$	$\frac{43}{128}=0.3359375$	$+$	$\frac{171}{512}=0.333984375$	$+$
$9$	$\frac{85}{256}=0.33203125$	$-$	$\frac{171}{512}=0.333984375$	$+$	$\frac{341}{1024}=0.3330078125$	$-$
$10$	$\frac{341}{1024}=0.3330078125$	$-$	$\frac{171}{512}=0.333984375$	$+$

So to within accuracy of $\frac{1}{1024} < 0.001$, $1/3$ is approximated to lie in the interval $\left[ \frac{341}{1024},\frac{171}{512} \right] = [0.3330078125,0.333984374].$

We note that the signs of $f \left( \frac{a_n + b_n}{2} \right)$ alternate $+$, $-$, $+$, $-$, etc. This corresponds to the fact that, in binary, $1/3$ is written as $0.0101010101\cdots = 0.\overline{01}$. The alternating zeroes and ones correspond to the alternating between positive and negative signs. See the section "Bisection and binary numbers" above for details.

Exercise 7

In the example, we obtained an interval of $\left[ \frac{181}{128}, \frac{91}{64} \right] = [1.4140625, 1.421875]$ of length $\frac{1}{128}$ approximating $\sqrt{2}$. The best guess for $\sqrt{2}$ is then the midpoint of this interval, $\frac{363}{256} = 1.41796875$. It is within $\frac{1}{256} = 0.00390625$ of a solution.

Exercise 8

The next intervals obtained after $[a_5, b_5] = \left[ \frac{25}{8}, \frac{101}{32} \right] = [3.125, 3.15625]$ are $[a_6, b_6] = [ 3.140625, 3.15625 ]$, $[a_7, b_7] = [3.140625, 3.1484375]$, $[a_8, b_8] = [3.140625, 3.14453125]$. As both $a_8$ and $b_8$ round to $3.14$ to two decimal places, we have approximated $\pi \sim 3.14$, to two decimal places.

Exercise 9

After $[a_7, b_7] = 1.4140625, 1.421875]$ the bisection method yields $[a_8, b_8] = [1.4140625, 1.41796875]$, $[a_9, b_9] = [1.4140625, 1.416015625]$, $[a_{10}, b_{10}] = [1.4140625, 4.4150390625]$, $[a_{11}, b_{11}] = [1.4140625,1.41455078125]$. Both endpoints round to $1.41$ to 2 decimal places, so $\sqrt{2} \sim 1.41$ to 2 decimal places.

Exercise 10

For part (a), since $f(x) = x^2 - 2$ and $f'(x) = 2x$, we have

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n^2 - 2}{2x_n} = x_n - \frac{1}{2} x_n + \frac{1}{x_n} = \frac{x_n}{2} + \frac{1}{x_n}. \]

Now substituting $x_n = y_n + \sqrt{2}$ gives $y_{n+1} + \sqrt{2} = \frac{y_n + \sqrt{2}}{2} + \frac{1}{y_n + \sqrt{2}}$ so

\[ y_{n+1} = \frac{y_n + \sqrt{2}}{2} + \frac{1}{y_n + \sqrt{2}} - \sqrt{2} = \frac{(y_n + \sqrt{2})^2 + 2 - 2 \sqrt{2} (y_n + \sqrt{2}) }{2(\sqrt{2} + y_n)} = \frac{y_n^2}{2(\sqrt{2}+y_n)}. \]

For part (b), let $g(x) = \frac{x}{2} + \frac{1}{x}$, so $x_{n+1} = g(x_n)$. The function $g$ is graphed below. When $x>0$, $g(x)>0$; and when $x<0$, $g(x)<0$. For $x>0$, the minimum value of $g$ is given by $g(\sqrt{2}) = \sqrt{2}$; when $x<0$, the maximum value of $g$ is given by $g(-\sqrt{2})=-\sqrt{2}$. Hence if $x>0$ then $g(x) \geq \sqrt{2}$; and if $x<0$ then $g(x) \leq -\sqrt{2}$. So if $x_1 > 0$ then $x_2 = g(x_1) \geq \sqrt{2}$, and all subsequent $x_n \geq \sqrt{2}$. Similarly, if $x_1 < 0$ then all subsequent $x_n \leq - \sqrt{2}$.

For part (c), suppose $0 < y_n < 10^{-k}$. Then $y_{n+1} = \frac{y_n^2}{2(\sqrt{2}+y_n)}$ is positive, and

\[ y_{n+1} = \frac{y_n^2}{2(\sqrt{2}+y_n)} < \frac{y_n^2}{2\sqrt{2}} < \frac{10^{-2k}}{2\sqrt{2}} < 10^{-2k} \quad \text{as desired.} \]

For part (d), if $x_n$ differs from $\sqrt{2}$ by less than $10^{-k}$, for an integer $k \geq 1$, then $x_n$ is positive. By (b) above $x_1$ is positive; and as $n \geq 2$ then $x_n > \sqrt{2}$. So $y_n = x_n - \sqrt{2} \in (0, 10^{-k})$. By (c) above then $y_{n+1}\in (0, 10^{-2k})$, so $x_{n+1}$ differs from $\sqrt{2}$ by less than $10^{-2k}$.

Exercise 11

We apply Newton's method to $f(x) = \cos x - x$. We know, by the intermediate value theorem, that there is a solution in $[0,1]$, so we can start at $x_1 = 1$. We obtain (to 9 decimal places) $x_1 = 0.750 363 868$, $x_2 = 0.739 112 891$, $x_3 = 0.739 085 133$, $x_4 = 0.739 085 133$.

After only 3 iterations we have the solution to 9 decaimal places. This is much better than the bisection method, which took 7 iterations to obtain 6 decimal places.

Exercise 12

We have $f(x) = x(x-1)(x-2) = 2x-3x^2+x^3$ and $f'(x) = 2-6x+3x^2 = 3 \left[(x-1)^2 - \frac{1}{3}\right]$. Substituting $x = 1 \pm \frac{1}{\sqrt{5}}$, we obtain

\begin{align*} f(x) &= x(x-1)(x-2) = \left( 1 \pm \frac{1}{\sqrt{5}} \right) \left( \pm \frac{1}{\sqrt{5}} \right) \left( -1 \pm \frac{1}{\sqrt{5}} \right) = \frac{\pm 1}{5\sqrt{5}} \left( 1^2 - \left( \sqrt{5} \right)^2 \right) = \frac{\mp 4}{5\sqrt{5}} \\ f'(x) &= 3 \left[ \left( \pm \frac{1}{\sqrt{5}} \right)^2 - \frac{1}{3} \right] = 3 \left[ \frac{1}{5} - \frac{1}{3}\right] = \frac{-2}{5} \\ x - \frac{f(x)}{f'(x)} &= 1 \pm \frac{1}{\sqrt{5}} - \frac{ \frac{\mp 4}{5\sqrt{5}} }{ \frac{-2}{5} } = 1 \pm \frac{1}{\sqrt{5}} \mp \frac{2}{\sqrt{5}} = 1 \mp \frac{1}{\sqrt{5}} \end{align*}

Thus if $x_1 = 1+\frac{1}{\sqrt{5}}$ then $x_2 = 1-\frac{1}{\sqrt{5}}$ and $x_3 = 1+\frac{1}{\sqrt{5}}$.

Exercise 13

The original interval has length $b-a$. Afer $n$ iterations the interval has length $\frac{b-a}{2^n}$. The best guess is the midpoint of this interval; its distance from the solution can be no more than half the length of this interval. So this best guess is within $\frac{b-a}{2^{n+1}}$ of a solution.

Exercise 14

The first interval $[a_0, b_0] = [-5,5]$ has length $10$, so after $n$ iterations, the interval $[a_n, b_n]$ has length $\frac{10}{2^n}$. To obtain an accuracy of 0.05 we require $\frac{10}{2^n} < 0.05$, so $2^n > \frac{10}{0.05} = 200$, hence $n > \log_2 (200) \sim 7.64$, so $8$ steps are required.

Exercise 15

The first interval has length $b-a$, so after $n$ iterations, the interval $[a_n,b_n]$ has length $\frac{b-a}{2^n}$. To obtain an accuracy of $\epsilon$, we require $\frac{b-a}{2^n} < \epsilon$. Rearranging this gives $2^n > \frac{b-a}{\epsilon}$, or $n > \log_2 \left( \frac{b-a}{\epsilon} \right)$. So the bisection method will require at least $\log_2 \left( \frac{b-a}{\epsilon} \right)$ steps.

Exercise 16

Given an interval $[a,b] = [a_0, b_0]$, you could divide it into ten subintervals at the 9 points $\frac{1}{10}, \frac{2}{10}, \ldots, \frac{9}{10}$ from $a$ to $b$, i.e. at the points $a + \frac{1}{10}(b-a)$, $a + \frac{2}{10}(b-a)$, $\ldots$, $a + \frac{9}{10}(b-a)$. The $j$'th point is $a + \frac{j}{10} (b-a) = \frac{10-j}{10} a + \frac{j}{10} b$. You could then evaluate $f$ at these 9 points. If $f=0$ at any of these points, we have an exact solution. Otherwise, as $f$ changes sign between $a$ and $b$, it must change sign on at least one of the sub-intervals; one such sub-interval is chosen as $[a_1, b_1]$. Repeating this method produces a sequence of nested intervals $[a_0, b_0] \supset [a_1, b_1] \supset [a_2, b_2] \supset \cdots$, each of which contains a solution, and each of which is one tenth the size of the previous interval. If $[a_0, b_0] = [0,1]$, then each successive $[a_n, b_n]$ determines a successive decimal digit of the solution.