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 .