A fast computation of the best \(k\)-digit rational approximation to a real number (Q346908): Difference between revisions
From MaRDI portal
Changed an Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 03:41, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A fast computation of the best \(k\)-digit rational approximation to a real number |
scientific article |
Statements
A fast computation of the best \(k\)-digit rational approximation to a real number (English)
0 references
30 November 2016
0 references
Suppose the continued fraction expansion of a real number \(\alpha\) is known to be of the form \([a_0;a_1,a_2,\ldots]=a_0+\sum_{k=1}^\infty \frac{~1~|}{|\,a_k}\) with all \(a_k\) integers, \(a_0\geq0\), \(a_k>0\), \(k\geq 1\). The idea is to find the best rational approximant (\(bra_k\)) whose numerator (but which can be adapted for the denominator) has at most \(k\) digits. It is known that the \(bra_k\) is either a convergent \(s_n=[a_0;a_1,\dots,a_n]\) or a semiconvergent \(s_{n,m}=[a_0;a_1,\ldots,a_n,m]\) with integer \(m\in[1,a_{n+1})\). To make such a decision, also pseudoconvergents, forming a set of Farey fractions are used: \(\tilde{s}_{n,m}=[a_0;a_1,\ldots,a_{n-1},a_n-1,m]\). The \(bra_k\) with exactly \(k\) digits will be either a convergent, a semiconvergent or a pseudoconvergent. The \(s_n\) approximate \(\alpha\) alternatingly from above and below. And with \(m\) increasing, the \(s_{n,m}\) is a sequence monotonically varying between \(s_{n-1}\) and \(s_{n+1}\) while \(\tilde{s}_{n,m}\) is monotonically moving towards \(s_n\). With these properties a very efficient algorithm is given that defines the \(bra_k\) with \(k\) strictly equal to the number of digits or not. Also an error estimate is given for this \(bra_k\).
0 references
best rational approximation
0 references
number theory
0 references
continued fraction
0 references
Farey sequence
0 references
algorithm
0 references
error estimate
0 references