On continued fractions. Part 2: Convergence

Revision en5, by adamant, 2020-02-08 01:16:53

Hi everyone!

Let's continue with learning continued fractions. We began with studying the case of finite continued fractions and now it's time to work a bit with an infinite case. It turns out that while rational numbers have unique representation as a finite continued fraction, any irrational number has unique representation as an infinite continued fraction.

Distance between convergents. In the first part we learned that for continued fraction $$$r=[a_0, a_1, \dots, a_n]$$$ elements of the sequence $$$r_0, r_1, \dots, r_n$$$ where $$$r_k = [a_0, a_1, \dots, a_k]$$$ are called convergents. We also derived that subsequent convergents obey a simple formula:

$$$ \frac{p_{-2}}{q_{-2}} = \frac{0}{1},\quad\frac{p_{-1}}{q_{-1}} = \frac{1}{0},\quad\frac{p_k}{q_k}=\frac{a_k p_{k-1}+p_{k-2}}{a_kq_{k-1}+q_{k-2}} $$$

Subsequent convergents seemingly should be closer to $$$r$$$ with bigger $$$k$$$, culminating in $$$r_n=r$$$. So, let's find some bound on how far away from $$$r$$$ can $$$r_k$$$ be. We may start with looking on the difference between $$$r_k$$$ and $$$r_{k-1}$$$:

$$$ \frac{p_k}{q_k}-\frac{p_{k-1}}{q_{k-1}} = \frac{p_k q_{k-1} - p_{k-1} q_k}{q_k q_{k-1}} $$$

Let's rewrite the numerator of this fraction:

$$$ p_k q_{k-1} - p_{k-1} q_k = (a_k p_{k-1} + p_{k-2})q_{k-1} - p_{k-1}(a_k q_{k-1} + q_{k-2}) = p_{k-2} q_{k-1} - p_{k-1} q_{k-2} $$$

Which means that numerator of $$$r_k - r_{k-1}$$$ is the opposite of numerator of $$$r_{k-1} - r_{k-2}$$$. The base case here is defined by $$$p_0 q_{-1} - p_{-1} q_0$$$, which is equal to $$$-1$$$. In this way we may conclude that $$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$$$, thus the whole difference is written as follows:

$$$ r_k - r_{k-1} = \frac{(-1)^{k-1}}{q_k q_{k-1}} $$$

Further we will also need to know the distance between $$$r_{k+1}$$$ and $$$r_{k-1}$$$:

$$$ r_{k+1}-r_{k-1} = \frac{(-1)^k}{q_{k+1} q_k} + \frac{(-1)^{k-1}}{q_k q_{k-1}} = \frac{(-1)^{k-1}(q_{k+1}-q_{k-1})}{q_{k+1}q_k q_{k-1}} = \frac{(-1)^{k-1}a_{k+1}}{q_{k+1} q_{k-1}} $$$

Approximation properties. Formulas above allow us to represent number $$$r=r_n$$$ as explicit telescopic sum (given that $$$r_0=a_0$$$):

$$$ r=(r_n - r_{n-1}) + (r_{n-1} - r_{n-2}) + \dots + (r_1 - r_0) + r_0 = a_0 + \sum\limits_{k=1}^n \frac{(-1)^{k+1}}{q_k q_{k-1}} $$$

Since $$$q_k$$$ monotonically increases, we may say that $$$q_{k+1} q_k > q_k q_{k-1}$$$, thus we have an alternating sum which terms are decreasing by absolute value. This fact automatically implies several important properties, which may be illustrated by the picture below:



In our specific case difference between subsequent convergents quickly drops:

$$$ \left|\frac{r_{k+1} - r_k}{r_{k} - r_{k-1}}\right| = \frac{q_{k-1}}{q_{k+1}} \leq \frac{q_{k-1}}{q_{k} + q_{k-1}} \leq \frac{1}{2} $$$

Consequent convergents maintain lower and upper bound on possible values of $$$r$$$ and each summand makes one of bounds more accurate. Bound above means that segment of possible $$$r$$$ is at least halved on each step. Few important corollaries follow from this:

  • Convergents with even indices are lower than $$$r$$$ while convergents with odd indices are greater than $$$r$$$,
  • If indices $$$j$$$ and $$$i$$$ have different parity then:
$$$|r_j - r_i| = |r_i - r| + |r_j - r|$$$
  • If indices $$$j$$$ and $$$i$$$ have same parity and $$$j>i$$$ then:
$$$|r_j - r_i| = |r_i - r| - |r_j - r|$$$
  • If $$$j>i$$$, then $$$|r_i - r| \geq |r_j - r|$$$.

These observations provide us convenient means of estimating how close is $$$r_k$$$ to $$$r$$$:

$$$ \frac{1}{(q_{k+1}+q_k)q_k} \leq \frac{a_{k+1}}{q_{k+2} q_k}=|r_{k+2} - r_k| \leq |r_k - r| \leq |r_{k+1} - r_k| = \frac{1}{q_k q_{k+1}} \leq \frac{1}{q_k^2} $$$

So, the final "pretty" bounds on the distance between $$$r_k$$$ and $$$r$$$ may be written as follows:

$$$ \left|\frac{p_k}{q_k}-r\right| \leq \frac{1}{q_k^2} $$$

Geometric interpretation. Consider sequence $$$s_k = (q_k;p_k)$$$ on 2-dimensional space. Each point $$$s_k$$$ corresponds to convergent $$$\frac{p_k}{q_k}$$$ which is the slope coefficient of the vector from $$$(0;0)$$$ to $$$(q_k;p_k)$$$. As was mentioned earlier, convergent coefficients are determined by formula:

$$$ \frac{p_k}{q_k} = \frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}} $$$

Geometrically it means that $$$s_k=a_k s_{k-1} + s_{k-2}$$$. Let's recall how coefficients $$$a_k$$$ are obtained. Let $$$b_0, b_1, \dots, b_n$$$ be the states of $$$r$$$ at each step. Thus, we initially have $$$b_0=r$$$ and then for each $$$b_k$$$ we calculate $$$a_k = \lfloor b_k \rfloor$$$ and say that $$$b_{k+1} = \frac{1}{b_k - a_k}$$$. So, for example:

$$$ b_0 = \frac{r}{1},\\ b_1 = \frac{1}{r-a_0},\\ b_2 = \frac{1}{\frac{1}{r-a_0} - a_1}=\frac{r-a_0}{1+ a_0 a_1 - a_1 r},\\ b_3 = \frac{1}{\frac{r-a_0}{1-a_1r + a_0 a_1}-a_2} = \frac{1 + a_0 a_1 - a_1 r}{r(1 + a_1 a_2) - (a_0 + a_2 + a_0 a_1 a_2)} $$$

If you look closely, you may see that the numerator of $$$b_k$$$ is the denominator of $$$b_{k-1}$$$ and the denominator of $$$b_k$$$ is given by:

$$$ Q_k(a_0, a_1, \dots, a_{k-1}, r) = (-1)^k(P_{k-1}(a_0, a_1, \dots, a_{k-1})-r P_{k-2}(a_1, a_2, \dots, a_{k-1})) = (-1)^k(p_{k-1} - r q_{k-1}) $$$

Thus, the whole number $$$b_k$$$ may be defined as follows:

$$$ b_k = \left|\frac{p_{k-2} - r q_{k-2}}{p_{k-1} - r q_{k-1}}\right| = \frac{q_{k-1}}{q_{k-2}}\left|\frac{r_{k-2}-r}{r_{k-1}-r}\right| $$$

Delaunay.

Tags continued fraction, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English adamant 2020-02-08 06:11:13 114 Tiny change: 'tation**\n\n<br>\n[c' -> 'tation**\n<br>\n[c'
en6 English adamant 2020-02-08 03:11:17 6536 Tiny change: ' this line, that is value $|p' -> ' this line. That being said, value $|p' (published)
en5 English adamant 2020-02-08 01:16:53 46 Tiny change: 'ollaries from this' -> 'ollaries follow from this'
en4 English adamant 2020-02-08 01:07:17 2150 Tiny change: 'rmined by recurrent formula:\' -> 'rmined by formula:\'
en3 English adamant 2020-02-07 20:18:59 729 Tiny change: 'ntradicts with $|r_k - r' -> 'ntradicts initial bound of $|r_k - r'
en2 English adamant 2020-02-07 08:53:51 637 Tiny change: 'eq q_k$.\n- If $r_' -> 'eq q_k$.\n\n- If $r_'
en1 English adamant 2020-02-07 07:36:36 4637 Initial revision (saved to drafts)