It is very hard, if not impossible, to give a complete error analysis
for any algorithm that computes a global object like an unstable
manifold. Here we show that the distance between a * first finite
piece* of
and its approximating
triangulation
goes to zero with the initial distance from *H* and the mesh
size. We use that *f* is Lipschitz in a neighborhood of
.

To fix terms, suppose that
is the first finite piece of
of a normally hyperbolic
invariant circle *H* of saddle-type. (The argument goes through
for the unstable manifold of a hyperbolic fixed point as well.)

Because is bounded and *f* is at least , we can always
find a finite constant such that is
-Lipschitz in a neighborhood *U*. Furthermore, *H* is
normally hyperbolic, so that is even locally attracting if
it is contained in a small enough neighborhood of *H*. In other word,
for fixed -Lipschitz we can find a that is locally -attracting in a
neighborhood *V*, for a certain .

Let be the continuous approximation of , given as
a triangulation in `Tri`

with mesh points in `Mesh`

. For
simplicity we assume that
(see Section 3.4 for the definition of ). In other words, the mesh is uniform, and describes
its quality. We like to think of as a fixed object of which
we want to compute the distance to . If we change
, then `Tri`

and `Mesh`

change accordingly, so that
becomes a different object for which the distance
to is different as well. We assume that .

The idea is now to show that the error goes to zero as the
initial distance from *H* and the mesh width both go
to zero. For this we make use of the Lipschitz constants and
. Note that it is impossible to determine these constants in
practice if is a global object of reasonable size. In other
words, we cannot give an a priori error bound on the distance between
and for given and .
At the end of this section we discuss how the accuracy of
the approximation can be checked numerically.

For technical reasons we need the error at the mesh points of
`Mesh`

and the interpolation error.

If is not a mesh point, then the distance of *q* to
depends only on the distance of the mesh points to
and the mesh width . Hence, the difference between
the global error and the error at the mesh points is
finite and depends on .

Clearly, goes to zero as , since then . If is then .

* Proof of Theorem 3:*
Note that Definitions 2,
4 and
5
imply that

for all , where *N+1* is the total number of circles
in `Mesh`

. Hence, we need to show that becomes
arbitrarily small as .
The idea is to estimate the error on first and then
the error on the rest of .

To this end, we now consider the first *K+1* circles in `Mesh`

,
where *K* depends on and , and is such that for all
*p* = `Mesh[k][`

r`]`

with and

This means that the first *K+1* circles in `Mesh`

form an
approximation of .
(Note that *K = N* if .) Since
the first two circles in `Mesh`

are distance apart, we
can assume that *K > 1* by taking small enough. We also
assume that these *K* rings of are contained in *V*, the
neighborhood on which *f* is a contraction.

The initial error is the maximal distance
to of the mesh points on the first two circles
`Mesh[0]`

and `Mesh[1]`

. The mesh points of the circle
`Mesh[0]`

are the points of *M*. With the algorithm in
[Osinga 1996,
Broer et al. 1996,
Broer et al. 1997] it is possible to ensure that the distance
of the points in *M* to *H* is at most . The mesh points of
the circle `Mesh[1]`

lie at distance from
`Mesh[0]`

. Consequently, we get for the initial error
at the mesh points ,
because is at least
. If is then .

In the next step we express in terms of for
. By definition , but
it may happen that
the error in the -st step does not increase, so that
. Now suppose that is
the point on such that `Mesh[k+1][`

r`]`

=
. By construction, , and we have

This shows that the error does not increase, if
is small compared to . Suppose the error
increases *l* times in the *K* steps that build the first *K + 1*
circles. This means that

where the last inequality holds for all , because . Hence, the total error for the approximation of is bounded from above by:

Clearly, goes to zero as . If is , then and . Consequently, , which is the claimed result for .

For the circles `Mesh[k]`

with we need to
proceed more carefully. Again we concentrate on the error
at the mesh points, where now . As before, let
be the point on such that `Mesh[k+1][`

r`]`

= . If is contained in the part of given by
the first *K+1* circles, then we can immediately find a bound on the
error at by using
Equation (2) and the
Lipschitz constant for *f*.

The idea is to count the number of iterations it takes to reach any
given point in
with a point in . This number
is finite, because is bounded. Since we only have an
approximation of and , we need to consider the
maximum number of itererates that a point from *V* spends in a
closed neighborhood of . Note that the neighborhood
can be chosen such that , because we have assumed that . Since is compact, this maximal number of
iterates exists and we denote it by .
It is important to note that only depends on
and , so that it does not change if we decrease and/or
.

Let be
the point on such that `Mesh[k+1][`

r`]`

=
. Clearly, lies in ring *i* of for some
. Then

Hence, for any , either or we can apply the inequality with , However, we can do this at most times before we reach for which we already have an upper bound in terms of . Hence,

(Here we assume that , because
otherwise *K = N* and .)
Combining (2) and
(3) leads to

Because , and are constants, goes to zero with the same order as . If is then (1) follows.

**Remark 6** *
Note that the estimate does not depend on the accuracy
of the
bisection. In practice,
should be small to ensure
that f(q) lies approximately in the leaf
and at a distance
from the last
point. However, the distance of f(q) to
is
governed by the fact that q lies in a triangle of the
continuous object .
*

The error estimate in Theorem 3 is a theoretical
result. In practice, it is impossible to check if is locally
attracting, and to determine . However,
Theorem 3 suggests a strategy for numerically
checking if a computed piece is close to : repeat
the computation with a finer mesh and a smaller initial distance from
*H* to obtain a second approximation . If the
distance between and is small then it is
reasonable to assume that is indeed close to . We
have used this method to check the accuracy in the examples in
Section 5.

If there are periodic points on *H*, one can
compute their one-dimensional (strong) unstable manifolds, which lie in
. Then is close to if these
one-dimensional objects lie in within the given accuracy;
compare Section 5.1. Furthermore, in
Section 5.3 we study a test example,
where the unstable manifold (of a fixed
point) is known analytically. This allows us to estimate the global
error numerically and monitor its growth.

In summary, we have the confidence that our algorithm is capable of computing a large piece of with sufficient accuracy, so that statements on the global dynamics are possible. We refer to the examples in the next section.

Written by: Bernd Krauskopf
& Hinke Osinga

Created: May 27 1997 ---
Last modified: Fri May 30 19:52:54 1997