Dynamical systems often display sensitive dependence on initial conditions: small changes in the conditions at any point in the orbit produce solutions that exponentially diverge from each other, leading to a vastly different solution a short time later. Since a numerical method introduces small perturbations like roundoff and truncation error, we must naturally ask what effect these errors have on the validity of numerical solutions.

A true trajectory of a dynamical system lying near an approximate
trajectory is called a *shadow*. A pleasant introduction to
the shadowing idea is provided by Sanz-Serna and Larsson
[67].
Although there exist other methods of global error analysis, shadowing
is unique in that it demands that the equation governing the ODE
remain fixed, while the initial conditions are perturbed in
an effort to find a nearby true solution that remains close to the
computed solution. The measures of error for shadowing are the
distance between the numerical trajectory and the shadow, and the
length of time the two remain near to each other.
This is different from more common forms of
backward error analysis for ODEs (see, *eg., * [19])
and also the argument used in favour of symplectic integrators,
in which it is shown that the numerical solution lies along the exact
solution of an ODE system whose governing equation has been slightly
perturbed.
Although the latter approach is useful in some contexts,
it is not clear that changing the
governing equation is always the best way to measure error,
especially if the governing equation satisfies special conditions
that, if violated, could produce qualitatively different solutions.
For example, a Hamiltonian
system may not remain Hamiltonian if small, arbitrary,
time-varying perturbations are allowed in its governing equation.
Most practitioners of physical simulation are optimistic that their
results are at least statistically valid, but ``even optimists need criteria
to decide how accurate the integration has to be to yield valid statistical
results.'' [62]

We start with some definitions. The terms *orbit*, *trajectory*,
and *solution* are used interchangeably.
We assume a well-scaled problem where all macroscopic
quantities of interest are of order unity.
Throughout this section, denotes the Euclidian norm, and
denotes the max norm, although any other norm should give
similar results.

*Definition.* A *true trajectory*
of *f* satisfies for .

We are interested in the case that *a* and *b* are finite integers.
For a discrete
map, *f* may be a simple equation, such as the logistic equation
, which maps the interval [-1,1] onto itself.
For an ODE system like the *N*-body problem,
represents the one-timestep flow through .

*Definition.* is a -*
pseudo-trajectory*, also called a *noisy orbit*, for *f* if
for , where
is the noise amplitude.

For a discrete map, is often the machine epsilon; for an ODE system that has position at time , it is the error per step.

*Definition of shadowing.* The true trajectory
-*shadows* if
for .

*Definition.* For , the *1-step error*
made between step *i* and step *i*+1
of the pseudo-trajectory is
.

Thus, a true trajectory is one whose 1-step errors are identically zero, and a -pseudo-trajectory is one whose 1-step errors satisfy for .

*Definition.* The pseudo-trajectory has a
*glitch* at point if for some relevant there
exists a true trajectory that -shadows ,
but no true trajectory that -shadows
for .

As noted by Quinlan and Tremaine [62], ``The failure [to find a shadow] does not [seem to] arise from a gradual increase in distance over time. Instead, there are isolated regions of a few iterations (``glitches'') over which no true orbit can be found that shadows the noisy orbit.''

*Definition.* *Refinement* is a process, similar to Newton's
Method, that iteratively takes a noisy orbit and tries to produce
a nearby orbit with less noise, *i.e., * one with smaller 1-step errors.
A refinement iteration is *successful* if before
the iteration the trajectory has noise , after the iteration it
has noise , and

Otherwise the refinement iteration is *unsuccessful*.

Shadowing was first discussed by Anosov [3] and Bowen [10],
in relation to *hyperbolic* systems. In a 2-dimensional
hyperbolic system, there are two special directions called the *
unstable* (or *expanding*) and the *stable* (or *
contracting*) directions, which may vary with time and generally are
not orthogonal. Small perturbations along the stable direction decay
exponentially in forward time, while small perturbations in the
unstable direction grow exponentially in forward time. The two
directions reverse rôles in backward time. In addition, the angle
between the stable and unstable directions is uniformly bounded away
from 0. In such a system, Anosov and Bowen proved that
if is a -pseudo orbit of
arbitrary length, then there exists a true orbit that stays within
of .

Fri Dec 27 17:41:39 EST 1996

Access count (updated once a day) since 1 Jan 1997: 9011