From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math Subject: Re: rational approximation of several numbers Date: 3 Jun 1997 19:09:08 GMT In article , Pierre Boulet writes: |> I am considering a generalisation of the rational approximation |> problem solved using continued fractions: |> |> given several real numbers, find (small) integers which are in |> the same proportion as these real numbers. |> |> |> Example: approximate 48 21 and 31 by 5 2 and 3 |> |> Has anybody heard of works like this, please? It's called simultaneous Diophantine approximation. If your real numbers are s1, ..., sn and your integers are i1, ..., in, what you are doing is approximating n-1 reals s2/s1, ..., sn/s1 by rationals i2/i1, ..., in/i1 with the same denominator. An easy result: Given any n real numbers r1, ..., rn, there exist infinitely many sets of integers (a1,...,an,b) with b > 0 such that | rj - aj/b | < b^(-1-1/n) for all j On the other hand, the set of (r1,...,rn) for which you can improve the exponent to -1-1/n-epsilon (where epsilon > 0) has measure 0. See H. Davenport, Simultaneous Diophantine approximations, Mathematika 1 (1954) 51-72. Robert Israel israel@math.ubc.ca Department of Mathematics (604) 822-3629 University of British Columbia fax 822-6074 Vancouver, BC, Canada V6T 1Y4 ============================================================================== Newsgroups: sci.math From: iain@stt.win-uk.net (Iain Davidson) Date: Wed, 04 Jun 1997 02:22:46 GMT Subject: Re: rational approximation of several numbers In article , Pierre Boulet (Pierre.Boulet@cs.utk.edu) writes: Hi, > >I am considering a generalisation of the rational approximation >problem solved using continued fractions: > > given several real numbers, find (small) integers which are in > the same proportion as these real numbers. > > >Example: approximate 48 21 and 31 by 5 2 and 3 You can use various generalized continued fractions to solve your problem. The obvious generalizations of SCFs are basically Euclids Algorithm in various guises. Using 48,31,21 you could proceed as follows (Sang's Algorithm): 48 = 1*31 + 0*21 + 1*17 31 = 1*21 + 0*17 + 1*10 21 = 1*17 + 0*10 + 1*4 17 = 1*10 + 1*4 + 1*3 10 = 2*4 + 0*3 + 1*2 4 = 1*3 + 0*2 + 1*1 3 = 1*2 + 1*1 + 0*0 2 = 2*1 + 0*0 + 0*0 You can then express 48 = k*21 + ... 31 = l*21 + ... 21 = 1*21 48 = m*17 + ... 31 = n*17 + ... 21 = p*17 + ... and so on by back substitution (k,l,1) (m,n,p) etc. being the ratios you need In this case 1,1,1 2,1,1 3,2,1 9,6,4 11,7,5 14,9,6 48,31,21 The approximation you have is the intermediate convergent (2,1,1) + (3,2,1) = (5,3,2) This can be generalized to any number of reals. There are many variations of these Euler and Jacobi-Perron type generalized continued fractions, but they all have the drawback that they do not usually produce best approximations. These may be adequate for your needs though. A good overview of generalized continued fractions is Multi-dimensional Continued Fraction Algorithms A.J. Brentjes Mathematical Centre Tracts 145 Amsterdam 1981 There is an extensive bibliography that will help you to follow up anything that interests you. I was wondering why you were interested in this problem. Generalized Farey series (Farey dissections) can also be used to find simultaneous rational approximations to real numbers. Iain Davidson Tel : +44 1228 49944 4 Carliol Close Fax : +44 1228 810183 Carlisle Email : iain@stt.win-uk.net England CA1 2QP