5
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ demonstrations.wolfram.com/… $\endgroup$ Jul 28, 2012 at 14:46
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 28, 2012 at 17:11

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ True, but even for $n=1$ one must do more to efficiently find such a solution when $Q$ is too large for exhaustive search. $\endgroup$ Jul 29, 2012 at 0:47
  • $\begingroup$ 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. $\endgroup$ Jul 29, 2012 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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