Real sequences/Heron's method/Introduction/Section

Heron of Alexandria (1. century a.C.)

We begin with a motivating example.

Example

We would like to "compute“ the square root of a natural number, say of ${}5$. Such a number ${}x$ with the property ${}x^{2}=5$ does not exist within the rational numbers (this follows from unique prime factorization). If ${}x\in R$ is such an element, then also ${}-x$ has this property. Due to fact, there can not be more than two solutions.

Though there is no solution within the rational numbers for the equation ${}x^{2}=5$, there exist arbitrarily good approximations for it with rational numbers. Arbitrarily good means that the error (the deviation) can be made so small that it is below any given positive bound. The classical method to approximate a square root is Heron's method. This is an iterative method, i.e., the next approximation is computed from the preceding approximation. Let us start with ${}a:=x_{0}:=2$ as a first approximation. Because of

${}x_{0}^{2}=2^{2}=4<5\,$

we see that ${}x_{0}$ is to small, ${}x_{0}<x$. From ${}a^{2}<5$ (${}a$ being positive) we get ${}5/a^{2}>1$ and therefore ${}(5/a)^{2}>5$, so ${}5/a>{\sqrt {5}}$. Hence we have the estimates

${}a<{\sqrt {5}}<5/a\,,$

where we get a rational number on the right hand side if ${}a$ is rational. Such an estimate provides a certain idea where ${}{\sqrt {5}}$ lies. The difference ${}5/a-a$ is a measure for how good the approximation is.

In particular, when we start with ${}2$, we get that the square root ${}{\sqrt {5}}$ is between ${}2$ and ${}5/2$. Then we take the arithmetic mean of the interval bounds, so

${}x_{1}:={\frac {2+{\frac {5}{2}}}{2}}={\frac {9}{4}}\,.$

Due to ${}{\left({\frac {9}{4}}\right)}^{2}={\frac {81}{16}}>5$, this value is too large and therefore ${}{\sqrt {5}}$ is in the interval ${}[5\cdot {\frac {4}{9}},{\frac {9}{4}}]$. Then, we take again the arithmetic mean of these interval bounds and we set

${}x_{2}:={\frac {5\cdot {\frac {4}{9}}+{\frac {9}{4}}}{2}}={\frac {161}{72}}\,$

to be the next approximation. Continuing like that, we get better and better approximations for ${}{\sqrt {5}}$.

In this way we get always a sequence of better and better approximations of the square root of a positive real number.

Definition

Let ${}c\in \mathbb {R} _{+}$ denote a positive real number. The Heron-sequence, with the positive initial value ${}x_{0}$, is defined recursively by

${}x_{n+1}:={\frac {x_{n}+{\frac {c}{x_{n}}}}{2}}\,$

Accordingly, this method is called Heron's method for the computation of square roots. In particular, this method produces for every natural number ${}n$ a real number which approximates a number defined by a certain algebraic property within an error which is arbitrarily small. In many technical applications, it is enough to know a certain number within a certain accuracy, but the accuracy aimed at might depend on the technical goal. In general, there is no accuracy which will work for all possible applications. Instead, it is important to know how to improve a good approximation by a better approximation and to know how many (computational) steps one has to take in order to reach a certain desired approximation. This idea yields the concepts sequence and convergence.

Definition

A real sequence is a mapping

$\mathbb {N} \longrightarrow \mathbb {R} ,n\longmapsto x_{n}.$

We usually write a sequence as ${}{\left(x_{n}\right)}_{n\in \mathbb {N} }$ or simple as ${}(x_{n})_{n}$. For a given starting number ${}x_{0}$, the recursively defined numbers by Heron's method (for the computation of ${}{\sqrt {c}}$) form a sequence. Sometimes a sequence is not defined for all natural numbers, but just for all natural numbers ${}\geq N$. But all concepts and statements apply also in this situation.

Definition

Let ${}{\left(x_{n}\right)}_{n\in \mathbb {N} }$ denote a real sequence, and let ${}x\in \mathbb {R}$. We say that the sequence converges to ${}x$, if the following property holds.

For every positive ${}\epsilon >0$, ${}\epsilon \in \mathbb {R}$, there exists some ${}n_{0}\in \mathbb {N}$, such that for all ${}n\geq n_{0}$, the estimate

${}\vert {x_{n}-x}\vert \leq \epsilon \,$

holds.

If this condition is fulfilled, then ${}x$ is called the limit of the sequence. For this we write

${}\lim _{n\rightarrow \infty }x_{n}:=x\,.$

If the sequence converges to a limit, we just say that the sequence converges, otherwise, that the sequence diverges.

One should think of the given ${}\epsilon$ as a small but positive real number which expresses the desired aiming accuracy (or the allowed error). The natural number ${}n_{0}$ represents the effort how far one has to go in order to achieve the desired accuracy, and in fact in such a way that above this effort number ${}n_{0}$, all the following members will stay within this allowed error. Thus, convergence means that every possible accuracy can be achieved by some suitable effort. The smaller the error is supposed to be (the better the approximation shall be), the higher the effort will be. Instead of arbitrary positive real numbers ${}\epsilon$, one can also work with unit fractions (the rational numbers of the form ${}{\frac {1}{k}}$, ${}k\in \mathbb {N} _{+}$), see exercise, or with the inverse powers of ten ${}{\frac {1}{10^{\ell }}}$, ${}\ell \in \mathbb {N}$.

For ${}\epsilon >0$ and a real number ${}x$, the interval ${}]x-\epsilon ,x+\epsilon [$ is also called the ${}\epsilon$-neighborhood of ${}x$. A sequence converging to ${}0$ is called null sequence.

Example

A constant sequence ${}x_{n}:=c$ converges to the limit ${}c$. This follows immediately, since for every ${}\epsilon >0$, we can take ${}n_{0}=0$. Then we have

${}\vert {x_{n}-c}\vert =\vert {c-c}\vert =\vert {0}\vert =0<\epsilon \,$

for all ${}n$.

Example

The sequence

${}x_{n}={\frac {1}{n}}\,$

converges to the limit ${}0$. To show this, let some positive ${}\epsilon$ be given. Due to the Archimedean axiom, there exists an ${}n_{0}$, such that ${}{\frac {1}{n_{0}}}\leq \epsilon$. Then for all ${}n\geq n_{0}$, the estimate

${}\vert {x_{n}-0}\vert ={\frac {1}{n}}\leq {\frac {1}{n_{0}}}\leq \epsilon \,$

holds.

Example

We consider the sequence

${}x_{n}=0.33\ldots 33\,,$

with exactly ${}n$ digits after the point. We claim that this sequence converges to ${}1/3$. For this, we have to determine ${}\vert {0,33\ldots 33-{\frac {1}{3}}}\vert$, and before we can do this, we have to recall the meaning of a decimal expansion. We have

${}x_{n}=0.33\ldots 33={\frac {33\ldots 33}{10^{n}}}={\frac {\sum _{j=0}^{n-1}3\cdot 10^{j}}{10^{n}}}\,,$

and therefore

${}{\begin{aligned}\vert {0,33\ldots 33-{\frac {1}{3}}}\vert &=\vert {{\frac {\sum _{j=0}^{n-1}3\cdot 10^{j}}{10^{n}}}-{\frac {1}{3}}}\vert \\&=\vert {\frac {3\cdot {\left(\sum _{j=0}^{n-1}3\cdot 10^{j}\right)}-10^{n}}{3\cdot 10^{n}}}\vert \\&=\vert {\frac {{\left(\sum _{j=0}^{n-1}9\cdot 10^{j}\right)}-10^{n}}{3\cdot 10^{n}}}\vert \\&=\vert {\frac {-1}{3\cdot 10^{n}}}\vert \\&={\frac {1}{3\cdot 10^{n}}}.\end{aligned}}$

If now a positive ${}\epsilon$ is given, then for ${}n$ sufficiently large, this last term is ${}\leq \epsilon$.

Lemma

A

real sequence has at most one limit.

Proof

We assume that the sequence has two distinct limits ${}x,y$, ${}x\neq y$. Then ${}d:=\vert {x-y}\vert >0$. We consider ${}\epsilon :=d/3>0$. Because of the convergence to ${}x$ there exists an ${}n_{0}$ such that

$\vert {x_{n}-x}\vert \leq \epsilon {\text{ for all }}n\geq n_{0}$

and because of the convergence to ${}y$ there exists an ${}n_{0}'$ such that

$\vert {x_{n}-y}\vert \leq \epsilon {\text{ for all }}n\geq n_{0}'.$

hence both conditions hold simultaneously for ${}n\geq \max\{n_{0},n_{0}'\}$. Suppose that ${}n$ is as large as this maximum. Then due to the triangle inequality we arrive at the contradiction

${}d=\vert {x-y}\vert \leq \vert {x-x_{n}}\vert +\vert {x_{n}-y}\vert \leq \epsilon +\epsilon =2d/3\,.$

$\Box$