Convergents are Best Approximations

From ProofWiki
Jump to: navigation, search

Theorem

Let $x$ be an irrational number.

Let $(p_n)_{n\geq0}$ and $(q_n)_{n\geq0}$ be the numerators and denominators of its continued fraction expansion.

Let $\dfrac {p_n} {q_n}$ be the $n$th convergent.

Let $\dfrac a b$ be any rational number such that $0 < b < q_{n+1}$.


Then:

$\forall n > 1: \left\vert{q_n x - p_n}\right\vert \le \left\vert{b x - a}\right\vert$

The equality holds only if $a = p_n$ and $b = q_n$.


Corollary

Each convergent $\dfrac {p_n} {q_n}$ is a best rational approximation to $x$.

That is, for any rational number $\dfrac a b$ such that $1 \le b \le q_n$:

$\left\vert{x - \dfrac {p_n} {q_n}}\right\vert \le \left\vert{x - \dfrac a b}\right\vert$


The equality holds only if $a = p_n$ and $b = q_n$.


Proof

Let $\dfrac a b$ be a rational number in canonical form such that $b < q_{n + 1}$.

Suppose it is not true that $a = p_n$ and $b = q_n$, in which case the equality certainly holds.

Consider the system of equations:

\(\displaystyle a\) \(=\) \(\displaystyle r p_n + s p_{n - 1}\) $\quad$ $\quad$
\(\displaystyle b\) \(=\) \(\displaystyle r q_n + s q_{n - 1}\) $\quad$ $\quad$

Multiplying the first by $b_n$, and the second by $a_n$, then subtracting, we get:

$a q_n - b p_n = s \left({p_{n + 1} q_n - p_n q_{n + 1} }\right)$


After applying Difference between Adjacent Convergents of Simple Continued Fraction we get:

\(\displaystyle s\) \(=\) \(\displaystyle \left({-1}\right)^{n + 1} \left({a q_n - b p_n}\right)\) $\quad$ $\quad$
\(\displaystyle r\) \(=\) \(\displaystyle \left({-1}\right)^{n + 1} \left({b p_{n + 1} - a q_{n + 1} }\right)\) $\quad$ by a similar process $\quad$

So $r$ and $s$ are integers.

Neither of them is $0$ because:

if $r = 0$ then $a q_{n + 1} = b p_{n + 1}$, and Euclid's Lemma means $q_{n + 1} \mathrel \backslash b$ as $p_{n + 1} \perp q_{n + 1}$, which contradicts $0 < b < q_{n + 1}$
if $s = 0$ we have $\dfrac a b = \dfrac {p_n} {q_n}$ and this we have already excluded as a special case.


From Even Convergent of Simple Continued Fraction is Strictly Smaller than Odd Convergent, the convergents are alternately greater than and less than $x$.

Hence since $0 < b = r q_n + s q_{n + 1} < q_{n + 1}$, the integers $r$ and $s$ must have opposite sign.

It follows that $r \left({q_n x - p_n}\right)$ and $s \left({q_{n + 1} x - p_{n + 1} }\right)$ have the same sign.

This is necessary for the Triangle Inequality to hold.

So:

\(\displaystyle \left\vert{b x - a}\right\vert\) \(=\) \(\displaystyle \left\vert{\left({r q_n + s q_{n + 1} }\right) x - \left({r p_n + s p_{n+1} }\right)}\right\vert\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{r \left({q_n x - p_n}\right) + s \left({q_{n + 1} x - p_{n + 1} }\right)}\right\vert\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert + \left\vert{s}\right\vert \left\vert{q_{n + 1} x - p_{n + 1} }\right\vert\) $\quad$ $\quad$
\(\displaystyle \) \(>\) \(\displaystyle \left\vert{r}\right\vert \left\vert{q_n x - p_n}\right\vert\) $\quad$ $\quad$
\(\displaystyle \) \(\ge\) \(\displaystyle \left\vert{q_n x - p_n}\right\vert\) $\quad$ $\quad$

as we wanted to prove.

$\blacksquare$