Question

Fix a positive number \(\alpha\). Choose \(x_{1}>\sqrt{\alpha}\), and define \(x_{2}, x_{3}, x_{4}, \ldots\), by the recursion formula $$x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{\alpha}{x_{n}}\right) .$$ (a) Prove that \(\left\\{x_{n}\right\\}\) decreases monotonically and that \(\lim x_{n}=\sqrt{\alpha}\). (b) Put \(\varepsilon_{n}=x_{n}-\sqrt{\alpha}\), and show that $$\varepsilon_{n+1}=\frac{\varepsilon_{n}^{2}}{2 x_{n}}<\frac{\varepsilon_{n}^{2}}{2 \sqrt{\alpha}}$$ so that, setting \(\beta=2 \sqrt{\alpha}\), $$\varepsilon_{_{n+1}}<\beta\left(\frac{\varepsilon_{1}}{\beta}\right)^{2^{n}} \quad(n=1,2,3, \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<\frac{1}{10}\) and that therefore $$\varepsilon_{5}<4 \cdot 10^{-16}, \quad \varepsilon_{6}<4 \cdot 10^{-32} .$$

Short answer

Question: Prove that the given sequence {x_n} decreases monotonically and find its limit, which is given as √α. Then, derive an expression for ε_{n+1}, and show rapid convergence for α = 3 and x_1 = 2. Answer: The sequence {x_n} is proven to be monotonically decreasing, and its limit is found to be √α. The derived expression for ε_{n+1} is: ε_{n+1} < β(\frac{ε_1}{β})^{2^n}, where β = 2√α. For α = 3 and x_1 = 2, the sequence converges rapidly, with ε_5 ≈ 4 × 10^{-16} and ε_6 ≈ 4 × 10^{-32}.

Step-by-step solution

(a) Prove that {x_n} decreases monotonically and find its limit

First, note that each term of the sequence is positive since x_1 > √α and the recursion formula only involves positive terms. Now, let's examine the difference between two consecutive terms of the sequence: x_{n+1} - x_n = \frac{1}{2}(x_n + \frac{α}{x_n}) - x_n = \frac{α-x_n^2}{2x_n}. Since x_1 > √α, we have x_1^2 > α and thus x_2 - x_1 < 0. This means x_2 < x_1. Now, assuming x_{n} > √α, we have: x_{n+1} - x_n = \frac{α-x_n^2}{2x_n} < 0. So, x_{n+1} < x_n, and the sequence is monotonically decreasing. Now, since the sequence is bounded below by √α and monotonically decreasing, it converges to a limit L. Let's examine what happens when n approaches infinity in the recursion formula: L = \frac{1}{2}(L + \frac{α}{L}). By solving for L, we find: L^2 = α. Thus, L = √α.

(b) Prove the inequality related to ε_n and derive the given expression

Using the definition ε_n = x_n - √α, let's examine ε_{n+1}: ε_{n+1} = x_{n+1} - √α = \frac{1}{2}(x_n + \frac{α}{x_n}) - √α. Now, subtract √α from both sides of the recursion formula: ε_n = x_n - √α = \frac{1}{2}(x_n - √α + \frac{α}{x_n} - \frac{α}{√α}) = \frac{1}{2}(ε_n + \frac{ε_n^2}{x_n}). Rearranging the terms: ε_{n+1} = \frac{ε_n^2}{2x_n}. We know that x_n > √α as established in part (a), so: ε_{n+1} = \frac{ε_n^2}{2x_n} < \frac{ε_n^2}{2√α}. Now, setting β = 2√α, we have: ε_{n+1} < β(\frac{ε_1}{β})^{2^n}.

(c) Show the rapid convergence for the given values α = 3 and x_1 = 2

Let's calculate ε_1 and check if ε_1/β < 1/10: ε_1 = x_1 - √α = 2 - √3 ≈ 0.26795. Now calculate β: β = 2√α = 2√3 ≈ 3.4641. We find that ε_1/β ≈ 0.0774, which is indeed less than 1/10. Now, using the inequality derived in part (b), we have: ε_5 < β(\frac{ε_1}{β})^{2^4} ≈ 4 × 10^{-16}, and ε_6 < β(\frac{ε_1}{β})^{2^5} ≈ 4 × 10^{-32}. This illustrates the extremely rapid convergence of the algorithm for computing square roots.

Key concepts

Monotonic Sequence

A monotonic sequence is a sequence that either never increases or never decreases. In the context of the exercise, we deal with a sequence that is monotonically decreasing. This means that each term is smaller than the previous one, indicating a consistent decrease as the sequence progresses. It's an important concept in mathematical analysis because it helps to understand the behavior of sequences and their limits.

In the given problem, the sequence defined by the recursion formula \(x_{n+1}=\frac{1}{2}\left(x_{n}+\frac{\alpha}{x_{n}}\right)\) is said to be monotonically decreasing because the terms continue to get smaller. Demonstrating this characteristic involves proving that any term \(x_{n+1}\) is less than the preceding term \(x_{n}\). As the solution suggests, after showing \(x_2 < x_1\), one can use induction to prove that for all \(n\), \(x_{n} > \sqrt{\alpha}\) and that \(x_{n+1} < x_{n}\). This results in a sequence that snugly 'squeezes' down towards \(\sqrt{\alpha}\), ensuring that we're moving closer to the actual square root with successive iterations.

Monotonic sequences are helpful as they provide a sense of direction in terms of increasing or decreasing trends, and when they are bounded, they always converge to a limit, which brings us to our next core concept.

Convergence of Sequences

The convergence of sequences is another fundamental concept in mathematical analysis. It describes the behavior of a sequence as the term number grows indefinitely. A sequence converges if its terms get arbitrarily close to a fixed value, known as the limit, as one progresses through the sequence.

In the exercise, after establishing that the sequence \(\{x_{n}\}\) is monotonically decreasing and bounded below by \(\sqrt{\alpha}\), we infer that it must converge to a limit \(L\). The challenge is to show that this limit is indeed \(\sqrt{\alpha}\). Using the provided recursion formula and taking the limit as \(n\) goes to infinity gives us a vital equation involving \(L\), which we then solve to deduce that \(L = \sqrt{\alpha}\).

The resulting convergence is proof that no matter the initial term (as long as it’s greater than \(\sqrt{\alpha}\)), the sequence will creep towards and ultimately reach an approximate value of the square root. This ties into the value proposition of sequences in calculations and the precision obtainable through iterative methods, such as the one outlined in the exercise.

Square Root Algorithm

The square root algorithm provided in the exercise is a practical application of the convergence of sequences to compute square roots. Also known as Heron's method, it is an iterative process that produces a sequence of numbers which converge to the square root of a given positive number \(\alpha\).

The algorithm starts with an initial guess \(x_{1}\) that is greater than \(\sqrt{\alpha}\) and then uses the average of \(x_{n}\) and \(\alpha/x_{n}\) to get closer to the true square root. As the solution aptly demonstrates, this method is not only simple but also exhibits extremely rapid convergence, which means that it reaches a close approximation in a small number of iterations.

Particularly, in the exercise for \(\alpha=3\) and \(x_{1}=2\), we see how quickly the error term \(\varepsilon_{n}\) diminishes. When refining the algorithm’s efficiency, a small initial error corresponds to a significantly lesser error in a matter of a few steps, resulting in a highly precise approximation of the square root. This example underlines why such algorithms are integral to numerical computation and why they hold significant value in fields requiring high precision, such as engineering and computer science.