Computing the invariant measure and the Lyapunov exponent for one-dimensional maps using a measure-preserving polynomial basis

Aston, Philip; Junge, Oliver

doi:10.1090/S0025-5718-2013-02811-6

Computing the invariant measure and the Lyapunov exponent for one-dimensional maps using a measure-preserving polynomial basis
HTML articles powered by AMS MathViewer

by Philip J. Aston and Oliver Junge PDF

Math. Comp. 83 (2014), 1869-1902 Request permission

Abstract:

We consider a generalisation of Ulam’s method for approximating invariant densities of one-dimensional maps. Rather than use piecewise constant polynomials to approximate the density, we use polynomials of degree $n$ which are defined by the requirement that they preserve the measure on $n+1$ neighbouring subintervals. Over the whole interval, this results in a discontinuous piecewise polynomial approximation to the density. We prove error results where this approach is used to approximate smooth densities. We also consider the computation of the Lyapunov exponent using the polynomial density and show that the order of convergence is one order better than for the density itself. Together with using cubic polynomials in the density approximation, this yields a very efficient method for computing highly accurate estimates of the Lyapunov exponent. We illustrate the theoretical findings with some examples.

References

Vítor Araújo, Stefano Luzzatto, and Marcelo Viana, Invariant measures for interval maps with critical points and singularities, Adv. Math. 221 (2009), no. 5, 1428–1444. MR 2522425, DOI 10.1016/j.aim.2009.03.004
Philip J. Aston and Michael Dellnitz, The computation of Lyapunov exponents via spatial integration with application to blowout bifurcations, Comput. Methods Appl. Mech. Engrg. 170 (1999), no. 3-4, 223–237. Computational methods and bifurcation theory with applications. MR 1678618, DOI 10.1016/S0045-7825(98)00196-0
E. Borel, Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo, 27 (1909), 247–271. DOI 10.1002/BF0301965.
Christopher Bose and Rua Murray, The exact rate of approximation in Ulam’s method, Discrete Contin. Dynam. Systems 7 (2001), no. 1, 219–235. MR 1806382, DOI 10.3934/dcds.2001.7.219
Henk Bruin, Stefano Luzzatto, and Sebastian Van Strien, Decay of correlations in one-dimensional dynamics, Ann. Sci. École Norm. Sup. (4) 36 (2003), no. 4, 621–646 (English, with English and French summaries). MR 2013929, DOI 10.1016/S0012-9593(03)00025-9
H. Bruin, J. Rivera-Letelier, W. Shen, and S. van Strien, Large derivatives, backward contraction and invariant densities for interval maps, Invent. Math. 172 (2008), no. 3, 509–533. MR 2393079, DOI 10.1007/s00222-007-0108-4
R. L. Burden and J. D. Faires. Numerical Analysis, 9th edition. Brooks Cole, 2010.
C. Chiu, Q. Du, and T. Y. Li, Error estimates of the Markov finite approximation of the Frobenius-Perron operator, Nonlinear Anal. 19 (1992), no. 4, 291–308. MR 1178404, DOI 10.1016/0362-546X(92)90175-E
Geon Ho Choe, Computational ergodic theory, Algorithms and Computation in Mathematics, vol. 13, Springer-Verlag, Berlin, 2005. MR 2130385
Michael Dellnitz, Gary Froyland, and Stefan Sertl, On the isolated spectrum of the Perron-Frobenius operator, Nonlinearity 13 (2000), no. 4, 1171–1188. MR 1767953, DOI 10.1088/0951-7715/13/4/310
Michael Dellnitz, Andreas Hohmann, Oliver Junge, and Martin Rumpf, Exploring invariant sets and invariant measures, Chaos 7 (1997), no. 2, 221–228. MR 1477552, DOI 10.1063/1.166223
M. Dellnitz and O. Junge. An adaptive subdivision technique for the approximation of attractors and invariant measures. Comput. Vis. Sci., 1 (1998), no. 2, 63–68.
Michael Dellnitz and Oliver Junge, On the approximation of complicated dynamical behavior, SIAM J. Numer. Anal. 36 (1999), no. 2, 491–515. MR 1668207, DOI 10.1137/S0036142996313002
Michael Dellnitz, Oliver Junge, Wang Sang Koon, Francois Lekien, Martin W. Lo, Jerrold E. Marsden, Kathrin Padberg, Robert Preis, Shane D. Ross, and Bianca Thiere, Transport in dynamical astronomy and multibody problems, Internat. J. Bifur. Chaos Appl. Sci. Engrg. 15 (2005), no. 3, 699–727. MR 2136742, DOI 10.1142/S0218127405012545
Peter Deuflhard, Jan Hermans, Benedict Leimkuhler, Alan E. Mark, Sebastian Reich, and Robert D. Skeel (eds.), Computational molecular dynamics: challenges, methods, ideas, Lecture Notes in Computational Science and Engineering, vol. 4, Springer-Verlag, Berlin, 1999. MR 1722497, DOI 10.1007/978-3-642-58360-5
Peter Deuflhard and Marcus Weber, Robust Perron cluster analysis in conformation dynamics, Linear Algebra Appl. 398 (2005), 161–184. MR 2121349, DOI 10.1016/j.laa.2004.10.026
J. Ding, Q. Du, and T. Y. Li, High order approximation of the Frobenius-Perron operator, Appl. Math. Comput. 53 (1993), no. 2-3, 151–171. MR 1200085, DOI 10.1016/0096-3003(93)90099-Z
J. Ding, Q. Du, and T. Y. Li, The spectral analysis of Frobenius-Perron operators, J. Math. Anal. Appl. 184 (1994), no. 2, 285–301. MR 1278389, DOI 10.1006/jmaa.1994.1200
Jiu Ding, Congming Jin, and Aihui Zhou, A posteriori error estimates for Markov approximations of Frobenius-Perron operators, Nonlinear Anal. 67 (2007), no. 3, 763–772. MR 2319207, DOI 10.1016/j.na.2006.06.028
Jiu Ding and Tien-Yien Li, Markov finite approximation of Frobenius-Perron operator, Nonlinear Anal. 17 (1991), no. 8, 759–772. MR 1131018, DOI 10.1016/0362-546X(91)90211-I
Jiu Ding and Tien Yien Li, A convergence rate analysis for Markov finite approximations to a class of Frobenius-Perron operators, Nonlinear Anal. 31 (1998), no. 5-6, 765–777. MR 1487860, DOI 10.1016/S0362-546X(97)00438-0
Jiu Ding, Tien Yien Li, and Aihui Zhou, Finite approximations of Markov operators, J. Comput. Appl. Math. 147 (2002), no. 1, 137–152. MR 1931773, DOI 10.1016/S0377-0427(02)00429-6
J. Ding and N. H. Rhee, Approximations of Frobenius-Perron operators via interpolation, Nonlinear Anal. 57 (2004), no. 5-6, 831–842. MR 2067736, DOI 10.1016/j.na.2004.03.020
Jiu Ding and Aihui Zhou, Finite approximations of Frobenius-Perron operators. A solution of Ulam’s conjecture to multi-dimensional transformations, Phys. D 92 (1996), no. 1-2, 61–68. MR 1384679, DOI 10.1016/0167-2789(95)00292-8
Jiu Ding and Aihui Zhou, A finite element method for the Frobenius-Perron operator equation, Appl. Math. Comput. 102 (1999), no. 2-3, 155–164. MR 1688833, DOI 10.1016/S0096-3003(98)10039-5
Jiu Ding and Aihui Zhou, Structure preserving finite element approximations of Markov operators, Nonlinearity 15 (2002), no. 3, 923–936. MR 1901114, DOI 10.1088/0951-7715/15/3/324
Gary Froyland, Finite approximation of Sinai-Bowen-Ruelle measures for Anosov systems in two dimensions, Random Comput. Dynam. 3 (1995), no. 4, 251–263. MR 1362773
Gary Froyland, Estimating physical invariant measures and space averages of dynamical systems indicators, Bull. Austral. Math. Soc. 56 (1997), no. 1, 157–159. (Thesis summary). MR 1464058, DOI 10.1017/S0004972700030823
Gary Froyland, Approximating physical invariant measures of mixing dynamical systems in higher dimensions, Nonlinear Anal. 32 (1998), no. 7, 831–860. MR 1618409, DOI 10.1016/S0362-546X(97)00527-0
Gary Froyland, Ulam’s method for random interval maps, Nonlinearity 12 (1999), no. 4, 1029–1052. MR 1709869, DOI 10.1088/0951-7715/12/4/318
G. Froyland, K. Padberg, M. England, and A. Treguier, Detection of coherent oceanic structures via transfer operators, Phys. Rev. Lett., 98, 224503, 2007.
Gary Froyland, Naratip Santitissadeekorn, and Adam Monahan, Transport in time-dependent dynamical systems: finite-time coherent sets, Chaos 20 (2010), no. 4, 043116, 10. MR 2791360, DOI 10.1063/1.3502450
Rabbijah Guder, Michael Dellnitz, and Edwin Kreuzer, An adaptive method for the approximation of the generalized cell mapping, Chaos Solitons Fractals 8 (1997), no. 4, 525–534. MR 1450216, DOI 10.1016/S0960-0779(96)00118-X
Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2002. Structure-preserving algorithms for ordinary differential equations. MR 1904823, DOI 10.1007/978-3-662-05018-7
Michael-Robert Herman, Sur la conjugaison différentiable des difféomorphismes du cercle à des rotations, Inst. Hautes Études Sci. Publ. Math. 49 (1979), 5–233 (French). MR 538680, DOI 10.1007/BF02684798
F. Y. Hunt, A Monte Carlo approach to the approximation of invariant measures, Random Comput. Dynam. 2 (1994), no. 1, 111–133. MR 1265229
Fern Y. Hunt, Approximating the invariant measures of randomly perturbed dissipative maps, J. Math. Anal. Appl. 198 (1996), no. 2, 534–551. MR 1376279, DOI 10.1006/jmaa.1996.0097
Fern Y. Hunt, Unique ergodicity and the approximation of attractors and their invariant measures using Ulam’s method, Nonlinearity 11 (1998), no. 2, 307–317. MR 1610768, DOI 10.1088/0951-7715/11/2/007
Fern Y. Hunt and Walter M. Miller, On the approximation of invariant measures, J. Statist. Phys. 66 (1992), no. 1-2, 535–548. MR 1149495, DOI 10.1007/BF01060079
Oliver Junge, An adaptive subdivision technique for the approximation of attractors and invariant measures: proof of convergence, Dyn. Syst. 16 (2001), no. 3, 213–222. MR 1851062, DOI 10.1080/14689360110060708
Oliver Junge and Péter Koltai, Discretization of the Frobenius-Perron operator using a sparse Haar tensor basis: the sparse Ulam method, SIAM J. Numer. Anal. 47 (2009), no. 5, 3464–3485. MR 2576507, DOI 10.1137/080716864
Jonathan L. King, Three problems in search of a measure, Amer. Math. Monthly 101 (1994), no. 7, 609–628. MR 1289271, DOI 10.2307/2974690
A. Lasota and James A. Yorke, On the existence of invariant measures for piecewise monotonic transformations, Trans. Amer. Math. Soc. 186 (1973), 481–488 (1974). MR 335758, DOI 10.1090/S0002-9947-1973-0335758-1
A. Lasota, and P. Rusek, Stability of self-induced vibrations in metal cutting. Proc. the Fifth World Congress on the Theory of Machines and Mechanisms, Montreal, 1979.
T. Y. Li, Finite approximation for the Frobenius-Perron operator. A solution to Ulam’s conjecture, J. Approximation Theory 17 (1976), no. 2, 177–186. MR 412689, DOI 10.1016/0021-9045(76)90037-x
MichałMisiurewicz and Ana Rodrigues, Double standard maps, Comm. Math. Phys. 273 (2007), no. 1, 37–65. MR 2308749, DOI 10.1007/s00220-007-0223-5
R. Murray. Discrete approximation of invariant densities. PhD thesis, University of Cambridge, 1997.
Nils Nicolaisen and Bodo Werner, Discretization of circle maps, Z. Angew. Math. Phys. 49 (1998), no. 6, 869–895. MR 1664719, DOI 10.1007/s000330050127
A. Ralston, On differentiating error terms, Amer. Math. Monthly 70 (1963), 187–189. MR 157162, DOI 10.2307/2312891
Anthony Ralston and Philip Rabinowitz, A first course in numerical analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Auckland-Bogotá, 1978. MR 0494814
Ch. Schütte, A. Fischer, W. Huisinga, and P. Deuflhard, A direct approach to conformational dynamics based on hybrid Monte Carlo, J. Comput. Phys. 151 (1999), no. 1, 146–168. Computational molecular biophysics. MR 1701575, DOI 10.1006/jcph.1999.6231
J. F. Steffensen, Interpolation, Chelsea Publishing Co., New York, N. Y., 1950. 2d ed. MR 0036799
S. M. Ulam, A collection of mathematical problems, Interscience Tracts in Pure and Applied Mathematics, no. 8, Interscience Publishers, New York-London, 1960. MR 0120127
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422