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