An optimal, stable continued fraction algorithm for arbitrary dimension
- We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
Volltext Dateien herunterladen
Weitere Dienste
| Verfasserangaben: | Carsten Rössner, Claus Peter SchnorrGND |
|---|---|
| URN: | urn:nbn:de:hebis:30-12463 |
| URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| Dokumentart: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Veröffentlichung (online): | 19.07.2005 |
| Jahr der Erstveröffentlichung: | 1996 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 19.07.2005 |
| Freies Schlagwort / Tag: | Dirichlet bound; continued fraction algorithm; floating point arithmetic; integer relation; simultaneous diophantine approximations |
| Bemerkung: | Postprint, auch in: 5th IPCO Conference on Integer Programming and Combinatorial Optimization.Springer LNCS 1084, 31 - 43, 1996 , s.a. ECCC Report TR96-020 |
| Quelle: | 5th IPCO Conference on Integer Programming and Combinatorial Optimization.Springer LNCS 1084, 31 - 43, 1996 , s.a. ECCC Report TR96-020 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
| HeBIS-PPN: | 224866249 |
| Institute: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
