Accuracy of Convergents of Continued Fraction

From ProofWiki
Jump to: navigation, search

Theorem

Continued fraction expansion of irrational number

Let $x$ be an irrational number.

Let $(a_0, a_1, \ldots)$ be its continued fraction expansion.

Let $\left \langle {C_n}\right \rangle_{n \geq 0}$ be its sequence of convergents.

Let $p_0, p_1, p_2, \ldots$ and $q_0, q_1, q_2, \ldots$ be its numerators and denominators.


Then:

$\forall k \ge 1: \left\vert{x - \dfrac {p_{k + 1} } {q_{k + 1} } }\right\vert < \dfrac 1 {q_{k + 1} q_{k + 2} } \le \dfrac 1 {2 q_k q_{k + 1} } < \left\vert{x - \dfrac {p_k} {q_k} }\right\vert$


Thus:

The left hand side of the inequality gives an indication of how close each convergent gets to its true value.
The right hand side gives a bound that limits its accuracy.


Convergent simple infinite continued fraction

Let $C = (a_0, a_1, \ldots)$ be an infinite simple continued fraction in $\R$.

Let $C$ converge to $x \in \R$.

For $n\geq0$, let $C_n = p_n/q_n$ be the $n$th convergent of $C$, where $p_n$ and $q_n$ are the $n$th numerator and denominator.


Then for all $n\geq 0$:

$\left\vert x - \dfrac {p_n}{q_n}\right\vert < \dfrac 1{q_nq_{n+1}}$.


Caution

A posteriori, by Correspondence between Irrational Numbers and Simple Infinite Continued Fractions, the statements above coincide, or at least partially. The point is that they are used when proving the correspondence.


Also see