Exercise 3.16

Question

\def\eps{\varepsilon}
Exercise 16:
    Fix a positive number $\alpha$. Choose $x_1>\sqrt{\alpha}$, and define $x_2,x_3,\ldots$ by the recursion formula $$x_{n+1}=\frac{1}{2}\biggl(x_n+\frac{\alpha}{x_n}\biggr).$$

(a) Prove that $\{x_n\}$ decreases monotonically and that $\lim x_n=\sqrt{\alpha}$.

(b) Put $\varepsilon=x_n-\sqrt{\alpha}$, and show that $$\varepsilon_{n+1}=\frac{\varepsilon_n^2}{2x_n}<\frac{\varepsilon_n^2}{2\sqrt{\alpha}}$$ so that, setting $\beta=2\sqrt{\alpha}$,
    $$\varepsilon<\beta\biggl(\frac{\varepsilon_1}{\beta}\biggr)^{2^n}\quad\quad(n=1,2,\ldots).$$

(c) this is a good algorithm for computing square roots, since the recursion formula is simple and the convergence is extremely rapid. For example, if $\alpha=3$ and $x_1=2$, show that
    $\varepsilon_1/\beta<0.1$ and that therefore $\varepsilon_5<4\cdot10^{-16}$, $\varepsilon_6<4\cdot10^{-32}$.

Dan Whitman · Accepted Answer

\def\where{\,|\,} \def\eps{\varepsilon} \def\sa{\sqrt\alpha} (a) First we show that $x_n > \sa$ for all $n \geq 1$ by induction. The $n=1$ case is obvious since $x_1 > \sa$ by construction. So then assume that $x_n > \sa$. We then have \begin{align*} x_n &> \sa \ x_n - \sa &> 0 \ (x_n - \sa)^2 &> 0 && \text{(since both sides $\geq 0$)}\ x_n^2 - 2x_n\sa + \alpha &> 0 \ x_n^2 + \alpha &> 2x_n\sa \ \frac{x_n^2 + \alpha}{x_n} &> 2\sa && \text{(since $x_n > \sa > 0$)}\ x_n + \frac{\alpha}{x_n} &> 2\sa \ \frac{1}{2}\left(x_n + \frac{\alpha}{x_n}\right) &> \sa \ x_{n+1} &> \sa \end{align*} by definition. Therefore $x_n^2 > \alpha$ for any $n \geq 1$ . From this we can easily show that $\{x_n\}$ is decreasing monotonically: $$ x_{n+1} = \frac{1}{2}\left(x_n + \frac{\alpha}{x_n}\right) < \frac{1}{2}\left(x_n + \frac{x_n^2}{x_n}\right) = \frac{1}{2}\left(x_n + x_n\right) = x_n \,. $$ Now since $\{x_n\}$ is monotonic and bounded (bounded above by $x_1$ and bounded below by $\sa$), it converges by Theorem~3.14. So suppose that $\lim_{n \to \infty} x_n = x$. Then clearly it must be that $\lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} x_n = x$ also. So we have $$ \lim_{n \to \infty} x_{n+1} = \lim_{n \to \infty} \frac{1}{2}\left(x_n + \frac{\alpha}{x_n}\right) = \frac{1}{2}\left(\lim_{n \to \infty} x_n + \frac{\alpha}{\lim_{n \to \infty} x_n}\right) = \frac{1}{2}\left(x + \frac{\alpha}{x}\right) = x \,, $$ where we have used Theorem~3.3. Solving this simple equation for $x$ results in $x = \lim_{n \to \infty} x_n = \sa$. (b) We have simply $$ \epsilon_{n+1} = x_{n+1} - \sa = \frac{1}{2}\left(x_n + \frac{\alpha}{x_n}\right) - \sa = \frac{1}{2x_n}(x_n^2 + \alpha) - \sa = \frac{1}{2x_n}(x_n^2 + \alpha - 2x_n\sa) $$ $$ \frac{(x_n - \sa)^2}{2x_n} = \frac{\epsilon_n^2}{2x_n} < \frac{\epsilon_n^2}{2\sa} $$ since $x_n > \sa$. So then, letting $\beta = 2\sa$, we claim that $$ \epsilon_{n+1} < \beta\left(\frac{\epsilon_1}{\beta}\right)^{2^n} $$ for all $n \geq 1$. A simple proof by induction shows that this is indeed the case. For $n=1$ we have $$ \epsilon_{n+1} = \epsilon_2 < \frac{\epsilon_1^2}{\beta} = \beta\frac{\epsilon_1^2}{\beta^2} = \beta\left(\frac{\epsilon_1}{\beta}\right)^2 = \beta\left(\frac{\epsilon_1}{\beta}\right)^{2^1} = \beta\left(\frac{\epsilon_1}{\beta}\right)^{2^n} \,. $$ Now assume that $$ \epsilon_{n+1} < \beta\left(\frac{\epsilon_1}{\beta}\right)^{2^n} \,. $$ Then we have $$ \epsilon_{n+2} < \frac{\epsilon_{n+1}^2}{\beta} < \frac{1}{\beta}\left[\beta \left(\frac{\epsilon_1}{\beta}\right)^{2^n}\right]^2 = \frac{1}{\beta}\left[\beta^2 \left(\frac{\epsilon_1}{\beta}\right)^{2^n \cdot 2}\right] = \beta\left(\frac{\epsilon_1}{\beta}\right)^{2^{n+1}} \,. $$ (c) For $\alpha = 3$ and $x_1 = 2$ we first show that $\epsilon_1 / \beta < 1/10$ without using decimal approximations for $\sa = \sqrt3$, starting with the obvious: $$ 100 < 108 = 36 \cdot3 $$ $$ \sqrt{100} < \sqrt{36}\sqrt{3} $$ $$ 10 < 6\sqrt{3} $$ $$ 10 - 5\sqrt{3} < \sqrt{3} $$ $$ 20 - 10\sqrt{3} < 2\sqrt{3} $$ $$ 10(2 - \sqrt{3}) < 2\sqrt{3} $$ $$ \frac{2 - \sqrt{3}}{2\sqrt{3}} < \frac{1}{10} $$ $$ \frac{x_1 - \sa}{2\sa} < \frac{1}{10} $$ $$ \frac{\epsilon_1}{\beta} < \frac{1}{10} \,. $$ We also have $$ 12 < 16 $$ $$ 4 \cdot 3 < 16 $$ $$ \sqrt{4}\sqrt{3} < \sqrt{16} $$ $$ 2\sqrt{3} < 4 $$ $$ \beta < 4 \,, $$ from which it follows that $$ \epsilon_5 < \beta \left(\frac{\epsilon_1}{\beta}\right)^{2^4} < 4 \left(\frac{\epsilon_1}{\beta}\right)^{16} < 4 \left(\frac{1}{10}\right)^{16} = 4 \cdot 10^{-16} \,. $$ Likewise $$ \epsilon_6 < \beta \left(\frac{\epsilon_1}{\beta}\right)^{2^5} < 4 \left(\frac{\epsilon_1}{\beta}\right)^{32} < 4 \left(\frac{1}{10}\right)^{32} = 4 \cdot 10^{-32} \,. $$

Amit Awasthi · Answer

\begin{proof}[Proof of $(a)$] First, we show that $x_n > \sqrt{\alpha}$ for all $n$ by contradiction by assuming $x_{n+1} = \left( x_n + \alpha/x_n \right)/2 < \sqrt{\alpha}$. Then, \begin{align*} x_n + \frac{\alpha}{x_n} &< 2\sqrt{\alpha}\ (x_n - \sqrt{\alpha})^2 &< 0, \end{align*} but this is a contradiction since a square of a real number is always greater than or equal to 0. So, $x_{n+1} > \sqrt{\alpha}$ for all $n$, and we already know $x_1 > \sqrt{\alpha}$, so $x_n > \sqrt{\alpha}$ for all $n$. \par Next to show that $\{x_n\}$ decreases monotonically we have to show $x_n - x_{n+1} > 0$ for all $n$. So substituting in \eqref{3.16a}, we get \begin{equation*} x_n - x_{n+1} = x_n - \frac{1}{2}\left( x_n + \frac{\alpha}{x_n} \right) = \frac{x_n^2 - \alpha}{2x_n}, \end{equation*} and since $x_n > \sqrt{\alpha}$, we have $x_n - x_{n+1} > 0$. \par Next we know the limit of $\{x_n\}$ exists since it is monotonic and bounded since $x_n > \sqrt{\alpha}$. So, we know that $\lim x_n = \lim x_{n+1}$, and let $l$ equal this limit. Then, substituting into \eqref{3.16a}, \begin{align*} l &= \frac{1}{2} \left( l + \frac{\alpha}{l} \right)\ 2l &= l + \frac{\alpha}{l} = \frac{\alpha}{l} = \sqrt{\alpha}.\qedhere \end{align*} \end{proof} \begin{proof}[Proof of $(b)$] Since $\epsilon_n = x_n - \sqrt{\alpha}$, \begin{align*} \epsilon_{n+1} &= x_{n+1} - \sqrt{\alpha}\ &= \frac{1}{2}\left( x_n + \frac{\alpha}{x_n} \right) - \sqrt{\alpha}\ &= \frac{x_n^2}{2x_n} + \frac{\alpha}{2x_n} - \frac{2x_n\sqrt{\alpha}}{2x_n}\ &= \frac{(x_n - \sqrt{\alpha})^2}{2x_n} = \frac{\epsilon_n^2}{2x_n} < \frac{\epsilon_n^2}{2\sqrt{\alpha}}. \end{align*} Next, setting $\beta = 2\sqrt{\alpha}$, and when $n=1$, \begin{equation*} \epsilon_2 < \frac{\epsilon_1^2}{\beta} = \beta \left( \frac{\epsilon_1}{\beta} \right)^2. \end{equation*} Now suppose that $\epsilon_n < \beta\left(\epsilon_1/\beta \right)^{2^n}$. Then, for the case $n+1$, \begin{equation*} \epsilon_{n+1} < \frac{\epsilon_n^2}{\beta} = \beta \left( \frac{\epsilon_n}{\beta} \right)^2 < \beta\left( \frac{\epsilon_1}{\beta} \right)^{2^{n+1}}, \end{equation*} and so our proof follows by induction since the inequality is satisfied for $n+1$. \end{proof} \begin{proof}[Proof of $(c)$] If $\alpha = 3$ and $x_1 = 2$, $\epsilon_1/\beta = (2 - \sqrt{3})/2\sqrt{3} = 1/\sqrt{3} - 1/2$. We have to prove this value is less than $1/10$: \begin{align*} \frac{1}{3} &< \frac{9}{25}\ \frac{1}{\sqrt{3}} &< \frac{3}{5}\ \frac{1}{\sqrt{3}} - \frac{1}{2} &< \frac{1}{10}. \end{align*} Next, since $3 < 4$, $\sqrt{3} < 2$, and so $\beta = 2\sqrt{3} < 4$. Then, for $n=4$ and $n=5$, \begin{align*} \epsilon_{5} &< \beta \left( \frac{1}{10} \right)^{2^4} < 4 \cdot 10^{-16},\ \epsilon_{6} &< \beta \left( \frac{1}{10} \right)^{2^5} < 4 \cdot 10^{-32}.\qedhere \end{align*} \end{proof}

Exercise 3.16

Answers

Comments

Comments

Exercise 3.16

Answers

Comments

Comments

Add answer