Continued Fraction - Best Rational Approximations

Best Rational Approximations

A 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:

1. Truncate the continued fraction, and possibly decrement its last term.
2. The decremented term cannot have less than half its original value.
3. 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 a_k is even, the halved term a_k/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 |d_kx − n_k| → 0 as k → ∞.)