A fast computation of the best \(k\)-digit rational approximation to a real number (Q346908): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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\). | |||
Property / review text: 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\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Adhemar Bultheel / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11A55 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11B57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 40A25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 41A50 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6657693 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
best rational approximation | |||
Property / zbMATH Keywords: best rational approximation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
number theory | |||
Property / zbMATH Keywords: number theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
continued fraction | |||
Property / zbMATH Keywords: continued fraction / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Farey sequence | |||
Property / zbMATH Keywords: Farey sequence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algorithm | |||
Property / zbMATH Keywords: algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
error estimate | |||
Property / zbMATH Keywords: error estimate / rank | |||
Normal rank |
Revision as of 08:30, 28 June 2023
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