Real Numbers: Constructive Mathematics

To keep track of position and time and quantities of different sorts, such as mass, volume, temperature, velocity,…, we use numbers:

$\mathcal{N}$ denotes the set of natural numbers $0, 1, 2, 3,...$
$\mathcal{Z}$ denotes the set of integers $0,\pm 1,\pm 2, \pm 3,...$ ,
$\mathcal{Q}$ denotes the set of rational numbers $r=\frac{p}{q}$ , where $p,q\in\mathcal{Z}$ with $q\neq 0$ .

A rational number has a decimal representation or expansion with a finite number of non-zero decimals or a neverending periodically repeating decimal representation. For example, $\frac{1}{3} = 0.3333....$ and $\frac{11}{13}=0.84615384615384...$

A neverending decimal representation which is not periodic , is said to be an irrational number. The set of rational and irrational numbers with finite or infinite decimal representations forms the set of real numbers denoted by $\mathcal{R}$ .

In constructive mathematics the decimals of decimal expansions, typically of roots to given equations, are computed successively by iterative methods such as fixed point iteration with Newton’s method as special case, which generate sequences of numbers as successively more accurate root approximations.

We say that a sequence of real numbers $x_1, x_2, x_3,...,$ , also denoted $\{ x_n\}_{n=1}^\infty$ or $\{ x_n\}$ for short, is convergent if for a positive constant $L<1$ and a positive constant $C$ :

$\vert x_{n} - x_{n+1}\vert\leq CL^n$ for $n=1, 2, 3,...$ (1)

A convergent sequence of real numbers specifies a unique decimal expansion which defines a real number $x=\lim_{n\rightarrow\infty}x_n$ called the limit of the sequence, satisfying

$\vert x_{n} - x\vert\leq \frac{C}{1-L}L^n$ for $n=1, 2, 3,...$ (2)

To see this we note that for $m = 1, 2, 3,...$ :

$\vert x_n - x_{n+m}\vert \leq \frac{C}{1-L}L^n$ ,

since

$\vert x_n - x_{n+m}\vert =\vert x_n - x_{n+1} + x_{n+1} - x_{n+2} +...+ x_{n+m-1} - x_{n+m}\vert$
$\leq\vert x_n - x_{n+1}\vert + \vert x_{n+1} - x_{n+2}\vert +...+ \vert x_{n+m-1} - x_{n+m}\vert$
$\leq C(L^n + L^{n+1} +...+ L^{n+m})$ $= CL^n(1+L+L^2+...+L^m)=C\frac{1-L^{m+1}}{1-L}L^n\leq \frac{C}{1-L}L^n$ ,

where we used the following formula for the sum of a finite geometric series with $0 < L < 1$ :

$(1+L+L^2+...+L^m)=\frac{1-L^{m+1}}{1-L} < \frac{1}{1-L}.$

For example, if $L = 0.1$ and $\frac{C}{1-L} =1$ , then it follows from (2) that the $n$ first decimals of $x$ are specified by the $n$ first decimals of $x_n$ , for $n=1, 2, 3,...$ .

We shall see that a convergent sequence $\{ x_n\}$ is typically constructed by time stepping or fixed point iteration (with Newton’s method as an important special case) with each iteration determining a new decimal of the limit $x$ if $L= 0.1$ (and binary digit if $L = 0.5$ ) and $\frac{C}{1-L} =1$ as a root to an equation $f(x)=0$ for a given function $f(x)$ .

We shall see that for Newton’s method the number of correct decimals doubles with each iteration which gives a very fast convergence.

In short, we will construct convergent sequences $\{x_n\}$ by fixed point iteration with the decimals of the limit $x$ succesively being determined by the decimals of $x_n$ for increasing $n$ .

Example 1: Consider the sequence $\{x_n\}$ with $x_n = 1 - 2^{-n}$ , that is the sequence, $\frac{1}{2}, \frac{3}{4}, \frac{7}{8}, \frac{15}{16},...$ . We see that

$\vert x_n - x_{n+1}\vert$ $=\frac{1}{2}2^{-n}$ ,

showing that the sequence satisfies (1) with $C=\frac{1}{2}$ and $L=\frac{1}{2}$ and thus converges, and we see that $\lim_{n\rightarrow\infty}x_n=1$ since $\vert 1 - x_{n}\vert = 2^{-n}$ .

Example 2: We shall discover (MST Chapter 8 and 190) that the sequence $\{x_n\}$ generated by the successive iteration $x_{n+1}=x_n - \frac{x_n^2 -2}{2x_n}=\frac{x_n}{2}+\frac{1}{x_n}$ for $n=1, 2, 3,....,$ with $x_1=1$ , which is Newton’s method for computing a root of the equation $x^2 = 2$ , that is the sequence $1,\frac{3}{2}=1.5, \frac{17}{12}\approx 1.42 , \frac{577}{408}\approx 1.41421...$ , converges and $\lim_{n\rightarrow\infty}x_n=\sqrt{2}$ $=1.414213562373095048801 ....$ .

Example 3: Below we will meet a typical case of time stepping, where we will compare the result $x_n$ computed with time step $\Delta t$ and the result $x_{n+1}$ computed with half the time step $\frac{\Delta t}{2}$ , and find that $\vert x_n - x_{n+1}\vert\le C\Delta t$ with a constant $C$ independent of $n$ , which leads to a sequence $\{x_n\}$ satisfying (1) with $L=\frac{1}{2}$ , so that one binary digit of precision is gained in each step.

Remark: We will use the concepts of convergence and limit only with (1) as criterion, and not in the more general but more vague epsilon-delta form typically used in standard versions of Calculus (to define continuity and derivate in terms of limits):

$\lim_{n\rightarrow\infty}x_n=x$ if for all $\epsilon >0$ there is $N >0$ such that $\vert x_n - x\vert\leq \epsilon$ for $n > N$ .

Share this:

Like this:

Leave a Reply Cancel reply