Algorithms for approximation of invariant measures for IFS

We prove convergence of two algorithms approximating invariant measures to iterated function systems numerically. We consider IFSs with finitely many continuous and injective non-overlapping maps on the unit interval. The first algorithm is a version of the Ulam algorithm for IFSs introduced by Strichartz et al. [16]. We obtain convergence in the supremum metric for distribution functions of the approximating eigen-measures to a unique invariant measure for the IFS. We have to make some modifications of the usual way of treating the Ulam algorithm due to a problem concerning approximate eigenvalues, which is part of our more general situation with weights not necessarily being related to the maps of the IFS. The second algorithm is a new recursive algorithm which is an analogue of forward step algorithms in the approximation theory of ODEs. It produces a sequence of approximating measures that converges to a unique invariant measure with geometric rate in the supremum metric. The main advantage of the recursive algorithm is that it runs much faster on a computer (using Maple) than the Ulam algorithm.Mathematics Subject Classification (2000): 37A30, 37C30, 37M25, 47A58Acknowledgement I would like to express my deep gratitude to Andreas Strömbergsson and to the anonymous referee. The referee had several very enlightening comments, which Andreas helped me to deal with. Section 4 is essentially due to Andreas and he also came up with the new Proposition 3 and helped me to improve Lemma 1. Thanks also to Svante Janson, Anders Johansson, Sten Kaijser, Robert Strichartz and Hans Wallin.