next up previous
Next: Tutorial Up: Shadowing Previous: Shadowing

Introduction

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, tex2html_wrap_inline2218 denotes the Euclidian norm, and tex2html_wrap_inline2218 denotes the max norm, although any other norm should give similar results.

Definition. A true trajectory tex2html_wrap_inline2222 of f satisfies tex2html_wrap_inline2226 for tex2html_wrap_inline2228 .

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 tex2html_wrap_inline2236 , which maps the interval [-1,1] onto itself. For an ODE system like the N-body problem, tex2html_wrap_inline2242 represents the one-timestep flow through tex2html_wrap_inline2244 .

Definition. tex2html_wrap_inline2246 is a tex2html_wrap_inline2248 - pseudo-trajectory, also called a noisy orbit, for f if tex2html_wrap_inline2252 for tex2html_wrap_inline2228 , where tex2html_wrap_inline2248 is the noise amplitude.

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

Definition of shadowing. The true trajectory tex2html_wrap_inline2222 tex2html_wrap_inline2266 -shadows tex2html_wrap_inline2246 if tex2html_wrap_inline2270 for tex2html_wrap_inline2272 .

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

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

Definition. The pseudo-trajectory tex2html_wrap_inline2246 has a glitch at point tex2html_wrap_inline2292 if for some relevant tex2html_wrap_inline2266 there exists a true trajectory that tex2html_wrap_inline2266 -shadows tex2html_wrap_inline2298 , but no true trajectory that tex2html_wrap_inline2266 -shadows tex2html_wrap_inline2302 for tex2html_wrap_inline2304 .

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 tex2html_wrap_inline2306 , after the iteration it has noise tex2html_wrap_inline2308 , and

  equation280

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 tex2html_wrap_inline2310 if tex2html_wrap_inline2312 is a tex2html_wrap_inline2314 -pseudo orbit of arbitrary length, then there exists a true orbit that stays within tex2html_wrap_inline2154 of tex2html_wrap_inline2312 .


next up previous
Next: Tutorial Up: Shadowing Previous: Shadowing

Wayne Hayes
Fri Dec 27 17:41:39 EST 1996

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