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 correspondingis ``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
![]()
satisfy
![]()
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.