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

The exact rate of approximation in Ulam's method

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.
Citation: Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems - A, 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 - A, 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 - A, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009

[5]

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

[6]

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

[7]

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

[8]

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 - A, 2008, 22 (1&2) : 35-61. doi: 10.3934/dcds.2008.22.35

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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 - A, 2004, 11 (2&3) : 547-556. doi: 10.3934/dcds.2004.11.547

[16]

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

[17]

Paola Goatin, Philippe G. LeFloch. $L^1$ continuous dependence for the Euler equations of compressible fluids dynamics. Communications on Pure & Applied Analysis, 2003, 2 (1) : 107-137. doi: 10.3934/cpaa.2003.2.107

[18]

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

[19]

Jiu Ding, Noah H. Rhee. A unified maximum entropy method via spline functions for Frobenius-Perron operators. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 235-245. doi: 10.3934/naco.2013.3.235

[20]

Marc Kesseböhmer, Sabrina Kombrink. A complex Ruelle-Perron-Frobenius theorem for infinite Markov shifts with applications to renewal theory. Discrete & Continuous Dynamical Systems - S, 2017, 10 (2) : 335-352. doi: 10.3934/dcdss.2017016

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (27)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]