Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are there any well known algorithms for finding good rational approximations to sets of real numbers?

Given just two real numbers, I can use continued fractions to find a rational approximation to their ratio, then use the numerator and denominator; for example a "good" rational approximation to { $\sqrt{2}$, $\sqrt{3}$ } is {9, 11} and {40, 49} is better.

However, with sets of three or more reals, there are some obvious special cases, but I can't see any obvious solution for the general case: in particular, pairwise approximations won't give a "good" approximation for the whole set (in general), i.e. there will be sets of smaller integers which are a better approximation.

Any reasonable definition of good will do - even defining what would count as a "reasonable" definition of good is interesting (in my opinion) even if a rather trivial question! A suitably cunning definition of "good" might even suggest an algorithm... :-)

I do think this question is more mathematical than computational, although perhaps a little elementary for this site, but please suggest where else I could ask it, if it is not appropriate here (and you can't point me at an answer).

share|improve this question
    
2  
The underlying mathematical technique is lattice basis reduction (LBR). Finding a small denominator $d_0 \in \bf Z$ such that each of $n$ real numbers $a_1,a_2,\ldots,a_n$ is within $\epsilon$ of an integer is almost the problem of finding a short nonzero vector in the $n+1$ dimensional lattice of integer vectors $(d_0, d_1, d_2, \ldots, d_n)$ with the quadratic form $d_0^2 + \epsilon^{-2} \sum_{i=1}^n (d_i - a_i d_0)^2$. In the familiar case $n=1$ we get 2-dimensional LBR which is essentially the same as the familiar Euclidean algorithm for rational approximation. –  Noam D. Elkies Jul 28 '12 at 17:11

1 Answer 1

Given reals $x_1,x_2,\dots,x_n$ and real $Q$, Dirichlet's Pigeonhole Principle argument guarantees the existence of integers $p_1,p_2,\dots,p_n,q$ such that $1\le q\le Q^n$ and $|p_n-qx_n|\le1/Q$. There is a good exposition here.

share|improve this answer
    
True, but even for $n=1$ one must do more to efficiently find such a solution when $Q$ is too large for exhaustive search. –  Noam D. Elkies Jul 29 '12 at 0:47
    
Sure, but 1. Jonathan has asked for a definition of good rational approximation, and I have given one, and 2. I believe the article does go into the practical aspects. In short, I think Jonathan will benefit from checking it out. –  Gerry Myerson Jul 29 '12 at 6:32

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.