American Institute of Mathematical Sciences

Advanced
January  2001, 7(1): 219-235. doi: 10.3934/dcds.2001.7.219

The exact rate of approximation in Ulam's method

Christopher Bose 1, and  Rua Murray 2,

1. 

Department of Mathematics and Statistics, University of Victoria, P.O. Box 3045, Victoria, BC, Canada V8W 3P4, Canada
2. 

Department of Mathematics, University of Waikato, Private Bag 3105, Hamilton, New Zealand

Received  July 2000 Revised  November 2000 Published  November 2000

This paper investigates the exact rate of convergence in Ulam's method: a well-known discretization scheme for approximating the invariant density of an absolutely continuous invariant probability measure for piecewise expanding interval maps. It is shown by example that the rate is no better than $O(\frac{\log n}{n})$, where $n$ is the number of cells in the discretization. The result is in agreement with upper estimates previously established in a number of general settings, and shows that the conjectured rate of $O(\frac{1}{n})$ cannot be obtained, even for extremely regular maps.
Keywords: $L^1$ Error Bounds., Perron-Frobenius Operator, Interval Maps, Approximation of Absolutely Continuous Invariant Measures.
Mathematics Subject Classification: 28D05, 41A25, 41A4.
Citation: Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219
[1]

Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003
[2]

Martin Lustig, Caglar Uyanik. Perron-Frobenius theory and frequency convergence for reducible substitutions. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 355-385. doi: 10.3934/dcds.2017015
[3]

Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457
[4]

Marianne Akian, Stéphane Gaubert, Antoine Hochart. A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors. Discrete & Continuous Dynamical Systems, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009
[5]

Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002
[6]

Simon Lloyd, Edson Vargas. Critical covering maps without absolutely continuous invariant probability measure. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2393-2412. doi: 10.3934/dcds.2019101
[7]

Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007
[8]

Jiu Ding, Aihui Zhou. Absolutely continuous invariant measures for piecewise $C^2$ and expanding mappings in higher dimensions. Discrete & Continuous Dynamical Systems, 2000, 6 (2) : 451-458. doi: 10.3934/dcds.2000.6.451
[9]

Jawad Al-Khal, Henk Bruin, Michael Jakobson. New examples of S-unimodal maps with a sigma-finite absolutely continuous invariant measure. Discrete & Continuous Dynamical Systems, 2008, 22 (1&2) : 35-61. doi: 10.3934/dcds.2008.22.35
[10]

Lucia D. Simonelli. Absolutely continuous spectrum for parabolic flows/maps. Discrete & Continuous Dynamical Systems, 2018, 38 (1) : 263-292. doi: 10.3934/dcds.2018013
[11]

Rua Murray. Approximation error for invariant density calculations. Discrete & Continuous Dynamical Systems, 1998, 4 (3) : 535-557. doi: 10.3934/dcds.1998.4.535
[12]

Arno Berger, Roland Zweimüller. Invariant measures for general induced maps and towers. Discrete & Continuous Dynamical Systems, 2013, 33 (9) : 3885-3901. doi: 10.3934/dcds.2013.33.3885
[13]

Xavier Bressaud. Expanding interval maps with intermittent behaviour, physical measures and time scales. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 517-546. doi: 10.3934/dcds.2004.11.517
[14]

Adrian Tudorascu. On absolutely continuous curves of probabilities on the line. Discrete & Continuous Dynamical Systems, 2019, 39 (9) : 5105-5124. doi: 10.3934/dcds.2019207
[15]

Leandro Cioletti, Artur O. Lopes, Manuel Stadlbauer. Ruelle operator for continuous potentials and DLR-Gibbs measures. Discrete & Continuous Dynamical Systems, 2020, 40 (8) : 4625-4652. doi: 10.3934/dcds.2020195
[16]

Christoph Bandt, Helena PeÑa. Polynomial approximation of self-similar measures and the spectrum of the transfer operator. Discrete & Continuous Dynamical Systems, 2017, 37 (9) : 4611-4623. doi: 10.3934/dcds.2017198
[17]

Fawwaz Batayneh, Cecilia González-Tokman. On the number of invariant measures for random expanding maps in higher dimensions. Discrete & Continuous Dynamical Systems, 2021, 41 (12) : 5887-5914. doi: 10.3934/dcds.2021100
[18]

Tatsuya Arai, Naotsugu Chinen. The construction of chaotic maps in the sense of Devaney on dendrites which commute to continuous maps on the unit interval. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 547-556. doi: 10.3934/dcds.2004.11.547
[19]

Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547
[20]

Chengxiang Wang, Li Zeng. Error bounds and stability in the $l_{0}$ regularized for CT reconstruction from small projections. Inverse Problems & Imaging, 2016, 10 (3) : 829-853. doi: 10.3934/ipi.2016023

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (134)
  • HTML views (0)
  • Cited by (26)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences