4
$\begingroup$

If $\alpha$ is an irrational, and I'm trying to judge the suitability of of a rational $p/q$ as its approximation by the error $\Delta = |\alpha - p/q|$. For a given denominator $q$, I am finding a $p$ for which the error $\Delta$ is minimized. Why is this error "certainly less than $1/2q$ " ?

$\endgroup$
  • $\begingroup$ If you use convergents of the continued fraction you get particularly good approximations. You can see en.wikipedia.org/wiki/Continued_fraction for information, especially the section "Best rational approximations". If you quit just before a large value in the continued fraction, it is even better. $\endgroup$ – Ross Millikan Aug 7 '11 at 1:44
  • $\begingroup$ @Ross that was precisely the motivation for this question. I encountered the problem when trying to prove the result. $\endgroup$ – kuch nahi Aug 7 '11 at 1:52
7
$\begingroup$

Fix denominator $q$. If $\alpha -p/q$ is greater than $\frac{1}{2q}$ than $\frac{(p+1)}{q}$ is a better approximation.

[EDIT] Equality is impossible since $\alpha$ is assumed irrational.

$\endgroup$
20
$\begingroup$

You can find approximations with error less than $\frac{1}{q^2}$ with continued fractions. The following can be proven with a simple pigeonhole proof.

Approximation Lemma: Let $x$ be any real number and $N$ be a positive integer. Then there are integers $p$ and $q$ with $0 < q \le N$ so that $|p - qx| < \frac{1}{N}$.

Proof: Break up the unit interval $[0,1)$ into $N$ equal subintervals. Notice which subinterval contains the residues $\pmod{1}$ of $kx$ for $0\le k\le N$. There are $N+1$ residues distributed among $N$ subintervals; thus, there must be at least one subinterval with at least two residues, $(k_1 x - j_1)$ and $(k_2 x - j_2)$. We may assume that $k_2 > k_1$. Let $q = k_2 - k_1$ and $p = j_2 - j_1$, then $0 < q \le N$ and, because both residues are in the same subinterval, $|p - qx| = |(k_1 x - j_1) - (k_2 x - j_2)| < \frac{1}{N}$. QED

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.