Theorem 4

If , , , , is the sequence of iterates of , and , , , is the sequence of (machine representable) integers that arise in the process, then has an orbit under G whose elements are close to , , in a sense to be made precise, and, in particular, y is close to .


We will show first that we may approximate an element of the orbit of y by a certain rational number. We then show, using a common model of floating-point arithmetic, that the corresponding is ``machine close'' to this same rational number. This last will be seen to depend on the fact that if you run the Gauss map backwards, errors are damped instead of amplified.

Consider . The rational numbers


and where is the nth Fibonnacci number, from elementary properties of simple continued fractions (see [20] or [11] for details). This means that given an we can find an n so that .

To prove the second part, we use the common model of floating-point division that states that if the floating-point numbers a, b, and c satisfy , where the division takes place over the floating point numbers, then there is a number with u so that exactly. Note that we do not model the addition, since this will be seen to be unnecessary.

If the orbit has been produced by a floating-point system satisfying this model, then for each n there is a number with u such that

where we may consider the addition as exact, since is a machine representable number, defined by this process, and is a machine representable floating-point number. If we put then we have

Now put for , and put for . Note that is the error we wish to estimate, since by the first part we can estimate the error . So now

from whence, on cross-multiplying and expanding, we get the recurrence relation

from which we may derive an upper bound on , and we note at this point that is one of the rationals which approximates . Note that the first term in this recurrence relation is essentially the roundoff error introduced at this particular step, while the second term is the error from one level below in the continued fraction, multiplied by a ``shrinkage factor'' .

As in the proof that has the minimum Lyapunov exponent, we are unable to say anything useful about directly, but we are able to bound , which is easily shown to be less than . With some simple estimates on the above recurrence this gives

and since as , , we have at last

Thus there is a nearby initial point whose orbit under G follows as near as can be expected the computed orbit of the floating-point Gauss map.