On the numerical approximation of the Perron-Frobenius and Koopman operator

Stefan  Klus; Péter Koltai; Christof  Schütte

doi:10.3934/jcd.2016003

Article Contents

2016, Volume 3, Issue 1: 51-79. Doi: 10.3934/jcd.2016003

This issue Previous Article Towards a formal tie between combinatorial and classical vector field dynamics Next Article Rigorous enclosures of rotation numbers by interval methods

On the numerical approximation of the Perron-Frobenius and Koopman operator

1.
Department of Mathematics and Computer Science, Freie Universität Berlin
2.
Freie Universität Berlin, Department of Mathematics and Computer Science, Arnimallee 6, 14195 Berlin

Received: December 2015

Revised: July 2016

Published: January 2016

Abstract / Introduction Related Papers Cited by

Abstract

Information about the behavior of dynamical systems can often be obtained by analyzing the eigenvalues and corresponding eigenfunctions of linear operators associated with a dynamical system. Examples of such operators are the Perron-Frobenius and the Koopman operator. In this paper, we will review dierent methods that have been developed over the last decades to compute nite-dimensional approximations of these innite-dimensional operators - in particular Ulam's method and Extended Dynamic Mode Decomposition (EDMD) - and highlight the similarities and dierences between these approaches. The results will be illustrated using simple stochastic dierential equations and molecular dynamics examples.

Keywords:

Mathematics Subject Classification: Primary: 37M10, 37M25; Secondary: 34L16, 37L65, 37N25.

Citation:

Related Papers

Cited by

References

[1]	J. R. Baxter and J. S. Rosenthal, Rates of convergence for everywhere-positive Markov chains, Statistics & Probability Letters, 22 (1995), 333-338.doi: 10.1016/0167-7152(94)00085-M.
[2]	A. Bittracher, P. Koltai and O. Junge, Pseudogenerators of spatial transfer operators, SIAM Journal on Applied Dynamical Systems, 14 (2015), 1478-1517.doi: 10.1137/14099872X.
[3]	E. M. Bollt and N. Santitissadeekorn, Applied and Computational Measurable Dynamics, Society for Industrial and Applied Mathematics, 2013.doi: 10.1137/1.9781611972641.
[4]	C. J. Bose and R. Murray, The exact rate of approximation in Ulam's method, Discrete and Continuous Dynamical Systems, 7 (2001), 219-235.
[5]	C. J. Bose and R. Murray, Dynamical conditions for convergence of a maximum entropy method for Frobenius-Perron operator equations, Applied Mathematics and Computation, 182 (2006), 210-212.doi: 10.1016/j.amc.2006.01.089.
[6]	C. J. Bose and R. Murray, Minimum 'energy' approximations of invariant measures for nonsingular transformations, Discrete and Continuous Dynamical Systems, 14 (2006), 597-615.
[7]	C. J. Bose and R. Murray, Duality and the computation of approximate invariant densities for nonsingular transformations, SIAM Journal on Optimization, 18 (2007), 691-709.doi: 10.1137/060658163.
[8]	A. Boyarsky and P. Gora, Laws of Chaos: Invariant Measures and Dynamical Systems in One Dimension, Probability and its Applications. Birkhäuser Boston, Inc., Boston, MA, 1997.doi: 10.1007/978-1-4612-2024-4.
[9]	J. P. Boyd, Chebyshev and Fourier Spectral Methods, 2nd edition, Dover Publications, Inc., 2001.
[10]	M. Budišić, R. Mohr and I. Mezić, Applied Koopmanism, Chaos: An Interdisciplinary Journal of Nonlinear Science, 22.
[11]	H.-J. Bungartz and M. Griebel, Sparse grids, Acta Numerica, 13 (2004), 147-269.doi: 10.1017/S0962492904000182.
[12]	D. A. Case, J. T. Berryman, R. M. Betz, D. S. Cerutti, T. E. Cheatham, T. A. Darden, R. E. Duke, T. J. Giese, H. Gohlke, A. W. Goetz, N. Homeyer, S. Izadi, P. Janowski, J. Kaus, A. Kovalenko, T. S. Lee, S. LeGrand, P. Li, T. Luchko, R. Luo, B. Madej, K. M. Merz, G. Monard, P. Needham, H. Nguyen, H. T. Nguyen, I. Omelyan, A. Onufriev, D. R. Roe, A. Roitberg, R. Salomon-Ferrer, C. L. Simmerling, W. Smith, J. Swails, R. C. Walker, J. Wang, R. M. Wolf, X. Wu, D. M. York and P. A. Kollman, AMBER 2015, University of California, San Francisco, 2015.
[13]	M. D. Chekroun, J. D. Neelin, D. Kondrashov, J. C. McWilliams and M. Ghil, Rough parameter dependence in climate models and the role of Ruelle-Pollicott resonances, Proceedings of the National Academy of Sciences, 111 (2014), 1684-1690.doi: 10.1073/pnas.1321816111.
[14]	G. Chen and T. Ueta (eds.), Chaos in Circuits and Systems, World Scientific Series on Nonlinear Science, Series B, Volume 11, World Scientific, 2002.doi: 10.1142/9789812705303.
[15]	M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems, in Ergodic theory, analysis, and efficient simulation of dynamical systems, Springer, 2001, 145-174, 805-807.
[16]	M. Dellnitz and O. Junge, On the approximation of complicated dynamical behavior, SIAM Journal on Numerical Analysis, 36 (1999), 491-515.doi: 10.1137/S0036142996313002.
[17]	J. Ding, A maximum entropy method for solving Frobenius-Perron operator equations, Applied Mathematics and Computation, 93 (1998), 155-168.doi: 10.1016/S0096-3003(97)10061-3.
[18]	J. Ding, Q. Du and T.-Y. Li, High order approximation of the Frobenius-Perron operator, Applied Mathematics and Computation, 53 (1993), 151-171.doi: 10.1016/0096-3003(93)90099-Z.
[19]	J. Ding and T.-Y. Li, Markov finite approximation of the Frobenius-Perron operator, Nonlinear Analysis: Theory, Methods & Applications, 17 (1991), 759-772.doi: 10.1016/0362-546X(91)90211-I.
[20]	J. Ding and A. Zhou, Finite approximations of Frobenius-Perron operators. A solution of Ulam's conjucture on multi-dimensional transformations, Physica D, 92 (1996), 61-68.doi: 10.1016/0167-2789(95)00292-8.
[21]	H. Federer, Geometric Measure Theory, Springer New York, 1969.
[22]	G. Froyland, C. González-Tokman and T. M. Watson, Optimal mixing enhancement by local perturbation, Preprint.
[23]	G. Froyland, G. Gottwald and A. Hammerlindl, A computational method to extract macroscopic variables and their dynamics in multiscale systems, SIAM Journal on Applied Dynamical Systems, 13 (2014), 1816-1846.doi: 10.1137/130943637.
[24]	G. Froyland, R. M. Stuart and E. van Sebille, How well-connected is the surface of the global ocean?, Chaos: An Interdisciplinary Journal of Nonlinear Science, 24 (2014), 033126, 10pp.doi: 10.1063/1.4892530.
[25]	G. Froyland, Approximating physical invariant measures of mixing dynamical systems, Nonlinear Analysis, Theory, Methods, & Applications, 32 (1998), 831-860.doi: 10.1016/S0362-546X(97)00527-0.
[26]	G. Froyland and O. Junge, On fast computation of finite-time coherent sets using radial basis functions, Chaos, 25 (2015), 087409, 11 pp.doi: 10.1063/1.4927640.
[27]	G. Froyland, O. Junge and P. Koltai, Estimating long term behavior of flows without trajectory integration: The infinitesimal generator approach, SIAM Journal on Numerical Analysis, 51 (2013), 223-247.doi: 10.1137/110819986.
[28]	P. R. Halmos, Lectures on Ergodic Theory, vol. 142, American Mathematical Soc., 1956.
[29]	E. Hopf, The general temporally discrete Markoff process, Journal of Rational Mechanics and Analysis, 3 (1954), 13-45.
[30]	P. Huber, Dünngitter-Spektralmethoden zur Approximation des Frobenius-Perron-Operators, Diploma thesis (in German), Technische Universität München, 2009.
[31]	M. R. Jovanović, P. J. Schmid and J. W. Nichols, Sparsity-promoting dynamic mode decomposition, Physics of Fluids, 26.
[32]	O. Junge and P. Koltai, Discretization of the Frobenius-Perron operator using a sparse Haar tensor basis: The Sparse Ulam method, SIAM Journal on Numerical Analysis, 47 (2009), 3464-3485.doi: 10.1137/080716864.
[33]	P. Koltai, Efficient Approximation Methods for the Global Long-Term Behavior of Dynamical Systems - Theory, Algorithms and Examples, PhD thesis, Technische Universität München, 2010.
[34]	B. O. Koopman, Hamiltonian systems and transformation in Hilbert space, Proceedings of the National Academy of Sciences of the United States of America, 17 (1931), 315-318.doi: 10.1073/pnas.17.5.315.
[35]	U. Krengel, Ergodic Theorems, vol. 6 of de Gruyter Studies in Mathematics, Walter de Gruyter & Co., Berlin, 1985.doi: 10.1515/9783110844641.
[36]	A. Lasota and M. C. Mackey, Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics, vol. 97 of Applied Mathematical Sciences, 2nd edition, Springer, 1994.doi: 10.1007/978-1-4612-4286-4.
[37]	T.-Y. Li, Finite approximation for the Frobenius-Perron operator. A solution to Ulam's conjecture, Journal of Approximation Theory, 17 (1976), 177-186.doi: 10.1016/0021-9045(76)90037-X.
[38]	J. C. Mattingly and A. M. Stuart, Geometric ergodicity of some hypo-elliptic diffusions for particle motions, Markov Process. Related Fields, 8 (2002), 199-214.
[39]	S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, Springer Science & Business Media, 2012.
[40]	R. Murray, Discrete Approximation of Invariant Densities, PhD thesis, University of Cambridge, 1997.
[41]	R. Murray, Optimal partition choice for invariant measure approximation for one-dimensional maps, Nonlinearity, 17 (2004), 1623-1644.doi: 10.1088/0951-7715/17/5/004.
[42]	F. Noé and F. Nüske, A variational approach to modeling slow processes in stochastic dynamical systems, Multiscale Modeling & Simulation, 11 (2013), 635-655.doi: 10.1137/110858616.
[43]	F. Nüske, B. G. Keller, G. Pérez-Hernández, A. S. J. S. Mey and F. Noé, Variational approach to molecular kinetics, Journal of Chemical Theory and Computation, 10 (2014), 1739-1752.
[44]	F. Nüske, R. Schneider, F. Vitalini and F. Noé, Variational tensor approach for approximating the rare-event kinetics of macromolecular systems, The Journal of Chemical Physics, 144.
[45]	S. Ober-Blöbaum and K. Padberg-Gehle, Multiobjective optimal control of fluid mixing, PAMM, 15 (2015), 639-640.
[46]	D. Ornstein, Bernoulli shifts with the same entropy are isomorphic, Advances in Mathematics, 4 (1970), 337-352.doi: 10.1016/0001-8708(70)90029-0.
[47]	R. Preis, M. Dellnitz, M. Hessel, C. Schütte and E. Meerbach, Dominant Paths Between Almost Invariant Sets of Dynamical Systems, DFG Schwerpunktprogramm 1095, Technical Report 154, 2004.
[48]	P. Schmid and J. Sesterhenn, Dynamic mode decomposition of numerical and experimental data, in 61st Annual Meeting of the APS Division of Fluid Dynamics, American Physical Society, 2008.
[49]	Schrödinger, LLC, The PyMOL molecular graphics system, Version 1.7.4, 2014.
[50]	C. Schütte, Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules, 1999, Habilitation Thesis.
[51]	C. Schütte and M. Sarich, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches, no. 24 in Courant Lecture Notes, American Mathematical Society, 2013.
[52]	Y. G. Sinai, On the notion of entropy of dynamical systems, in Doklady Akademii Nauk, 124 (1959), 768-771.
[53]	A. Tantet, V. Lucarini, F. Lunkeit and H. A. Dijkstra, Crisis of the chaotic attractor of a climate model: A transfer operator approach, Preprint, arXiv:1507.02228.
[54]	A. Tantet, F. R. van der Burgt and H. A. Dijkstra, An early warning indicator for atmospheric blocking events using transfer operators, Chaos, 25 (2015), 036406.doi: 10.1063/1.4908174.
[55]	J. H. Tu, C. W. Rowley, D. M. Luchtenburg, S. L. Brunton and J. N. Kutz, On dynamic mode decomposition: Theory and applications, ArXiv e-prints.
[56]	S. M. Ulam, A Collection of Mathematical Problems, Interscience Publisher NY, 1960.
[57]	U. Vaidya, P. G. Mehta and U. V. Shanbhag, Nonlinear stabilization via control Lyapunov measure, IEEE Transactions on Automatic Control, 55 (2010), 1314-1328.doi: 10.1109/TAC.2010.2042226.
[58]	M. O. Williams, I. G. Kevrekidis and C. W. Rowley, A data-driven approximation of the Koopman operator: Extending dynamic mode decomposition, J. Nonlinear Sci., 25 (2015), 1307-1346.doi: 10.1007/s00332-015-9258-5.
[59]	M. O. Williams, C. W. Rowley and I. G. Kevrekidis, A kernel-based approach to data-driven Koopman spectral analysis, J. Comput. Dyn., 2 (2015), 247-265.doi: 10.3934/jcd.2015005.
[60]	M. O. Williams, I. I. Rypina and C. W. Rowley, Identifying finite-time coherent sets from limited quantities of Lagrangian data, Chaos, 25 (2015), 087408, 13pp.doi: 10.1063/1.4927424.