Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$ " ?

share|improve this question
    
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. –  Ross Millikan Aug 7 '11 at 1:44
    
@Ross that was precisely the motivation for this question. I encountered the problem when trying to prove the result. –  kuch nahi Aug 7 '11 at 1:52

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
Excellent. Thanks! –  kuch nahi Aug 7 '11 at 1:39

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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