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:
“Social and scientific progress are assured, sir, once our great system of postpossession payments is in operation, not the installment plan, no sir, but a system of small postpossession payments that clinch the investment. No possible rational human wish unfulfilled. A man with a salary of fifty dollars a week can start payments on a Rolls-Royce, the Waldorf-Astoria, or a troupe of trained seals if he so desires.”
—John Dos Passos (18961970)