\documentclass[cvs,envcountsect]{svjour} \usepackage{amsfonts} \usepackage{psfig} \begin{document} \newcommand{\Ref}[1]{(\ref{#1})} \newcommand{\R}{{\mathbb R}} \newcommand{\N}{{\mathbb N}} \newcommand{\cB}{{\cal B}} \newcommand{\cM}{{\cal M}} \newcommand{\diam}{\mathop{\rm diam}\nolimits} \renewcommand{\labelenumi}{(\roman{enumi})} \title{An adaptive subdivision technique for the approximation\\ of attractors and invariant measures} \author{Michael Dellnitz\thanks{Research of the authors is partly supported by the Deutsche Forschungsgemeinschaft under Grant De 448/5-2 and by the Konrad-Zuse-Zentrum f\"ur Informationstechnik Berlin.}, Oliver Junge} \institute{Mathematisches Institut, Universit\"at Bayreuth, D-95440 Bayreuth, Germany\\ {\scriptsize\tt (http://www.uni-bayreuth.de/departments/math/\~{}mdellnitz; http://www.uni-bayreuth.de/departments/math/\~{}ojunge)}} \date{Received: 13 January 1997 / Accepted: 29 September 1997 \\[1em] Communicated by: P. Deuflhard} \maketitle \begin{abstract} Recently subdivision techniques have been introduced in the numerical investigation of the temporal behavior of dynamical systems. In this article we intertwine the subdivision process with the computation of invariant measures and propose an adaptive scheme for the box refinement which is based on the combination of these methods. Using this new algorithm the numerical effort for the computation of box coverings is in general significantly reduced, and we illustrate this fact by several numerical examples. \end{abstract} \section{Introduction} % Recently subdivision methods have been successfully applied to the numerical analysis of complex dynamical behavior (e.g.\ \cite{Eiden,DH1,DH2,DJ:96,DJchua:97}). These methods can be used for two essentially different purposes: the first is to understand the geometric structure of an underlying attractor. Secondly the goal may be to approximate the observable dynamical behavior of the underlying system in a specific region of state space by the computation of invariant measures. This paper concerns the second possibility, and we propose an adaptive scheme incorporated into the subdivision technique which allows to reduce the numerical effort significantly. Obviously the dynamical behavior just needs to be approximated on the support of a certain invariant measure. Indeed, the idea for the adaptive principle stated here is to intertwine the subdivision techniques with the computation of a natural invariant measure, an {\em SBR-measure}, say. Roughly speaking, the size of the covering boxes is reduced in those parts of state space where the natural invariant measure $\mu$ is concentrated, and, on the other hand, boxes are not subdivided in areas which have $\mu$-measure zero. The main goal of this article is to illustrate the efficiency of the new method by numerical examples. For that purpose we consider several dynamical systems for which the SBR-measure is known analytically since this allows us to compare the numerical results obtained by the {\em adaptive\/} subdivision algorithm to those obtained by the {\em standard\/} subdivision procedure. The adaptive algorithm is essentially based on the combination of two existing methods for which convergence results are known. However, this fact does not immediately imply convergence of the adaptive method as well. Rather this theoretical but relevant problem is currently under investigation, and the results will be published elsewhere. An outline of the paper is as follows: in Sect.\,\ref{sec:CSA} we recall the standard subdivision technique from \cite{DH1}. The numerical method for the approximation of SBR-measures is described in Sect.\,\ref{sec:fp}. Then, in Sect.\,\ref{sec:ASA}, we present our adaptive subdivision technique, and the efficiency of this method is illustrated by several examples in Sect.\,\ref{sec:num}. \section{The standard subdivision algorithm} \label{sec:CSA} % The purpose is to approximate invariant sets of discrete dynamical systems of the form \[ x_{j+1} = f(x_j),\quad j=0,1,\ldots, \] where $f$ is a continuous mapping on $\R^n$. The central object which is approximated by the subdivision algorithm developed in \cite{DH1} is the so-called {\em relative global attractor}, \begin{equation} \label{eq:relativAttractor2} A_Q=\bigcap_{j\geq0}f^j(Q), \end{equation} where $Q\subset\R^n$ is a compact subset. Roughly speaking, the set $A_Q$ should be viewed as the {\em union of unstable manifolds of invariant objects inside $Q$}. In particular, $A_Q$ may contain subsets of $Q$ which cannot be approximated by direct simulation. The subdivision algorithm for the approximation of $A_Q$ generates a sequence $\cB_0,\cB_1,\cB_2,\ldots$ of finite collections of boxes with the property that for all integers $k$ the set $Q_k=\bigcup_{B\in\cB_k}B$ is a covering of the relative global attractor under consideration. Moreover the sequence of coverings is constructed in such a way that the diameter of the boxes, \[ \diam(\cB_k) = \max_{B\in\cB_k}\diam(B) \] converges to zero for $k\rightarrow\infty$. Given an initial collection $\cB_0$, one inductively obtains $\cB_k$ from $\cB_{k-1}$ for $k=1,2,\ldots$ in two steps. \begin{enumerate} \item {\em Subdivision:} Construct a new collection $\hat\cB_k$ such that \begin{eqnarray*} \bigcup_{B\in\hat\cB_k}B &=& \bigcup_{B\in\cB_{k-1}}B \\ \mbox{and}\quad \diam(\hat\cB_k) &\leq& \theta\diam(\cB_{k-1}) \end{eqnarray*} for some $0<\theta<1$. \item {\em Selection:} Define the new collection $\cB_k$ by \[ \cB_k=\left\{B\in\hat\cB_k \!:\! f^{-1}(B)\!\cap\!\hat B\!\ne\!\emptyset \!\!\quad\mbox{for some}\!\!\quad\hat B\!\in\!\hat\cB_k\right\}. \] \end{enumerate} The following proposition establishes a general convergence property of this algorithm. \begin{proposition}[\cite{DH1}] \label{prop:sdconv} Let $A_Q$ be the global attractor relative to the compact set $Q$, and let $\cB_0$ be a finite collection of closed subsets with $Q_0=Q$. Then \[ \lim\limits_{k\rightarrow\infty} h\left( A_Q, Q_k \right)=0, \] where we denote by $h(B,C)$ the usual Hausdorff distance between two compact subsets $B,C\subset\R^n$. \end{proposition} \setcounter{equation}{0} \section{Approximation of SBR-measures} \label{sec:fp} % Recently it has been shown in \cite{DJ:96} how to compute numerically approximations of an {\em SBR-measure\/} supported on a hyperbolic invariant set. Since we want to use this method in our adaptive scheme we now sketch the main ingredients of this algorithm. To make the ideas more transparent we simplify the description drastically by avoiding all technical details concerning the underlying mathematical foundation in Ergodic Theory. The crucial observation is that the calculation of invariant measures can be viewed as a fixed point problem. Let ${\cal M}$ be the set of probability measures on $\R^n$. Then $\mu\in{\cal M}$ is invariant if and only if it is a fixed point of the {\em Frobenius-Perron operator\/} $P:{\cal M}\to {\cal M}$, \begin{equation} \label{eq:fp-fixed} (P\mu)(B)=\mu(f^{-1}(B))\quad\mbox{for all measurable $B\subset\R^n$}. \end{equation} For a discretization of the operator $P:\cM\rightarrow\cM$ we replace $\cM$ by a finite dimensional set $\cM_k$: let $B_i\in\cB_k$, $i=1,\ldots,N$, denote the boxes in the covering obtained after $k$ steps in the subdivision algorithm and set as before $Q_k=\bigcup_{B\in\cB_k}B$. We choose $\cM_k$ to be the set of ``discrete probability measures'' on $\cB_k$, that is, \[ \cM_k = \left\{ u:\cB_k\to [0,1] \quad\Bigg| \quad \sum_{i=1}^N u(B_i)=1\right\}. \] Assuming that $f(Q_k)\subset Q_k$ the discretized Frobenius-Perron operator $P_k:\cM_k\rightarrow\cM_k$ is given by \begin{eqnarray}\label{eq:FP} v= P_k u,\quad v(B_i)=\sum_{j=1}^N \frac{m(f^{-1}(B_i)\cap B_j)}{m(B_j)}u(B_j),\\ \hfill i=1,\ldots,N,\nonumber \end{eqnarray} where $m$ denotes Lebesgue measure. Now a fixed point $u=P_k u$ of $P_k$ provides an approximation to an invariant measure of $f$. \begin{remark} For the mathematically precise statement on the convergence of this method one would have to introduce the concept of {\em small random perturbations}. The reason is that this allows one to use a result of Yu.\ Kifer on the convergence of invariant measures in the perturbed systems to the SBR-measure (\cite{Kifer:86}). However, the purpose of this article is to develop and to test an adaptive scheme for the box refinement in the subdivision algorithm rather than to explain the theoretical background concerning the computation of SBR-measures. Therefore the reader is referred to \cite{DJ:96} for the rigorous mathematical treatment. \end{remark} \section{The adaptive subdivision algorithm} \label{sec:ASA} % As mentioned above, the standard subdivision algorithm may approximate a part of the global attractor which is dynamically irrelevant in the sense that no invariant measure has support on this subset. The reason is that {\em each\/} box is subdivided in a step of the subdivision algorithm regardless of any information on the dynamical behavior. In particular, also those subsets of the relative global attractor corresponding to unstable or transient dynamical behavior are approximated by the standard procedure. On the other hand, if one is mainly interested in the approximation of the support of the (natural) invariant measure rather than in the precise geometric structure of the global attractor then this strategy may lead to unnecessary high storage and computation requirements. In the following we present a modified subdivision strategy which avoids this drawback: roughly speaking, \begin{itemize} \item[--] in the subdivision step we use the information on the actual approximation of the invariant measure to decide whether or not a box should be subdivided; \item[--] in the selection step we keep only those boxes which have a nonempty intersection with the support of the invariant measure. \end{itemize} To be more precise, let $\{\delta_k\}$ be a sequence of positive real numbers such that $\delta_k\to 0$ for $k\to\infty$. The algorithm generates a sequence of pairs \[ (\cB_0, u_0),(\cB_1, u_1), (\cB_2, u_2), \ldots \] where the $\cB_k$'s are finite collections of compact subsets of $\R^n$ and the discrete measures $u_k:\cB_k\to[0,1]$ can be interpreted as approximations to the SBR-measure $\mu_{SBR}$: \[ u_k(B) \approx \mu_{SBR}(B)\quad\mbox{for all $B\in\cB_k$}. \] Given an initial pair $(\cB_0, u_0)$, one inductively obtains $(\cB_k, u_k)$ from $(\cB_{k-1}, u_{k-1})$ for $k=1,2,\ldots$ in three steps: \begin{enumerate} \item {\em Subdivision:} Define \begin{eqnarray*} \cB_{k-1}^- &=&\{B\in\cB_{k-1}: u_{k-1}(B) < \delta_{k-1}\} \\ \mbox{and}\qquad && \\ \cB_{k-1}^+ &=& \cB_{k-1}\backslash\cB_{k-1}^-. \end{eqnarray*} Construct a new (sub-)collection $\hat\cB_k^+$ such that \[ \bigcup_{B\in \hat\cB_k^+} B = \bigcup_{B\in \cB_{k-1}^+} B \] where \[ \diam(\hat\cB_k^+) \leq \theta\diam(\cB_{k-1}^+) \] for some $0 < \theta < 1$. \item {\em Calculation of the invariant measure:} Set \[ \hat \cB_k = \cB_{k-1}^-\cup\hat\cB_k^+. \] For the collection $\hat \cB_k$ calculate the approximating invariant measure as the fixed point $\hat u_k$ of the discretized Frobenius-Perron operator defined by \Ref{eq:FP}. \item {\em Selection:} Set \[ \cB_k = \{ B\in \hat \cB_k: \hat u_k(B) > 0\} \] and \[ u_k = \hat u_k|_{\cB_k}. \] \end{enumerate} \begin{remark}\label{rmk:real} \begin{itemize} \item[(a)] In the realization of the algorithm we typically subdivide the boxes in the collection $\cB_k^+$ by bisection. This guarantees that the number of boxes is not growing too fast. For the details concerning the implementation the reader is again referred to \cite{DH1,DJ:96}. \item[(b)] In principle there is some freedom in choosing the sequence $\{\delta_k\}$ of positive numbers used in the subdivision step. Note however that this sequence determines the number of boxes which will be subdivided and hence it has a significant influence on the storage requirement. In the computations it turned out to be quite efficient to choose the average \[ \delta_k = {1\over N_k}\sum_{B\in\cB_k} u_k(B) = {1\over N_k}, \] where $N_k$ is the number of boxes in $\cB_k$. \item[(c)] In the numerical realization of the selection step (iii) we check whether $\hat u_k(B) > \epsilon$ where $\epsilon>0$ is chosen sufficiently small with respect to the machine precision. \end{itemize} \end{remark} \section{Numerical examples} \label{sec:num} % In this section we illustrate the efficiency of the adaptive scheme by several numerical examples. First we consider three one-dimensional mappings for which the SBR-mea\-sures are known analytically. For these cases we will see that, as expected, the new technique is particularly useful if the underlying invariant density has singularities. Additionally we consider the H\'{e}non map as a two-dimensional example and show the box refinement produced by the adaptive subdivision algorithm at a certain step. Before proceeding let us indicate some details concerning the implementation of the adaptive subdivision algorithm: \begin{itemize} \item[(a)] The subdivision is always done by bisection and the boxes are stored in a binary tree. This way we keep the storage requirement at a low level. \item[(b)] For the computation of the transition probabilities \linebreak $m(f^{-1}(B_i)\cap B_j)$ in \Ref{eq:FP} we use an exhaustion technique as described in \cite{GDK}. This method is particularly useful when -- as in our examples -- local Lipschitz constants are available for the underlying dynamical system. \item[(c)] The computation of the discrete measures is done by an inverse power method. In the solution of the corresponding linear systems the fact is taken into account that the discretized Frobenius-Perron operator is extremely sparse. \end{itemize} The adaptive algorithm is integrated into the C++ code {\sf GAIO} ({\bf G}lobal {\bf A}nalysis of {\bf I}nvariant {\bf O}bjects). A link to a detailed description of {\sf GAIO} can be found on the homepages of the authors. \subsection*{Three one-dimensional examples} \label{subsec:1D} % Motivated by the numerical investigations in \cite{DingDuLi:93} we apply the adaptive subdivision algorithm to three different one-dimensional dynamical systems on the interval $[0,1]$. In each case we have chosen the initial collection $\cB_0=\{[0,1]\}$. \begin{itemize} \item[{\it 1.}] As a first example we consider the Logistic Map $f_1:[0,1]\to [0,1]$, \[ f_1(x)=\lambda x(1-x) \] for $\lambda=4$. The unique absolutely continuous invariant measure $\mu$ of $f_1$ has the density \[ h_1(x)={1\over \pi \sqrt{x(1-x)}} \] (see e.g.\ \cite{Lasota:94}). Using the standard and the adaptive algorithm we have approximated this density on several levels and the results are shown in Table 1. We remark that even the computation for $\ell=20$ only takes about 50 sec on an MIPS R4400 cpu. \begin{table} \label{tab:log} \caption{Comparison between the standard and the adaptive subdivision algorithm for the Logistic Map. The minimal box volume in each row is $2^{-\ell}$} \begin{tabular}{ l l l l l } \hline $\ell$ & \multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\ & standard & adaptive & standard & adaptive \\ \hline 6 & 64 & 17 & 0.1390 & 0.1431 \\ 8 & 256 & 34 & 0.0670 & 0.0765 \\ 12 & 4096 & 151 & 0.0210 & 0.0258 \\ 16 & 65536 & 679 & 0.0064 & 0.0073 \\ 20 & $2^{20}$ & 2831 & - & 0.0021 \\ \hline \end{tabular} \end{table} In Fig.~\ref{fig:log} we illustrate the fact that the size of the boxes is much smaller for those which are close to zero or one. Indeed, this is what we expect since the density has singularities in these points. \begin{figure*} \vbox{\hbox to\textwidth{\psfig{figure=cvs21.f1a,width=6cm}\hspace{5mm} \psfig{figure=cvs21.f1b,width=6cm}\hfill \parbox[b]{50mm}{% \caption[]{Illustration of the relation between the density and the actual box refinement produced by the adaptive subdivision algorithm for $\ell =10$: {\bf a} the density $h_1$; {\bf b} the radii versus the midpoints of boxes}\vspace{2mm}}}} \label{fig:log} \end{figure*} \item[{\it 2.}] We consider the map $f_2:[0,1]\to [0,1]$, \renewcommand{\arraystretch}{2.1} \[ f_2(x)=\left\{ \begin{array}{ll} \displaystyle{2x\over 1-x^2} & \mbox{for}\quad 0\le x< \sqrt{2}-1, \\ \displaystyle{1-x^2\over 2x} & \mbox{for}\quad \sqrt{2}-1 \le x \le 1. \end{array} \right. \] \renewcommand{\arraystretch}{1.0} Its invariant density is \[ h_2(x)= {4\over \pi (1+x^2)}\; , \] see Fig.\,\ref{fig:tent}. \begin{figure*} \vbox{\hbox to\textwidth{\psfig{figure=cvs21.f2a,width=6cm}\hspace{5mm}% \psfig{figure=cvs21.f2b,width=6cm}\hfill \parbox[b]{50mm}{% \caption[]{{\bf a} The map $f_2$; and {\bf b} its invariant density $h_2$}\vspace{1mm}}}} \label{fig:tent} \end{figure*} In Table \ref{tab:tent} we present the numerical results for this case. As expected the application of the adaptive subdivision algorithm is not more efficient than the standard one since the invariant measure is quite close to Lebesgue measure. \begin{table} \caption[]{Comparison of the numerical results for $f_2$ ($\ell$ as in Table~1)} \label{tab:tent} \begin{tabular}{ l l l l l } \hline $\ell$ & \multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\ & standard & adaptive & standard & adaptive \\ \hline 6 & 64 & 45 & 0.0027 & 0.0053 \\ 8 & 256 & 187 & $6.5\cdot 10^{-4}$ & 0.0013 \\ 10 & 1024 & 759 & $1.7\cdot 10^{-4}$ & $3.2\cdot 10^{-4}$ \\ 12 & 4096 & 3047 & $4.6\cdot 10^{-5}$ & $7.8\cdot 10^{-5}$ \\ \hline \end{tabular} \end{table} \item[{\it 3.}] Finally we consider the map $f_3:[0,1]\to [0,1]$, \[ f_3(x) = \left({1\over 8} -2 \left|x-{1\over 2}\right|^3\right)^{1\over 3} + {1\over 2}, \] with the invariant density \[ h_3(x) = 12\left(x-{1\over 2}\right)^2. \] The graphs of $f_3$ and $h_3$ are shown in Fig.\,\ref{fig:stahl}. \begin{figure*} \vbox{\hbox to\textwidth{\psfig{figure=cvs21.f3a,width=6cm}\hspace{5mm}% \psfig{figure=cvs21.f3b,width=6cm}\hfill \parbox[b]{50mm}{% \caption[]{{\bf a} The map $f_3$; and {\bf b} its invariant density $h_3$}\vspace{2mm}}}} \label{fig:stahl} \end{figure*} \begin{figure*} \vbox{\hbox to\textwidth{\psfig{figure=cvs21.f4a,height=5.3cm}\hspace{5mm}% \psfig{figure=cvs21.f4b,height=5.3cm}\hfill}} \caption[]{{\bf a} A tiling of the square $[-2,2]^2$ obtained by the adaptive subdivision algorithm; and {\bf b} the subcollection $\tilde{\cB}$ of boxes with discrete density bigger than $0.35$ (see also \protect\Ref{eq:dm})} \label{fig:henon} \end{figure*} We now discuss the numerical results presented in Table~\ref{tab:stahl}. Note that the derivative of $f_3$ has singularities at two points inside $[0,1]$. This is the reason why several boxes get lost in the realization of the selection step in the standard subdivision algorithm. Consequently the computation of the invariant measure does not lead to satisfying results. In contrast to this no boxes are lost in the application of the adaptive subdivision technique, and accordingly the $L^1$-error is decreasing with an increasing number of subdivision steps. \begin{table} \caption[]{Comparison of the numerical results for $f_3$ ($\ell$ as in Table~1)} \label{tab:stahl} \begin{tabular}{ l l l l l } \hline $\ell$ & \multicolumn{2}{c}{number of boxes} & \multicolumn{2}{c}{$L^1$-error} \\ & standard & adaptive & standard & adaptive \\ \hline 6 & 63 & 11 & 0.0260 & 0.2931 \\ 8 & 249 & 30 & 0.0105 & 0.2583 \\ 10 & 993 & 189 & 0.0110 & 0.0435 \\ 12 & 3967 & 816 & 0.0133 & 0.0065 \\ \hline \end{tabular} \end{table} \end{itemize} \subsection*{The H\'enon map} \label{subsec:henon} % We apply the adaptive subdivision algorithm to a two-di\-men\-sio\-nal example, namely a scaled version of the well known {\em H\'enon map} \[ f:\R^2\to \R^2,\quad f(x,y) = (1-ax^2+y/5,\; 5bx). \] In the computations we have fixed the parameters by $a=1.2$, $b=0.2$, and we have chosen $\cB_0=\{[-2,2]^2\}$. In Fig.\,\ref{fig:henon} we present a tiling of the square $[-2,2]^2$ obtained by the adaptive subdivision algorithm after several subdivision steps. The resulting box-collection $\cB$ consists of the grey boxes shown in part (a) of this figure. We expect that due to the numerical approximation some boxes have positive {\em discrete\/} measure although they do not intersect the support of the {\em real\/} natural invariant measure. Having this in mind we neglect those boxes with very small discrete measure and show in Fig.\,\ref{fig:henon}b a subcollection $\tilde\cB\subset\cB$ with the property that \begin{equation} \label{eq:dm} \sum_{B\in\tilde\cB} u(B) \approx 0.99 \end{equation} (see also Remark~\ref{rmk:real}(c)). \begin{figure} \vbox{\hbox to\textwidth{\psfig{figure=cvs21.f5,width=8.6cm}\hfill}} \caption[]{Illustration of the (natural) invariant measure for the H\'enon map. The picture shows the density of the discrete measure on $\tilde\cB$, see \protect\Ref{eq:dm}} \label{fig:hen2} \end{figure} \begin{remark} For our choice of the parameter values we cannot explicitly write down a natural invariant measure. Hence it is impossible to compare our numerical results using analytical ones. Moreover, it is not even known for an arbitrary choice of the parameter values whether or not the H\'enon map possesses an SBR-measure. However, recently it was proved by M.\ Benedicks and L.-S.\ Young that the H\'enon map indeed has an SBR-measure for a ``large'' set of parameter values, see \cite{BenYoung}. \end{remark} Finally we apply the numerical techniques described in \cite{DJ:96} to determine the essential dynamical behavior of the H\'enon map for this choice of parameter values. An approximation of the (natural) invariant measure obtained by the adaptive subdivision algorithm is shown in Fig.\,\ref{fig:hen2}. This computation is based on the total number of 1514 boxes inside the square $[-2,2]^2$, whereas the support of the invariant measure is covered by 1442 boxes. The results indicate that the H\'enon map exhibits complicated dynamical behavior. Moreover it can be shown that the areas where the density is colored red resp.\ blue are permuted cyclically by the mapping. Hence altogether we may conclude that for these parameter values the H\'enon map exhibits a two-cycle (the ``macro-dynamics'') in addition to unpredictable (chaotic) behavior. This fact is also demonstrated by a {\sf Java}-animation for which a link can be found on the homepages of the authors. \thisbottomragged \begin{thebibliography}{10.} \bibitem{BenYoung} M.\ Benedicks, L.-S.\ Young. Sinai-\protect{Bowen}-\protect{Ruelle} measures for certain \protect{Henon} maps. {Invent.\ math.}, {\bf 112}:541--576, 1993 \bibitem{DH2} M.\ Dellnitz, A.\ Hohmann. The computation of unstable manifolds using subdivision and continuation. In H.W. Broer, S.A. van Gils, I.~Hoveijn, F.~Takens (eds), {Nonlinear Dynamical Systems and Chaos}, pages 449--459. Birkh\"auser, {PNLDE} {\bf 19}, 1996 \bibitem{DH1} M.\ Dellnitz, A.\ Hohmann. A subdivision algorithm for the computation of unstable manifolds and global attractors. {Numerische Mathematik}, {\bf 75}:293--317, 1997 \bibitem{DJ:96} M.\ Dellnitz, O.\ Junge. On the approximation of complicated dynamical behavior. To appear in SIAM J. on Numerical Analysis, 1998 \bibitem{DJchua:97} M.\ Dellnitz, O.\ Junge. Almost invariant sets in \protect{Chua's} circuit. To appear in {Int.\ J.\ Bif.\ and Chaos}, 1997 \bibitem{DingDuLi:93} J.~Ding, Q.~Du,, T.~Y. Li. High order approximation of the {Frobenius}-{Perron} operator. {Appl.\ Math.\ Comp.}, {\bf 53}:151--171, 1993 \bibitem{Eiden} M.\ Eidenschink. {Exploring Global Dynamics: A Numerical Algorithm Based on the Conley Index Theory}. PhD Thesis, Georgia Institute of Technology, 1995 \newpage \bibitem{GDK} R.\ Guder, M.\ Dellnitz,, E.\ Kreuzer. An adaptive method for the approximation of the generalized cell mapping. {Chaos, Solitons and Fractals}, {\bf 8}(4):525--534, 1997 \bibitem{Kifer:86} Yu.\ Kifer. General random perturbations of hyperbolic and expanding transformations. {J.\ Analyse Math.}, {\bf 47}:111--150, 1986 \bibitem{Lasota:94} A.\ Lasota, M.C.\ Mackey. {Chaos, Fractals and Noise}. Springer, 1994 \end{thebibliography} \end{document}