Before going into detail about shadowing algorithms and lemmas, it will be instructive to highlight how shadowing differs from other methods of error analysis, and to give some simple examples.

We look at error analysis techniques for the numerical solution of

Let *y*(*t*) be the true solution, and be a suitably smooth
and accurate interpolant of the (discrete) computed solution.

*Forward* error analysis is the most stringent.
It states that the numerical solution remains close to the true
solution with the same initial conditions:

*Backward* error analysis states that the numerical solution
lies on the solution to a slightly perturbed problem. For example,
*Defect control* is a method of backward error analysis demanding
that the derivative of the numerical solution
remain close to the right hand side computed along the numerical solution:

This is also called the method of *modified equations*, because
it tries to find a slightly different right hand side whose
true solution stays closer to the numerical solution than the true solution
of the original equation.
Finally, shadowing is another form of backward error analysis that
says that we remain close to some true solution
of the true ODE, but that has slightly different initial
conditions:

where is the shadow length.

A simple example of a shadowable system is provided by Quinlan and
Tremaine [63]. Let *x*''=*x*, *i.e., * in phase space,
and let . The true solution is
. Now introduce ``noise'' at *t*=0. The
noisy solution becomes

A shadow of this noisy solution is

which remains within (in phase space) from *x*(*t*) for
all *t*.

Next we offer a taste of the proof of an almost ``trivial'' theorem: if a 1D map is contracting, then noisy orbits are shadowed. First we prove a lemma.

*LEMMA* [1D Fixed Point Lemma]: Let be
a continuous map. Then there exists
a fixed point of *f*, *i.e., * .

*PROOF* [44]: If *f*(0)=0 or *f*(1)=1 we are done.
Thus, assume 0 < f(0) and *f*(1) < 1.
Consider *g*(*x*) = *x*-*f*(*x*). Clearly *g*(0) = 0 - *f*(0) < 0 and
*g*(1) = 1-*f*(1) > 0. Since *g*(*x*) is continuous, it must cross 0 as
x increases from 0 to 1. Hence, there is some in [0,1] for
which , so

A slightly more complex argument is required to prove the existence of
a fixed point for an arbitrary interval *X*. For our purposes we will
assume the above lemma holds for an arbitrary closed finite interval,
not just [0,1].

*THEOREM* [1D Contracting Map Shadowing Theorem]:
Let *X* be a continuous 1-dimensional interval and
let be a continuous,
uniformly contracting scalar map,
*i.e., * .
Note that if *f*' exists and is continuous then we can take
.
Then for every there exists such that every
-pseudo orbit is -shadowed.

*OUTLINE OF PROOF*: We demonstrate an asymptotically necessary
condition for , but do not prove sufficiency.
By the 1D fixed point lemma, there exists a fixed point .
Furthermore, since *f* is a stable (*i.e., * contracting) map, is a *
stable* fixed point, which all true orbits asymptotically
approach. To devise the necessary condition on ,
assume pessimistically that
after every iteration, the noisy orbit jumps by in the direction
away from .
Assume, without loss of generality, that *f* is increasing in
an -neighborhood of , so that .
Then, in order to stay within of , we require
that a point on the noisy orbit starting away from is
mapped to a new point which is also no more than away from :

**Figure:** FIGURE FOR 1D CONTRACTING MAP SHADOWING THEOREM

Thus,

Notice that the closer is to zero, the more stable *f*
is, so that it can accomodate a larger noise amplitude .

If *f* were instead uniformly expanding, then we would expect our
numerical solution to be exponentially pushed away from the true
solution. This is true, but note that if *f* is expanding,
then is contracting. In this case, we can apply a theorem
similar to the above in *reverse* time.

A simple example of a system which is *not* shadowable, at least
by the definitions we've seen so far, was provided by Yorke [personal
communication]. Let *x*''=0, the solution of which is
straight-line motion at constant
velocity (assume ). This motion is about
as regular, and non-hyperbolic, as one could possibly imagine.
Now, add noise of size in *x*' at *t*=0. Since all true
solutions have constant velocity, but our noisy solution
has velocity , and a *different* velocity
, it is easy to see that any true solution will
diverge linearly away from the noisy solution inside at least one of
the intervals . Thus, no true solution
exists that remains close to the noisy solution for both and
.

Fri Dec 27 17:41:39 EST 1996

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