2
$\begingroup$

I understand the sequence $x_{n+1} = \frac12\left(x_n + \frac2 {x_n}\right) $ converges to $ \sqrt2 $ algebraically.

That is proved by means of fixed-point method or monotone convergence theorem and so on.

But, I do want to know whether the sequence converges numerically (and if so, the proof of it).

So, here is my question.

Does the following algorithm always terminate?

  1. Choose an initial number $ x_0 > 0 $.
  2. Calculate $x_{n+1}=\frac12\left(x_n + \frac2 {x_n}\right)$ to one more places of decimals you need.
  3. Truncate the number $x_{n+1}$ to places of decimals you need.
  4. When $x_{n+1}=x_n$ occurs, this algorithm terminates.

In step 3, you need to truncate the number, and I'm worried about the effect of truncation on the convergence.

$\endgroup$
7
  • $\begingroup$ What is the difference between the two modes of convergence by your interpretation? Does "numerical" convergence refer to the number of correct digits? $\endgroup$ – Chris Jun 17 '18 at 18:06
  • $\begingroup$ I'm worried about oscillation of the sequence, because the sequence is truncated in calculus $\endgroup$ – CWPC Jun 17 '18 at 18:11
  • $\begingroup$ The "fixed point theorems" you allude to, if I'm interpreting you correctly, do provide guarantees on the number of correct digits, which must be monotonically increasing (in fact, quadratically). There can't be any "oscillation" in the sense I believe you find troublesome. $\endgroup$ – Chris Jun 17 '18 at 18:19
  • $\begingroup$ Suppose an initial number $ x_0 > \sqrt2$ , the sequence is monotonically decreasing and always larger than $\sqrt2$ algebraically. But the sequence is truncated numerically, there is a number n such that the term $x_n$ is less than $\sqrt2$. Then, the sequence increases! And in this point, the term is larger than $\sqrt2$. So, the sequence restart to decrease... Thus does the sequence oscillate in such a way? $\endgroup$ – CWPC Jun 17 '18 at 18:41
  • $\begingroup$ The kind of “truncation” I recall from calculus does not mean throwing away the “extra” digits from a number. It means you stop adding the series after some term. $\endgroup$ – David K Jun 17 '18 at 18:42
3
$\begingroup$

Actually, this issue does come up in square root algorithms if you are not careful. To take a simple example, suppose we work in base $12$ and we truncate using the floor function. Start with a bigger approximation to $\,\sqrt{2}\,$ which is $\, 17/12. \,$ Using the Babylonian algorithm, the next approximation is $\, (17/12 + 24/17)/2 = 577/408 = 16.9705.../12 \,$ and if you truncate this to $\, 16/12, \,$ then the next approximation is $\, (16/12 + 24/16)/2 = 17/12 \,$ and we have a loop, unless we terminate the algorithm at this step since we are getting a bigger approximation. The exact behavior of the sequence of approximations to $\, \sqrt{x} \,$ depends on the exact details of how the arithmetic is done, but except for the first iteration, you should always terminate if this sequence stops decreasing.

This issue is a very general one. Suppose you have $\,\{x_n\},\,$ a sequence of real numbers given by a recurrence $\, x_{n+1} = f(x_n) \,$ that converges to a finite limit. Now replace the real numbers by $\,F,\,$ a finite set of numbers such as used in a computer system, fixed point or floating point. Then the computing function $\, f_F : F \to F \,$ corresponding to $\,f,\,$ no matter what the initial value or even if the original $\,f\,$ converges or not, must eventually loop, and in best cases the loop is a fixed point.

Just as a curiousity, this kind of loop happens in other bases, namely, $\, \{2, 12, 70, 408, 2378, \dots\} \,$ which is OEIS sequence A001542 which relates them to continued fraction convergents to $\, \sqrt{2}. \,$

$\endgroup$
6
  • $\begingroup$ Great ! Thank you ! Neat counterexample ! Such a good generalization ! Then, if we work in base 10 , doesn't this issue occur? Moreover, necessary and sufficient condition that this issue occur is determined? $\endgroup$ – CWPC Jun 17 '18 at 19:10
  • 1
    $\begingroup$ If you can tell me the exact details of how the arithmetic is done, then we can dicuss necessary and sufficient conditions. Best to be safe and terminate upon increase. $\endgroup$ – Somos Jun 17 '18 at 19:25
  • $\begingroup$ Oh,I see! as you said, if the algorithm terminates when the sequence stops being monotone decreasing, this issue doesn't occur in base any number. $\endgroup$ – CWPC Jun 17 '18 at 20:01
  • $\begingroup$ But, the above algorithm is often referred as the Babylonian method. So, I've guessed that the convergence is provable. But, this is not the case! Amazing! $\endgroup$ – CWPC Jun 17 '18 at 20:01
  • $\begingroup$ So, I'm curious what if the number $2$ in $\sqrt2$ is replaced by other number or the base is replaced by other or fixed-point representation is replaced by floating-point representation... $\endgroup$ – CWPC Jun 17 '18 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.