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 . 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 : 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
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 .