Welcome to MathOverflow

Question

4

2

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

edited Jul 29 at 10:00

Nikita Sidorov
1,106●1●4●11

asked Jul 28 at 13:29

Jonathan
41●1

demonstrations.wolfram.com/… – Nikita Sidorov Jul 28 at 14:46

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 at 17:11

Gerry Myerson · Answer 1 · 2012-07-28 22:45:46Z UTC

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.

answered Jul 28 at 22:45

Gerry Myerson
15.7k●1●47●87

	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 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 at 6:32

Rational approximation to a set of reals

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.