next up previous
Next: Shadowing lemmas for ODE Up: Shadowing Lemmasand theoretical Previous: Shadowing Lemmasand theoretical

Shadowing lemmas for discrete maps

Chow and Palmer [14] provide a proof of the shadowing lemma in 1 dimension when f is a (non-uniformly) expanding map. (Recall that if f is expansive in forward time, then it is contractive in reverse time. Thus we want f to be as expansive as possible when iterated forward, i.e.,  we want tex2html_wrap_inline2890 to be as small as possible, to facilitate shadowing.) Let tex2html_wrap_inline2892 be a pseudo-orbit of a tex2html_wrap_inline2894 continuous map tex2html_wrap_inline2360 . They define the ``expansiveness'' as


Each tex2html_wrap_inline2900 measures how contractive the map is when applied backwards at step i, so that smaller is ``better''. So, each term in the sum measures how contractive the map is when applied backwards from step m down to n. Thus, the larger the sum of absolute values is, the less contractive the map is, when applied backwards from any point beyond n, down to n. Finally, the supremum measures how non-contractive the map can be anywhere. The larger tex2html_wrap_inline2912 is, the less contractive the inverse map tex2html_wrap_inline2466 is, and the more difficult it is to shadow the orbit.

Then they define a term I would call the ``error diminishing factor'':


where tex2html_wrap_inline2918 is the 1-step error of step m+1. The description is similar to that of tex2html_wrap_inline2912 . For example, the n=0 term measures by how much all the 1-step errors are contracted when they are propagated backwards to step 0.

THEOREM[14]: Let tex2html_wrap_inline2360 be a tex2html_wrap_inline2894 function with


Let tex2html_wrap_inline2932 be a pseudo-orbit of f such that


Then there is an exact orbit tex2html_wrap_inline2938 with


OUTLINE OF PROOF: We will not discuss the lower bound except to note the interesting fact that it says that the shadow can not be arbitrarily close to the noisy orbit. It is the upper bound that concerns us.

Let the 1-step error at each step be tex2html_wrap_inline2942 and let tex2html_wrap_inline2944 be the offset from the noisy orbit to the true orbit we will find, tex2html_wrap_inline2946 . The tex2html_wrap_inline2948 are analogous to the correction terms tex2html_wrap_inline2950 of the GHYS/QT refinement algorithm defined in equation (7). Then we find that the tex2html_wrap_inline2944 need to satisfy




tex2html_wrap_inline2958 measures the quality of the 1st order Taylor approximation to tex2html_wrap_inline2960 , so tex2html_wrap_inline2962 for small z. It comprises the terms we ignored in equation (7) that go to zero as tex2html_wrap_inline2966 approaches a true orbit.

Denote by S the set of sequences tex2html_wrap_inline2948 with tex2html_wrap_inline2972 for all n. The following mapping T is analogous to 1 refinement of the GHYS/QT algorithm, with the boundary condition tex2html_wrap_inline2978 . However, it includes, via tex2html_wrap_inline2980 , the second-and-higher order terms ignored by GHYS/QT, so that if one could actually construct T, it would find the exact shadow in a single ``refinement'' iteration:


Chow and Palmer go on to show that T maps S into itself by showing that tex2html_wrap_inline2990 and hence that tex2html_wrap_inline2992 is bounded by tex2html_wrap_inline2994 . Finally, since T maps S into itself, they invoke Brouwer's Fixed Point Theorem to prove that there is a fixed point tex2html_wrap_inline3000 of T, proving that a shadow exists within tex2html_wrap_inline3004

Since computing tex2html_wrap_inline2912 and tex2html_wrap_inline3008 in full would be very expensive ( tex2html_wrap_inline3010 time), they instead compute


where p is a positive integer chosen as follows. For tex2html_wrap_inline3016 , we define


Then we choose the smallest p so that tex2html_wrap_inline3022 . What tex2html_wrap_inline3024 says in words is, ``ensure that any sequence of p iterations of tex2html_wrap_inline2466 , taken as a unit, perform a contraction''. Said another way, if tex2html_wrap_inline3022 , then there does not exist an expansive sequence of backwards iterations of f lasting longer than p. Thus, all backwards sequences of iterations of f longer than p will be contracting, so that, as a whole, the trajectory is ``shadowable''. The larger p is, however, the less shadowable the trajectory becomes until, if tex2html_wrap_inline3042 , there is too little hyperbolicity. Using a similar argument they define a tex2html_wrap_inline3044 , using the same p as tex2html_wrap_inline3024 above.

Finally, Chow and Palmer apply this algorithm to the quadratic map


They show that with a=3.8 and tex2html_wrap_inline3054 , they can choose p=30, and can shadow the orbit for N=426,000 iterates, with a shadowing distance of tex2html_wrap_inline3060 . They also perform a detailed analysis of roundoff errors to ensure that their bound is completely rigorous, but we do not detail their analysis here.

Hadeler [29] relates Chow & Palmer's one dimensional Shadowing Lemma to the older and more well understood work related to Newton's method and Kantorovich's theorem. Kantorovich's theorem is a statement relating G, G', tex2html_wrap_inline3066 and an initial guess tex2html_wrap_inline2244 to the convergence of Newton's method. Hadeler shows how to translate between Chow & Palmer's Shadowing Lemma and Kantorovich's theorem, showing the relation between the former's tex2html_wrap_inline2912 and tex2html_wrap_inline3008 quantities to quantities needed in order for Kantorovich's theorem to hold. This means that we are closer to being able to apply the vast amount of literature related to Newton's method to shadowing.

Chow and Palmer extended their analysis to maps in higher dimensions [15]. Although the details are different for the multidimensional case, the basic idea is the same as the one dimensional case. Letting tex2html_wrap_inline2946 be a true orbit offset by tex2html_wrap_inline2944 from the noisy orbit tex2html_wrap_inline2966 , one defines an operator L that computes 1-step errors from offsets:


where Z is the set of possible offsets and E is the set of possible 1-step errors. Note that if the space is D dimensional and there are N points in the orbit, then tex2html_wrap_inline3092 , but tex2html_wrap_inline3094 , so L is many-to-one. (This is not surprising: there are many different noisy orbits that can possess the same set of 1-step errors.) Finally, our task is to solve tex2html_wrap_inline3098 . However, since L is many-to-one, tex2html_wrap_inline3102 is not unique and our task is to choose the tex2html_wrap_inline3102 with smallest norm, so that tex2html_wrap_inline3106 is minimized. Chow and Palmer show that if the map has strong hyperbolicity, then the tex2html_wrap_inline3102 with smallest norm is the one that we would expect if we understand the GHYS/QT algorithm: after decomposing space into the stable and unstable subspaces, tex2html_wrap_inline3110 has zero component in the stable subspace, while tex2html_wrap_inline3112 has zero component in the unstable subspace. They demonstrate their method on the Hénon map, and show that for a noisy orbit in double precision with 1-step errors of tex2html_wrap_inline3114 , they can use p=40 and shadow N=333,000 iterates with an tex2html_wrap_inline3120 . This means that the shadowing distance is about tex2html_wrap_inline2008 times the size of the 1-step errors, giving a shadow distance of about tex2html_wrap_inline3124 .

This ``magnification factor'', the ratio between shadow distance and local error, is termed the ``brittleness'' of an orbit by Dawson et al.  [20]. They show that if the number of positive and negative Lyapunov exponents changes, or if a particular one fluctuates about zero, then this magnification factor can blow up. If the brittleness is of order the inverse of the machine epsilon, then all accuracy is lost as the shadowing error is comparable to the size of the variables themselves. The reason that a fluctuating exponent is bad is related in the following diagram, where tex2html_wrap_inline2314 is the local error, and the vertical direction is initially contracting, but then becomes expanding (Figure 3).


As we see, (a) an ensemble of trajectories that starts off in an tex2html_wrap_inline2154 -ball is first compressed into a sheet. (b) If the local error steps outside this sheet, and then the direction becomes an expanding direction, then (c) the numerical trajectory diverges away from all true trajectories that started in the original tex2html_wrap_inline2154 -ball, (d) possibly entering regions of phase space with qualitatively different behaviour than the true trajectories.

However, Dawson et al.  make the strong claim that they believe this kind of fluctuation of Lyapunov exponents is ``common'' in high dimensional systems, with the only justification apparently being that there are so many dimensions, there must be a fluctuating exponent somewhere. It is unclear if this argument applies to all systems. For example, Hamiltonian systems always have equal numbers of positive and negative exponents.

next up previous
Next: Shadowing lemmas for ODE Up: Shadowing Lemmasand theoretical Previous: Shadowing Lemmasand theoretical

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

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