On continued fractions. Part 2: Convergence

Правка en3, от adamant, 2020-02-07 20:18:59

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_{-1}}{q_{-1}} = \frac{1}{0},\quad\frac{p_0}{q_0}=\frac{a_0}{1},\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 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} $$$

Important observation which follows from this bound is that there is no $$$r'\neq r$$$ such that $$$r'=\frac{p}{q}$$$ where $$$q \leq q_k$$$ and $$$|r'-r| < |r_k - r|$$$.

Proof

Geometric interpretation.

Теги continued fraction, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский adamant 2020-02-08 06:11:13 114 Tiny change: 'tation**\n\n<br>\n[c' -> 'tation**\n<br>\n[c'
en6 Английский 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 Английский adamant 2020-02-08 01:16:53 46 Tiny change: 'ollaries from this' -> 'ollaries follow from this'
en4 Английский adamant 2020-02-08 01:07:17 2150 Tiny change: 'rmined by recurrent formula:\' -> 'rmined by formula:\'
en3 Английский adamant 2020-02-07 20:18:59 729 Tiny change: 'ntradicts with $|r_k - r' -> 'ntradicts initial bound of $|r_k - r'
en2 Английский adamant 2020-02-07 08:53:51 637 Tiny change: 'eq q_k$.\n- If $r_' -> 'eq q_k$.\n\n- If $r_'
en1 Английский adamant 2020-02-07 07:36:36 4637 Initial revision (saved to drafts)