\magnification = 1200 \hfuzz=10pt \hsize=4.8in \vsize=7.3in \baselineskip=18pt \hoffset=0.35in \voffset=0.1in \parindent=0pt \def\R{I\!\!R} \def\C{I\!\!\!\!C} \def\N{I\!\!N} \def\Q{I\!\!\!\!Q} \def\Z{I\!\!\!\!Z} \def\ui{[0,1]} \def\O{\Omega_{\geq}} \def\o{\omega} \def\t{\theta} \def\S{\Sigma_{\geq}} \def\SE{\Sigma} \def\s{\sigma} \def\sp{\sigma^{\prime}} \def\A{\cal A} \def\L{{\cal L}} \def\E{{\cal E}} \def\Ln{{\cal L}_n} \def\df{f^{\prime}} \def\ddf{f^{\prime \prime}} \def\dphi{\phi^{\prime}} \def\dg{g^{\prime}} \def\B{{\cal B}} \def\di{\displaystyle} \def\DSP{\Lambda ({\cal L} )} \def\DSPn{\Lambda ({\cal L}_n )} \def\ESP{{\rm ess}({\cal L} )} \def\RES{r_{\rm ess}({\cal L} )} \def\v{{{\rm var }\,}} \def\t{\theta} \def\A{{\cal A}} \def\Dn{\Delta_n} \def\Gn{\Gamma_n} \def\lip{{\rm L}} \centerline{\bf TRANSFER OPERATOR FOR PIECEWISE AFFINE} \centerline{\bf APPROXIMATIONS OF INTERVAL MAPS} \vglue 0.2cm \vglue 1.0cm \centerline{ Viviane Baladi } \centerline{\it ETH Z\"urich, CH-8092 Z\"urich, Switzerland} \centerline{\it (On leave from CNRS, UMR 128, ENS Lyon, France)} \vglue 0.2cm\centerline{ Stefano Isola} \centerline{\it Dipartimento di Matematica, Universit\'a degli Studi di Bologna,} \centerline{\it I-40127 Bologna, Italy} \vglue 0.2cm\centerline{ Bernard Schmitt} \centerline{\it Universit\'e de Bourgogne, Laboratoire de Topologie - URA 755,} \centerline{\it F-21004 Dijon, France} \vskip 0.5cm \centerline{\bf August 1994} \vskip 0.2cm {\bf Abstract.} We consider a natural approximation scheme for piecewise expanding, piecewise $C^{1+\rm{Lipschitz}}$, mixing Markov interval maps $f$ by piecewise affine maps. We prove that the densities of the absolutely continuous invariant probability measures of the approximations converge exponentially fast to the density of the absolutely continuous invariant probability measure of $f$ in the uniform norm. To do this we compare the relevant transfer operators of the approximations with that of $f$, and use recently developed perturbation techniques. \vfill \eject {\bf 1. Introduction.} \vskip 0.2cm A transformation $f$ of $\ui$ is called Markov if there exist disjoint open intervals $I_1, \dots ,I_l$, the union of whose closures is $\ui$, such that $f$ restricted to each $I_j$ is monotone and continuous, and such that the closure of each $f(I_j)$ is the closure of a union of intervals $I_k$. When this property holds, one may study the dynamical system generated by the iteration of $f$ using symbolic dynamics and transfer operators which are the same as those in equilibrium statistical mechanics [Ru]. However the statistical properties of the dynamical orbits of $f$ can only be fully described in terms of Markov chains if the restriction of the Markov map $f$ to each interval $I_j$ is affine. Indeed, in this case, the associated transfer operator (see below) has a finite matrix representation. Thus, given a (non-linear) Markov transformation $f$, which we will assume to be topologically mixing, we are faced with the problem of approximating it with a sequence of piecewise affine Markov maps. We show that the above problem can be solved constructively. More precisely, we obtain a sequence of finite Markov stochastic matrices whose normalised eigenvectors to the eigenvalue one approach the stationary probability density of $f$ exponentially fast in the uniform norm. Our main technical tool is a non-standard perturbative argument, first used in [Ba.Yo] to deal with stochastic perturbations. The problem of finding the invariant probability measure by discretisation of the transfer operator was first raised by Ulam [U] and has been studied by many authors. In particular, Gora and Boyarski [Go.Bo] considered more general approximation schemes than ours, and did not need any Markov assumption. However, they only obtained the $L^1$ convergence of the invariant densities, and no estimate on the speed of this convergence (we believe that the methods from [Ba.Yo] used in the present article would yield another proof of the $L^1$ convergence of the invariant densities obtained by [Go.Bo, p. 865] for piecewise affine, Markov approximations of topologically mixing piecewise monotone interval maps which are not necessarily Markov). See [Li], [Ke1, p.328] for other approximation schemes, also with results in an $L^1$ framework, and [Sc] for some numerical results. This work was made possible by a visit of the first two named authors to the Universit\'e de Bourgogne and we are grateful for the warm hospitality enjoyed in the Laboratoire de Topologie. \vskip 1cm {\bf 2. Markov transformations of $\ui$ and their piecewise affine approximations.} \vskip 0.2cm Our assumption on the transformation $f:\ui \to \ui$ is that there exist points $0=a_0 1$ such that $|\df_i|\geq \rho, \;\; i=1,\dots ,\ell$; \vskip 0.1cm \item{3)} for any $1\leq i,j \leq \ell$, if $f(]a_{i-1},a_{i}[)\, \cap \, ]a_{j-1},a_{j}[ \, \not= \emptyset$, then $f(]a_{i-1},a_{i}[)\supset ]a_{j-1},a_{j}[$; \vskip 0.1cm \item{4)} there exists $k_0 \ge 1$ such that $f^{k_0}$ is onto on each branch of monotonicity (this is equivalent to a topological mixing assumption). \vskip 0.2cm We set $|f'(a_i)| := \min \{ \lim_{y \uparrow a_i} |f'(y)|, \lim_{y \downarrow a_i} |f'(y)| \}$ (with the obvious modification for $a_0, a_\ell$). It is well known that under the above conditions there is a unique absolutely continuous invariant probability measure (a.c.i.p.m.) whose density $h$ is the unique normalised positive eigenfunction with eigenvalue one of a transfer operator $\L$ defined on measurable functions $\phi $ by $$ \L \phi(x) = \sum_{f(y)=x} {\phi (y)\over |\df (y)|} \, . $$ Several interesting properties of the dynamical system generated by $f$ are intimately related to $\s(\L)$, the spectrum of $\L$ (see e.g. [Co]). However, the latter depends crucially on the Banach space considered. If one is interested in the unique a.c.i.p.m., one can let $\L$ act on the ``large'' function space $L^1({\rm Lebesgue})$. Then, the spectral radius of $\L$ is equal to $1$, which is the only element of the spectrum of $\L$ on the unit circle and is a simple eigenvalue with a positive normalised eigenfunction $h$ mentioned above, finally {\it each} $z\in \C$ with $|z|< 1$ is an eigenvalue of $\L$ with infinite multiplicity ([Ke.2]). Recall that given a Banach space of functions on the interval $(\B ,\Vert \;\, \Vert )$ such that our transfer operator $\L : \B \to \B$ is bounded, we may define the essential spectral radius, $\RES(\B)$, by: $$ \eqalign { \RES(\B) = \inf \{ &r \in \C \; : \; z \in \sigma(\L:\B \to \B) \, , |z| > r \, \Rightarrow \cr &z {\rm \,\,\, is \,\,\, an \,\,\, isolated \,\,\, eigenvalue \,\,\, of \,\,\, finite \,\,\, multiplicity } \}\, . } $$ We define the discrete spectrum of $\L$ acting on $\B$ to be the set of points $z$ in $\sigma(\L)$ with $|z| > \RES(\B)$. If $h \in \B$, $\RES(\B) < 1$, and if $1$ is the only eigenvalue of modulus $1$, then, setting $$ \tau := \max \{|\lambda |\; :\; \lambda \in \sigma(\L)\setminus\{ 1\} \}< 1 \, , $$ for any $\phi\in \B$ and any $\epsilon >0$, the spectral decomposition of $\L$ yields that $$ \Vert \L^k \phi - (\int \phi(x) dx )\cdot h \Vert \leq C (\tau +\epsilon)^k \Vert \phi \Vert \, .\eqno(2.1) $$ In other words, $\tau$ determines the rate of convergence to equilibrium, also called {\sl rate of mixing}. We shall consider $\L$ acting on the space of function of bounded variation $(BV ,\Vert \;\, \Vert )$. Recall that the total variation of $\phi : \ui \to \R$ on an interval $[a,b]$ is $$ \v_{_{[a,b]}}\phi = \sup \{\sum_{i=0}^{n-1}|\phi(x_{i+1})-\phi(x_i)|\, : \, n\geq 1, \, a\leq x_0 < \ldots < x_n \leq b \, \}\, . $$ Let then $BV := \{\phi :\ui \to \R \; : \; {\v}_{_{\ui}} \phi< \infty \}$ and $$ \Vert \phi \Vert = \Vert \phi \Vert_{\infty} + \v_{_{\ui}} \phi \, .\eqno(2.2) $$ The spectrum of $\L$ in this setting has been studied by several authors ([Wo], [Ho.Ke], [Ry], [Ke2], [Ba.Ke]): the spectral radius is equal to one, $\L$ has $1$ as an eigenvalue (and no other eigenvalues on the unit circle), and its essential spectral radius $\RES(BV)$ is $$ \t = \lim_{k\to \infty} \left(\, \sup (\, 1/|(f^k)^{\prime}|\,)\, \right)^{1/k} \leq 1/\rho< 1 \, .\eqno(2.3) $$ We now construct a sequence $\{f_n\}$ of piecewise affine approximations to $f$. For any $n\geq 1$ let $\tilde \A_{n}$ be the (mod $0$) partition of $\ui$ whose elements are the intervals of the form $ I_{i_0}\cap f^{-1}(I_{i_1})\cap \ldots \cap f^{-(n-1)}(I_{i_{n-1}})$, where $I_j = ]a_{j-1}, a_j[$ (i.e., the iterate $f^{n}$ is monotone on each $I \in \tilde \A_n$). Let $\A_n$ be the partition (in the strict sense) of $[0,1]$ obtained by adding one or two endpoints to atoms of $\tilde \A_n$, in such a way that $f^k|I$ is continuous for each $I \in \A_k$ (there might be several ways of doing this). {\bf Definition.} {\it The $n$-th piecewise affine approximation of $f$ is the transformation $f_n$ of $\ui$ such that for any $I\in \A_{n}$ the restriction ${f_n}_{|I}$ is affine, and for any extremal point $x$ of $I \in \A_n$} $$ \lim_{y\uparrow x}f_n(y) = \lim_{y\uparrow x}f(y), \quad \lim_{y\downarrow x}f_n(y) = \lim_{y\downarrow x}f(y) $$ {\it Again, we set $|f'_n(x)| := \min \{ \lim_{y \uparrow x} |f_n'(y)|, \lim_{y \downarrow x} |f_n'(y)| \}$ if $x$ is an endpoint of $I \in \A_n$, with the obvious modification for $a_0, a_\ell$.} The transfer operator associated to $f_n$ is $$ \Ln \phi(x) = \sum_{f_n(y)=x}{\phi (y)\over |f'_n(y)|} \, . \eqno(2.4) $$ The results mentioned above apply, in particular $1$ is a simple eigenvalue of $\Ln$ acting on $BV$, with normalised positive eigenfunction $h_n$ equal to the density of the unique a.c.i.p.m., and (2.3) yields a value $\t_n$ for the essential spectral radius. \vskip 0.2cm We now want to characterise the discrete spectrum and the corresponding eigenfunctions of $\Ln: BV \to BV$. Let $\Dn$ be the closed $\Ln$-invariant subspace of $BV$ defined by $$ \Dn = {\rm span} \, \{\, {\chi}_{I} \, : \, I\in \A_n\, \}\, .\eqno(2.5) $$Then, for any $n\geq 1$, we may consider the restricted operator ${\Ln}_{|\Dn}$, and the coinduced operator ${\Ln}^{\Gn}$, acting on the quotient space $\Gn = BV/\Dn$. We have the decomposition [Er.La] $\s(\Ln) \subseteq \s({\Ln}_{|\Dn}) \cup \s({\Ln}^{\Gn})$. Moreover, it is easy to check that in the natural basis for $\Dn$, the restriction ${\Ln}_{|\Dn}$ is given by the $\ell^n \times \ell^n$ matrix $M^{(n)}$ defined by: $$ M_{ij}^{(n)} = {|J_j\cap f^{-1}_n(J_i)|\over |J_i|} ={ |J_j| \over \sum_k |J_k \cap f(J_j)|} \, , \qquad J_i,J_j\in \A_{n} $$ By the mixing assumption, the matrix $M^{(n)}$ is irreducible and aperiodic, so that $\sigma(M^{(n)})=\{1\}\cup \sigma_n$, where $\sigma_n$ is strictly contained in the unit disc. On the other hand, the norm induced by (2.2) on $\Gn$ is $\Vert \phi \Vert^{\Gn} = \Vert \phi - Q_n\phi \Vert$, where $Q_n:BV \to \Dn$ is given by $$ Q_n\phi (x) = \sum_{I\in \A_n} \alpha_I(\phi)\, \chi_I(x), \qquad \alpha_I(\phi) = {1\over |I|}\, \int_I \, \phi(s)\, ds\, , $$ so that the spectral radius of ${\Ln}^{\Gn} : BV \to BV$ is easily seen to be $\leq \t_n$ and thus $=\t_n$ (see e.g. [Ba]). Putting together these observations we have: \vskip 0.2cm {\bf Lemma 2.1.} $$ \{ z \in \s(\Ln) \, , |z| > \t_n \} = \{ z \in \s({\Ln}_{|\Dn})\, , |z| > \t_n \} = \{ z \in \s(M^{(n)}) \, , |z| > \t_n \} \, . $$ {\it In particular, the normalised fixed function $h_n$ of $\Ln$ is in $\Dn$, and is a fixed vector of the matrix $M^{(n)}$.} \vskip 0.2cm We are now in a position to state our main result. \vskip 0.2cm {\bf Theorem.} {\it Let $f$ be a piecewise monotone interval map satisfying assumptions (1)-(4) from the beginning of this section, let $h$ be the density of its unique a.c.i.p.m. and $\tau$ its rate of mixing. Let $\L_n$ be the transfer operators of the $n$-th piecewise affine approximation of $f$. Then there is a constant $C_1> 0$ and for each $\kappa^2 > \tau$ a constant $C_2>0$ such that for each $n \ge 1$ the normalised eigenfunction $h_n\in \Dn$ for the simple eigenvalue $1$ of $\L_n$ satisfies $$ \eqalign {\v h_n &\le C_1 \cr \sup_{x \in \ui} |h_n(x) - h(x)| &\le C_2 \kappa^{(2/3)n} \, . } $$ Moreover, the spectrum of $\L_n$ decomposes as $\{ 1\} \cup \Sigma_n$ with rate of mixing $\tau_n=\sup \{ z \in \Sigma_n\} < 1$ and if $\tau \ne r_\ESP$, the rates $\tau_n$ converge to the rate of mixing of $f$, i.e., $\lim_{n \to \infty} \tau_n = \tau$.} \vskip 0.2cm {\bf Remark.} We only prove convergence of the maximal eigenvector. This is related to the fact that the nature of our approximations forces the use of balanced norms (see below). It would be interesting to know whether a different approach would yield results on eigenvectors corresponding to other elements of the discrete spectrum. Note also that we do not know whether the obtained exponential rate of convergence ($\tau^{1/3}$) is optimal. \vskip 0.2cm The proof of our theorem uses two lemmas. Lemma 2.2 is the analogue of the ``dynamical'' Lemma 9 in [Ba.Yo] and Lemma 2.3 corresponds to the ``abstract functional lemmas'' in [Ba.Yo]. The Markov situation considered here yields a simplification and a strenghtening of the results, because there are no ``bad'' intervals of monotonicity (in the terminology of [Ba.Yo]). We first make some preliminary remarks. For each $\tilde \theta > \theta$, there exists $k_1 \ge 1$ so that for all $n\ge k \ge k_1$ and all $I \in \A_k$, $$ \sup_{x \in \bar I} {1\over |(f_n^k)'(x)|}\le \sup_{x \in \bar I} {1\over |(f^k)'(x)|} \le \tilde \theta^k\, ,\eqno(2.6) $$ and also (see [Ba.Ke, Lemma 2.3]) $$ \v_{\bar I} {1\over |(f_n^k)'(x)|} \le\v_{\bar I} {1\over |(f^k)'(x)|} \le \tilde \theta^k\, .\eqno(2.7) $$ (We may assume that $k_1$ is a multiple of $k_0$: this will be convenient below.) Observe also that for any $\tilde \t > \t$, there exists a constant $C$ such that for all $k \ge 1$ the maximum length of the intervals in $\A_k$ is not larger than $$ \sup_{I \in \A_k} \sup_{x \in \bar I} {1\over |(f^k)'(x)|} \le C \, \, \tilde \theta^k\, . \eqno(2.8) $$ It will be necessary to make use of balanced norms in $BV$: for $0<\gamma \leq 1$ define $$ \Vert \phi \Vert_{\gamma} = \Vert \phi \Vert_{\infty} + \gamma \, \v_{\ui} \phi \, . $$ {\bf Lemma 2.2.} {\it Let ${\t} < \kappa^2 <1$. Then there exists $C_3 > 0$ such that for all $n\ge (3/2) k\ge k \ge k_1$ } $$ \Vert {\L}^k - {\Ln}^k \Vert_{\kappa^k} \leq C_3\kappa^{k}\, . $$ \vskip 0.2cm {\it Proof of Lemma 2.2.} Fix ${\tilde {\t}}$ with $\t< {\tilde {\t}} < \kappa^2$. We start by preliminary computations useful to control the supremum part of the norm. For $n\ge k \geq k_1$, we denote by $(\psi_I^k)_{I\in \A_{n}}$ and $(\psi_{n,I}^k)_{I\in \A_{n}}$ the collection of the inverse branches of all the restrictions to the atoms of $\A_{n}$ of $f^k$ and $f^k_n$ respectively. Since $n \ge k$, we have for $\phi \in BV$: $$ {\L}^k \phi (x)=\sum_{I\in \A_{n}} {\chi_{f^k(I)}(x)\, \phi (\psi_I^k(x)) \over |(f^k)^{\prime} (\psi_I^k(x))| },\qquad {\Ln}^k \phi (x)=\sum_{I\in \A_{n}} {\chi_{f^k(I)}(x)\, \phi (\psi_{n,I}^k(x)) \over | (f_n^k)^{\prime}(\psi_{n,I}^k(x))| } $$ where the characteristic functions $\chi_{f^k(I)}= \chi_{f^k_n(I)}$ are the same in both sums by the definition of $f_n$. Therefore $$ \eqalign{ |{\L}^k \phi (x) - &{\Ln}^k \phi (x) | \cr &\leq \sum_{I\in \A_{n}}{|\phi (\psi_I^k(x)) -\phi (\psi_{n,I}^k(x)) | \over |(f^k)^{\prime} (\psi_I^k(x))| }\, \chi_{f^k(I)}(x) \, + \cr &+\, \sum_{I\in \A_{n}}|\phi (\psi_{n,I}^k(x))|\left| {1\over (f^k)^{\prime} (\psi_I^k(x)) }- {1\over (f_n^k)^{\prime}(\psi_{n,I}^k(x)) }\right| \, \chi_{f^k(I)}(x) \,\cr & = \, {\rm I} + {\rm II} \, . \cr }\eqno(2.9) $$ A straightforward calculation using (2.6) yields $$ {\rm I} \leq \,\, \v_{[0,1]} (\phi) \, \, \tilde \theta^{k} \, . \eqno(2.10) $$ The second term can be estimated as follows. Let $K> 0$ be such that ${\L}^k1(x)\leq K$ for all $k \ge 1$ (such a constant $K$ exists because $\| \L^k 1 \|_\infty \le \int \L^k 1 \, dx + \v_{[0,1]} \L^k 1 = \|\L^k 1\|$, and (2.1) implies that $\|\L^k 1\|\le \| h \| + {\rm{cst}} (\tau +\epsilon)^k$) and let $C>0$ be the constant from (2.8). Then we will prove that there is a constant $\bar C$ such that for all $n \ge k$: $$ \eqalign { {\rm II}\, &\leq \| \phi\|_\infty \sup_{y_1,y_2 \in I\in \A_n} \left| { (f^k)^{\prime} (y_1)\over (f_n^k)^{\prime}(y_2)} -1 \right | \sum_{I\in \A_{n}} \left| {1\over (f^k)^{\prime} (\psi_I^k(x)) } \right | \, \chi_{f^k(I)}(x) \cr &\le \, \Vert \phi \Vert_{\infty}\, K \, \bar C\, C \tilde \t^{n-k}\, . }\eqno(2.11) $$ To obtain (2.11) we will use the following distorsion inequality: if $f$ is piecewise $C^{1+\rm{Lipschitz}}$ and expanding (in particular, $\log| f'|$ is piecewise Lipschitz), there is a constant $\hat C>0$ so that for each interval $J$ of monotonicity of $f$ and all $x_1, x_2 \in J$, $$ \left| { f^{\prime} (x_1)\over f^{\prime}(x_2)} -1 \right | \le \hat C \, |x_1 - x_2| \, . $$ To apply this inequality, we first observe that for all $n\ge k\ge 1$, and all $y_1, y_2 \in I\in \A_n$, the mean value theorem (and the remark that $f^m(I)= f^m_n(I)$ for all $0 \le m \le k$), yields $$ \eqalign{ { (f^k)^{\prime} (y_1)\over (f^k_n)^{\prime}(y_2)} &= \prod_{m=0}^{k-1} { f'(f^m(y_1)) \over f_n'(f^m_n(y_2))} = \prod_{m=0}^{k-1} { f'(f^m(y_1)) \over f'(f^m_n(y_{2,m}))} \cr } $$ where each $y_{2,m}$ is in $I$. We now combine the distorsion inequality with a second application of the mean value theorem and obtain points $z_m=z_m(y_2) \in I$, and a constant $\bar C>0$ with $$ \eqalign{0\le { (f^k)^{\prime} (y_1)\over (f^k_n)^{\prime}(y_2)} &\le \prod_{m=0}^{k-1} (1+\hat C | f^m(y_1) - f^m(z_m) |)\cr &\le \prod_{m=0}^{k-1} (1+\hat C\, \rho^{m-k}\, | f^k(y_1) - f^k(z_m) |)\cr &\le \exp \sum_{\ell=1}^{k} \log (1+\hat C\, \rho^{-\ell}\, | f^k(y_1) - f^k(z_{k-\ell}) |)\cr &\le \sup_{y_3 \in I} (1 + \bar C \, |f^k(y_1) - f^k(y_3)| )\, . } $$ Since $f^k(y_1) $ and $f^k(y_3)$ are in the same atom of $\A_{n-k}$ we may apply (2.8). It then suffices to exchange numerator and denominator to get the other inequality required for (2.11). (On distorsion inequalities, see e.g. [dM.vS, I.2, V.2].) Therefore, using $\tilde \t < \kappa^2$, there is $D_1 > 0$ so that for all $n \ge (3/2)k\ge k \ge k_1$ and $\phi \in BV$ $$ |{\L}^k \phi (x) - {\Ln}^k \phi (x) | \leq \tilde \theta^{k} \v_{_{\ui}} \phi + \Vert \phi \Vert_{\infty}\,K \, \bar C \, C \, \tilde \t^{n-k} \le D_1 \kappa^{k} \Vert \phi \Vert_{\kappa^k} \, . \eqno(2.12) $$ To estimate the variation, we write $$ \v_{_{\ui}}({\L}^k \phi - {\Ln}^k \phi ) \leq \v_{_{\ui}}{\Ln}^k \phi + \v_{_{\ui}}{\L}^k \phi $$ and bound each term of the right-hand-side separately. We consider first $\Ln^k$ for $k= k_1$ where $k_1$ is a multiple of $k_0$. We may assume that $2 \tilde \theta^{k_1} < \kappa^{k_1}$ (otherwise take $k_1$ to be a larger multiple of $k_0$). Using the fact that for each $I \in \A_{k_1}$ the branch $f^{k_1}_{|_I}$ can be extended to a surjective function on the closure of $I$ (and the inverse branches accordingly), we find for each $I\in {\A}_{k_1}$: $$ \eqalign{ \v_{_{\ui}}{ \chi_{f^{k_1}(\bar I)}(x)\, \phi (\psi^{k_1}_{n,\bar I}(x)) \over | (f^{k_1}_n)^{\prime}(\psi^{k_1}_{n,\bar I}(x))| } &= \v_{_{\ui}} {\phi (\psi^{k_1}_{n,\bar I}(x)) \over | (f^{k_1}_n)^{\prime}(\psi^{k_1}_{n,\bar I}(x))| }\cr &\leq \sup_{x \in \bar I} {1\over |({f_n}^{k_1})'(x)|}\, \v_{\bar I}\phi + \sup_{\bar I} |\phi |\, \v_{\bar I}{1\over |(f^{k_1}_n)^{\prime}|}\cr &\leq \tilde \theta^{k_1}\, \v_{\bar I}\phi + \tilde \t^{k_1}\sup_{\bar I} |\phi |\cr &\le 2 \tilde \theta^{k_1} \v_{\bar I}\phi + \tilde \t^{k_1}\inf_{\bar I} |\phi |\, \cr &\le \kappa^{k_1}\, \v_{\bar I}\phi + \tilde \t^{k_1} \beta(k_1)^{-1} \int_{\bar I} |\phi (x)| \, dx \, , \cr } $$ where $\beta(k_1)> 0$ is the minimum length of the atoms of ${\A}_{k_1}$. Hence taking the sum over the atoms of ${\A}_{k_1}$ we find $$ \v_{_{\ui}}{\Ln}^{k_1} \phi \leq \kappa^{k_1}\, {\rm var}_{_{\ui}}\phi + \tilde \t^{k_1}\, \beta({k_1})^{-1}\, \int_0^1 |\phi(x) |\, dx\, . $$ Finally, applying recursively the above inequality (and using $\int|\Ln \phi|\, dx= \int |\phi|\, dx$) we find a constant $D_2 > 0$ so that for all $n\ge k =m \cdot k_1 + p \ge k_1$ ($p< k_1$): $$ \v_{_{\ui}}{\Ln}^k \phi \leq D_2 ( \kappa^{k}\, \v_{_{\ui}}\phi + \tilde\t^{k_1}\, \beta({k_1})^{-1} \, {1- \kappa^{k}\over 1- \kappa^{k_1}}\, \int |\phi (x)|\, dx )\, . $$ The estimate for $\L^k$ is exactly the same: $$ \v_{_{\ui}}{\L}^k \phi \leq D_2 ( \kappa^{k}\, \v_{_{\ui}}\phi + \tilde\t^{k_1} \beta({k_1})^{-1} \, {1- \kappa^{k}\over 1- \kappa^{k_1}}\, \int |\phi(x)|\, dx )\, . $$ Putting together these estimates and using $\int |\phi|\, dx \le \|\phi\|_\infty$, we find a constant $D_3 > 0$ such that for all $n \ge k \ge k_1$ $$ \v_{_{\ui}}({\L}^k \phi - {\Ln}^k \phi ) \leq D_3 {\kappa}^k \, \v_{_{\ui}}\phi + D_3 \, \Vert \phi \Vert_{\infty}\, . \eqno(2.13) $$ >From (2.12) and (2.13) and using again $\tilde \t < \kappa^2$, we obtain $C_3>0$ so that for all $n \ge (3/2) k \ge k \ge k_1$ $$ \Vert {\L}^k - {\Ln}^k \Vert_{\kappa^k} \leq C_3\kappa^{k} \, . \, \, {\rm{Q.E.D.}} $$ \vskip 0.2cm We decompose the spectrum of $\L$ on $BV$ into $\sigma(\L)=\Sigma_0 \cup \Sigma_1$ where $\Sigma_0=\{ 1\}$, with the corresponding decomposition into generalised eigenspaces $BV=X_0\oplus X_1=\C h \oplus X_1$, and projections $\pi_0 : BV \to X_0$, $\pi_1 : BV\to X_1$ (see e.g. [Ka]). \vskip 0.2cm {\bf Lemma 2.3.} {\it Consider the operators $\Ln$ acting on $BV$ and let $\theta < \kappa^2 < 1$. For any $\kappa'$ so that $\tau/\kappa' < \kappa < \kappa' < 1$, there exist $C_4>0$ and $k_2 \ge 1 $ so that for all $n\ge (3/2) k\ge k\ge k_2$:} \item{1)} {\it The spectrum $\sigma(\Ln)$ decomposes into} $$ \sigma(\Ln)= \Sigma_0^n \cup \Sigma_1^n $$ {\it with } $$ \sup \{ |z| \mid z \in \Sigma_1^n \} < \kappa' < \inf \{ |z| \mid z \in \Sigma_0^n \} \, . $$ \item{2)} {\it Let $\pi_0^n : X_0^n \oplus X_1^n \to X_0^n$ be the projection associated with this spectral decomposition, then for each $\eta > \kappa/\kappa'$} $$ \|\pi_0 -\pi_0^n\|_{\kappa^k} < C_4 \, \eta^k \, . $$ {\it (In particular, $\Sigma_0^n=\{1\}$ and $1$ is a simple eigenvalue of $\Ln$.)} \vskip 0.2cm {\it Proof of Lemma 2.3.} (We essentially follow [Ba.Yo].) \item{1)} Let $\tau'$ and $\kappa_0'$ be such that $$ {\tau \over \kappa'}< {\tau' \over \kappa'} <\kappa < \kappa' < \kappa'_0 < 1\, . $$ Let $k_2\ge k_1$ be a fixed multiple of $k_0$, large enough for various purposes. In particular, we require that for $k \ge k_2$ $$ \phi \in X_{1} \Rightarrow \| \L^k \phi \| \le (\tau')^k\| \phi \| \, . $$ For $n \ge (3/2)k\ge k\ge k_2$ we will show that $\lambda \notin \sigma(\Ln)$ for $\lambda$ with $\kappa' < |\lambda| < \kappa'_0$ by proving that the resolvent $R(\Ln^k,\lambda^k) =(\Ln^k-\lambda^k \, \rm{Id})^{-1}$ is a bounded operator on $(BV, \| \cdot \|_{\kappa^k})$. If the resolvent exists, it can be written as: $$ R(\Ln^k,\lambda^k)= \sum_{m=0}^\infty \bigl ( R(\L^k, \lambda^k) (\Ln^k-\L^k) \bigr)^m \cdot R(\L^k, \lambda^k) \, .\eqno{(2.14)} $$ By Lemma 2.2, it is enough to show that $\|R(\L^k, \lambda^k) \|_{\kappa^k} < (1/\kappa)^k$. Since $R(\L^k,\lambda^k) X_i = X_i$ for $i=0,1$, we have for $\phi \in X$, $\|\phi \|_{\kappa^k} =1$ $$ \eqalign { \| R(\L^k, \lambda^k) \phi\|_{\kappa^k} &\le \| R(\L^k,\lambda^k) \pi_0 \phi\|_{\kappa^k} + \| R(\L^k, \lambda^k)\pi_1 \phi \|_{\kappa_k} \cr &\le \| R(\L^k, \lambda^k)|_{X_0} \|_{\kappa^k} \| \pi_0\|_{\kappa^k} + \| R(\L^k, \lambda^k)|_{X_1} \|_{\kappa^k} \| \pi_1\|_{\kappa^k}\, . \cr } $$ Since $\pi_0 \phi= h \, \int \phi(x) \, dx$, there exists a constant $A_0>0$ with $$ \| \pi_0 \phi \|_\infty \le \| h\|_\infty |\int \phi(x) \, dx|\le A_0 \|\phi\|_1 \le A_0 \| \phi\|_\infty \, . $$ Therefore $\|\pi_0\|_{\kappa^k}$ and $\|\pi_1\|_{\kappa^k} \le 1 + \|\pi_0\|_{\kappa^k}$ are uniformly bounded (because $\|\pi_0 \phi \|_{\kappa^k}\le\|\pi_0\phi\|\le A'\|\pi_0 \phi\|_\infty\le A' A_0 \|\phi\|_\infty \le A' A_0 \|\phi\|_{\kappa^k}$, where we have used that all norms on $X_0$ are equivalent). It thus suffices to bound $\|R(\L^k, \lambda^k)|_{X_i} \|_{\kappa^k}$, $i=0,1$. There exists a constant $A_1 > 0$ so that for all $\phi \in X_0$ $$ \| \L^k \phi -\lambda^k \phi \|_{\kappa^k} \ge A_1 \cdot \| \phi \|_{\kappa^k} \, . $$ For $\phi \in X_{1}$, we have $$ \| \L^k \phi \|_{\kappa^k} \le \|\L^k \phi\| \le (\tau')^k \| \phi\| \le ({\tau'\over \kappa})^{k} \| \phi \|_{\kappa^k} \, , $$ from which it follows that there is a constant $A_2 > 0$ with $$ \| \L^k \phi -\lambda^k \phi \|_{\kappa^k} \ge A_2 \cdot (\kappa')^k \| \phi \|_{\kappa^k} \, . $$ Therefore, there is a constant $A_3>0$ so that for all large enough $k$ $$ \| R(\L^k, \lambda^k) \|_{\kappa^k}\le {A_3\over (\kappa')^k} \le {1\over \kappa^k} \, . \eqno{(2.15)} $$ \item{2)} Note that $\pi_0$ can be viewed as the projection associated with $(\L^k, (\Sigma_0)^k)$ for any $k$, and similarly for $\pi_0^n$. We will again consider a fixed $k\ge k_2$ and $n \ge (3/2) k$. We write $B_\delta$ for the circle of radius $\delta$ centered at $0$ in $\C$. Let $\kappa_0'$ be as in part (1) and let $\gamma = B_{{\hat \kappa}^k} \cup B_{r_0^k}$ for some $\kappa' < \hat \kappa < \kappa_0'$, with $\hat \kappa <\eta (\kappa')^2/\kappa$ (using $\eta(\kappa')^2/\kappa > \kappa'$) and $r_0 > 1$. Then by (1), $\Sigma_0^k$ and $(\Sigma_0^n)^k$ are contained in the annular region bounded by $\gamma$, and we have $$ \pi_0 = {1 \over 2 i \pi} \int_\gamma R(\L^k,\lambda) \, d\lambda \qquad\qquad \pi_0^n = {1 \over 2 i \pi} \int_\gamma R(\Ln^k,\lambda) \, d\lambda \, . $$ Therefore $$ \eqalign { \| \pi_0 - \pi_0^n\|_{\kappa^k} & \le {1 \over 2 \pi} \int_\gamma \| R(\L^k, \lambda) - R(\Ln^k, \lambda)\|_{\kappa^k}\, d\lambda\cr &\le {1 \over 2 \pi} \cdot \ell(B_{{\hat \kappa}^k}) \, \max_{\lambda \in B_{{\hat \kappa}^k}} \| R(\L^k, \lambda) - R(\Ln^k, \lambda)\|_{\kappa^k} \cr &\quad + {\rm \quad the \quad corresponding \quad term\quad for \quad} B_{r_0^k} \cr &= {\rm III} + {\rm IV} \, . \cr } $$ Using (2.14) we have $$ \| R(\L^k, \lambda) - R(\Ln^k, \lambda)\|_{\kappa^k} \le \sum_{m=1}^\infty \| R(\L^k, \lambda)\|_{\kappa^k}^{m+1} \cdot \| \Ln^k - \L^k\|_{\kappa^k}^m \, . $$ Since $\ell(B_{{\hat\kappa}^k}) = 2 \pi {\hat\kappa}^k$, and $\| R(\L^k, \lambda) \| \le A_3/ (\kappa')^k$ for $\lambda \in B_{\hat \kappa^k}$ (by (2.15)), we obtain $A_4 > 0$ such that $$ {\rm III} \le {\hat\kappa}^k \, \sum_{m=1}^\infty \biggl ( {A_3 \over {\kappa'}^k} \biggr )^{m+1} (\kappa^k)^m \le A_4 \, {\hat\kappa}^k \cdot {\kappa^k \over ({\kappa'}^k)^2} \le A_4 \, \eta^k \, . $$ For $\rm{IV}$, we use $\ell(B_{{r_0}^k}) = 2 \pi {r_0}^k$, to get $A_5> 0$ so that $$ {\rm IV} \le A_5 \, r_0^k \, {\kappa^k \over r_0^{2k}} \le A_5 \, \eta^k \, .\, $$ The assertion in parenthesis follows from classical perturbation results, see e.g. [Ka]. Q.E.D. \vskip 0.2cm {\it Proof of the Theorem.} Let $\tau/\kappa' < \kappa < \kappa'<1$. First we show that for $n \ge (3/2) k\ge k\ge k_2$ the space $X_0^n$ from Lemma 2.3 is the graph of some linear $S_n : X_0 \to X_1$: Let $\phi \in X_0^n$, since $$ \eqalign { \|\pi_1 \phi\|_{\kappa^k}&=\| \phi - \pi_0 \phi \|_{\kappa^k} \le \| \pi_0^n - \pi_0 \|_{\kappa^k} \| \phi\|_{\kappa^k}\, ,\cr \|\pi_0 \phi \|_{\kappa^k} &\ge \|\phi\|_{\kappa^k} (1 - \|\pi_0 -\pi_0^n\|_{\kappa^k}) \, , \cr } $$ it follows from Lemma 2.3(2) that $\|\pi_1 \phi\|_{\kappa^k} \ll \| \pi_0 \phi \|_{\kappa^k}$. In particular if $\phi$, $\phi' \in X_0^n$ and $\pi_0 \phi = \pi_0 \phi'$, then $\pi_1 \phi =\pi_1 \phi'$ and thus $\phi = \phi'$. We now estimate $\| S_n\|_{\kappa_k}$. Since ${\rm dim}\, X_0 =1$, and $\Sigma_0^n=\{1\}$, there exists $\phi_0 =\phi_0(n,k) \in X_0$, $\| \phi_0\|_{\kappa^k}=1$, such that $$ \| S_n \|_{\kappa^k} = \|S_n \phi_0 \|_{\kappa^k} = \| \pi_1 (\phi_0, S_n \phi_0)\|_{\kappa^k} = \| \pi_1 \Ln^k(\phi_0, S_n \phi_0)\|_{\kappa^k}\, . $$ For $\kappa^2 > \tau'' > \tau$ and large enough $k$, Lemma 2.2 thus yields $$ \eqalign{ \| S_n \|_{\kappa^k} &= \| \pi_1 \bigl [ \Ln^k(\phi_0, S_n \phi_0) -\L^k \phi_0 +\L^k S_n \phi_0 - \L^k S_n \phi_0 \bigr ] \|_{\kappa^k}\cr &\le \| \pi_1 \|_{\kappa^k} \biggl ( \bigl ( (\tau''/\kappa)^k + C_3 \kappa^k \bigr ) \| S_n \|_{\kappa^k} + C_3 \kappa^k \biggr ) \, .\cr } $$ Therefore, there exist $k_3\ge k_2$ and a constant $B>0$ so that for all $n \ge (3/2) k \ge k \ge k_3$ $$ \| S_n \|_{\kappa^k} \le B\, \kappa^k \, . \eqno{(2.16)} $$ In particular, writing $[y]$ for the integer part of $y$, for all $n \ge (3/2)k_3$ $$ \| S_n \|_{\kappa^{[(2/3)n}]} \le B\, \kappa^{[(2/3)n]} \, . \eqno{(2.17)} $$ We need a bound on $\|S_n\|_\infty$. For $n \ge (3/2)k_3$ and $\phi \in X_0$ we have, using the constant $A'$ from the proof of Lemma 2.3(1), $$ \eqalign { \|S_n \phi\|_\infty &\le \| S_n \|_{\kappa^{[(2/3)n]}} \| \phi \|_{\kappa^{[(2/3)n]}}\cr &\le \| S_n\|_{\kappa^{[(2/3)n]}} (\kappa^{[(2/3)n]} \cdot A' \cdot \|\phi\|_\infty + (1-\kappa^{[(2/3)n]})\cdot \|\phi\|_\infty ) \cr &\le (A'+1) B \kappa^{[(2/3)n]} \|\phi\|_\infty \, . \cr } \eqno{(2.18)} $$ By definition $$ h_n={ h+S_n(h) \over \int (h(x)+S_n(h)(x))\, dx}\ . $$ Now $ |\int (h(x) +S_n (h)(x)) \, dx - 1 | \le \|S_n(h)\|_\infty$, which tends to zero as $n \to \infty$ by (2.18). Therefore (2.17) implies that for $n\ge (3/2) k_3$: $$ \eqalign { \v h_n &\le {\v h + \v S_n h \over \int (h+S_n h) \, dx}\cr &\le {\v h + \kappa^{-[(2/3)n]} \| S_n \|_{\kappa^{[(2/3)n]}} \| h\| \over 1- \|S_n (h)\|_\infty }\cr &\le (1+B) \|h\| (1+2 \|S_n (h)\|_\infty) \, , } $$ which proves the existence of $C_1$. We now bound $\|h_n -h \|_\infty$ using again (2.18): $$ \eqalign {\|h_n -h\|_\infty &\le{ (1+\|h\|_\infty) \|S_n h\|_\infty\over 1-\|S_n h\|_\infty}\cr &\le (1+\|h\|_\infty) (1+2\|S_n h\|_\infty) (A'+1) B \kappa^{[(2/3)n]} \|h\|_\infty \, , } $$ which proves the existence of $C_2$. The statement on the convergence of $\tau_n$ follows from the property of the convergence of the discrete spectrum in [Ba, Corollary to the main Theorem]. Q.E.D. \vskip 0.8cm {\bf References.} \vskip 1cm \item{ [Ba]} Baladi V., {\sl Infinite kneading matrices and weighted zeta functions of interval maps}, Preprint, 1993, to appear in J. Funct. Anal. \vskip 0.2cm \item{ [Ba.Ke]} Baladi V. and Keller G., {\sl Zeta functions and transfer operators for piecewise monotone tranformations}, Comm. Math. Phys. {\bf 127}, 459-477 (1990). \vskip 0.2cm \item{ [Ba.Yo]} Baladi V. and Young L.-S., {\sl On the spectra of randomly perturbed expanding maps}, Comm. Math. Phys. {\bf 156}, 355-385 (1993) (see also Erratum, to appear in Comm. Math. Phys.). \vskip 0.2cm \item{ [Co]} Collet P., {\sl Some ergodic properties of maps of the interval}, Dynamical Systems and Frustrated Systems (R. Bamon, J.-M. Gambaudo and S. Martinez eds.) 1991 (to appear). \vskip 0.2cm \item{ [Er.La]} Erdelyi I. and Lange R., {\sl Spectral Decompositions on Banach Spaces}, Lecture Notes in Math. {\bf 623}, 1977. \vskip 0.2cm \item{ [Go.Bo]} Gora P. and Boyarsky A., {\sl Compactness of invariant densities for families of expanding, piecewise monotonic transformations}, Can. J. Math. {\bf XLI}, 855-869 (1989). \vskip 0.2cm \item{ [Ho.Ke]} Hofbauer F. and Keller G., {\sl Ergodic properties of invariant measures for piecewise monotonic transformations}, Math. Z. {\bf 180}, 119-140 (1982). \vskip 0.2cm \item{ [Ka]} Kato T., {\sl Perturbation Theory for Linear Operators} (Second printing of second edition), Springer-Verlag, Berlin (1984). \vskip 0.2cm \item{ [Ke1]} Keller G., {\sl Stochastic stability in some chaotic dynamical systems}, Mh. Math. {\bf 94}, 313-333 (1982). \vskip 0.2cm \item{ [Ke2]} Keller G., {\sl On the rate of convergence to equilibrium in one-dimensional dynamics}, Comm. Math. Phys. {\bf 96}, 181-193 (1984). \vskip 0.2cm \item{ [Li]} Li T.-Y., {\sl Finite approximation for the Frobenius-Perron operator. A solution to Ulam's conjecture}, Jour. of Approx. Theory {\bf 17}, 177-186 (1976). \vskip 0.2cm \item{ [dM.vS]} de Melo W. and van Strien S., {\sl One-Dimensional Dynamics}, Springer Verlag, Berlin (1993). \vskip 0.2cm \item{ [Ru]} Ruelle D., {\sl Thermodynamic Formalism}, Addison-Wesley, Reading, 1978. \vskip 0.2cm \item{ [Ry]} Rychlik M., {\sl Bounded variation and invariant measures}, Studia Math. {\bf LXXVI}, 69-80 (1983). \vskip 0.2cm \item{ [Sc]} Scholtz H.J., {\sl Markov chains and discrete chaos}, Physica {\bf 4D}, 281-286 (1982). \vskip 0.2cm \item{ [U]} Ulam S., {\sl Problems in modern mathematics}, Interscience Publishers, New York, 1960. \vskip 0.2cm \item{ [Wo]} Wong S., {\sl Some metric properties of piecewise monotonic mappings of the unit interval}, Trans. Amer. Math. Soc. {\bf 246}, 493-500 (1978). \end