\magnification=\magstep1
\baselineskip 0.5cm
\def \frac{{\rm Frac}}

\centerline    {\bf Pathologies generated by round-off in dynamical systems}
\smallskip 
\centerline    {\bf Michael Blank} 
\bigskip
\centerline {Observatoire de Nice BP 229, 06304 Nice Cedex 4, France,
e-mail: blank@obs-nice.fr}

\centerline {Russian Academy of Sci. Inst. for Information Transmission 
Problems, 101447 Moscow, Russia}

\bigskip

{\bf Abstract.} When solving differential equations or other dynamical systems
on a computer, the effect of finiteness (round-off) can sometimes be very
drastic. We discuss on the one hand rigorous conditions under which statistical
(the most rough) properties of the system survive discretization, and on
another hand examples where, even in the limit of vanishing perturbation, a
"localization" phenomenon takes place: trajectories which should normally be
dense remain confined to a small number of points. In some instances, the
addition of a small amount of true noise can cure the pathologies. From the
point of view of computer theory questions that we shall consider may seem very
simple, but often they lead to quite nontrivial mathematical constructions.

\smallskip Key words: dynamical system, mapping, SBR measure, periodic
trajectory, discretization.
 
\bigskip 
\centerline      {\bf 0. Introduction} 
\smallskip 

When solving differential equations or other dynamical systems on a 
computer, we inevitably run into perturbations caused by various types of 
discretization. The first of them is time discretization, that is, the 
transition from differential equations or flows to difference equations or 
maps. The second type is space discretization, that is, the transition 
from continuous phase space to a discrete lattice. There are also some 
other types, for example partial time and space discretization when some 
of the equations describing our system are discretized in space or time 
and some not. A typical example of that type is a machine-tool with a 
numerical program control. We shall consider a dynamical system (DS) 
obtained as a result of discretizations of all types as a perturbed DS. We 
shall be interested in the questions about the connections between 
properties of the original and the perturbed system for sufficiently fine 
discretizations. There are a lot of problems here (see for example [1-9] 
and references therein) and in this paper we shall restrict ourselves only 
to the case of space and partial space discretizations.

Let us consider now a difference equation $$x_{n+1}=f(x_n),$$ acting on some
compact subset $X \subset R^d$. What does it mean the space discretization of
such systems? Really in the computer simulations we have not a continuous
compact phase space, but a discrete lattice of points, and after the
calculation of the following point $x_{n+1}$ we in fact have not the precise
value of $f(x_n)$ but the nearest point to it in our lattice. So to describe
the discretized version of the difference equation above we need some rigorous
definitions.  

{\bf Definition 1.} By an $\epsilon$-discretization of a compact set $X \subset
R^d$ we mean a choice in the set $X$ of an ordered finite lattice (a collection
of points) $X_\epsilon$ so that the distances between its neighboring elements
do not exceed the value $\epsilon>0$. By an operator of the
$\epsilon$-discretization we mean a map $D_\epsilon: X \to X_\epsilon$ that
associates with each point $x \in X$ its closest point from the lattice
$x_\epsilon = D_\epsilon(x) \in X_\epsilon$ (if there are several such points
we choose the point with the minimal number). The value of the parameter
$\epsilon>0$ we call the diameter of the $\epsilon$-discretization.  

{\bf Definition 2.} By an $\epsilon$-discretized (perturbed) system for the map
$f$ with the compact phase space $X$ we mean a pair $(f_\epsilon, X_\epsilon)$,
where $f_\epsilon = D_\epsilon \circ f$.

Note that in the distinction to usual perturbation schemes the discretized 
(perturbed) system here is given not on the original phase space $X$ but on 
the lattice $ X_\epsilon$.

In the case of round off errors in the computer modeling we deal with the
uniform $\epsilon$-discretization and in the case of the unit $d$-dimensional
cube (or torus) phase space $X$ and for $\epsilon = 1/N, N \in Z_+$, the
lattice $X_\epsilon$ consists of all points $x \in X$ with rational coordinates
with the denominator $N$. Another example can be a random discretization when
all the points of the lattice are chosen randomly according to some
distribution law (for example, the Poisson distribution).  

In many papers (especially of applied type) effects of round off errors in
numerical simulations are considered and it seems that these effects may be
neglected especially in the case of rough systems (that is stable with respect
to smooth perturbations) and sufficiently high computer precision.  However we
shall show that the effect of finiteness (round-off) can sometimes be very
drastic. For example a stable periodic orbit may be replaced by one with a
period which is a multiple of the true one or a infinite chaotic orbit may turn
into a periodic one with very small period. Understanding such phenomena
requires the study of a particular kind of perturbations of dynamical systems. 
These perturbations are deterministic by their nature but their effect is close
in a sense to that of pure random perturbations. It is of interest to remark
here that loss of chaoticity for discretized bounded orbits due to the finite
number of points in the discretized phase space around them in principle is not
an obstacle in the investigation of chaotic properties of dynamical systems
(calculation of Lyapunov exponents and so on). On another hand if the
discretization is sufficiently fine, usually the periodicity of the trajectory
is so long that, in practical applications one couldn't distinguish the result
of round-off errors of the action of small random perturbations. Some of the
patologies (such as period multiplication and disruption or stabilization of
unstable cycles), that we consider, persist for arbitrary fine discretizations
for typical dynamical systems. About others our results show that they also
persist for an open set in the space of dynamical systems. On another hand
numerous numerical simulations (see for example [7-9] and referencies therein)
demonstrate that this open set has to be small in a sense.

The paper is organized as follows. Section 2 contains information about
properties of periodic orbits under discretization. The most interesting among
them are period multiplication of periodic orbits (Theorem 1) with all possible
dangers in the study of bifurcations and the disruption or stabilization of
unstable cycles - ``localization'' phenomenon (Theorem 2). In section 3 we
consider the discretized chaotic dynamical systems from the statistical point
of view. We show that although the phenomena, described in section 2, depend on
the the diameter of the discretization in a very irregular way, the statistical
approach gives an adequate description (Theorem 4). In section 4 we investigate
the case of neutral periodic trajectories, that are nor stable and nor
unstable. The most interesting results here are non ergodicity of the
discretized irrational rotation on the d-dimensional unit torus (Theorem 7) and
pathologies of generalized rotations on the plane (Theorem 9). Contraction of
the phase--space and possible methods to avoid this pathology by adding a
Markov perturbation are considered in section 5. Partial space discretizations,
when some of the variables are discrete and some not, are discussed in section
6. In section 7 we give rigorous sufficient conditions for numerical
verification of shadowing of individual trajectories for general
(nonhyperbolic) maps (Theorem 12). Section 8 contains the proofs of Theorems
1,7 and 12.  


\bigskip
\centerline {\bf 2. Properties of periodic orbits under discretizations.}
\smallskip

Remind that an orbit or trajectory of the map $f$ is a sequence of points 
$\{x_k\}_1^\infty$ such that $x_{k+1}=f(x_k)$ for all $k$, and in the case of a 
periodic orbit or or simply a cycle of period $n$ such sequence is formed by a
repetition of a finite collection of different points $(x_1, x_2, \cdots, 
x_n)$ and therefore it is defined by one of these points (for example $x_1$) 
and its period. We call this point periodic with the period $n$. In contrast 
with the original dynamical system, for every map $f$ the set of 
non-wandering points (that is the most broad nontrivial invariant set) of 
the discretized system coincides with the set of periodic points. 
Therefore, an investigation of asymptotic properties of perturbed systems 
is reduced to an investigation of solely periodic orbits.  

Let us consider at first the most simple case in numerical simulations, 
which is to find the globally stable periodic orbit of the system. It 
seems that for sufficiently high precision the only visible effect of 
perturbations is to deform and shift the periodic orbit. However it turns 
out that here the "period multiplication" may take place. This phenomenon 
consists in the emergence in a neighborhood of the original cycle of a new 
cycle, the period of which is a multiple of that of the parent cycle.

{\bf Theorem 1.} Suppose that the map $f$ has a cycle of period $n$ in some
neighborhood of which, consisting of disjoint neighborhoods of points of this
cycle, $f$ is a local homeomorphism, and there is a cycle of the
$\epsilon$-discretized system of period $k$. Then the fraction $k/n$ may 
take values 1 or 2 in the one-dimensional case and may be arbitrary integer 
in general multidimensional case.

On Fig. 1 we show the general construction of the period doubling of a cycle of
period $2$. By solid squares we denote the points of the parent cycle, and by
lines the trajectory of the cycle of the discretized system.

Let us consider the multidimensional case. In this case the discretized 
system may have a cycle of arbitrary period multiplicator with respect to 
the parent cycle. Geometrically this result means that the orbit of the 
$\epsilon$-discretized system curls around the original orbit, but in the 
one-dimensional case the only one variant of rotation around the initial 
orbit may take place - the rotation through the angle $\alpha$. However the 
proof of this statement is not too simple and bases on some properties of 
homeomorphism of ordered sets. To show that even in the two-dimensional 
case we may have this phenomenon with arbitrary large multiplicator, let 
us consider the example of a mapping of the two-dimensional plane, which 
may be written in polar coordinates as

$$ re^{i\phi} \to r \lambda e^{i(\phi+\alpha)}.$$

\noindent Here $0 < \lambda < 1$ and the irrational number $\alpha$ are
parameters. Each trajectory of this mapping has a spiral shape and tends 
to the zero point as time tends to infinity. On another hand, if 
$1 - \lambda \ll 1$, then for sufficiently fine uniform 
$\epsilon$-discretizations any trajectory of the discretized mapping, started 
from the point $(r,\phi)$ with $r \gg 1$ will not go to the origin, but 
will hit into a cycle around the origin. The shape of this cycle is close to 
a circle with the radius, defined by the following inequality:

$$ \epsilon [r \lambda /\epsilon] \ge r, $$

\noindent where $[x]$ is the closest to $x$ integer number. Therefore this
cycle is a rotation of angle close to $\alpha$ around the origin and
we may obtain arbitrary large periods by a suitable choice of parameters
$\lambda$ and $\alpha$. This example show how "curls" around initial 
trajectory can appear. The distance between the "curls" has order 
$\epsilon/ \mid \lambda-1 \mid$, where $\lambda$ is the modulus of the cycle 
multiplier (i.e. the largest eigenvalue of the linearized mapping along the 
cycle). Hence, far from the bifurcation point (i.e. the point where the cycle 
became unstable and $\mid \lambda \mid \approx 1$) this effect is hardly 
noticed. However, it is very difficult to distinguish this effect from a 
bifurcation of the original system when investigating the bifurcation picture 
itself (in particular, in the well known Feigenbaum scenario of the transition 
to chaos by repeated doublings of the period). The unique way to verify that 
there is no this phenomenon is to repeat the simulation with several 
different precisions. However further we shall show that this phenomenon 
depends on the precision in a very complicated way.

We can consider a partition of the set $U \cap X_\epsilon$ to domains, 
in each of which there are cycles of the discretized system with 
equal multiplicators. All other points of $X_\epsilon$ hit in these 
sets or go out of the considered neighborhood under the action of
$f_\epsilon$. 

The problem of the general effects of discretization is of special 
interest in the case of chaotic dynamical systems (see for example [10]), 
because all their trajectories are unstable and therefore the influence of 
perturbations on individual trajectories may grow in time. A typical 
example is the one-dimensional mapping $x \to \frac(kx)$ for which 
the iterates of almost all initial points are uniformly distributed and 
all features of developed chaos are visible. Here $\frac(x)$ is the 
fractional part of the number $x$. Another important example is so called tent 
map: $f_{\rm tent}(x)=\min \{ax,-ax+a\}$. More complex examples occur in the 
three body problem in celestial mechanics, the Henon mapping $(x,y) \to 
(1-ax^2+y,bx)$ and others (see [10] and references therein for further 
examples). The theorem above describes the situation also in these cases. 
Questions about properties of discretized chaotic systems are an active 
area of mathematical investigation and many problems are still open. 
Number of questions here is quite larger than number of known answers. We 
shall consider only some of them. Practically there are only a few 
results, showing that orbits of the discretized chaotic systems may have a 
connection to the original orbits. Among these results the main general 
one shows the connection of the orbit of weakly perturbed system (with 
arbitrary type of perturbation) to the original orbit. This result is due 
to D.V.Anosov [11], who showed that for smooth hyperbolic system for each 
orbit of weakly perturbed system there exists uniformly closed orbit of 
the initial one. But this shadowing orbit may be not typical in the sense 
that the distribution of its points (which is the most important feature 
of chaotic system) differs from the typical one, defined by the 
Sinai-Bowen-Ruelle measure [10]. The following statement shows that these 
situations may often happen in case of discretizations.

{\bf Theorem 2.} If the set of all preimages of a certain cycle is dense in the
phase space, then there is a sequence of discretizations with diameters that
tend to zero, such that each discretized system has only one cycle that
coincides with the original one.

To prove this statement it is sufficient to consider a family of discrete
lattices $\{X^{(n)}\}$, points of the $n$-th of which coincide with the $n$-th
preimage of the points of the considered cycle.

We may consider also the more general approach to this situation. Let us fix a
mapping $f$ and a family of discretizations $\{X_\epsilon\}$. Then for each
cycle $\bar x_\epsilon$ of the discretized mapping $f_\epsilon$ we may take
into account the number of points in all of its preimages (including the cycle
itself), divided by the number of points in the lattice $\{X_\epsilon\}$, and
denote this value by $p(\bar x_\epsilon)$. This number shows how often we may
observe a cycle when initial points are chosen at random. Now, assigning for
each discretization $\{X_\epsilon\}$ its cycle $\bar x_\epsilon$ with the
largest value of $p(\bar x_\epsilon)$ and the probabilistic measure
$\mu_\epsilon$ uniformly distributed along this cycle, we may ask a question
about the limit points (in the weak topology of measures) of these measures for
the typical family of discretizations. It may be shown that for sufficiently
"good" mapping $f$ these limit points are invariant measures of the mapping.
However the family of invariant measures may be very rich (for example uniform
measures on cycles and their closure). We think that the most probable answer
is the following: the limit point coincides with one of the measures - Sinai -
Bowen - Ruelle measure or the measure of the maximal entropy (see [10] for
definitions). Neither of these possibilities can be ruled out at the moment.  

It seems that the situation, described in Theorem 2 is unrealistic, but the
condition about the density of preimages is typical for chaotic systems, and so
the question is only about how often such special discretizations may occur? It
is interesting to remark that for the mapping $x \to \frac(2x)$ and any binary
discretization (i.e. computer discretization) the discretized system has only
one cycle with the period equal to 1. The same is true also for the mapping $x
\to \frac(kx)$ with natural $k$ and corresponding uniform discretizations.  In
the general case however discretizations of this type are not uniform and this
gives a hope to think that the resonance between the mapping and the
discretization in the numerical simulation may appear only randomly.  

On another point of view Theorem 2 shows that some sort of a "localization"
phenomenon takes place: trajectories which should normally be dense remain
confined to a small number of points. This is of special interest, because the
most frequently applied numerical method for the calculation of the density of
an invariant measure of a chaotic dynamical system on a computer consists in
the computation of the histogram of a sufficiently long numerical orbit, and
Theorem 2 says that the error here can be very large even in the integral norm.
Indeed in the simplest example $x \to \frac(2x)$ every point is mapped by this
mapping in the computer simulation in no more than $N$ steps (where $N$ is the
number of binary positions in a computer word) into a zero unstable fixed point
of the mapping $x \to \frac(2x)$ and remains there. For example on a VAX
computer it could be verified that the orbit starting from 1/3 (which is a
periodic point of period 2 in the true mapping $\frac(2x)$) falls to 0 in 57
iterations, even in double precision. One could think that, for computational
purposes, there is no need to study asymptotic properties but it is enough to
stop the count when the histogram is already stabilized and the accumulated
error is not yet large. However, the analysis shows that also this method may
not lead to the required result.  In the case of the uniform
$\epsilon$-discretization the number of steps at which the count should be
stopped is of order $-\ln(\epsilon)$, while the guaranteed precision is of
order $(-\ln(\epsilon))^{-1/2}$.  

Though a number of papers have been devoted to the investigation of the
question of convergence of the histograms of trajectories calculated on the
computer to the density of a smooth invariant measure, there is actually only
one theoretical result due to P.Gora and A.Boyarsky, that confirms the
possibility of such convergence. 

{\bf Theorem 3} [7]. Let $f$ be sufficiently smooth one-dimensional mapping
with a smooth invariant measure $\mu$ and for all $n$ there is a cycle of
length not less than $tn$, $t>0$, for a uniformly $1/n$-discretized mapping
$f_{1/n}$.  Then the measures that are uniformly distributed on these cycles
converge weakly to $\mu$.

The existence of the required estimate of cycle periods has been obtained in a
paper [7] for the the family of piecewise linear mappings $x \to \frac(3^kx)$.
A large amount of numerical data on the influence of uniform
$\epsilon$-discretizations on the maximal length of cycles of discretized
systems was given in the paper by C.Beck and G.Roepstorff [1], where it was
shown numerically, that the maximal cycle length for the family of
one-dimensional mappings $f(x) = 1-2\mid x \mid ^\alpha$, has order
$\epsilon^{1/ \alpha}$, for $\alpha>0$. This shows that Theorem 3 cannot be
applied in this case.

\bigskip
\centerline {\bf 3. Statistical probability under discretizations.}
\smallskip

Now let us try to answer the question about how "typical" the behavior of the
discretized systems. At first let us consider the question of the existence of a
cycle of an $\epsilon$-discretized system for sufficiently small $\epsilon>0$
in small neighborhood of an unstable cycle of the unperturbed system. For
different values of $\epsilon$ a cycle of an $\epsilon$-discretized system can
appear and disappear with arbitrary small changes in $\epsilon$ and a choice of
$X_\epsilon$. Therefore to answer this question it is necessary to make some
additional assumptions about the structure of discretizations. Now we shall
restrict ourselves to the most interesting case for applications of uniform
discretizations of the $d$-dimensional unit cube $X$. In this case $\epsilon$
has values of the type $\epsilon=1/n, \, n \in Z_+$. Even in this case the
presence or absence of a cycle for a uniform $1/n$-discretized system depends
on $n$ in a very irregular way. The statistical approach seems to be the most
natural one for the description of this situation. 

{\bf Definition 3.} By the statistical probability of some event (with respect
to a given family of space discretizations) we mean the fraction of that
discretizations under which this event takes place.

Thus the statistical probability $p(x_1,x_2, \cdots, x_n)$ of the stabilization
of an unstable cycle $(x_1,x_2, \cdots, x_n)$ of a mapping $f$ is the density
of the set of those natural numbers $N$ for which $(D_{1/N}x_1, D_{1/N}x_2,
\cdots, D_{1/N}x_n)$ is a cycle of a uniformly $1/N$-discretized system.

The meaning of this definition is that the existence in the case of uniform
discretizations of a cycle of a discretized system in a small neighborhood of
the original system implies the possibility of the actual observation of an
unstable trajectory in the computer modeling. It is therefore natural to call
this situation the "stabilization of an unstable cycle". Numerical experiments
show that in the modeling of chaotic dynamical systems, the cycles of which are
all unstable, some of the cycles are observed much more frequently than others
[12]. The following statement provides an explanation for this phenomenon.

{\bf Theorem 4.} Let $\bar x = (x_1,x_2, \dots, x_n)$ be an unstable cycle
of the mapping $f$, which is continuously differentiable in a neighborhood 
of the cycle, and its coordinates are rationally independent. Then 
$p(\bar x)$ is well defined and depends only on the derivatives of $f$ 
at the points of the cycle: it is equal to the volume of the 
$dn$-dimensional polyhedron $\Omega = \Omega(f; \bar x)$ defined by the 
system of semi-linear inequalities:

$$ \mid f^\prime (x_1) z_1 - z_2 \mid \le 1/2 $$
$$ \mid f^\prime (x_2) z_2 - z_3 \mid \le 1/2 $$
$$ \cdots $$
$$ \mid f^\prime (x_n) z_n - z_1 \mid \le 1/2 $$
$$ \mid z_i \mid \le 1/2, \quad i=1,2, \dots , n $$

\noindent where $f^\prime (x)$ is the matrix of partial derivatives of the
mapping $f$ at the point $x$, and $\mid z \mid$ for a vector $z \in R^d$ is 
the maximal value of moduli of its coordinates.

{\bf Proof.} To calculate the density of the set of natural numbers it is
sufficient to consider only large such numbers, corresponding to sufficiently
fine discretizations. Therefore working only in small neiborhoods of the points
of the cycle we may assume that the mapping $f$ is linear there. Let us fix a
natural number $k \gg 1$. The set of points $\bar x_{1/k} =
(D_{1/k}x_1,D_{1/k}x_2, \dots, D_{1/k}x_n)$ is a cycle of the mapping $f_{1/k}$
if and only if the following system of inequalities holds:

$$ \mid x_2 + f^\prime (x_1) (D_{1/k}x_1 - x_1) - D_{1/k}x_2 \mid < 1/(2k) $$
$$ \mid x_3 + f^\prime (x_2) (D_{1/k}x_2 - x_2) - D_{1/k}x_3 \mid < 1/(2k) $$
$$ \cdots $$
$$ \mid x_1 + f^\prime (x_n) (D_{1/k}x_n - x_n) - D_{1/k}x_1 \mid < 1/(2k). $$

\noindent Indeed, if it is true, then $f_{1/k}(D_{1/k}x_i) = D_{1/k}x_{i+1}$ for
all $i$. On another hand, if one of these inequalities fails, say the $i$-th
inequality, then $f_{1/k}(D_{1/k}x_i) \ne D_{1/k}x_{i}$. Remind now that
$D_{1/k}x_i$ is the best rational approximation of the vector $x_i$ with the
rational coordinates with the common denominator $k$. Therefore, multiplying
both hands of these inequalities by $k$ and denoting the difference between a
vector $v \in R^d$ and the closest to it vector with all integer coordinates by
$\{v\}$, we have:

$$ \mid f^\prime (x_1) \{kx_1\} - \{kx_2\} \mid < 1/2 $$
$$ \mid f^\prime (x_2) \{kx_2\} - \{kx_3\} \mid < 1/2 $$
$$ \cdots $$
$$ \mid f^\prime (x_n) \{kx_n\} - \{kx_1\} \mid < 1/2 $$

Now let us consider a rotation $F_\alpha$ through the $nd$-dimensional angle
$\alpha=(x_1,x_2, \dots, x_n) \in R^{nd}$ on the $dn$-dimensional unit torus
$T = [-0.5, 0.5)^{nd}$. Then the trajectory of this mapping, starting from 
the point $\alpha \in T$ hits into the domain $\Omega$, defined in the 
theorem, if and only if there is a stabilization effect. Thus, $p(\bar x)$
coincides with the part of the time during which this trajectory spends in
$\Omega$ and consequently coincides with the $F_\alpha$-invariant measure of
this domain. However, the rotation mapping of the torus through an angle with
rationally independent coordinates has a unique invariant measure that is 
equal to the Lebesgue measure on the torus $T$. Q.E.D.

To clarify this construction let us consider a close problem which is quite
simpler. Let $x$ be arbitrary irrational number in the interval $[0,1]$ and 
let us compute how often a rational approximation of this number with a
denominator $n$ has precision not worse than some constant $\epsilon \ll 1$
divided by $n$; which is to calculate the density $p(x)$ of those natural
numbers $n$ for which the inequality 
$$\mid x- q/n \mid \le \epsilon /n$$
holds for some natural $q=q(n)$. Multiplying the both parts of this inequality
by $n$ we see that it is equal to $$\mid \frac(nx) \mid \le \epsilon$$ 
Now considering the two intervals on the unit circle defined by the latter
inequality and the rotation through the angle $x$ we come to the same situation
as in the theorem and can calculate this density precisely: $p(x)=2\epsilon$. 
Note that this situation coincides with the stabilization of a fixed point 
$x$ of a one-dimensional mapping with the derivative at this point 
$1/(2\epsilon)$. 

There is a question about the practical applicability of this statement in a
sense which magnitude of $k$ needed to reach the value of $p(\alpha)$ (defined 
by Theorem 4) with a sufficiently good precision. From the proof above it 
follows that the answer to this question depends on the rate of 
convergence of the fraction of the points of a typical trajectory of the 
torus rotation which happen to be in the specified region. In the "good" 
case this convergence is of order $\log(k)/k$, so it is sufficiently fast.  

It is interesting to remark, that the statistical probability of 
stabilization obtained above does not depend on the coordinates of the 
points of the cycle. It should be pointed out that such a uniform estimate 
is true only for "typical" cycles. If the condition of rational 
independence of the coordinates (or irrationality of the number $x$ above) 
does not hold, there are "exceptional" cycles (and even maps for which all 
the cycles are "exceptional") whose stabilization probability depends on 
the coordinates of its points. Among the "exceptional" cycles there are 
cycles with abnormally high probability of stabilization (for example, 
equal to 1) and also cycles for which this magnitude is abnormally small 
(in comparison with the "typical" situation described in the theorem). 

The method used in the proof of Theorem 4 enables us to study even finer 
properties of the discretized systems. For example one can calculate by 
this method the statistical probabilities of all events that can appear in 
the "period multiplication" phenomenon. The close construction also may be 
carried out to consider not all uniform discretizations but only binary 
ones, that is for the case $\epsilon = 2^{-n}$. In this case we can also use 
the described construction, but the dynamical system appearing in this 
case on the $dn$-dimensional unit torus $T$ is $x \to \frac(2x)$ rather 
than a rotation. An invariant measure of the latter mapping is not unique and 
the answer depends on the invariant measure represented by the trajectory 
of this system, starting from the point $(x_1,x_2, \dots, x_n)$. However 
for almost all initial conditions this measure is equal to the Lebesgue 
measure on the $dn$-dimensional unit torus $T$.

{\bf Theorem 5.} Suppose that the mapping $f$ is continuously differentiable in
a neighborhood of its cycle $\bar x = (x_1,x_2, \dots, x_n)$. Then there is a
mapping $\hat f$ arbitrary $C^1$-close to $f$ with a cycle $\hat x = (\hat x_1,
\hat x_2, \dots, \hat x_n)$ close to initial one, such that the statistical
probability of the stabilization of the cycle $\hat x$ in the case of binary
discretizations of the mapping $\hat f$ is equal to $1$.

To prove this statement it is sufficiently to note that the preimages of the
zero fixed point of the mapping $x \to \frac(2x)$ (which is the 
replacement of the rotation mapping for binary discretizations) are dense 
on the interval $[0,1]$. Therefore we may choose a mapping $\hat f$ such 
that the cycle $\hat x$ on one hand lies in this set of preimages, and on 
another hand is arbitrary close to the initial one. However the trajectory 
of the mapping $x \to \frac(2x)$ starting from the point $\hat x$
is far from typical, because it hits into the unstable zero fixed point and 
stays there. Therefore the statistical probability of the stabilization of 
the cycle $\hat x$ is equal to $1$.

For the systems given on the unit torus there is also another approach to 
investigate how typical are the properties of discretized systems. For a
torus (in contrast with a cube) it is natural to fix a discretization up to a
shift of the origin and a rotation around it. Therefore, in this case the
parameter is not discrete and by the statistical probability of the
stabilization of the cycle $(x_1,x_2, \cdots, x_n)$ we mean the value
$p(x_1,x_2, \cdots, x_n; \epsilon)$, which is equal to the Lebesgue measure of
the set of shifts ($\le 1$) of the origin and rotations (through angles from
$0$ to $2\pi$) around it, divided by $2\pi$ for normalization, for which the
stabilization effect takes place. Here $\epsilon$ is the diameter of the
discretization. By a similar definition we can obtain the dependence of the
probability of the stabilization on the diameter $\epsilon$. Let us consider
the map $\phi: R_+^1 \to R_+^1$, defined by the following relation:
$\phi(x)=x/(1+x)$. The following statement shows some variant of the
universality of the dependence of this probability of the parameter $\epsilon$.

{\bf Theorem 6.} Suppose that the mapping $f$ is continuously differentiated in
a neighborhood of its cycle $(x_1,x_2, \cdots, x_n)$. Then for any sufficiently
small $\epsilon>0$ the sequence of quantities $\{ p(x_1,x_2, \cdots, x_n;
\phi^k(\epsilon)) \}_{k=1}^\infty$ is almost periodic. Here $\phi^k(x)$ is the
value of the function $\phi$ applied $k$ times recursively in the point $x$.  

\bigskip
\centerline {\bf 4. Case of neutral periodic trajectories.}
\smallskip

Let us now study the influence of uniform discretizations on the systems, 
the trajectories of which are neither stable nor unstable, or they have a 
local invariant component of this type. The main example here is a 
rotation $f^{(\alpha)}$ of the $d$-dimensional unit torus $T$ through the angle 
$\alpha \in R^d$. In this case an investigation of individual trajectories 
has no sense, and we shall study the influence of discretizations on some 
global properties of the system, such as the ergodicity property. In the 
case of discretized system ergodicity means that there exists only one 
periodic trajectory and therefore the orbit of every point hits into this 
trajectory after a finite time. Due to the fact that the discretized 
rotation preserves distances between the points of the uniform lattice, 
in the ergodic case there is only one periodic trajectory with a period 
which equal to the number of points in $X_\epsilon$. Since the ergodicity in 
the case of the rotation does not depend on a shift of origin, or a 
rotation of our lattice around it, we can give the following definition.

{\bf Definition 4.} By the statistical probability of ergodicity $p(\alpha)$ we
mean the density of the set of those natural numbers $N$ for which uniformly
$1/N$-discretized systems $(f_{1/N}^{(\alpha)},T_{1/N})$ are ergodic.

{\bf Theorem 7.} If the coordinates of the vector $\alpha \in R^d$ are
rationally independent, then $p(\alpha)$ is well defined and is identically
equal to zero.

This result shows the qualitative distinction between the effect of
perturbations arising from space discretizations and those due to smooth
perturbations, since in the latter case the well known KAM theory says that it
is the ergodicity which is "typical". This makes clear the qualitative
difference of the influence of the round-off errors. However, it will be
interesting to precise the link between the chaotic appearance and
disappearance of periodic trajectories in the $1/N$-discretized systems, for $N
\to \infty$, and the phenomenon of subfurcation [13], arising from smooth
perturbations. We note that if the coordinates of the angle $\alpha$ are
rationally dependent, that is, the original system is nonergodic, then the
statistical probability of ergodicity is also well defined but can be very far
from zero (for instance, $p(2\pi * 1/3)=2/3$.

It is surprising that if we restrict ourselves to the case of the binary
discretizations the result would not be the same.

{\bf Theorem 8.} For almost all vectors $\alpha \in R^d$ the statistical
probability of ergodicity with respect to the binary discretizations
$p_2(\alpha)$ is well defined and identically equal to $(1/2)^d$.

It is sufficient to prove the one-dimensional version of this statement. 
Let us fix a natural number $n$. Then the $1/2^n$-discretized system 
$(f_{1/2^n}^{(\alpha)},T_{1/2^n})$ is ergodic if and only if the following 
inequality holds:

$$ \mid 2^n \alpha - (2k+1) \mid < 1/2. $$

\noindent This is equivalent to the inequality

$$ 1/4 < \frac(2^{n-1} \alpha) < 3/4. $$

\noindent Just as we did in the proof of Theorem 4 we may consider now the
one-dimensional mapping $ x \to \frac(2x)$ and then, for a typical
initial point $x_0=\alpha$ we have that $p_2(\alpha)$ is equal to the fraction
of time that the trajectory started from the point $x_0$ spends in the segment
$(1/4, 3/4)$, that is $1/2$, because the Lebesgue measure is invariant for
the considered mapping. Q.E.D.

Another problem arises in the investigation of a rotation $f^{(\alpha)}$ of 
points in the two-dimensional plane $R^2$ by a fixed angle $\alpha$ around the 
origin. It seems that the situation here is just the same as in the 
previous example, but there is a large difference between these examples. 
It consists in the fact that although the mapping $f^{(\alpha)}$ preserves 
distances, the discretized mapping does not preserve them (in distinction 
to the previous case). Moreover, if we consider a broken line, consisting 
of consecutive points of some trajectory and straight lines between them, 
then two such different lines may intersect each other. Without 
discretization, the trajectories of the mapping $f^{(\alpha)}$ lie on 
concentric circles. With round-off, it is not known when the trajectories 
go to the origin and when they go to infinity (neither can be ruled out at 
the moment). Numerical simulations (see Fig. 2.) show the evidence of a 
picture similar to the situation in the KAM theory, that is we can see 
some quasi-circles (invariant tori) with gaps between them. Remark that 
the distribution of points on these tori may be not ergodic. However there 
is no analytical proof of this fact.

To show that under the discretization similar neutral systems may behave as
dissipative ones, let us consider a generalization of the previous model.

{\bf Definition 5.} A map $f:R^2 \to R^2$ is called the generalized rotation
around some fixed point $x_0 \in R^2$ if $f(x_0)=x_0$ and for any point $x \ne
x_0$ the trajectory $\{ f^n(x) \}_{n \ge 0}$ started from this point lies on a
closed curve, homeomorphic to a circle.

An example of such map is a usual rotation around the origin onto the 
irrational angle. The latter mapping is Hamiltonian and, as it follows from
Kolmogorov - Arnold - Moser (KAM) theory [13, 14], for sufficiently "good" 
rotation angles and "good" sufficiently small smooth perturbations, the 
perturbed mapping has invariant curves (homeomorphic to a circle) around 
the origin and each trajectory of the perturbed system is bounded by this 
invariant curves. We have noted before, that in the case of perturbations, 
arising in the computer modeling the behavior of perturbed systems looks 
similar. However in the case of the generalized rotation this is not longer
true.

Let us fix in the two-dimensional plane $R^2$ a system of orthogonal
coordinates $(x,y)$ and a family of "triangle" curves $T_t, t>0$ the $i$-th
side of which satisfies the equality $$a_ix+b_it=y, \quad i = 1,2,3.$$ We now
define a map $f_{\alpha}:R^2 \to R^2$ as a generalized rotation around the
origin along the curves $T_t$ with the unit rate, i.e. a shift of the current
point by means of one of the vectors: 

$$ \alpha^{(i)}=(1/\sqrt{1+a_i^2}, a_i/\sqrt{1+a_i^2}), \quad i = 1,2,3.$$

\noindent according to the number of the side of the "triangle" curve $T_t$, on
which the current point lies. If during this shift we are going through the
corner of the "triangle", then we continue the shift along the next side. The
collection of vectors $\alpha^{(i)}$ we denote by $\alpha$. We show a 
typical trajectory of this system on Fig. 3.

To study the event that any point of the $1/n$-discretized plane, outside the
ball of radius $10/n$ centered in the origin, goes to infinity under the action
of the $1/n$-discretized generalized rotation $f_{\alpha}$, we may consider the
more coarse situation, when after each iteration of the discretized mapping we
go to the "triangle" with the larger value of the parameter $t$. We shall call
the latter event the "coarse destabilization".  

{\bf Theorem 9.} Let the vectors $\alpha^{(i)}$ and the vector with all unit
coordinates be jointly rationally independent. The density of natural numbers
$n$ such that for the $1/n$-discretized generalized rotation $f_{\alpha}$ the
coarse destabilization takes place is equal to $1/2^3$.

Sketch of the {\bf proof}. For a fixed vector $\beta=(\beta_1,\beta_2) \in R^2$
with rationally independent coordinates let us define a map
$h_\beta(x)=x+\beta, \quad x \in R^2$ and a function $H_\beta:R^2 \to R_+^1$,
which is equl to the distance from the point $x$ to the line
$y=\beta_2/\beta_1x=\gamma_x$. We assume at first that $\gamma>0$. Let us
consider a unit square with sides parallel to coordinate axis and the left
lower corner in the origin. We divide this square into four equal squares and
consider a set $A_+$, consisting of three parts: the left upper square, the
part of the left lower square lying below the line $y=\gamma x$, and the part
of the right upper square lying below the line $y=\gamma x+(1-\gamma)$. Then
the density $p(\beta)$ of natural numbers $n$ such that the $1/n$-discretized
mapping $h_{\beta,1/n}$ monotonically increases the distance function $H_\beta$
(i.e. $H_\beta(x) \le H_\beta(h_{\beta,1/n}(x))$ for any $x$), is equal to the
Lebesgue measure of the set $A_+$. The explanation is that the
$1/n$-discretized mapping $h_\beta$ increases the distance function if and only
if the $n$-th iterate of the mapping $x \to \frac(x+\beta)$, beginning at the
point $\beta \in R^2$, lies in the set $A_+$. Therefore $p(\beta)$ is equal to
the occurrence time of this set for the rotation mapping above, which is equal
to the Lebesgue measure of this set ($1/2$). The considered set is shown on
Fig. 4. The situation with $\gamma<0$ is considered in the same way. Now
applying this result coupled with the rational independency of $\alpha^{(i)}$,
we obtain the statement of the theorem, because the statistical probability of
the considered event is equal to the multiplication of probabilities of events,
related to each $\alpha^{(i)}$. Q.E.D.

Although this example shows that in the general case trajectories of
generalized rotations in the computer modeling are not bounded, all numerical
simulations with Hamiltonian generalized rotations (for example, with usual
rotations onto irrational angles) give another result similar to that in 
Fig. 2. Therefore we can formulate a conjecture.

{\bf Conjecture.} Let $f:R^2 \to R^2$ be a Hamiltonian generalized rotation
(and thus preserving the Lebesgue measure). Then for any $n$ each trajectory of
the $1/n$-discretized mapping is bounded.

If this statement is true, then since each computer trajectory is bounded and
lies on the discrete lattice, it hits into a finite cycle. As we mentioned
above it looks like an invariant torus in the KAM theory (apart from the 
distribution of points on such torus).

\bigskip
\centerline {\bf 5. One method of numerical modeling of chaotic systems.}
\smallskip

There are two possible ways of computer modeling of chaotic systems. The first
one is to compute a good approximation of a typical trajectory of the system
under consideration, and then to calculate some statistics along it.  The
second method is to construct a new dynamical system on the computer so that
the statistical properties of the new system are equal in a certain sense to
those of the initial one.

Let us define the domain $M_\epsilon(x)$ of the point $x \in X_\epsilon \subset
R^d$ under the $\epsilon$-discretization as a union of all points in the
genuine phase space $X$ such that under the discretization they coincide with
$x$, that is 

$$M_\epsilon(x) = \{ y \in X: D_\epsilon(y) = x \}.$$

The main qualitative difference of the discretized system from the parent 
one is the fact that under the action of the discretized mapping $f_\epsilon$ 
the image of the domain $M_\epsilon(x)$ consists only of one point 
$f_\epsilon(x)$ and therefore the volume of this element of the phase space 
decreases dramatically, in distinction to the action of the unperturbed 
mapping. To cure this pathology we suggest a method of numerical modeling 
which is based on the replacement of the mapping $f$ by a random Markov 
process on the lattice $X_\epsilon$, which takes each point $x \in X_\epsilon$ 
with equal probability to any point of the set $D_\epsilon(f(M_\epsilon(x)))$. 
We note that for the above example of the mapping $x \to \frac(kx)$ with the 
natural $k$ for any uniform $\epsilon$-discretization the constructed random 
Markov process has a unique invariant measure, which coincides up to a 
discretization with the Lebesgue measure; the latter is the unique smooth 
measure of the unperturbed system.

We consider two types of random perturbations. The first is a Markov random
process which takes each point $x \in X_\epsilon$ with equal probability to any
point of some neighborhood of it on the lattice. Fix a natural number $k \gg 1$
and consider a Markov random process $\pi_{\epsilon,k}$ on $X_\epsilon$ with
the transition probabilities $q_{\epsilon,k}(x,y)$ of the following form: 

$$q_{\epsilon,k}(x,y) = \cases{(2k)^{-d}, &if $\mid x-y \mid \le k\epsilon$; \cr
                                0, &otherwise. \cr}$$

To define the second type of random perturbations it is more convenient to
describe note a random perturbation itself, but a perturbed system in the whole.
Let $F_\epsilon$ be a Markov random process on $X_\epsilon$ with the transition
probabilities $p_\epsilon(x,y)$ of the form: 

$$p_\epsilon(x,y) = \cases{1/{\rm Card }(D_\epsilon(f(M_\epsilon(x)))), 
                             &if $y \in D_\epsilon(f(M_\epsilon(x))) $; \cr
                           0, &otherwise. \cr}$$

Now by a stochastically perturbed $\epsilon$-discretized dynamical system we
mean a Markov random process $F_{\epsilon,k} = \pi_{\epsilon,k} \circ
F_\epsilon$ on $X_\epsilon$, which is the superposition of the random processes
mentioned above.

For a sufficiently wide class of chaotic dynamical systems, namely for the so
called piecewise expanding systems, the correctness of this method is proved
rigorously [3], using the ergodic theorem by Ionescu Tulchi and Marinescu for 
the Perron - Frobenius operator of the discretized system. Numerical simulations
for the Henon mapping, the horseshoe mapping, standard mapping and some others
also gave good agreement of statistical properties.

\bigskip
\centerline {\bf 6. Partial space discretizations.}
\smallskip

>From the pure mathematical point of view due to the finiteness of the 
phase space $X_\epsilon$ of the $\epsilon$-discretized dynamical systems, 
discretization results only in the destruction of chaotic properties. 
Remark that this does not mean that one could not compute numerically 
Lyapunov exponents and so on, but only that the discretized dynamical 
systems are not chaotic (there is no mixing etc.). However this scheme 
does not describe all possibilities. Let us consider an example. Suppose 
we have a machine tool with computer control. Then it is natural to 
consider the part of the system describing the dynamics of the machine 
tool in a continuous phase space and the part describing the computer 
control on a discrete lattice. In this way partial discretization arises 
in applications. Because of lack of a general theory we shall consider 
only one of the possible approaches to this type of discretizations.

{\bf Definition 6.} Let the mapping $f=f^{(1)}$ to be decomposed into the sum
$f^{(1)}(x) = f^{(2)}(x) + f^{(3)}(x); \, f^{(i)}: R^d \to R^d, \, i=1,2,3$. 
We call a "partially $\epsilon$-discretized mapping" the mapping $f_\epsilon(x)
= f^{(2)}(x) + D_\epsilon(f^{(3)}(D_\epsilon(x)))$ acting in the initial phase
space $R^d$. Here $D_\epsilon$ is the operator of the usual space
discretization.

{\bf Theorem 10.} Suppose that $f^{(i)}, \, i=1,2,3$ are twicely continuously 
differentiable and the mapping $f^{(1)}$ is dissipative (i.e. has a globally 
attracting ball) and $f^{(2)}$ is an expanding mapping with a sufficiently 
large expanding constant. Then the partially $\epsilon$-discretized system 
$(f_\epsilon, R^d)$ has a stochastic attractor with a smooth mixing 
invariant measure.
                                 
{\bf Proof} of this statement bases on the fact that, for any discretization,
the discretized mapping is piecewise expanding. Indeed, let us fix some
discretization. Then we have a partition of $R^d$ to cubes $X_i$, such that for
all $x \in X_i$ the function $D_\epsilon(f^{(3)}(D_\epsilon(x)))$ has a common
value, say $C_i$. Therefore for $x \in X_i$, we have $f_\epsilon(x) =
f^{(2)}(x) + C_i$. Now, because of the dissipativity of the mapping $f$ and the
expanding condition for the mapping $f^{(2)}$, we obtain the statement of the
theorem. Q.E.D.

Note that the assumptions of Theorem 10 do not exclude a situation where 
the initial system for any discretization has a unique globally attracting 
fixed point. For example let us consider in the one-dimensional case the 
following functions: $f^{(2)}(x)=3x; f^{(3)}(x)=-2.5x$. Then the unperturbed 
mapping $f(x)=0.5x$ has a unique globally attracting fixed point in the 
origin, but the partially discretized system has a stochastic attractor in 
some neighborhood of the origin.

There is also a local variant of the previous result.

{\bf Theorem 11.} Suppose that $f^{(i)}, \, i=1,2,3$ are twicely continuously
differentiable and these mappings have a common periodic trajectory, which is
stable with respect to $f$ and is unstable in $f^{(2)}$. Then there is an
$\epsilon_0>0$ such that for all $0 < \epsilon < \epsilon_0$, the partially
discretized system has a stochastic attractor.

Thus the emergence of chaos under partial discretization seems to be typical,
and though the results obtained guarantee only the emergence of local chaotic
islands, we believe it is plausible that at least in the case of completely
integrable Hamiltonian systems there could appear chaotic domains of a finite
size that does not vanish when the discretization diameter tends to zero.

\bigskip
\centerline {\bf 7. Shadowing of individual trajectories.}
\smallskip

One of the main questions, arising in the computer modeling of dynamical
systems, is to check up the adequacy of the obtained results. That question is
especially critical in the case of modeling of chaotic dynamical systems, i.e.
systems with statistical laws in the behavior. In computer modeling of 
discrete time dynamical system, when we calculate a numerical trajectory for
the mapping $f: R^d \to R^d$, we may only say that the obtained sequence of
points $\{ x_i \}$ is an $\epsilon$-trajectory of the mapping $f$. That is
$\mid x_{i+1} - f(x_i) \mid < \epsilon$  for all $i$. We say that an 
$\epsilon$-trajectory $\{ x_i \}$ is shadowed with the accuracy $\sigma$, if
there exists a point $x \in R^d$, such that $\mid f^n(x) - x_n \mid < \sigma$
for all $n$. In other words, if an $\epsilon$-trajectory is shadowed, then
there exists a real trajectory of the mapping $f$ lying in its neighborhood.

The first result in which such a possibility is proven to happen for 
chaotic dynamical systems is the theorem by D.V.Anosov about the shadowing 
property of $\epsilon$-trajectories in the case of smooth hyperbolic 
dynamical systems [11]. There are a lot of generalizations of this result 
(see for example [8,9] and a survey there). Authors in these papers 
investigate the possibility of the shadowing of any $\epsilon$-trajectory of 
a mapping $f$ of some class. In the present paper we propose a method of the 
verification of the shadowing property for a given specific 
$\epsilon$-trajectory of a mapping for which this property may not hold in 
the whole (i.e. not all $\epsilon$-trajectories and not for all $n$ are 
shadowed).

The method consists in the construction of special parallelograms around the
points of the $\epsilon$-trajectory with sufficiently small diameters and the
verification of the fact that these parallelograms satisfy some property, which
we name the local Markov property on the analogy with the definition of the
Markov partition of the dynamical system [10]. One can say that this
condition is equal to the transversal crossing of the image of the $i$-th
parallelogram (under the action of the mapping $f$) with the $(i+1)$-st
parallelogram. The background of this method is a construction that was
proposed in [8] for computer analysis of trajectories of the two dimensional
Henon mapping.

Let $f: R^d \to R^d$ be a nonsingular mapping of the Euclidean space $R^d$ with
the metric $\mid.\mid$ into itself. In this space we fix an arbitrary sequence
of points $\{ x_i \}_{i=1}^N$ in the $\sigma$-neighborhood ($\sigma \ll 1$) of
which the mapping $f$ is continuously differentiable and nondegenerate. For
each $i$ we represent the space $R^d$ in the form of the direct sum of two
linear subspaces $E_i^+$ and $E_i^-$ the dimensions of which in the general
case depend on the number $i$. One can take $E_i^+$ ($E_i^-$) as the eigenspace
of the matrix of derivatives of the mapping $f$ at the point $x_i$
corresponding to eigenvalues of absolute value greater than $1$ (smaller or
equal to $1$).  In this paper the subspace $E_i^+$ and all objects
corresponding to it will be called positive and denoted by the sign plus, while
$E_i^-$ and corresponding objects will be called negative and denoted by the
sign minus. The projection onto $E_i^+$ parallel to $E_i^-$ we denote by
$\pi_i^+$, and onto $E_i^-$ parallel to $E_i^+$, by $\pi_i^-$.
         
For each $i$ we fix three parallelograms: $A_i^+ \subset E_i^+$ and $A_i^-
\subset E_i^-$, which are Cartesian products of one-dimensional intervals, and
$A_i = A_i^+ * A_i^-$ which is the Cartesian product of the parallelograms
$A_i^+$ and $A_i^-$. The center of the parallelogram $A_i^+$ coincides with the
point $\pi_i^+(x_i)$, and the center of the parallelogram $A_i^-$ with the
point $\pi_i^-(x_i)$. Moreover, we assume that the diameter of the
parallelogram $A_i$ is smaller than $\sigma$. The boundary of the parallelogram
$A_i^+$ ($A_i^-$), which is viewed as a region in $E_i^+$ ($E_i^-$), will be
denoted by $\partial A_i^+$ ($\partial A_i^-$). Since the boundary of $A_i$ is
$\partial A_i^- * \partial A_i^+ \cup \partial A_i^+ * \partial A_i^-$, we
introduce the notion of positive and negative boundaries of the parallelogram
$A_i$:

$$  \partial^+A_i = \partial A_i^- * A_i^+, \quad \partial^-A_i = \partial
A_i^+ * A_i^-.$$

\noindent By $A_i^\sigma$ we denote the parallelogram with center at the same
point, but with positive part $(1+\sigma)$ times smaller and negative
$(1+\sigma)$ times greater than in the initial one. The parallelogram
$A_i^{-\sigma}$ is defined in the same way, but the value $\sigma$ is replaced
by $-\sigma$.

Definition 7. We shall say that the sequence of parallelograms $\{ A_i \}$
satisfies the weak local Markov condition (for the mapping $f$) if for all $i$
we have:

$$(1) \quad  \pi_{i+1}^+(fA_i \cap A_{i+1}) = \pi_{i+1}^+(A_{i+1}), $$

$$(2) \quad  \pi_i^-(f^{-1}(f(A_i) \cap A_{i+1})) = \pi_i^-(A_i), $$

$$(3) \quad  f(\partial A_i) \cap \partial A_{i+1} = f(\partial^+ A_i) \cap
\partial^-A_{i+1}, $$

\noindent and we will say that it satisfies the local Markov condition if (1) -
(3) are still satisfied when we replace $A_i$ by $A_i^\sigma$ and $A_{i+1}$ by
$A_{i+1}^{-\sigma}$.

The meaning of the last operation is that we require the conditions (1) - (3)
to be satisfied with some excess.

{\bf Theorem 12.} There is a $\sigma_0 = \sigma_0(f) > 0$, such that for any
$\sigma < \sigma_0$ the local Markov condition for the sequence of
parallelograms $\{ A_i \}$ implies that the intersection of the preimages of
these parallelograms is not empty. Therefore there exists a point $x \in A_0$,
such that $f^n(x) \in A_n$ for all natural $n$.  

Conditions (1) - (3) are necessary in a certain sense, because for each $\sigma
> 0$ there exists a mapping $f$ and a sequence of parallelograms $\{ A_i \}$
such that if only one of the conditions (1) - (3) is not satisfied, then the
intersection of the pre-images $f^{-n}(A_n)$ is empty.

Remark that in the Anosovs' case our linear subspaces $E_i^+$ and $E_i^-$ may
be choosen in a such way to coincide with local unstable and stable directions.
In the one-dimensional case the weak local Markov condition could be reduced
to a very simple form:

$$ A_{i+1} \subset fA_i $$

\noindent for all $i$. Therefore if we have a numerical trajectory (i.e. a
finite number of points) of a one-dimensional map we can verify the shadowing
property in the following way. Choose small intervals around the considered
points and if any subsequent interval is a subset of the image (under the
action of the map) of the previuos interval, then the shadowing property holds.
Another remark concerned the fact that in the proof of this result (see Section
8) we actually do not use the independency of the map $f$ on the number of the
point along the trajectory. This gives us a possibility to use the conditions
above even in the nonstationary case, when the map $f$ depends on the number of
iteration.

\bigskip
\centerline      {\bf 8. Main Proofs} 
\smallskip

{\bf Proof of Theorem 1.} Let $\bar x = (x_1, \dots , x_n)$ be a cycle of the
map $f$ and let $U = \cup U_i$ be its neighborhood, consisting of disjoint
neighborhoods of points of the cycle, in which there is a cycle $\bar y = (y_1,
\dots , y_k)$ of the $\epsilon$-discretized map.  

We start from the one dimensional case ($d=1$). The map $f$ is a local 
homeomorphism of a neighborhood $U$ of the cycle, therefore the function 
$f(x)$ is monotonous on $U$ and hence the function $f_\epsilon(x)$, restricted 
to the set $U \cap X_\epsilon$, is also monotonous as a superposition of two 
monotonous functions $f$ and $f_\epsilon$. Let us denote by $f_\epsilon^*$ the 
derivative map [10], constructed for the dynamical system 
$(f_\epsilon,X_\epsilon)$ with respect to the set $U_1 \cap X_\epsilon$. Remind 
that the derivative map $f^*$ for a dynamical system $(f,X)$ with respect to 
a set $U$ is defined in the following way. For any point $x \in U$ we set 
$f^*(x)=f^n(x)$, where $n$ is the minimal natural number $n$ such that $f^n(x) 
\in U$. Let $z_1 < z_2 < \dots < z_{m_1}$ be points of the cycle $\bar y$ lieing 
in $U_1$. Due to the fact that the map $f$ is a local homeomorphism, the 
number $m_i$ of points of the cycle $\bar y$ lieing in $U_i$ does not depend on 
$i$ and is equal to an integer $m$ (the period multiplicator). There are 
three possibilities:

(a) $f_\epsilon^*z_1 = z_1$. This means that $m=1$ and $k=n$, i.e.
there is no period multiplication.

(b) $f_\epsilon^*z_1 \ne z_1$ and $(f_\epsilon^*)^2 z_1 = z_1$. Then 
$m=2$ and $k=2n$, i.e. the discretized system has a cycle of a double
period. Remark, that the necessary condition of the period doubling is 
a monotonous decrease of $f^n(x)$ in a neighborhood of the cycle. 

(c) $f_\epsilon^*z_1 \ne z_1$ and $(f_\epsilon^*)^2 z_1 \ne z_1$. Let us 
show that such a situation does not exist. At first suppose that the 
value $m$ is even, i.e. $m=2l$. Since $f_\epsilon^*$ is monotonous, 
then $(f_\epsilon^*)^2$ is monotonously nondecreasing. Hence we have:

$$ z_1 < (f_\epsilon^*)^2 z_1 \le (f_\epsilon^*)^4 z_1 \le \dots 
       \le (f_\epsilon^*)^{2l} = z_1. $$

\noindent We come to a contradiction, because the first inequality is strict.
It remains tio prove that there is no cycle of odd order $m=2l+1$. There are
also two possibility: the function $f_\epsilon^*$ is monotonically
nondecreasing or monotonically nonincreasing. In the first case the
orientations of the pairs $(z_i,z_{i+1})$ are the same for all $i=1,2, \dots ,
m-1$. Therefore such sequence of points cannot be a cycle. In the second case
the orientations of the subsequent pairs are reverse, because $f_\epsilon^* z_i
= z_{i+1}$ by the construction of the derivative map. Hence the pairs
$(f_\epsilon^* z_{2l+1},f_\epsilon^* z_{2l+2})$ and $(z_1,z_2)$ must have a
reverse orientation. We come to a contradiction once more, because
$f_\epsilon^* z_{2l+1} = z_1$ and $z_1 < z_i$ for any $1 < i \le m$.Proof. Let
$\bar x = (x_1, \dots , x_n)$ be a cycle of the map $f$ and let $U = \cup U_i$
be its neighborhood, consisting of disjoint neighborhoods of points of the
cycle, in which there is a cycle $\bar y = (y_1, \dots , y_k)$ of the
$\epsilon$-discretized map.  

The multidimensional case was discussed in Section 2. Q.E.D.

\bigskip {\bf Proof of Theorem 7.} Let us begin from the one-dimensional case
($d=1$). Let us denote by $I(x)$ the nearest integer to $x \in R^1$. The
uniformly $1/N$-discretized dynamical system $(f_{1/N}^{(\alpha)},T_{1/N})$ is
ergodic if and only if the natural numbers $N$ and $I(N\alpha)$ have no common
multipliers.  Therefore the statistical probability of ergodicity (if it
exists) is equal to the density of numbers $N$ such that $N$ and $I(N\alpha)$
have no common multipliers.  

Let us number the set of prime numbers by their order:
$ r_1=2 < r_2=3 < r_3=5 < \dots$ and denote $r_i? = r_1*r_2* \dots *r_i$.
To calculate the density above we consider a partition of the set 
of natural numbers to nonintersected subsets $Q_i$, such that for each $i$
the set $Q_i$ consists of all natural numbers dividing by $r_i$ and 
not dividing by $r_1, \, r_2, \, \dots ,r_{i-1}$. The set $Q_i$ may be 
represented in the following form:

$$ Q_i = \{ m \in Z^+: mr_i(r_{i-1}?n + q), \, n \in Z^0, \, q \in \Pi_i \} $$

\noindent where $Z^0=Z^+ \cap \{0\}$ and the set $\Pi_i$ consists of $1$ and
a set of all prime numbers larger or equal than $r_i$ and less than $r_{i-1}?$.
Hence the density of this set is well defined and is equal to 
$p_i=\#(\Pi_i)/r_i?$.

Now let us answer a question: when for a fixed pair $(i,j)$ a number 
$n \in Q_i$ is such that $n$ is divided by $r_j$ and $I(n\alpha) \in Q_j$.
This means that the system $(f_{1/n}^{(\alpha)},T_{1/n})$ is not ergodic.
>From the definition of the sets $Q_i$ it follows that the necessary and 
sufficient condition for the event above is the following:

$$ \mid r_j(r_{j-1}?m + q_j) - r_jr_i(r_{i-1}?n + q_i)\alpha \mid < 1/2, $$

\noindent where $m,n \in Z^0$ are arbitrary nonnegative integers, 
$q_i \in \Pi_i$ and $q_j \in \Pi_j$. This inequality is equivalent to 

$$ \mid m + q_j/r_{j-1}? - r_iq_i\alpha/r_{j-1}? - r_i?n\alpha/r_{j-1}? \mid 
   < 1/(2r_j?). $$

\noindent Denoting $R_{ij} = r_i?/r_{j-1}?$ and 
$L_{ij} = (q_j - r_iq_i\alpha)/r_{j-1}?$, we obtain

$$ \mid m + L_{ij} - nR_{ij}\alpha \mid < 1/(2r_j?). $$

The value $m$ is arbitrary, therefore the last inequality is equivalent to 
a condition that the fractional part of $nR_{ij}\alpha$ lies in the smaller 
segment $\Delta_{ij}$ of the unit circle between the points 
$(L_{ij} \pm 1/(2r_j?)) \, ({\rm mod} 1)$. The length of this segment 
is equal to $1/r_j?$.

Now we consider a dynamical system $(F,T)$ on a unit circle $T$, where $F$ 
is a rotation through the irrational angle $R_{ij}\alpha$. Analogously 
to the proof of Theorem 4 the fraction of time that the trajectory of 
this system starting from the zero point spends in the segment 
$\Delta_{ij}$ is equal to its length $1/r_j?$. On another hand for a fixed 
value $q_j \in \Pi_j$ this means that the relative density of natural 
numbers such that $n \in Q_i$ is such that $n$ is divided by $r_j$ and 
$I(n\alpha) \in Q_j$ and $n=mr_i(r_{i-1}?n + q_j)$ is equal to $1/r_j?$ and 
does not depend on $q_j$. Therefore the whole relative density $p_{ij}$ of
natural numbers such that $n \in Q_i$ is such that $n$ is divided by $r_j$ 
and $I(n\alpha) \in Q_j$ is equal to $\#(\Pi_j)/r_j? = p_j$. 

Now using these relative densities we can calculate the the 
statistical probability of ergodicity: 

$$ p(\alpha) = 1 - \sum_i p_i \sum_j p_{ij} = 1 - \sum_i p_i \sum_j p_j
             = 1 - (\sum_i p_i)^2 = 1-1 = 0.$$ 

In the multidimensional case the system $(f_{1/N}^{(\alpha)},T_{1/N})$ is 
ergodic if and only if 

\item{(a)} for all $i$ natural numbers $N$ and $I(N\alpha_i)$ have no 
common multipliers;  

\item{(b)} for all $i \ne j$ natural numbers $I(N\alpha_i)$ and $I(N\alpha_j)$ 
have no common multipliers. 

\noindent By the first part of the proof the density of all natural $N$ 
satisfying the first condition is equal to zero. It remains to prove that
the density of all natural $N$ satisfying the second condition is well 
defined, but one can do this in the same manner as the first part of the 
proof. Q.E.D.

\bigskip

{\bf Proof of Theorem 12.} At first we consider the linear case and certain
generalizations of the weak local Markov conditions (1) - (3) for a sequence of
linear mappings $\{ f_i \}$:

$$(1^\prime) \quad  \pi_{i+1}^+(f_iA_i \cap A_{i+1}) = \pi_{i+1}^+(A_{i+1}), $$

$$(2^\prime) \quad  \pi_i^-(f_{i+1}^{-1}(f_iA_i \cap A_{i+1})) = \pi_i^-(A_i),
$$

$$(3^\prime) \quad  f_i(\partial A_i) \cap \partial A_{i+1} = f_i(\partial^+
A_i) \cap \partial^-A_{i+1}, $$

We shall show that if the sequence of linear mappings $\{ f_i \}$ satisfies
conditions ($1^\prime$) - ($3^\prime$), then there exists a point $x \in A_0$
such that for all natural numbers $n$ we have

$$ f_nf_{n-1} \cdots f_2f_1(x) \in A_n. $$

For each $i$ we construct a new sequence of sets $\{ A_i^{(k)} \}_k$, where
$A_i^{(0)} = A_i$, and consecutive sets are defined inductively:

$$  A_i^{(k+1)} = f_{i+1}^{-1}(f_iA_i^{(k)} \cap A_{i+1}^{(k)}).  $$

By construction, $A_i^{(k+1)} \subset A_i^{(k)} \subset A_i$. Moreover, the
linearity of the mappings $f_i$ and condition ($3^\prime$) imply that the sets
$f_i^{(k)}A_i \cap A_i^{(k)}$ and $A_i^{(k+1)}$ are parallelograms for all $i$
and $k$. Now from conditions ($1^\prime$) and  ($2^\prime$) it follows that for
each $i$ and $k$ the intersection of parallelograms $A_{i+1}^{(k)}$ and
$f_iA_i^{(k)}$ is not empty.

Since the parallelograms $A_i^{(k)}$ on $k$ are nested, there exists a nonempty
set $A_i^* = \cap_k A_i^{(k)}$. However according to the definition, 

$$  f_{i+1}^{-1}(f_iA_i^* \cap A_{i+1}^*) = A_i^*. $$

\noindent Therefore, $f_iA_i^* \supset A_{i+1}^*$ for all $i$, i.e. the family
of sets $\{ A_i^* \}$ is invariant with respect to the sequence of mappings $\{
f_i \}$, and this implies the desired statement.

It remains to consider the nonlinear case. To reduce this case to linear one,
in a small neighborhood of each point $x_i$ we carry out a change of variables
$g_i$, transforming the mapping $f$ locally to its linear part $f_i$. Note that
by the assumptions of the theorem the mapping $g_i$ is close to the identity in
this neighborhood for all $i$.  

Now, since the weak local Markov conditions (1) - (3) are satisfied for the
mapping $f$ with excess (replacing $A_i$ by $A_i^\sigma$ and $A_{i+1}$ by
$A_{i+1}^{-\sigma}$) and the parallelograms $\{ A_i \}$ are small, the sequence
of parallelograms $\{ A_i \}$ satisfies conditions ($1^\prime$) - ($3^\prime$)
for the sequence of linear mappings $\{ f_i \}$. Therefore there exists a point
$y \in A_0$ such that for all natural numbers $n$ we have

$$ f_nf_{n-1} \cdots f_2f_1(y) \in A_n. $$

\noindent Carring out the inverse change of variables and setting $x =
g_0^{-1}(y)$, we obtain the statement of the theorem.

When condition (1) or condition (2) breaks down, there is no intersection 
of the image and the preimage of some parallelograms (see Fig. 5(a,b)), 
therefore the set $A_0^* = \cap_n f^{-n}(A_n)$ is empty. In the case when the 
condition (3) breaks down, we come to the same situation as in the 
previous cases, only on the next step of the construction of the sets $A_i$ 
(see Fig. 5(c)).

To verify the absence of excess in conditions (1) - (3) we consider a
counterexample for this case, which is shown on the Fig. 5(d). If the image and
preimage are close to fine strips (strong expansion along the positive
direction and strong compression along the negative one) and are close to one
of diagonals of parallelograms, then the nonlinearity of the mapping $f$ may
bring to their repeated intersections. As a result, $A_i^{k+1}$ on the next
iteration consists of several connected components, among which lies an image
of the set $A_{i-1}^k$, so that the intersection is empty. Q.E.D.


\bigskip
\centerline      {\bf 9. Conclusion} 
\smallskip

It was shown that the influence of small deterministic perturbations due to the
phase space discretizations to the dynamics of chaotic dynamical systems may be
very drastic even in the case of sufficiently "good" systems. Results of type
of "period multiplication" show that numerical investigations of the Feigenbaum
scenario of the transition to chaos are not quite evident. The same problem
appears in the numerical investigation of histograms along trajectories of
dynamical systems. Due to the finiteness of the phase space $X_\epsilon$ of the
$\epsilon$-discretized dynamical systems, discretization results only in the
destruction of chaotic properties. However section 6 shows that the emergence
of chaos under partial discretization seems to be typical. Some applied results
are given in sections 5 and 7. The method of section 5 gives a possibility to
investigate statistical properties of chaotic systems by means of adding small
suitably chosen random perturbations. The results of section 7 show that even
in the general case one can verify numerically the existence of the genuine
trajectory of the system in the neighborhood of a numerical trajectory.  

\bigskip
\centerline      {\bf Acknowledgement} 
\smallskip

I wish to thank the Cassini Laboratory of Nice Observatory, where part of this
work was done, for its kind hospitality. I also thank U.Frisch and M.Henon for
very useful discussions. The work was supported by the French Ministry of
Education.

\vfill \eject

\bigskip
\centerline      {\bf Literature} 
\smallskip

\item {[1]} Beck C., Roepstorff G. Effect of phase space discretization on
the long-time behavior of dynamical systems. Physica D 25, 1987, p.173-180.

\item {[2]} Blank M.L. Ergodic properties of discretizations of dynamical
systems. Docl. Russian Ac. of Sci, 278:4(1984), 779-782.

\item {[3]} Blank M.L. Ergodic properties of one method of computer
modeling of chaotic dynamical systems. Matem. Zametki, 45:4,1989, p.3-12.

\item {[4]} Blank M.L. Small perturbations of chaotic dynamical systems.
Uspekhi Matem. Nauk., 44:6,1989, p.3-28.

\item {[5]} Blank M.L. Stochastic attractors and their small
perturbations. Math. Problems of Statistical Dynamics, Reidel. Holland, 1986,
p.161-197.

\item {[6]} Blank M.L. Marginal singularities, almost invariant sets,
and small perturbations. Chaos, 1:3(1991), 347-356.

\item {[7]} Gora P., Boyarsky A. Why computers like Lebesgue measure?
Preprint Concordia Univ., 1987.

\item {[8]} Hammel S.M., Yorke J.A., Grebogi C. Numerical orbits of chaotic
processes represent true orbits. Bull. AMS, 19:2(1988), 465-469.

\item {[9]} Nusse H.E., Yorke J.A. Is every approximate trajectory of some
process near an exact trajectory of a nearby process? Comm. Math.  Phys.,
114:3(1988), 363-379.

\item {[10]} Bunimovich L.A., Pesin Ya.G., Sinai Ya.G., Jacobson M.V. 
Ergodic theory of smooth dynamical systems. Modern problems of mathematics.
Fundamental trends. v.2, 1985, P.113-231.

\item {[11]} Anosov D.V. Geodesic flows on closed Riemannian manifolds with
negative curvature. Trudi. Math. Inst. Russian Ac. of Sci, V.90(1967), 210 p.

\item {[12]} Matsumoto K., Tsuda I. Noise - induced order, J. of Statist.
Phys., 31:1(1983).

\item {[13]} Arnold V.I. Additional chapters of theory of ordinal
differential equations. - M.:Nauka, 1978, 304 p.

\item {[14]} Bernstein D., Katok A. Birkhoff periodic orbits for small
perturbations of completely integrable Hamiltonian systems. Invent.
Math. 88(1987), 225-141.


\bigskip \bigskip \bigskip \bigskip
\bigskip
\centerline      {Figure Captions} 
\smallskip

\item {Fig. 1.} Period doubling due to round-off errors. Case of a period
2 cycle. By solid squares we denote the points of the parent cycle, and by
lines the trajectory of the cycle of the discretized system.

\item {Fig. 2.} Invariant set of the discretized rotation of the plane 
($\alpha=0.1234, \, \epsilon = 0.01$).

\item {Fig. 3.} Destabilization of the generalized discretized rotation of the
plane. By solid lines we denote one of the invariant curves for the genuine
system, and by lines with arrows a trajectory of the discretized system.

\item {Fig. 4.} The region, where the discretized mapping monotonically
increases the distance from the origin.

\item {Fig. 5.} Counterexamples to Theorem 12.

\end