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 to be as small as possible, to
facilitate shadowing.)
Let be a pseudo-orbit of a continuous
map .
They define the ``expansiveness'' as

Each 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 is,
the less contractive the inverse map is, and
the more difficult it is to shadow the orbit.

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

where is the 1-step error of step *m*+1. The
description is similar to that of . 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 be a
function with

Let be a pseudo-orbit of *f* such that

Then there is an exact orbit 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 and let be the offset from the noisy orbit to the true orbit we will find, . The are analogous to the correction terms of the GHYS/QT refinement algorithm defined in equation (7). Then we find that the need to satisfy

where

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

Denote by *S* the set of sequences with
for all *n*. The following mapping *T* is analogous to 1 refinement
of the GHYS/QT algorithm, with the boundary condition .
However, it includes, via ,
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 and hence that is
bounded by . Finally, since
*T* maps *S* into itself, they invoke Brouwer's Fixed Point Theorem
to prove that there is a fixed
point of *T*, proving that a shadow exists within

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

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

Then we choose the smallest *p* so that . What says
in words is, ``ensure that any sequence of *p* iterations of ,
taken as a unit, perform a contraction''. Said another way, if ,
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 , there is too
little hyperbolicity. Using a similar argument they define a ,
using the same *p* as above.

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

They show that with *a*=3.8 and , they can choose *p*=30, and
can shadow the orbit for *N*=426,000 iterates, with a shadowing distance
of .
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*', and
an initial guess 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 and 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 be a true orbit offset by from the
noisy orbit , 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 , but
, 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 . However, since *L* is
many-to-one, is not unique and our task is to choose the
with smallest norm, so that is minimized.
Chow and Palmer show that if the map has strong hyperbolicity, then
the 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, has zero component in
the stable subspace, while 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 ,
they can use *p*=40 and shadow *N*=333,000 iterates with an
. This means that the shadowing
distance is about times the size of the
1-step errors, giving a shadow distance of about .

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 is the local error, and the vertical direction is
initially contracting, but then becomes expanding (Figure 3).

**Figure:** FLUCTUATING LYAPUNOV EXPONENT IN THE "VERTICAL" DIRECTION.

As we see, (a) an ensemble of trajectories that starts off in an -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 -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.

Fri Dec 27 17:41:39 EST 1996

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