$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

6.3: Very Good Approximation

• • Contributed by Wissam Raji
• Associate Professor and the Chairman (Mathematics) at American University of Beirut

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Continued fractions provide a representation of numbers which is, in a sense, generic and canonical. It does not depend on an arbitrary choice of a base. Such a representation should be the best in a sense. In this section we quantify this naive idea.

A rational number $$a/b$$ is referred to as a "good" approximation to a number $$\alpha$$ if $\frac{c}{d} \neq \frac{a}{b} \hspace{5mm} \text{and} \hspace{5mm} 0<d \leq b$ imply $|d\alpha - c| > |b\alpha -a|.$

Remarks. 1. Our "good approximation" is "the best approximation of the second kind" in a more usual terminology.
2. Although we use this definition only for rational $$\alpha$$, it may be used for any real $$\alpha$$ as well. Neither the results of this section nor the proofs alter.
3. Naively, this definition means that $$a/b$$ approximates $$\alpha$$ better then any other rational number whose denominator does not exceed $$b$$. There is another, more common, definition of "the best approximation". A rational number $$x/y$$ is referred to as "the best approximation of the first kind" if $$c/d\neq x/y$$ and $$0<d\leq y$$ imply $$|\alpha - c/d|>|\alpha - x/y|$$. In other words, $$x/y$$ is closer to $$\alpha$$ than any rational number whose denominator does not exceed $$y$$. In our definition we consider a slightly different measure of approximation, which takes into the account the denominator, namely $$b|\alpha - a/b|=|b\alpha -a|$$ instead of taking just the distance $$|\alpha - a/b|$$.

[good] Any "good" approximation is a convergent.

Proof. Let $$a/b$$ be a "good" approximation to $$\alpha = [a_0;a_1,a_2,\ldots,a_n]$$. We have to prove that $$a/b=p_k/q_k$$ for some $$k$$.

Thus we have $$a/b>p_1/q_1$$ or $$a/b$$ lies between two consecutive convergents $$p_{k-1}/q_{k-1}$$ and $$p_{k+1}/q_{k+1}$$ for some $$k$$. Assume the latter. Then $\left\vert \frac{a}{b} - \frac{p_{k-1}}{q_{k-1}} \right\vert \geq \frac{1}{bq_{k-1}}$ and $\left\vert \frac{a}{b} - \frac{p_{k-1}}{q_{k-1}} \right\vert < \left\vert \frac{p_k}{q_k} - \frac{p_{k-1}}{q_{k-1}} \right\vert = \frac{1}{q_kq_{k-1}}.$ It follows that $\label{l7} b>q_k.$ Also $\left\vert \alpha - \frac{a}{b} \right\vert \geq \left\vert \frac{p_{k+1}}{q_{k+1}} - \frac{a}{b} \right\vert \geq \frac{1}{bq_{k+1}},$ which implies $\left\vert b\alpha - a \right\vert \geq \frac{1}{q_{k+1}}.$ At the same time Theorem [inequ] (it right inequality multiplied by $$q_k$$) reads $\left\vert q_k \alpha - p_k \right\vert \leq \frac{1}{q_{k+1}}.$ It follows that $\left\vert q_k \alpha - p_k \right\vert \leq \left\vert b\alpha - a \right\vert,$ and the latter inequality together with ([l7]) show that $$a/b$$ is not a "good" approximation of $$\alpha$$ in this case.

This finishes the proof of Theorem [good].
Exercises

1. Prove that if $$a/b$$ is a "good" approximation then $$a/b \geq a_0$$.

2. Show that if $$a/b>p_1/q_1$$ then $$a/b$$ is not a "good" approximation to $$\alpha$$.

Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.