Abstract and Contents

4. Correctness

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.

Abstract and Contents

Written by: Bernd Krauskopf & Hinke Osinga
Created: May 27 1997 --- Last modified: Fri May 30 19:52:54 1997