Best Rational Approximations
See also: Diophantine approximation and Padé approximantA best rational approximation to a real number x is a rational number n/d, d > 0, that is closer to x than any approximation with a smaller denominator. The simple continued fraction for x generates all of the best rational approximations for x according to three rules:
- Truncate the continued fraction, and possibly decrement its last term.
- The decremented term cannot have less than half its original value.
- If the final term is even, half its value is admissible only if the corresponding semiconvergent is better than the previous convergent. (See below.)
For example, 0.84375 has continued fraction . Here are all of its best rational approximations.
-
1
The strictly monotonic increase in the denominators as additional terms are included permits an algorithm to impose a limit, either on size of denominator or closeness of approximation.
The "half rule" mentioned above is that when ak is even, the halved term ak/2 is admissible if and only if This is equivalent to:
The convergents to x are best approximations in an even stronger sense: n/d is a convergent for x if and only if |dx − n| is the least relative error among all approximations m/c with c ≤ d; that is, we have |dx − n| < |cx − m| so long as c < d. (Note also that |dkx − nk| → 0 as k → ∞.)
Read more about this topic: Continued Fraction
Famous quotes containing the word rational:
“I often wish for the end of the wretched remnant of my life; and that wish is a rational one; but then the innate principle of self-preservation, wisely implanted in our natures, for obvious purposes, opposes that wish, and makes us endeavour to spin out our thread as long as we can, however decayed and rotten it may be.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (16941773)