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
.