Abstract
In a given dynamical system there are essentially two different types of information which could be of practical interest: on the one hand there is the need to describe the behavior of single trajectories in detail. This information is helpful for the analysis of transient behavior and also in the investigation of geometric properties of dynamical systems. On the other hand, if the underlying invariant set is generated by complicated dynamics then the computation of single trajectories may give misleading results. In this case there still exists important set related information covering both topological and statistical aspects of the underlying dynamical behavior. Within the DFG-Schwerpunkt we have focussed on the development of set oriented methods for the numerical approximation of
-
invariant sets (e.g. invariant manifolds, global attractors, chain recurrent sets)
-
(natural) invariant measures
-
almost invariant sets
The basic concept is a subdivision algorithm which is similar in spirit to the well known cell mapping techniques but with the crucial difference that the numerical effort mainly depends on the complexity of the dynamics rather than on the dimension of the underlying state space. First, the invariant set is covered by boxes and then the dynamical behavior on the set is approximated by a Markov chain based on transition probabilities between elements of this covering. The algorithms have been implemented in the software package GAIO (Global Analysis of Invariant Objects), and in this article we describe both the related numerical techniques together with their theoretical foundations and how to use them within GAIO. We will also discuss details concerning the implementation such as adaptive versions of the methods.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Dellnitz, G. Froyland, and S. Serti. On the isolated spectrum of the Perron-Frobenius operator. Nonlinearity, 13(4):1171–1188, 2000.
M. Dellnitz, M. Golubitsky, and M. Nicol. Symmetry of attractors and the Karhunen-Loéve decomposition, pages 73108. Number 100 in Applied Mathematical Sciences. Springer-Verlag, 1994.
M. Dellnitz and A. Hohmann. The computation of unstable manifolds using subdivision and continuation. In H.W. Broer, S.A. van Gils, I. Hoveijn, and F. Takens, editors, Nonlinear Dynamical Systems and Chaos, pages 449–459. Birkhäuser, PNLDE 19, 1996.
M. Dellnitz and A. Hohmann. A subdivision algorithm for the computation of unstable manifolds and global attractors. Numerische Mathematik, 75:293–317, 1997.
M. Dellnitz, A. Hohmann, O. Junge, and M. Rumpf. Exploring invariant sets and invariant measures. CHAOS: An Interdisciplinary Journal of Nonlinear Science, 7(2):221, 1997.
M. Dellnitz and O. Junge. On the approximation of complicated dynamical behavior. SIAM J. Numer. Anal., 36(2):491–515, 1999.
M. Dellnitz, O. Junge, M. Rumpf, and R. Strzodka. The computation of an unstable invariant set inside a cylinder containing a knotted flow. In Proceedings of Equadiff ′99, Berlin, 2000.
P. Deuflhard, M. Dellnitz, O. Junge, and Ch. Schütte. Computation of essential molecular dynamics by subdivision techniques, pages 98–115. Number 4 in Lecture Notes in Computational Science and Engineering. Springer-Verlag, 1998.
J. Ding and A. Zhou. Finite approximations of Frobenius-Perron operators. A solution of Ulam’s conjecture to multi-dimensional transformations. Physica D, 92(1-2):61–68, 1996.
R.W. Easton. Geometric Methods for Discrete Dynamical Systems. Number 50 in Oxford engineering science. Oxford University Press, New York, 1998.
M. Eidenschink. Exploring Global Dynamics: A Numerical Algorithm Based on the Conley Index Theory. PhD thesis, Georgia Institute of Technology, 1995.
Euclid. Elements. Book X, (first Proposition).
G. Froyland. Finite approximation of Sinai-Bowen-Ruelle measures of Anosov systems in two dimensions. Random & Computational Dynamics, 3(4):251–264, 1995.
G. Froyland. Approximating physical invariant measures of mixing dynamical systems in higher dimensions. Nonlinear Analysis, Theory, Methods, & Appl.ications, 32(7):831–860, 1998.
G. Froyland and M. Dellnitz. Detecting and locating near-optimal almostinvariant sets and cycles. In preparation.
R. Guder, M. Dellnitz, and E. Kreuzer. An adaptive method for the approximation of the generalized cell mapping. Chaos, Solitons and Fractals, 8(4):525–534, 1997.
R. Guder and E. Kreuzer. Control of an adaptive refinement technique of generalized cell mapping by system dynamics. J. Nonl. Dyn., 20(1):21–32, 1999.
O. Junge. Mengenorientierte Methoden zur numerischen Analyse dynamischer Systeme. PhD thesis, University of Paderborn, 1999.
O. Junge. Rigorous discretization of subdivision techniques. In Proceedings of Equadiff ′99, Berlin, 2000.
G. Keller and C. Liverani. Stability of the spectrum for transfer operators. Preprint, 1998.
H. Keller and G. Ochs. Numerical approximation of random attractors. In Stochastic dynamics, pages 93–115. Springer, 1999.
R.Z. Khas’minskii. Principle of averaging for parabolic and elliptic differential equations and for Markov processes with small diffusion. Theory of Probability and its Applications, 8(1):1–21, 1963.
Y. Kifer. Random Perturbations of Dynamical Systems, volume 16 of Progress in Probability and Statistics. Birkhäuser, Boston, 1988.
A. Lasota and M.C. Mackey. Chaos, Fractals, and Noise. Stochastic Aspects of Dynamics, volume 97 of Applied Mathematical Sciences. Springer-Verlag, New York, second edition, 1994.
T.-Y. Li. Finite approximation for the Frobenius-Perron operator. A solution to Ulam’s conjecture. Journal of Approximation Theory, 17:177–186, 1976.
K. Mehlhorn. Data Structures and Algorithms. Springer, 1984.
G. Osipenko. Construction of attractors and filtrations. In K. Mischaikow, M. Mrozek, and P. Zgliczynski, editors, Conley Index Theory, pages 173–191. Banach Center Publications 47, 1999.
C. Robinson. Dynamical Systems: Stability, Symbolic Dynamics, and Chaos. CRC, Boca Raton, 1995.
M. Rumpf and A. Wierse. GRAPE, eine objektorientierte Visualisierungs-und Numerikplattform. Informatik, Forschung und Entwicklung, 7:145–151, 1992.
Ch. Schütte. Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules. Habilitation thesis, Freie Universität Berlin, 1999.
E.C. Zeeman. Stability of dynamical systems. Nonlinearity, 1:115–155, 1988.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dellnitz, M., Froyland, G., Junge, O. (2001). The Algorithms Behind GAIO — Set Oriented Numerical Methods for Dynamical Systems. In: Fiedler, B. (eds) Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-56589-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-56589-2_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-62524-4
Online ISBN: 978-3-642-56589-2
eBook Packages: Springer Book Archive