next up previous
Next: Shadowing non-hyperbolic systems Up: Shadowing Previous: Introduction


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 tex2html_wrap_inline2324 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 tex2html_wrap_inline2330 of the true ODE, but that tex2html_wrap_inline2330 has slightly different initial conditions:


where tex2html_wrap_inline2336 is the shadow length.

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


A shadow of this noisy solution is


which remains within tex2html_wrap_inline2354 (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 tex2html_wrap_inline2360 be a continuous map. Then there exists a fixed point tex2html_wrap_inline2362 of f, i.e.,  tex2html_wrap_inline2366 .

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 tex2html_wrap_inline2390 in [0,1] for which tex2html_wrap_inline2394 , so tex2html_wrap_inline2396

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 tex2html_wrap_inline2404 be a continuous, uniformly contracting scalar mapgif, i.e.,  tex2html_wrap_inline2406 . Note that if f' exists and is continuous then we can take tex2html_wrap_inline2410 . Then for every tex2html_wrap_inline2412 there exists tex2html_wrap_inline2414 such that every tex2html_wrap_inline2314 -pseudo orbit is tex2html_wrap_inline2154 -shadowed.

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




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

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 tex2html_wrap_inline2466 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 tex2html_wrap_inline2470 (assume tex2html_wrap_inline2472 ). This motion is about as regular, and non-hyperbolic, as one could possibly imagine. Now, add noise of size tex2html_wrap_inline2154 in x' at t=0. Since all true solutions have constant velocity, but our noisy solution has velocity tex2html_wrap_inline2480 , and a different velocity tex2html_wrap_inline2482 , it is easy to see that any true solution will diverge linearly away from the noisy solution inside at least one of the intervals tex2html_wrap_inline2484 . Thus, no true solution exists that remains close to the noisy solution for both tex2html_wrap_inline2486 and tex2html_wrap_inline2488 .

next up previous
Next: Shadowing non-hyperbolic systems Up: Shadowing Previous: Introduction

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

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