Convergence

We can say a little more about rational approximations. Let \(k\) be odd. The following generalizes to even \(k\) by flipping signs.

Since \(p_{k+1}, q_{k+1}\) are coprime, the solutions of \(p_{k+1} x - q_{k+1} y = 1\) are given by \(x = q_k + t q_{k+1}, y = p_k + t p_{k+1}\) for all integers \(t\). Likewise, we can construct a sequence of approximations, the intermediate convergents,

This sequence strictly increases, as do all the numerators and denominators, and gets closer and closer to \(p_{k+1}/q_{k+1}\).

Suppose \(p'/q'\) is a rational approximation to \(a\) that is at least as close as \(p_k/q_k\). We have three cases:

We establish handy rules of thumb for the accuracy of a convergent. Let \(x_k = [a_k; a_{k+1},...]\). Recall

thus

Furthermore \(x_{k+1}q_k + q_{k-1} \ge a_{k+1} q_k + q_{k-1} = q_{k+1} \ge q_k \), with equality only when \(x\) is a rational terminating with \(a_{k+1}\). We also have

In summary:

Theorem: Let \(p_k/q_k\) be the convergents of a nonnegative real \(a\). Then

This yields an efficient algorithm for Dirchlet’s approximation theorem, which is more easily proved via the pigeonhole principle, but with an impractical implied algorithm.

Legendre’s theorem is a sort of converse:

Theorem: If \(\left| \frac{r}{s} - a \right| < \frac{1}{2s^2}\) where \(r,s\) are coprime then \(\frac{r}{s}\) is a convergent of \(a\).

Proof: Let the expansion of \(r/s\) be \([a_1; a_2,...,a_k]\) where \(k\) is odd. (Recall a rational has two finite expansions, and one is one term longer than the other.) Define \(x_{k+1}\) by the real that satisfies \(a = [a_1;a_2,...,a_k, x_{k+1}]\).

We will show \(x_{k+1} \ge 1\), because this implies we could expand \(x_{k+1}\) into a continued fraction with a nonzero first term and obtain a continued fraction expansion for \(a\), proving the theorem.

Rewriting

gives

As \(k\) is odd, we have \(x - \frac{p_k}{q_k} = \epsilon\) for some \(0 < \epsilon < \frac{1}{2q_k^2}\), thus

We need only show \(1 - \epsilon q_k q_{k-1} \ge \epsilon q_k^2\):

At last we plug a hole in our proof that rationals have exactly two finite continued fraction expansions. Suppose the rational \(p/q\) has an infinite continued fraction expansion. This would imply

as \(n \rightarrow \infty\), a contradiction.

The mediant (affectionately known as the freshman sum) of \(\frac{a}{b}\) and \(\frac{c}{d}\) is \(\frac{a+c}{b+d}\), and lies strictly between them unless the fractions are equal. Here, the fractions need not be reduced. In fact, we may generalize the numerators and denominators beyond integers.

Above, the intermediate convergents are the mediants of \(\frac{p_k}{q_k}\) and each of \(\frac{p_{k+1}}{q_{k+1}}, \frac{2p_{k+1}}{2q_{k+1}}, ...\).

Suppose we have two different approximations to \(r\) whose geometric mean is \(r\). Then for any \(x\) strictly between the two approximations, the interval between \(x\) and \(r^2/x\) is smaller.

For example, to approximate \(\sqrt{2}\), we can start by guessing such as \(1/1\) and \(2/1\). Their mediant is \(3/2\), and dividing 2 by this yields \(4/3\), so \(3/2\) and \(4/3\) are a closer pair of approximations. Repeating this yields the interval between \(7/5\) and \(10/7\), and repeating again leads to \(17/12\) and \(24/17\).

We happen to produce exactly the continued fraction convergents (and their reciprocals doubled) but in general this process is less efficient than continued fractions. Roughly speaking, continued fractions are better because they scale up the numerator and denominator of the other convergent by the best possible amount before computing the mediant.

Here’s a curiosity. Suppose we want to approximate \(\sqrt{D}\), and we begin with \(x\) and \(D/x\). Write \(x\) as the fraction \(x^2/x\), and the resulting mediant is:

Improving approximations via mediants has led to Newton’s method! Though really, if we wish to avoid calculus, it’s simpler to find approximations with a given convergence rate by studying polynomials rather than play with mediants.

For example, suppose we desire quintic convergence to \(\sqrt{D}\). We find

Thus if \(x\) is an approximation, then

for some bound \(B\).

See also Farey sequences and Stern-Brocot trees.