Ergodic theory is a mathematical subject that studies the statistical properties of deterministic dynamical systems. It is a combination of several branches of pure mathematics, such as measure theory, functional analysis, topology, and geometry, and it also has applications in a variety of fields in science and engineering, as a branch of applied mathematics. In the past decades, the ergodic theory of chaotic dynamical systems has found more and more applications in mathematics, physics, engineering, biology and various other fields. For example, its theory and methods have played a major role in such emerging interdisciplinary subjects as computational molecular dynamics, drug designs, and third generation wireless communications in the past decade.

Many problems in science and engineering are often reduced to studying the asymptotic behavior of discrete dynamical systems. We know that in neural networks, condensed matter physics, turbulence in flows, large scale laser arrays, convection-diffusion equations, coupled mapping lattices in phase transition, and molecular dynamics, the asymptotic property of the complicated dynamical system often exhibits chaotic phenomena and is unpredictable. However, if we study chaotic dynamical systems from the statistical point of view, we find that chaos in the deterministic sense usually possesses some kind of regularity in the probabilistic sense. In this textbook, which is written for the upper level undergraduate students and graduate students, we study chaos from the statistical point of view. From this viewpoint, we mainly investigate the evolution process of density functions governed by the underlying deterministic dynamical system.  For this purpose, we employ the concept of density functions in the study of the statistical properties of sequences of iterated measurable transformations. These statistical properties often depend on the existence and the properties of those probability measures which are absolutely continuous with respect to the Lebesgue measure and which are invariant under the transformation with respect to time. The existence of absolutely continuous invariant finite measures is equivalent to the existence of nontrivial fixed points of a class of stochastic operators (or Markov operators), called Frobenius-Perron operators by the great mathematician Stanislaw Ulam, who pioneered the exploration of nonlinear science, in his famous book "A Collection of Mathematical Problems" in 1960.

In this book, we mainly study two kinds of problems. The first is the existence of nontrivial fixed points of Frobenius-Perron operators, and the other concerns the computation of such fixed points. They can be viewed as the functional analysis and the numerical analysis of Frobenius-Perron operators, respectively. For the first problem, many excellent books have been written, such as "Probabilistic Properties of Deterministic Systems" and its extended second edition "Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics" by Lasota and Mackey, and "Law of Chaos: Invariant Measures and Dynamical Systems in One Dimension" by Boyarsky and Gora. For the second problem, this book might be among the first ones in the form of a textbook on the computational ergodic theory of discrete dynamical systems. One feature that distinguishes this book from the others is that our textbook combines strict mathematical analysis and efficient computational methods as a unified whole. This is the authors' attempt to reduce the gap between pure mathematical theory and practical physical, engineering, and biological applications.

The first famous papers on the existence of nontrivial fixed points of Frobenius-Perron operators include the proof (see, e.g., Theorem 6.8.1 of) of the existence of a unique smooth invariant measure for a second order continuously differentiable expanding transformation on a finite dimensional, compact, connected, smooth Riemann manifold by Krzyzewski and Szlenk in 1969, and the pioneering work on the existence of absolutely continuous invariant measures of piecewise second order differentiable and stretching interval mappings by Lasota and Yorke in 1973. The latter also answered a question posed by Ulam in his above mentioned book. In the same book, Ulam proposed a piecewise constant approximation method which became the first approach to the numerical analysis of Frobenius-Perron operators. A solution to Ulam's conjecture by Tien-Yien Li in 1976 is a fundamental work in the new area of computational ergodic theory}.

Our book has nine chapters. As an introduction, Chapter 1 leads the reader into a mathematical trip from order to chaos via the iteration of a one-parameter family of quadratic polynomials with the changing values of the parameter, from which the reader enters the new vision of "chaos from the statistical point of view." The fundamental mathematical knowledge used in the book -- basic measure theory and functional analysis-- constitutes the content of Chapter 2. In Chapter 3, we study the basic concepts and classic results in ergodic theory. The main linear operator studied in this book -- the Frobenius-Perron operator-- is introduced in Chapter 4, which also presents some general results that have not appeared in other books.  Chapter 5 is exclusively devoted to the investigation of the existence problem of absolutely continuous invariant measures, and we shall prove several existence results for various classes of one-dimensional mappings and multi-dimensional transformations. The computational problem is studied in Chapter 6, in which two numerical methods are given for the approximation of Frobenius-Perron operators. One is the classic Ulam's piecewise constant method, and the other is its improvement with higher order approximation accuracy; that is, the piecewise linear Markov method which was mainly developed by the authors. In Chapter 7, we present Keller's result on the stability of Markov operators and its application to the convergence rate analysis of Ulam's method under theL-norm and Murray's work for a more explicit upper bound of the error estimate. We also explore the convergence rate under the variation norm for the piecewise linear Markov method. Chapter 8 gives a simple mathematical description of the related concepts of entropy, in particular the Boltzmann entropy and its relationship with the iteration of Frobenius-Perron operators. Several modern applications of absolutely continuous invariant probability measures will be given in the last chapter.

This book can be used as a textbook for students of pure mathematics, applied mathematics, and computational mathematics as an introductory course on the ergodic theory of dynamical systems for the purpose of entering the related frontier of interdisciplinary areas. It can also be adopted as a textbook or a reference book for a specialized course for different areas of computational science, such as computational physics, computational chemistry, and computational biology. For students or researchers in engineering subjects such as electrical engineering, who want to study chaos and applied ergodic theory, this book can be used as a tool book. A good background of advanced calculus is sufficient to read and understand this book, except possibly for Section 2.4 on the modern definition of variation and Section 5.4 on the proof of the existence of multi-dimensional absolutely continuous invariant measures which may be omitted at the first reading. Some of the exercises at the end of each chapter complement the main text, so the reader should try to do as many as possible, or at least take a look and read appropriate references if possible. Each main topic of ergodic theory contains matter for huge books, but the purpose of this book is to introduce as many readers as possible with various backgrounds into fascinating new fields having great potential of ever increasing applications. Thus, our presentation is quite concise and elementary and as a result, some important but more specialized topics and results must be omitted, which can be found in other monographs.

Another feature of this textbook is that it contains much of our own joint research in the past fifteen years. In this sense it is like a monograph. Our joint research has been supported by the National Science Foundation of China, the National Basic Research Program of China, the Academy of Mathematics and Systems Science at the Chinese Academy of Sciences, the State Key Laboratory of Scientific and Engineering Computing at the Chinese Academy of Sciences, the Chinese Ministry of Education, the China Bridge Foundation at the University of Connecticut, and the Lucas Endowment for Faculty Excellence at the University of Southern Mississippi, among the others, for which we express our deep gratitude.

Jiu Ding would also like to thank his Ph.D. thesis advisor, University Distinguished Professor Tien-Yien Li of Michigan State University. It is Dr. Li's highly educative graduate course "Ergodic Theory on [0, 1]" for the academic year 1988-1989, based on the lecture notes delivered at Kyoto University of Japan one year earlier, that introduced him into the new research field of computational ergodic theory and led him to write a related Ph.D. dissertation. Aihui Zhou is very grateful to his Ph.D. thesis advisor, Academician Qun Lin, of the Chinese Academy of Sciences, who with a great insight, encouraged him to enter this wide and exciting research area.

The first edition of this book was published in Chinese by the Tsinghua University Press in Beijing, China in January 2006 and reprinted in December in the same year. We thank editors Xiaoyan Liu, Lixia Tong, and Haiyan Wang and five former Ph.D. students of Aihui Zhou, Xiaoying Dai, Congming Jin, Fang Liu, Lihua Shen, and Ying Yang for their diligent editorial work and technical assistance, which made the fast publication of the Chinese edition possible. We thank Lixia Tong for her help during the preparation of this revised and expanded English edition of the book.

Liu Ding and Aihui Zhou

Beijing, March 2008