to my colleagues. A warm thought goes to Isaia and the UFRJ, a personal and academic experience that will always have a place in my heart.

I thank the Universit é Franco-Italienne, which has partly financed the mobility of my doctoral program, and which has been very helpful during this last difficult year. I would also like to thank EIPHI for financing my visit to the UFRJ.

A special thank you to the Mesocentre, where part of the experiments reported in this thesis were performed.

Obviously, none of this would have been possible without my colorful and wandering family; I promise that one day I will repay you for all that you give me every day.

Mari ove le lentiggini isolate echeggiano.

iii CONTENTS

INTRODUCTION

In 2019 it has been estimated that the amount of digital data in the world is 40 zettabytes, 40 times the number of observable stars in the universe. Obviously providing an accurate estimate of this amount is impossible, but looking at our society, it is not difficult to imagine that it is so. Managing this amount of data and digital devices is a huge challenge for mankind, involving virtually every area of knowledge, from metallurgy to ethics. Digital data nowadays are produced in every observable context of human experience, and one of their main characteristics is to be in continuous evolution because they represent a changing reality; furthermore, it is clear to all, that human reality is permeated by chaos, that is, the evolution of natural phenomena cannot be exactly predicted. It arises spontaneously then, to wonder if, despite their intrinsic complexity, it is possible to understand, in some sense, the evolution of this type of complex systems. This question is naturally placed in the mathematical field, and one of the techniques currently used to model an observable phenomenon is to describe the evolution of a system through the evolution of a certain stochastic process, a random dynamical system. This allows us to take into account that nature rarely follows laws that are only deterministic or only random, but often everything is generated by the competition of these two tendencies. In any case, recall that chaotic behavior can arise in a purely deterministic system. The purpose of this thesis is to try to answer the following question: given a random dynamical system, are we able to predict (not just simulate) its behavior in the long term? When we say "predict and not simulate," we mean to have mathematical certainty of the long-term behavior of the model under consideration. If I put a drop of black ink in a glass of water, the short term interactions between these two liquids are unpredictable. However, we can all say with certainty that after enough time, the water and ink mix completely, the glass is filled with a grey liquid, the system will have reached its equilibrium state.

The example just exposed, can be formalized in many ways, one of these is to consider a certain operator defined on the appropriate spaces, which maps measures to measures, and prove for example that this operator admits as fixed point the Lebesgue's measure properly normalized (the state of equilibrium). This type of operators, are called Transfer Operators, and are linear operators defined on appropriate Banach spaces, and are the object of study of this thesis.

A transfer operator associated with a dynamical system describes the evolution of the densities according to the dynamics (in the previous example, the drop of ink that we CONTENTS can model with a delta of Dirac, will evolve in the measure of Lebesgue). The random dynamical systems can be studied substantially from two points of view, annealed and quenched; in the first case, one looks at the average behavior of the evolution of the system with respect to the random parameters, while in the second the focus is on a fixed realization of the random parameters. In this thesis, we will deal only with the annealed case, for results in the quenched case we refer for instance to [18; 1], and [START_REF] Chekroun | Stochastic climate dynamics: random attractors and time-dependent invariant measures[END_REF] for a remarkable application. Indeed, while in the first case the stochastic stability properties necessary to study the system are ensured by the presence of noise, in the second case this is no longer true and the relevant objects of study become the Oseledets-Lyapunov spectrum of some transfer operator cocycle associated to random products of maps.

Therefore we will study the dynamics of a system via annealed transfer operators (see definition 1.5). Under appropriate assumptions, these transfer operators admit fixed points, which are the stationary measures of the system, and our goal is to calculate these fixed points, which represent the statistic behavior of the system under consideration after a long time; a link between stationary measures and statistical behavior of the system, is proved in theorem 2.6, a variant of the Birkhoff's ergodic theorem, which, roughly speaking, show that the time averages of an observable converge to the spatial average with respect to the invariant measure.

Furthermore we can also study how these equilibrium states, the invariant measures, vary with respect to small perturbations of the system, i.e. we can study the statistical stability of the system; if this variation is smooth we say that the system admit Linear Response.

Unfortunately, in many cases, even simple ones, the calculation of the stationary measure, or better, of its density with respect to the Lebesgue measure, cannot be addressed analytically. The strategy we follow is therefore to rigorously approximate these densities; we remark on the importance of the fact that we are interested in having rigorous quantitative estimates, and not in numerically simulating a system. Numerical simulations are not mathematical proofs and often lead to totally misleading conclusions, see for instance [14; 26; 25; 29; 27], or 7.1 for a simple example. The central core of this interdisciplinary thesis is to use mathematical ideas that allow us to have an explicit estimation of the errors related to these rigorous approximations, combined with an accurate computer science implementation, which leads to have quantitative theorems proved with the aid of a computer.

In fact, since the transfer operator associated with a random dynamical system is a linear operator, we can expect to approximate it with a finite rank operator; this is done by a suitable composition of the transfer operator with a projection operator on a subspace of finite dimension. At this point, in order to have an invariant density approximation, it will be enough to calculate the eigenvector relative to the maximum eigenvalue of this matrix. All this procedure, if implemented in floating-point arithmetic, will not give us rigorous information about the system; however, by using the so-called interval arithmetic, we can keep track of all the errors numbers during the computation and if we combine this information with the theoretical estimates that come from the appropriate quantitative stability theorems, we obtain a rigorous approximation of the invariant measure of a system. There are three errors to manage during this process:

• the discretization error, coming from the fact that we are approximating the transfer operator with a finite rank operator; to estimate this error we use theoretical results on the stability of the fixed points of the operators under consideration, see for instance lemma 5.6.

• the approximation error, coming from the fact that we represent this finite rank operator with a matrix that cannot be exactly computed, but will be in fact approximated

• the eigen error, coming from the numerical computation of the eigenvector of this matrix.

These theoretical errors, added to the numerical errors on the computations which we automatically keep track of since we work with the interval arithmetic framework, provide a rigorous approximation of the equilibrium state of a random dynamical system. Our algorithms, return in output an approximation of the invariant density (a vector of coefficients) and a rigorous bound on the norm of the difference between the "true" invariant density, and the one calculated; the goodness of these rigorous approximations, depends on how small is the error computed. This strategy has been presented and successfully used for instance in [24; 23; 44; 48].

As we said, one way to reduce a linear operator to finite dimension is to compose it with appropriate projections onto spaces of finite size. This procedure is called Galerkin's method, and Ulam's method, which has been used in the above examples, is a special case of it, in which we choose as a finite basis of functions on which to project, the piecewise constant functions. In simple terms, we divide an interval into many small intervals and keep track of how the dynamics of the system moves these intervals. Ulam's method has been studied intensively in the literature [17; 45; 11; 13]. In dynamical system with additive noise of dimension one, the Ulam's method offer a valid and relatively fast method to compute the stationary measure; however if on the one hand, the Ulam basis is easy to implement and does not require assumptions of regularity on the system under consideration, on the other hand, it is not useful to approach multidimensional problems.

In fact, its strength, that is not to require regularity, is also its weakness, if there is regularity, the Ulam basis is not able to use it. Of course, considering smaller models, on one hand reduces the information on the system, on the other hand allows to manage CONTENTS it computationally. For this reason it is important to find the right compromise, and if we want to approach systems of dimension larger than one, Ulam's method may be no longer suitable for rigorous computations, due to its computational cost. In this perspective, in this thesis we present a report of a work in progress [START_REF] Marangio | A posteriori validated numerical method for the computation of stationary measures based on Fourier approximation[END_REF]: a rigorous approximation strategy, which uses the Fourier basis of functions. To get an idea of the "gain" in terms of approximation that results, we present a first simple, but not trivial, example, where we can obtain errors of the order of 10 -80 , while with the Ulam method we had errors of the order of 10 -10 or 10 -20 ; this comes from the fact that the Fourier basis guarantees us exponentials bounds on the discretization and approximation error, if the system is enough smooth. In the case of random system with additive noise, this regularity will be granted by the use of additive noise with Gaussian kernel; we also present theoretical results that allow us to obtain a bound on the approximation error of a system with noise with a different kernel, starting from the bounds for the same system with Gaussian noise. In the author's opinion, the strategy presented represents a promising first step towards the construction of a rigorous approximation algorithm for multidimensional systems.

In literature we can find other examples of rigorous approximation schemes, including Fourier-based ones. Regarding the latter: Pollicott, Jenkinson and others have presented an approach, which involves the computation of sums over periodic orbits, based on the theory of dynamical zeta function [35; 36]. In [START_REF] Slipantschuk | Transfer operator approach to ray-tracing in circular domains[END_REF] has been proved that for circular billiards, the convergence of finite-rank approximations using a Fourier basis follows a power law where the power depends on the smoothness of the source distribution driving the system. In [START_REF] Crimmins | Fourier approximation of the statistical properties on Anosov maps on tori[END_REF], using a Fourier-analytic method, it has been shown the first example of a rigorous scheme for approximating the peripheral spectral data of the Perron-Frobenius operator of an Anosov map without mollification. In [START_REF] Wormell | Spectral Galerkin methods for transfer operators in uniformly expanding dynamics[END_REF], two spectral Galerkin methods were presented, based on the Fourier exponential bases and the Chebyshev polynomial bases, for a class of systems satisfying certain assumption. The invariant measure for the Lanford map was then computed, leading to a bound on the error of about 10 -130 .

Regarding rigorous Ulam approximations: in [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF] a Ulam based approximation strategy was introduced which is the basis of the work presented in this thesis; This strategy has been refined in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF], where it has been proved that in the Matsumoto-Tsuda model of the famous Belosouv-Zabotinsky reaction, an increase in amplitude of the noise causes the Lyapunov exponent to decrease from positive to negative. This phenomenon is known as Noise Induced Order. In [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF], using a strategy based on linear response theory and Ulam-based rigorous approximation, it was shown that the rotation number associated with a family of Arnold maps is differentiable as a function of one of the parameters over a large range of values, and that in the case of strong nonlinearity, the rotation number is non-monotonic.

We now turn to the description of the chapters that make up this thesis, specifying basic references for each.

In Chapter 1 In chapter 1 we introduce the main objects of study of this thesis: we will see what is a random transformation and how it induces a linear operator, called transfer operator. We will be interested in the study of the fixed points of this operator, the stationary measures, of which we will demonstrate the existence. In this chapter, as well as in the next two, we will introduce standard notions from the literature, the texts to which we have referred are [START_REF] Arnold | Random Dynamical Systems[END_REF], [START_REF] Baladi | Positive transfer operator and decay of correlations[END_REF], [START_REF] Krenegel | On the speed of convergence in the ergodic theorem[END_REF], [START_REF] Krenegel | Ergodic Theorems[END_REF], [START_REF] Foguel | The ergodic theory of Markov processes[END_REF].

We then turn to Chapter 2, where we present, in brief, a variant for random dynamical system of the famous Birkhoff's ergodic theorem, one of the classical topics of ergodic theory. Indeed, in Chapter 3, we will define a class of operators, the Perron Frobenius operators, induced by non-singular transformations, which satisfy the assumptions of the ergodic theorem; we will introduce the concepts of ergodic transformation and mixing and prove the existence of stationary measures for positive contractions (of which the Perron Frobenius operators are a special case).

In Chapter 4, we introduce a particular class of random dynamical systems, dynamical systems with additive noise; we will study the existence and regularity of stationary measures for this type of systems, as well as introduce the necessary function spaces (e.g., the space of bounded-variation functions). We then introduce Linear Response theory, which allows us to analyze how a stationary measure changes in a perturbed random system. Linear Response theory deals with the following problem: if a dynamical system is submitted to some perturbation how does its invariant measure vary? If this change occurs in a smooth way, we say that the system admits Linear Response, and this change can be described by a suitable derivative. We refer to [START_REF] Baladi | Linear Response, or else[END_REF] for a survey about linear response for deterministic system (which was first achieved by Ruelle in the uniformly hyperbolic case [55; 54]), meanwhile for the random case, we refer to [START_REF] Bahsoun | Linear response in the intermittent family: ƒrentiation in a weighted C 0 -norm[END_REF], [START_REF] Bahsoun | Linear response for random dynamical systems[END_REF], [START_REF] Bahsoun | A Rigorous Computational Approach to Linear Response[END_REF], [START_REF] Galatolo | Linear response for dynamical systems with additive noise[END_REF].

After having developed the necessary theoretical framework in the previous chapters, in Chapter 5 we introduce the finite schemes of rigorous approximation: as we have already said, we are interested in the computation of a fixed point of a linear operator. To do this we project this operator onto a finite basis of functions and study this "discretized" operator. Since it is a finite-dimensional operator, we can calculate a matrix to approximate it and study its properties with a computer. We will also provide estimates of the various errors made during this approximation process, which will eventually lead to what we call a rigorous approximation. In the first section of this chapter, we will describe a strategy based on Ulam's method, i.e. we will choose as a basis of functions, the indicator functions. In the second section, we will present a work in progress, where we will choose as basis of functions the Fourier basis.

In Chapter 6 we present two applications of the Ulam method described above; in particular we will focus on a family of random dynamical systems, the Arnold maps, and show CONTENTS how the calculation of the stationary measure combined with Linear Response theory, introduced in Chapter 4, leads to interesting theoretical results, for example, the differentiability of the rotation number. The rotation number, which is a particular function associated with a dynamical system, in the case of the Arnold maps, presents a surprising behavior (see for instance Fig. 6.5), which seems to go through a smoothing process once the noise has been applied. In [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF], a linear response theorem has been applied, where the quantitative estimate required in the assumptions of this statement has been obtained via rigorous computation. As a consequence, the differentiability of the rotation number has been derived; in fact, the latter can be described as the integral of an appropriate observable with respect to the invariant measure of the system. Furthermore, by combining quantitative estimates on the rotation number with stochastic stability theorems, the non-monotonicity of the rotation number for a large set of parameters, in the case of strong nonlinearity, has been deduced.

To conclude in Chapter 7 we describe the numerical details of the work presented and the pseudocodes of the algorithms used, focusing on the Fourier-based algorithm that we have introduced. We conclude by showing an example application of the Fourier-based strategy, which shows the potentiality of this method.

RANDOM DYNAMICAL SYSTEMS

One of the surprises of the '60s and '70s was the discovery that three ordinary differential equations are sufficient to generate an irregular behavior (Lorentz attractor), an example of what today we call deterministic chaos. However, this kind of behavior is not enough to explain (or at least model) everything we observe in nature: for example in the phenomena of ocean-atmosphere interaction, we know that there is a myriad of factors that interact on virtually every spatial and temporal scale, and that actually contribute to the dynamics of the system. Mathematical models are often simplified descriptions that leave out some parameters or details present in reality. One of the ways in which we can integrate a model in a manner that takes into account very different interactions and behaviors is to use random noise. This can be done through different mathematical formalizations, such as stochastic differential equations, but in this thesis, we will use random dynamical systems, whose role in applied sciences has become of fundamental importance in recent years. This first chapter will introduce the basic theory of random dynamical systems, with particular attention to the associated transfer operators and the existence of stationary measures.

1.1/ RANDOM TRANSFORMATION

Let (S , S, p) be a probability space and let (Ω, A, µ) be the corresponding symbolic space of the one-sided sequences endowed with the σ-algebra A = S N and the probability measure µ = p; we will fix these notations throughout the text and we will also use the standard notation for the shift map on Ω, σ({ω i } i∈N ) = {ω i+1 } i∈N . Definition 1.1 . Let (M, B) be a measurable space and let A ⊗ B be the product σ-algebra on the space Ω × M. A random transformation over σ is a measurable function

F : Ω × M → Ω × M, such that 1. F(ω, x) = (σ(ω), F ω (x)), CHAPTER 1. RANDOM DYNAMICAL SYSTEMS 2.
the map ω → F ω depends only from the 0-th coordinate of ω; therefore we shall use, with abuse, the notation F ω 0 . Definition 1.2 . Let (M, B) be a measurable space and let F : Ω × M → Ω × M a random transformation. Given ω ∈ Ω, a random orbit for F at starting point x is the sequence

{x i ω } i∈N defined by x 0 ω = x, x n ω := F ω n-1 • • • • • F ω 0 (x).
We may also consider the canonical projections π Ω :

Ω × M → Ω and π M : Ω × M → M; if
q is a measure on Ω × M, we say that q projects to π Ω ( * q) and that π M ( * q) is the marginal of q.

The following is a standard example of random transformation.

Example 1.3 . Let {G 1 , . . . , G r } be a finite set of homeomorphism over a compact metric space M, and let S = {1, • • • , r}, Ω = S N . The map G defined as

G(σ(ω), G ω 0 (x))
is a random transformation over σ.

We are going to use the next proposition to define the transfer operator, which is one of the main mathematical objects under study in this thesis.

Proposition 1.4 . The operators P x : Ω → Ω × M and P ω : M → Ω × M, defined by P x (ω) = (ω, x) and P ω (x) = (ω, x) are well-defined. Moreover, for any measurable set

E ⊂ Ω × M 1.
the slices E x and E ω of E are measurable set of A and B.

2.

for any probability measures µ on (Ω, A) and η on (M, B), the maps x → µ(E x ) and ω → η(E ω ) are measurable.

3. M µ(E x )dη(x) = (µ × η)(E) = Ω η(E ω )dµ(ω).
Proof. P x is measurable, because π m • P x (ω) = x and P x • π Ω (ω, x) = (ω, x) are both measurable (the first is a constant function, the second is the identity); similarly P ω is measurable and E x = (P x ) -1 (E) and E ω = (P ω ) -1 (E) are measurable. The proof of the second and third item proceed in standard way [reference]. We will show that the set

E = E ⊂ Ω × M : x → µ(E x ) is measurable and M µ(E x )dη(x) = (µ × η)(E)
is a λ-set that contains the π-system of the sets A × B ∈ A × B. The proof is analogous for

ω → η(E ω ).

We first observe that

A × B ∈ A × B is a π-system, because (A × B) ∩ (A × B ) = (A ∩ A ) × (B ∩ B ); moreover a set of the form A × B belongs to E since µ((A × B) x ) =          µ(A) if x ∈ B, 0 if x ∈ M \ B. and M µ((A × B) x )dη(x) = µ(A)η(B) = (µ × η)(A × B).
Finally for E being a λ-system it must hold that Ω× M ∈ E. The maps x → µ(Ω× M) x ) = µ(Ω)

and x → µ((E c ) x ) = µ(Ω) -µ(E x ) are measurable and M µ(Ω × M) x )dη(x) = µ(Ω)η(M) = (µ × η)(Ω × M), M µ(E x ) x )dη(x) = µ(Ω)η(M) - M µ(E x )dη(x) = (µ × η)(E c ). Let {E(i)} i∈N a sequence of pairwise disjoint sets in E; observe that (∪ N E(i)) x = ∪ N (E(i) x ). Thus the map x → µ((∪ N E(i)) x ) = i∈N µ(E(i) x
) is given by a series of positive measurable functions, hence it is measurable and

M µ((∪ N E(i)) x )dη(x) = i∈N M µ(E(i) x )dη(x) = i∈N (µ × η)(E(i) x ) = = (µ × η)((∪ i∈N E(i))) x ). 1.1.1/ TRANSFER OPERATORS Suppose to have a random orbit {x i } i∈N , of a random transformation F : Ω × M → Ω × M,
for which we know the starting point x 0 = x ∈ M, it is a natural question whenever or not we can compute the expected value

E[φ(x 1 )|x 0 = x], where φ ∈ L p (η), p ∈ [1, ∞] is
an observable that quantifies some properties of M. Since the iterate depends on an outcome ω ∈ Ω which is distributed according to µ, this latter quantity can be formally computed in the following way

Uφ(x) = M φ(F ω (x))dµ(ω) = M φ(F ω 0 (x))d p(ω 0 ). (1.1)
Moreover Uφ(•) defines a bounded, measurable function on M according to proposition 1.4, in fact if φ = χ B , for some B ∈ B, the integral

Uφ(x) = µ(F -1 (Ω × B) x ), (1.2)
is well defined.

By standard measure theory argument we can extend this to every bounded measurable function φ.

Definition 1.5 . The operator U, as defined in 1.1, is called the transfer operator associated to F, which maps bounded (or nonnegative) measurable functions into bounded (or nonnegative) measurable functions. The adjoint transfer operator acts in the space of probability measures η on M and it is defined by

U * η(B) = η(F -1 (ω)(B))dµ(ω) = η(F -1 (Ω × B) ω )dµ(ω); (1.3)
this integral is well defined by proposition 1.4 and U * η is a well-defined probability, by proposition 1.11.

The following lemma explains in which sense U and U * are dual operators.

Lemma 1.6 . Let φ : M → R be a bounded or nonnegative measurable function. Then

φd(U * η) = Uφdη.
To prove this lemma we consider the positive linear functionals defined by

f (φ) = φd(U * η), g(φ) = Uφdη,
and we want to show that f (φ) = g(φ) for every bounded or nonnegative measurable function φ : M → R. The following lemma shows that if the condition above holds for every characteristic function φ = χ B , B ∈ B, then it holds for every function under consideration.

Lemma 1.7 . Let F be either the space of bounded or nonnegative measurable functions on (M, B), and let G be an ordered vector space. Let f, g : F → G be positive linear operators such that

1. if ∃φ ∈ F such that φ φ + , then f (1) = g(1) 2. ∀B ∈ B, f (χ B ) ≤ g(χ B ) 3. if φ n ↑ φ ∈ F then f (φ n ) ↑ f (φ). Then ∀φ ∈ F , f (φ) ≤ g(φ).
Proof. If φ is bounded, there exists c > 0 such that φ + c is nonnegative, hence we can assume φ nonnegative; moreover by linearity and positivity f (φ) ≤ g(φ) holds for all positive simple functions. Let n ∈ N and let φ be a nonnegative function, define

φ n (x) = ∞ i=0 1 2 n χ (i,1/2 n ] • φ(x) = ∞ i=0 1 2 n χ φ -1 ((i,1/2 n ]) (x),
which is simple functions because the sum contains n2 n non-zero terms. Observe that

φ n ↑ φ because if φ(x) ∈ [i/2 n , i + 1/2 n ), for some i ∈ {0, . . . , n2 n -1}, then φ n (x) = i/2 n , otherwise φ n (x) = 0. Since for every n ∈ N, f (φ n ) ≤ g(φ) and f (φ n ) ↑ f (φ) we conclude that f (φ) ≤ (φ).
proof of lemma 1.6. Let us prove that for every φ = χ B , B ∈ B, f (φ) = g(φ); by the last lemma this will extend to all bounded or nonnegative measurable functions φ : M → R.

By proposition 1.4, and 1.2, 1.3

f (φ) = Uχ B (x)dη = µ(F -1 (Ω × B) x )dη(x) = (µ × η)(F -1 (Ω × B)) = η(F -1 (Ω × B) ω )dµ(ω) = U * η(B) = g(φ).
1.1.2/ STATIONARY MEASURES Definition 1.8 . A probability measure η for M is called stationary for the random transformation F, if

U * η = η,
i.e. it is a fixed point of the operator U * .

In the deterministic set there is the concept of invariant measures: Definition 1.9 . Let (D, D) be a measure space, and T : D → D a measurable function, then µ is an invariant measure for T if for every

E ∈ D, µ(T -1 (E)) = µ(E).
Remark 1.10 . If η is invariant for every F ω , then η is stationary for F. The converse is not true: consider example 1.3, and set

d = 2, M = PR 2 , F 1 ([x]) = [A 1 x] and F 2 ([x]) = [A 2 x],
where A 1 and A 2 are invertible matrices that admit a decomposition in invariant sets, i.e.

R 3 = E s i ⊕ E u i , i = 1, 2
such that for all x s ∈ E s i and x u ∈ E u i ,

A i x s i ≤ λ i x s , A -1 i x u ≤ µ i x u , λ i , µ i ≤ 1,
and such that E s i and E u i are all distinct.

Let η be a measure which is both F 1 and F 2 invariant and let V be a neighborhood of

[E u 1 ]. Since V ⊂ F -1 1 (V) ⊂ . . . ⊂ ∪ ∞ k=0 F -k 1 (V) = M \ [E s 1 ]
, the invariance with respect to F 1 implies

η(V) = η(∪ ∞ k=0 F -k 1 (V)) = η(M \ [E s 1 ]).
This holds for every neighborhood V, therefore η(M \ (

[E s 1 ] ∪ [E u 1 ]
)) = 0. On the other side this holds also for

η(M \ ([E s 2 ] ∪ [E u 2 ]
)) = 0 and since we are assuming the eigenspaces to be distinct, this implies η(M) = 0, which is a contradiction.

The following proposition shows the link between invariant and stationary measures.

Proposition 1.11 ([53], lemma 2.1). For every probability measure η on M,

F * (µ × η) = µ × U * (η). In particular, η is stationary if and only if µ × η is invariant. Proof. Let A × B ⊂ Ω × M be a measurable set, (µ × η)(F -1 (A × B)) = χ A • σ(ω)χ B • F ω (x)dη(x)dµ(x) = χ A • σ(ω) χ B • F ω (x)dη(x)d p(ω 0 )dµ(σ(ω)) = µ(A) χ B F ω (x)dη(x)d p(ω 0 ) = µ(A) χ B F ω (x)dµ(x)dη(x) = µ(A)U * η(B).
However not every invariant measure for F which projects to µ can be written as a product measure of the kind above; an explicit example can be found in [START_REF] Arnold | Small denominators I. Mapping the circumference onto itself[END_REF], p.52, ex. 2.1.2.

1.2/ EXISTENCE AND REGULARITY OF STATIONARY DENSITIES

In this section we investigate conditions which guarantee the existence of stationary densities for a random transformation F : Ω × M → Ω × M that we assume continuous, i.e.

each F ω = F(ω, •) is continuous. The existence of these measures is guaranteed by the standard Krylov-Bogolyubov procedure, in fact we take advantage of the topological properties of U and U * , to deduce (in abstract) the existence of stationary densities, via a suitable fixed point theorem.

Remark 1.12 ([19],pag.262). The space of regular probability measures on M, denoted by P(M), can be identified with a subspace of C(M) * , the dual of the bounded continuous real function on M; under this identification, for all φ ∈ C(M), for all η ∈ P(M)

η(φ) = φdη.
In the following, we will consider the weak * -topology on P(M) as the subspace topology obtained when C * (M) is endowed with the weak * -topology.

Before to restate lemma 1.6 in this new taste, let us prove a variant of theorem 16.8 in [START_REF] Bilingsley | Probability and Measure[END_REF] Theorem 1.13 . Let O be an open subspace of a metric space, let µ be a probability measure on Ω and let f (•, x) : Ω → R be a measurable function for each x ∈ O. Then:

1. If f (ω, •
) is continuous at x 0 for a.e. ω ∈ Ω and there exists a neighborhood

O x 0 x 0 where | f (ω, •)| ≤ g(ω) for some g ∈ L 1 (µ); then f (•, x)dµ is continuous at x 0 .
2. Suppose that O ⊂ R, that for every x 0 ∈ O there exists a full measure set Ω x 0 such that f (ω, •) and ∂ x f (ω, •) are continuous at x 0 and that there exists some neighbor-

hood O x 0 x 0 where |∂ x f (ω, •)| ≤ g(ω, x 0 ) for some g(•, x 0 ) ∈ L 1 (µ). Then ∂ x Ω f (ω, •)dµ(ω) = Ω ∂ x f (ω, •)dµ(ω),
and

Ω f (ω, •)dµ(ω) ∈ C 1 (O).
Proof. For the first item, observe that

lim x→x 0 f (ω, x) = f (ω, x 0 ), for a.e. ω ∈ Ω and | f (ω, x)| ≤ g(ω)
, for all x ∈ O x 0 ; we obtain the thesis by Lebesgue's dominated convergence theorem.

Let Ω x 0 and O x 0 as in the hypothesis if item 2. We have that

lim x→x 0 f (ω, x) -f (ω, x 0 ) x -x 0 = ∂ x (ω, x 0 )
and that for every ω ∈ Ω x 0 and for every

x ∈ O x 0 | f (ω, x) -f (ω, x 0 ) x -x 0 | ≤ g(ω, x 0 ).
Since O x 0 is a full measure set, we may take ∂ x f (ω, x 0 ) = 0 where the partial derivative does not exists, and by this argument we can extend ∂ x (•, x 0 ) to the whole Ω. By applying Lebesgue's dominated convergence theorem

lim x→ 0 Ω x 0 | f (ω, x) -f (ω, x 0 ) x -x 0 -∂ x f (ω, x 0 )|dµ(ω) = 0, thus lim x→ 0 Ω f (ω, x)dµ(ω) -Ω f (ω, x 0 )dµ(ω) x -x 0 = Ω ∂ x f (ω, x 0 )dµ(ω).
Moreover, for every

ω ∈ Ω x 0 , lim x→x 0 ∂ x f (ω, x) = ∂ x f (ω, x 0 )
, and for all x ∈ O x 0 , |∂ x f (ω, x)| ≤ g(ω, x 0 ). Hence we can conclude by applying item 1 to

∂ x f (•, x).
Let us state the extension of this theorem to function defined on R n , recall that we use the multindex notation.

Corollary 1.14 . Let f (•, x) : Ω → R be a measurable function for each x ∈ O ⊂ R n , where
O is open, and let µ be a probability measure on Ω. Suppose that for every x 0 ∈ O there exists a full measure set Ω x 0 such that ∂ α f (ω, •) is a continuous function at x 0 for every

ω ∈ Ω x 0 and α ∈ N n 0 is such that |α| ≤ k. Suppose that there exists a neighborhood O x 0 of x 0 such that for every α ∈ N n 0 , with |α| ≤ k, |∂ α f (ω, •)| ≤ g α (ω, x 0 ) for some g α (•, x 0 ) ∈ L 1 (µ). Then Ω f (ω, •)dµ(ω) ∈ C k (O) and ∂ α Ω f (ω, •)dµ(ω = Ω ∂ α f (ω, •)dµ(ω) for α ∈ N n 0 , |α| ≤ k.
Proposition 1.15 . The operator U maps C(M) to itself and U * is weak * continuous.

Proof. For the first part observe that we can apply item 1 of theorem 1.13 to the continuous functions f (ω, •) := φ • F ω . For the second part let η ∈ P(M) and consider the following basic neighborhood of U * η,

V = {ξ ∈ P(M) : ∀φ ∈ Φ(|ξ(φ) -U * η(φ)| ≤ )},
where Φ is a finite subset of C(M) and > 0. Consider now

W = {ξ ∈ P(M) : ∀ψ ∈ U(Φ)(|ξ(ψ) -η(ψ)| ≤ )}, which is a basic neighborhood of η, because U(Φ) is finite subset of C(M) and U * (W) ⊂ V, because U * ξ(φ) = ξ(Uφ).
Corollary 1.16 . If M is compact, then there exists a stationary measure on M.

Proof. M is compact, hence the set of the signed Borel measures can be identify via Riesz representation theorem with C 0 (M) * , which it is, if endowed with the weak * -topolgy, locally convex ( [START_REF] Arnold | Small denominators I. Mapping the circumference onto itself[END_REF], pag 31) Under this identification

P(M) = ∩ φ∈C 0 (M) + {η ∈ C 0 (M) * : η(φ) ≥ 0} ∩ {η ∈ C 0 (M) * : η(1) = 1} ⊂ B(0, 1),
is weak * -compact, since B(0, 1) is compact by Banach-Alaoglu's theorem. Trivially, it is also convex, therefore U * admits a fixed point by Schauder-Tychnoff fixed point theorem [START_REF] Dunford | Linear operators. Part I: General Theory[END_REF], pag. 456.

A somewhat standard procedure to obtain stationary measures, is the so-called Krylov-Bogolyubov procedure ( [START_REF] Arnold | Small denominators I. Mapping the circumference onto itself[END_REF], pag 29).

Theorem 1.17 . Let n ∈ N, let ν be a probability measure on M, and define

ν n = 1 n n-1 j=0 U * j ν.
Then every limit point of {ν n } n∈N is weak * -invariant, and ν invariant arise in this way.

Proof. Assume without loss of generality that {ν n } weak * -converge to ν; since U * is weak *continuous, also

{U * ν n } weak * -converge to U * ν. Moreover, if φ ∈ C(M) then |U * ν n (φ) -ν n (φ)| = 1 n |U * n ν(φ) -ν(φ)| ≤ 2 n ||φ||, therefore U * ν = ν.
For the last part, observe that if ν is invariant, the (Birkhoff) averages ν n are equal to ν.

ERGODIC THEOREMS

2.1/ BIRKHOFF ERGODIC THEOREM

In the last chapter we described how the deterministic concept of invariant measure can be translated into the random context; another example which is of main importance, is the ergodicity, which naturally extend to random dynamical systems.

Let us recall that our setting is made by a measurable space (M, B) and a random trans-

formation F : Ω × M → Ω × M.
Definition 2.1 . Let η be a probability measure on M

• a set B is called η-stationary if U χ B = χ B . • a function φ ∈ L 1 (η), p ∈ [1, +∞] is called η-stationary, if Uφ = φ.
Definition 2.2 . A probability measure η on M is said to be ergodic for a random transformation F if every η-stationary set has either full or null measure.

The following is a technical lemma, which shows that in our setting monotone sequences converge. It will be used in lemma 2.14 to show that the invariant sets are a σ-algebra on M.

Lemma 2.3 . If φ n ↑ φ ∈ L p (η), then Uφ n ↑ Uφ.
Proof. Let n ∈ N and let

E n = {x ∈ M : |Uφ n (x) -Uφ(x)| > }.
{Uφ n } n∈N is a monotone sequence, by the positivity of U, thus E 1 ⊃ E 2 . . .; we claim that

in f n∈N η(E n ) = 0. If p = ∞, η(E n ) = 0 whenever φ n -φ ≤ / U . If p < ∞ we use Markov inequality.
In fact E n may be written as CHAPTER 2. ERGODIC THEOREMS We will now deal with the main feature of this section, (a variant of) the famous Birkhoff Ergodic Theorem. To formalize the idea that if η is stationary and ergodic for some random transformation F, then the space average is equal to the time average almost everywhere, we may want to introduce the Birkhoff sums: Definition 2.5 . Let T be a linear, positive, contractive operator on L 1 (η), then the n-th

E n = {x ∈ M|Uφ n (x) -Uφ(x)| p > p }, η(E n ) ≤ -p M |Uφ n (x) -U φ (x)| p dη(x) ≤ 1 p Uφ n -Uφ p ≤ U p p φ n -φ . A central
Birkhoff sum with respect to T , is the positive, linear, contractive operator S n :

L 1 (η) → L 1 (η) such that S n (φ) = n-1 i=0 T j φ = φ + T φ + . . . + T n-1 φ. (2.1)
We define also the positive, linear contractive operator

A n : L 1 (η) → L 1 (η), called the n-th
Birkhoff average, defined by

A n φ = S n φ n .
Our main result in this section is the following theorem, which shows the pointwise convergence of the Birkhoff averages:

Theorem 2.6 . Let T be a linear, positive, contractive operator on L 1 (η). If there exists φ 0 ∈ L 1 (η) such that φ 0 > 0 and the sequence {A n φ 0 } admits a weakly convergent subsequence, then for every φ ∈ L 1 (η) the limit

φ(x) = lim n→+∞ A n φ(x) = lim n→+∞ 1 n n-1 i=0 T i φ(x) (2.2)
exists for η-a.e. x ∈ M, and it defines a function φ ∈ L 1 (η) such that T φ = φ.

Furthermore, if C is the σ-algebra of the invariant sets, then for every B ∈ C, φ satisfies

B φdη = B H C φdη, (2.3)
where

H C = φ(x) = χ C ∞ k=0 (T I D ) k φ(x), with I D φ(x) = χ D (x)φ(x).
(2.4)

Remark 2.7 . In some particular case the link between time and space averages (which may be not clear in the last statement), is glaring; for instance, if T is the operator P η in proposition 3.11, then

lim n→+∞ 1 n n-1 i=0 T i φ(x) = M φdη,
for η-a.e. x ∈ M.

The rest of this section is devoted to the proof of theorem 2.6, which requires two general statements, namely the Hopf maximal ergodic lemma and the mean ergodic theorem.

2.1.1/ HOPF ERGODIC MAXIMAL LEMMA AND THE σ-ALGEBRA OF THE INVARI-ANT SETS

The Hopf lemma gives us a first way to investigate the Birkhoff averages, in particular it is used to decompose M into conservative and dissipative parts; for a proof see [START_REF] Foguel | The ergodic theory of Markov processes[END_REF], pag. 9.

Lemma 2.8 (Hopf maximal ergodic lemma). Let T : L 1 (η) → L 1 (η), be a linear, positive, contractive operator and let ψ ∈ L 1 (η). Then

E ψdη ≥ 0, where E = {x ∈ M : sup N S n ψ(x) > 0}.
(2.5) Definition 2.9 ([32], pag. 32). Let φ 0 ∈ L 1 (η), φ 0 > 0; the conservative and dissipative parts of M are defined respectively as

C = {x ∈ M : ∞ j=0 T j φ 0 (x) = +∞}, (2.6)
D = {x ∈ M : ∞ j=0 T j φ 0 (x) < +∞}. (2.7)
Lemma 2.10 . The definition above is well posed, in particular:

1. C, D do not depend of the choice of φ 0 > 0 and T χ c ≤ χ C , χ D ≤ T χ D 2.
the Banach operator adjoint of T , T * , is positive and

T * 1 ≤ 1. Proof. Let φ ∈ L 1 + (η) and let C = {x ∈ C : 0 < ∞ j=0 T j φ(x) < +∞} D = {x ∈ D : ∞ j=0 T j φ(x) = +∞}. Let j ∈ N such that η({x ∈ C : T j φ(x) > 0} > 2 -j-1 η(C )
If we apply 2.8 to ψ C = φ 0 -aT j φ 0 and ψ D = φaφ 0 , a > 0, then for I ∈ {C, D} we have

I ⊂ E I := {x ∈ M : sup N S n ψ I (x) > 0} 0 ≤ E C ψ C dη ≤ M φ 0 dη -a C T j φdη 0 ≤ E D ψ D ≤ M φdη -a D φ 0 dη.
By arbitrarily choosing a > 0, we conclude that

η(C ) = η(D ) = 0. Hence C ⊂ {x ∈ M : ∞ j=0 T j φ(x) = 0 or ∞ j=0 T j φ ( x) = +∞} (2.8) D ⊂ {x ∈ M : ∞ j=0 T j φ(x) < +∞}.
(2.9)

In particular C and D are independent from the choice of φ 0 ; moreover if x ∈ C then ∞ j=0 T j χ C (x) = +∞ and also ∞ j=0 T j (T χ C (x) = +∞, which implies the second part of item 1.

For item 2, fix > 0 and let B ∈ B defined as

B := {x ∈ M : T * 1 > 1 + }; then (1 + )η(B) ≤ M (T * 1)χ B dη = M T χ B dη ≤ T χ B ≤ chi B = η(B), thus η(B) = 0 and T * 1 ≤ 1. Definition 2.11 . A set B ∈ B is called invariant if T * χ B = χ B on C.
The following from [START_REF] Hopf | The general temporally discrete Markoff process[END_REF], is an easy criterion to verify if a set is invariant.

Lemma 2.12 . Let φ ∈ L ∞ (η) (or φ ∈ L 1 + (η)) such that T * φ ≤ φ on C (or T φ ≤ φ on C); then T * φ = φ on C (or T φ = φ on C). Proof. Let φ ∈ L ∞ (η) such that T 8 φ ≤ φ on C, let ψ = φ -T * φ and φ 0 = 1. We observe that ψ + . . . + T * ( n-1) ψ = φ -T * n φ, hence M ψ(φ 0 + . . . + T n-1 φ 0 )dη = M (φ -T * n φ)φ 0 dη ≤ 2 φ L ∞ φ 0 L 1 .
Trivially ∞ i=0 T n-1 φ 0 = +∞ on C thus ψ = 0 on C, which proves the first part of the theorem. For the second part let φ ∈ L 1 + (η) such that T φ ≤ φ and suppose T φ φ on C. Then there exists > 0 such that 13 . If M is an invariant set, using that T * 1 ≤ 1, we may deduce

F = {x ∈ C : φ(x) -T φ(x) > } has a positive measure. Let us prove that ∞ j=0 T * j χ F = +∞ on F: let c > 0 and let F = {x ∈ F : ∞ j=0 T * j χ F < c}, then M ( ∞ j=0 T j χ F )χ F dη = M χ F ( ∞ j=0 T * j χ F )dη < +∞, thus η(F ) = 0 and since F ⊂ F ⊂ C equation 2.8 implies ( ∞ j=0 T j χ F )χ F = +∞ on F . But this implies that on F (φ -T φ)( ∞ j=0 T * j χ F ) = +∞, which implies a contradiction M (φ -T φ)( ∞ j=0 T * j χ F dη = M ( ∞ j=0 T j (φ -T φ))χ F ≤ M φχ F dη < +∞. Remark 2.
χ C ≤ T * χ C and T * χ D ≤ χ D ; in fact T * χ C ≤ T * 1 ≤ 1 on C, which implies that T * χ C = 1 on C, i.e. T * χ C ≤ χ C . Moreover T * χ D = T * (1 -χ C ) ≤ 1 -χ C = χ D .
Lemma 2.14 . The set of the invariant sets is a σ-algebra C on M and every

φ ∈ L ∞ (η) such that T * φ = φ on C, is C-measurable. Proof. We seek a probability η C on (M, B) such that T * φ = φ on B if and only if T * φ = φ η C -a.e. The case η(C) = 0 is trivial, since we can set η = η C and C = B; so let η(C) > 0 and define for every B ∈ B η C (B) = η(B ∩ C) η(C) . Let B 1 , B 2 ∈ B such that χ B 1 = χ B 2 on C, observe that χ C T * χ D = 0 by remark 2.13, then χ C (T * χ B 1 ) = χ C (T * χ B 1 ∩C + T * χ B 1 ∩D ) = χ C T * χ B 1 ∩C = χ C T * χ B 2 .
By lemma 2.3 it follows that if φ = ψ on C then T * φ = T * ψ on C. Hence we can regard at T * as an operator defined on L 1 (η C ), on which it is still linear, positive and contractive.

Moreover

T * 1 = 1 η C -a.e., thus C is a σ-algebra for which every invariant φ ∈ L ∞ (η C ) is measurable.

2.1.2/ CONVERGENCE OF BIRKHOFF AVERAGES

The last ingredient of the Birkhoff theorem's proof it is the famous Mean ergodic theorem (for a proof refer to [START_REF] Krenegel | Ergodic Theorems[END_REF], th. 1.1).

Theorem 2. 15 (Mean ergodic theorem). Let T be a bounded operator on a Banach space V such that the Birkhoff averages are uniformly bounded (as operators). Then for any

v ∈ V such that lim n→+∞ n -1 T n-1 v = 0,
and for any w ∈ V, the following are equivalents:

1. T w = w and w ∈ cl{T n-1 v : n ∈ N} 2.
{A n v} n∈N strongly converges to w 3. {A n v} n∈N weakly converges to w 4. {A n v} n∈N admit a subsequences that converges to w.

Proof of theorem 2.6. We observe that the assumptions of the mean ergodic theorem are verified. In particular, by contraction property T n ≤ 1; furthermore for any φ ∈ L 1 (η)

the sequence {A n φ} n∈N = {S n φ/n} n∈N has a weakly convergent subsequence, which is equivalent to show ( [START_REF] Dunford | Linear operators. Part I: General Theory[END_REF], cor. 11) that uniformly on n the following holds

lim η(E)→0 E S n (φ) n dη = 0. Fix > 0 and let 0 such that if η(E) < 0 then E |φ(•)|dη < . Let t > 0 such that η(B t ) < min{ , 0 }, where B t = {x ∈ M : tφ 0 (x) < |φ(x)|}.
Let φ 0 such that {S n φ 0 /n} has a weakly convergent subsequence (such φ 0 exists by hypothesis); then there exists δ > 0 such that if η(E) < δ then E S n (φ 0 )/ndη < /t.

Thus if η(E) < δ, then E S n φ n dη = E\B t S n (φ + tφ 0 ) n dη + B t S n (φ + tφ 0 ) n dη - E S n (tφ 0 ) n dη = E\B t S n (φ + tφ 0 ) + n dη + B t S n (φ) n dη - E\B t S n (tφ 0 ) n dη ≤ E\B t S n (φ + tφ 0 ) + n dη + B t S n |φ(•)| n dη + t E\B t S n (φ 0 ) n dη ≤ E |φ(•)|dη + 2t E\B t φ 0 dη < 4 .
(2.10)

Hence the assumptions of the mean ergodic theorem are verified and we may apply it to obtain a function φ ∈ L 1 (η), such that T φ = φ and

lim n→+∞ S n φ n -φ L 1 (η) = 0.
We want to prove that

lim n→+∞ S n φ(x) n = φ(x), forη -a.e.x ∈ M. (2.11)
It is sufficient to show that for any given > 0, for η-a.e.

x ∈ M limsup n→+∞ S n φ(x) n ≤ φ(x) + , (2.12)
in fact the latter applied to -φ gives the opposite bound with the liminf. The set of the points x ∈ M such that 2.12 does not hold is contained in

G = {x ∈ M : sup n∈N S n (φ(x) -φ(x)) = +∞};
we claim that η(G) = 0. Let ψ = φφa, with a > 0. Using the Hopf maximal ergodic lemma 2.5

E (φ -φ)dη ≥ aη(E), where E = {x ∈ M : sup n∈N S n ψ(x) > 0}.
We observe that E ⊂ G and thus

φ + φ ≥ E (φ -φ)dη ≥ aη(E) ≥ aη(B),
hence η(G) = 0 by the arbitrariety of a. We now turn to the second part of the theorem (2.3). Observe that S n φ is bounded on D by 2.9, which implies that φ = 0 on D. Since

χ C T k φ = χ C T k (χ C φ) = χ C T k-1 (T I D )φ = . . . = χ C k j=0 T k-j (χ C (T I D ) j φ), then for any B ∈ C B φdη = B χ c φdη = lim n→+∞ 1 n n-1 k=0 B χ C T k φdη = lim n→+∞ 1 n n-1 k=0 B χ C k j=0 T k-j (χ C (T I D ) j φ)dη = lim n→+∞ 1 n M T * (k-j) (χ B χ C ) k j=0 χ C (T I D ) j φdη = lim n∈N 1 n < χ B χ C k j=0 χ C (T I D ) j φdη = B H C φdη.
(2.13)

We will end this section showing that since S n 1 = n, the η-a.e. convergence of A n φ is a particular case of the following theorem Theorem 2. 16 (Chacon-Ornstein [START_REF] Foguel | The ergodic theory of Markov processes[END_REF], pag. 26). Let φ ∈ L 1 (η), φ 0 ∈ L 1 + (η), and define

Q n (x) = S n φ(x) S n φ 0 (x) .
Then Q n converges to a finite limit η-a.e. on the set

B = {x ∈ M : ∞ j=0 S n φ 0 (x) > 0}.
We first need the following lemma Lemma 2.17 . Let φ, φ 0 ∈ L 1 + (η), and Q n as defined above, then

sup n∈N |Q n (•)| < +∞ η-a.e. on {x ∈ M : φ 0 (x) > 0}/
Proof. Let a > 0, and let

A := {x ∈ M : φ 0 > 0, sup n∈N |Q n (x)| = +∞} E := {x ∈ M : sup n∈N S n (φ -aφ 0 )(x) > 0}.
Observe that A ⊂ E; Hopf maximal ergodic lemma (2.5) applied to ψ = φaφ 0 implies

n φ ≥ E S n φ(x)dη ≥ a E S n φ 0 (x)dη ≥ a A S n φ 0 (x)dη.
Since a is arbitrary, it must holds

A S n φ 0 (x)dη = 0. But S n φ 0 (x) > 0 on A, hence η(A) = 0.
proof of theorem 2.16. Without loss of generality we may assume φ non-negative, because we can always split

Q n (x) = S n φ + (x) S n φ 0 (x) - S n φ -(x) S n φ 0 (x) .
By triangle inequality,

S n φ(x) S n ψ(x) ψ(x) -φ(x) ≤ S n φ(x) S n ψ(x) ψ(x) - S n ψ(x) n + S n φ(x) n -φ(x) .
The right-hand side converges to 0 for η-a.e. x ∈ B by the latter lemma and Birkhoff ergodic theorem, hence for η-a.e. x ∈ B CHAPTER 2. ERGODIC THEOREMS

lim n→+∞ S n φ(x) S n ψ(x) ψ(x) = φ(x).
Because ψ(x) is positive on B, we have

lim n→+∞ S n φ(x) S n ψ(x) = φ(x) ψ(x) < +∞.
So far from now we deal with several properties of linear positive contractive operators, in particular the Birkhoff Ergodic Theorem; in fact a non singular random transformation induced an operator of this kind, hence we can study some of the properties of a random transformation, by taking a look to the induced operator. Since the latter is a linear positive contractive operator, we can apply the results described in this chapter and in the next one we will see how to do it.

PERRON-FROBENIUS OPERATOR

In the last chapter we deal with the pointwise convergence of the Birkhoff averages of an operator U; turns out that a non singular transformation F induced an operator (the socalled Perron-Frobenius operator) which satisfies the hypothesis of the Birkhoff theorem.

This chapter is devoted to the study of this class of operators and then to the study of criteria for the existence of stationary densities for this particular class.

3.1/ PERRON-FROBENIUS OPERATOR

Let λ be a fixed Borel regular probability on M.

Definition 3.1 . A random transformation F : Ω × M → Ω × M is non singular with respect to λ if for every probability measure q << µ × λ then F * q << µ × λ.

Let us recall a sufficient condition for a transformation to be nonsingular.

Lemma 3.2 . If (F ω ) * λ << λ for µ-a.e. ω ∈ S , then F is non singular.
Proof. The sets of the form A × B generate the σ-algebra of Ω × M, and the null sets form a σ-algebra.

Let A × B ⊂ Ω × M be a µ × λ-null set, then either µ(σ -1 (A)) = µ(A) = 0 or λ(F -1 ω (B)) = λ(B) = 0 for a.e. ω ∈ Ω; thus F * (µ × λ)(A × B) = σ -1 (A) λ(F -1 ω (B))dµ(ω) = 0.
If F is a non singular transformation (from now on, we will omit with respect to λ), and

η << λ then π * M F * (µ × η) << π * M (µ × λ) = λ,
and by proposition 1.11

U * η = π * M F * (µ × η).

CHAPTER 3. PERRON-FROBENIUS OPERATOR

Thus U * may act on a space of densities instead of a space of measures; before to formalize the last statement, let us show with the following example that if F is non singular, U can be viewed as an operator acting on L ∞ (M), furthermore if η is stationary for F, U can be defined on L 1 (η).

Example 3.3 . Let F a non singular transformation and let φ and ψ two bounded measurable functions such that A = {x ∈ M : ψ(x) φ(x)} has null measure; then

|Uφ -Uψ|dλ ≤ M M |φ(F ω x) -ψ(F ω x)|dµ(ω)dλ(x) ≤ ( φ ∞ + ψ ∞ )F * (µ × λ)(Ω × A) = 0. (3.1)
Thus also the set {x ∈ M : Uφ(x) Uψ(x)} has null measure and U is well defined L is called the Perron Frobenius operator associated to F or induced by F. Furthermore,

as an operator U : L ∞ (M) → L ∞ (M). If η is stationary for F, then for all φ ∈ L ∞ (η), Uφ L 1 (η) ≤ φ L 1 (η) and L ∞ (η) = L 1 (η). Thus we may consider U : L 1 (η) → L 1 (η). Remark 3.4 . If φ ∈ L 1 (M),
for every φ ∈ L 1 (M) and ψ ∈ L ∞ (M), M (Lφ)ψdλ = M φ(Uψ)dλ,
thus identifying L ∞ (M) as the dual space L 1 (M), we may write L * = U.

We remark that the definition above naturally extends the definition in the deterministic context, via identification of a deterministic map T : M → M with a random map F :

Ω × M → Ω × M,
where Ω is the trivial probability space. The following proposition introduces some standard properties of the Perron-Frobenius operator Proposition 3.6 . Let F be a random transformation and let L : L 1 (M) → L 1 (M) be the induced Perron Frobenius operator, the following hold:

1. L is linear 2. L is positive, i.e. Lφ ≥ 0 if φ ≥ 0 3. for every φ ∈ L 1 (M), M Lφdλ = M φdλ 4. F ω , the random transformation on Ω × M defined by (ω, x) → F n M (x), induced a Perron-Frobenius operator L M such that L M = L n 5. if M is compact, then for any φ ∈ L 1 (M), Lφ L 1 ≤ φ L 1 .
Proof. 1. L can be written as the composition of the linear operators, φ → φλ, U * and η → dη/dm; the image of the first is the subspace of absolutely continuous measures, the second preserves this subspace by nonsingularity and the third is defined by absolutely continuous measures.

2.

We claim that if φ ≥ 0 then U * (φλ) is a non negative measure, because the Radon-Nikodym derivative of an unsigned measure is unsigned; this is true because U is positive, and thus U * preserves the subspace of nonnegative measures.

3.

We observe that U1 = 1 and

M Lφdλ = M (U1)φdλ = M φdλ. 4. U n φ(x) = M . . . M φ • F ω N • . . . • Fω 1 (x)dµ(ω 1 ) • • • dµ(ω n ).

5.

For any φ ∈ L ∞ (M) and for any B ∈ B

M χ B Lφdη = M U(χ B )φdη ≤ M |φ|dη = φ L ∞ .
Definition 3.7 . Let (M, B, η) be a measure space; an operator P : L 1 (η) → L 1 (η) which satisfies items 1, 2, 3 of proposition 3.6, is called Markov operator.

Proposition 3.8 . Let (M, B, η) be a measure space, let φ ∈ L 1 (η) and let P be a Markov operator, then

• (Pφ) + (x) ≤ Pφ + (x), for η-a.e. x ∈ M • (Pφ) -(x) ≤ Pφ -(x), for η-a.e. x ∈ M • |(Pφ)(x)| ≤ P|φ(•)|(x) for η-a.e. x ∈ M • P is contractive, i.e. Pφ L 1 ≤ φ L 1 .
Proof. The positivity of P implies that φ + -φ ≥ 0, then P(φ = -φ) ≥ 0 and Pφ + ≥ Pφ; observing that (Pφ) + ≥ 0, we conclude that (Pφ) + ≤ Pφ + (x). Symmetrically, (Pφ) -≤ Pφ -.

By linearity

|(Pφ)(•)| = (Pφ) + + (Pφ) -≤ Pφ + + Pφ -= P(φ + = φ -) = P|φ(•)|. As last step, since for all φ ∈ L 1 (η), M Pφdη = M φdη, Pφ = m |Pφ(•)|dη ≥ M P|φ(•)|dη = M |φ(•)|dη = φ .
If η is equal to the reference measure, i.e. η = λ, and we denote by D the set of positive densities h ∈ L 1 (M) such that h 1 = 1, then for any Markov operator P we have P(D) ⊂ D. Definition 3.9 . Let h ∈ D such that L(hλ) = hλ, then h is called a stationary density for F.

Stationary densities play a central role, because every fixed point of L can be obtained from them. Proposition 3.10 . Let P a Markov operator and let φ ∈ L 1 (η) such that Pφ = φ, then

Pφ + = φ + and Pφ -= φ -.
Proof. By hypothesis we have

φ + = (Pφ) + ≤ Pφ + and φ -= (Pφ) -≤ Pφ -; (Pφ + -φ + )dη + (Pφ --φ -)dη = P(φ + + φ -) -(φ + + φ -)dη + P|φ(•)| -|φ(•)|dη = P|φ(•)|dη -|φ(•)|dη = 0.
Since (Pφ + -φ + ) ≥ 0 and (Pφ --φ -) ≥ 0, we conclude that Pφ + -φ + = 0 and Pφ --φ -= 0.

3.1.1/ ERGODICITY AND MIXING

If h is a stationary density for a random transformation F, we can naturally define a Markov operator P η with fixed point 1; throughout this particular class of operators we will define a mixing property. From now on we will use Lebesgue's measure as reference measure.

Proposition 3.11 . Let F be a non singular random transformation, let U * be its adjoint transfer operator; let h ∈ D and η = hλ. Then the operator P η : L 1 (η) → L 1 (η) defined as

P η φ = d(U * (φη)) dη
is a Markov operator. If h is also stationary, then P η 1 = 1 and for every φ ∈ L 1 (η) and n ∈ N

P n η (φ)h = L n (φh).
Proof. P η is a Markov operator by the same arguments used in proposition 3.6 and it is well defined by proposition 1.11. If h is stationary then U * η = η which implies P η 1 = 1;

furthermore for every φ ∈ L 1 (η), φh ∈ L 1 (M) and for every B ∈ B,

B P n η (φ)hdλ = (U * ) n (φη)(B) = B L n (φh)dλ.
Definition 3.12 . A non singular random transformation F is said to be mixing for η = hdλ,

if for every φ ∈ L 1 (M) and ψ ∈ L ∞ (M).
(η) = M; if ψ ∈ L ∞ (M) then ψ ∈ L ∞ (η) and if φ ∈ L 1 (M), there exists φ ∈ L 1 (η) such that φ = φ h. Using 3.2 lim n∈N M P n (φ )ψdη = M φ dη M ψdη = M φdλ M ψhdλ.
We will end this section with a characterization of ergodicity and mixing which clarifies the link between these two notions ( [START_REF] Lasota | Chaos, Fractals and Noise[END_REF], th. 4.2.2 and th. 4.4.1).

Proposition 3.14 . Let F be a non singular random transformation. If η is ergodic for F then there is at most one stationary density of P η . Moreover, if there is a unique stationary density h of η and h > 0 η-a.e., then η is ergodic.

Proof. Suppose η ergodic, and let φ 1 , φ 2 be two stationary densities for F. Consider

ψ = φ 1 -φ 2 , then P η ψ = ψ and P η ψ + = ψ + , P η ψ -= ψ -(proposition 3.10).cannot Let A ± := {x ∈ M : ψ ± = 0} and observe that Uχ A ± = χ A ± .
In fact U * (φ ± η) << φη by the non singularity condition. But η is ergodic, hence either η(χ A + ) = 0 or 1, the same for χ A -.

Since their union lies in M they cannot have both null measure, thus they both have full measure, and the same must hold for the intersection {x ∈ M :

ψ(x) = 0}, i.e. φ 1 = φ 2 .
For the second part of the proposition, suppose that P η has a unique positive stationary

density h > 0. Let B ∈ B be any η-stationary set, let B = M \ B and rewrite h = χ B g + χ B h.

Now we can apply L

χ B h + χ B h = L(χ B h) + L(χ B h).
We observe that L(χ B h) = 0 on B because L(χ B h) ≥ 0 and

B L(χ B h)dη = M (Uχ B )χ B hdη = M χ B χ B hdη = 0.
Hence L(χ B h) = χ B h and either χ B = 0 or χ B = 1 (because the stationary density is unique).

Proposition 3.15 . Let F be a random transformation and η a stationary measure for F.

Then F is ergodic (mixing) for η if and only if the sequence {P j η φ} j∈N converge in the sense of Ces àro (weakly converge) to 1, for all φ ∈ D η := {ψ ∈ L 1 (η) : M ψdη = 1}.

Proof. The C ésaro convergence of {P j η φ} is equivalent to the pointwise convergence of the Birkhoff avareges {A n φ}; we also observe that since η is stationary the conservative part is just M. By Birkhoff ergodic theorem, we deduce that the pointwise limit of these averages, say φ , it is η-stationary and φdη = φ dη; furthermore it is equal to 1 for all φ ∈ D n , if and only if every η-stationary φ it is equal to φ dη, if and only if η is ergodic.

Combining the latter with the fact that L 1 (η) can be identified with L ∞ (η), give us the proof of the claim in the mixing case.

3.1.2/ EXISTENCE OF STATIONARY MEASURE FOR POSITIVE CONTRACTIONS

We end this section by discussing the existence of stationary measures for a random transformation, which are absolutely continuous with respect to a reference measure λ (e.g. Lebesgue measure). A first criteria is given by the Krylov-Bogolyubov procedure, which shows that a necessary and sufficient condition for the existence of stationary densities is the existence of some φ ∈ D such that { 1 n n1 j=) L j φ} n∈N is a weakly sequentially compact set.

However positive contractions satisfy the following criteria for the existence of nonzero positive fixed points ( [START_REF] Krenegel | Ergodic Theorems[END_REF], th 4.2), which can be utilized for the Perron-Frobenious operators since it is a particular case of positive contractions. Theorem 3.16 . Let P be a positive contraction on L 1 (η); there exists

f ∈ L 1 + (η) such that P f = f 0 if and only if for every strictly positive h ∈ L ∞ + (η), inf n≥0 P * n hdη > 0. (3.4)
Moreover, there exists a strictly positive

f ∈ L 1 + (η) such that P f = f if and only if 3.4 holds for all non zero h ∈ L ∞ + (η). Proof. Let f ∈ L 1 + (η) such that P f = f 0 and let 0 h ∈ L ∞ + (η).
If either f or h is strictly positive, then there exists > 0 such that for all n ∈ N

f P * n (h ∧ 1)dη = (P n f )(h ∧ 1)dη = f (h ∧ 1)dη > 2 f L 1 (η) .
Let A n := P * n (h ∧ 1) ≥ } and observe that P * n (h ∧ 1)

≤ P * n 1 ≥ 1 implies 2 f L 1 (η) < f P * n (h ∧ 1)dη < M\A n f dη + A n f dη, thus for every n ∈ N, A n f dη > f L 1 )η . But f ∈ L 1 + (η), hence there exists a δ > 0 such that η(A n ) > δ, which implies inf n≥0 P * n hdη ≥ inf n≥0 P * n (h ∧ 1)dη ≥ δ > 0.
Let us split the other direction of the statement in two different cases

1. If there exists a strictly positive h ∈ L ∞ + (η) such that inf n≥- P * n hdη = 0,
then for every f ∈ L 1 + (η) it holds inf n≥0 f P * n hdη = 0. In fact for every n ∈ N and > 0 there exists a > 0 such that ( fa) + L 1 (η) < and by observing that f ≤ a + ( fa) + we obtain

f P * n h.dη ≤ a P * n hdη + P * n ( f -a) + hdη, thus f P * n h.dη ≤ a P * n hdη + h L ∞ (η .
Hence for every > 0 we have

inf n≥0 f P * n hdη ≤ h L ∞ (η) . If now f ∈ L 1 + (η) is such that P f = f we have f hdη = inf n≥0 (P n f )hdη = inf n≥0 f P * n hdη = 0,
but h is strictly positive, which implies f = 0.

If 3.4 is satisfied by every non zero

h ∈ L ∞ + (η), then M = C. Otherwise there exists c > 0 such that B = { ∞ j=0 P j 1 < c} has positive measure, which implies ∞ n=0 P * j χ B dη = B ∞ n=0 P j 1 < c, which contradicts 3.4.
Let δ be a linear functional on L ∞ (η) defined by δ(h) := l P * n hdη n∈N , where l is a Banach limit. We observe that for any

h ∈ L ∞ + (η), δ(h) ≥ 0 and δ(P * h) = δ(h). For h ∈ L ∞ + we define ν(h) := inf{ ∞ n=1 δ(h n ) : h = ∞ n=1 h n , h n ∈ L ∞ + (η)}.
Let us prove now that ν(B) := ν(χ B ) defines a σ-additive finite measure on B. For

every b ∈ B, χ B ∈ L ∞ + (η) and it holds ν(B) ≤ δ(χ B ) < ∞,
thus ν is a finite function; for sure it is σ-additive, because given a sequence of disjoint sets {B i } i∈N and their union B = ∪B i , for every > 0 there exist sequences {h i, j } j∈N such that

χ B i = ∞ j=1 h i, j and ν(B i ) > ∞ j=1 δ(h i, j ) - 2 i hence ∞ i=1 ν(B i ) > ∞ i, j=1 δ(h i, j ) ≥ δ(χ B ) ≥ ν(B).
the reverse inequality holds as well, because if

{h j } j∈N is a sequence in L ∞ + (η) such thatχ B = ∞ j=1 h j , we have n i=1 ν(B i ) ≤ n i=1 ∞ j=1 δ(χ B i h j ) = ∞ j=1 δ(χ B 1 ∪...∪B n h j ) ≤ ∞ j=1 δ(h j ),
which implies using that δ is linear and positive

∞ i=1 ν(B i ) ≥ ∞ j=1 δ(h j ).
So ν is a σ-additive measure on B; let f = dν dη , we want to show that P f = f . In fact δ(P * h) = δ(h) which implies ν(P * h) ≤ ν(h), hence P f ≤ f . On the other side, since M = C we conclude P f = f by lemma 2.12. Now suppose that the set B = { f = 0} has a positive measure; we observe that ν(χ B ) = 0 which implies that for every m ∈ N

there exists a sequence {h m,n } n∈N such that χ B = ∞ n=1 h m,n and ∞ n=1 δ(h m,n ) < 1/m. Take k(m) large enough to have ∞ n=k(m)+1 h m,n dη < 2 -m η(B),
and define h * = inf m∈N k(m) n=1 h m,n . Since h m,n ∈ L ∞ + (η) also h * ∈ L ∞ + (η) and moreover h * dη + ∞ m=1 ∞ n=k(m)+1 h m,n dη ≥ η(B), hence h * dη > 0 which implies in particular that h * 0. However for all m ∈ N δ(h * ) ≤ δ( k(m) n=1 h m,n ) = k(m) n=1 ρ(h m,n < 1 m , thus δ(h * ) = 0.
In particular lim inf n→∞ P * nh * dη = 0, which contradicts 3.4, implying that B has null measure, i.e f is strictly positive.

Example 3.17 . Let T : [0, 1] → [0, 1] the square map T (x) = x 2 ; then T does not admit any invariant measure absolutely continuous with respect to Lebesgue. Let U be the transfer operator of T and h(x) = x; observe that h ∈ L ∞ + , it is strictly positive and for every n ∈ N, for every > 0

U n h(x)dx = √ 2n 0 h(T n (x))dx + 1 √ 2n U n h(T n (x))dx ≤ ≤ √ 2n + (1 - √ 2n ) → ,
as n tends to infinity, and this implies

inf n∈N U n h(x)dx = 0.
The next proposition shows that there is a large class of random transformations which admit stationary densities absolutely continuous with respect to Lebesgue ( [START_REF] Foguel | The ergodic theory of Markov processes[END_REF]).

Proposition 3.18 . Let F : Ω × M → Ω × M be a non singular random transformation with respect to λ. Suppose there exists δ > 0 such that

λ(B) > 1 -δ ⇒ inf x∈M µ({ω ∈ Ω : F ω (x) ∈ B}) > 0,
then F admits a stationary density η << λ.

Proof. Let us show that there exists

f ∈ L 1 + (λ) such that L f = f 0, where L is the Perron- Frobenius operator of F. If h ∈ L ∞ + (M) is strictly positive, fix > 0 such that B = {h > } satisfies λ(B) > 1 -δ. For every x ∈ M we have Uh(x) = Ω h(F ω (x))dµ(ω) > inf x∈M µ({ω ∈ Ω : F ω (x) ∈ A}) = β > 0.
We conclude by applying theorem 3.16, observing that for all n ∈ N U n hdλ ≥ β > 0.

3.1.3/ REGULARITY OF PERRON-FROBENIUS ITERATES

We first introduce an alternative approach to the Perron-Frobenius operator based on transition probabilities. Proof. For every fixed x ∈ M, proposition 1.4 implies that the map P x : ω → (ω, x) is measurable; µ x : B → p(x, B) is a probability measure on M, in fact µ x (M) = µ(Ω) = 1 and Proof. U is a bounded linear operator, and because the first identity is true for φ = χ B , it follows for any φ ∈ L ∞ (M). On the other hand, let B ⊂ M be a measurable set, then by Fubini's theorem

µ x = (π 2 • F • P x ) * µ, and for every fixed B ∈ B, x → µ x (B) = U χ B (x) is measurable. Thus µ(A × B) = A µ x (B)dλ(x),
B Lφdλ = M (Uχ B )φdλ = M p(•, B)φdλ = B M p(•, x)φdλdλ.
By the proposition above, if F is non singular, B is countably generated and φ ∈ L 1 (M), the Perron-Frobenius operator L : L 1 (M) → L 1 (M) admits the following expression

Lφ(x) = p(t, x)φ(t)dλ(t).
Therefore if we set Ω = M and µ = λ in corollary 1.14 we have the following

Proposition 3.22 . If p ∈ L 1 (M × M) is of class C k , then for every φ ∈ L ∞ (M), Lφ is also of class C k . Proof. The function x → f (t, x) = p(t, x)φ(t) is C k for any t ∈ M. Moreover, for every x 0 ∈ M, for all α ∈ N n 0 , |α| ≤ k, |∂ α f (t, x)| ≤ ∂ α p L ∞ (B(x 0 )) |φ(t)|,
where x ∈ B(x 0 ), a sufficiently small neighborhood of x 0 such that ∂ α p are bounded. Hence corollary 1.14 applies to f and the claim follows.

II RIGOROUS SCHEMES OF APPROXIMATION

SYSTEMS WITH ADDITIVE NOISE

From now on the rest of the thesis will focus on systems with additive noise. In this chapter, in addition to introducing the basic concepts, we will see how adding noise to a deterministic dynamical system regulates its behavior (for example, we will prove that in such random systems, every stationary measure is Lipschitz-continuous). This regularization property will allow us to rigorously approximate the transfer operator associated with a dynamical system with additive noise, as we will explain in the next chapter. A random dynamical system with additive noise is formally defined in the following way. A random dynamical system with additive noise is the random system T ξ :

Ω × M → Ω × M defined by T ξ (ω, x) = (σ(ω), π(T (x) + ω 0 )),
where Ω is the symbolic space of the one-sided sequences on M endowed with the probability measure p with density ρ ξ . As required in the definition of random system, the map (ω, x) → π(T (x) + ω 0 ) depends only from the 0-th coordinate of ω; the noise is modeled as an i.i.d. stochastic process distributed according to the probability density ρ ξ .

In concrete applications, it might be difficult to model a natural phenomenon with a single system; it makes more sense to take into consideration a family of dynamical systems, dependent on a parameter, and to study how the corresponding statistical properties (e.g.

the stationary measures) vary with this parameter: the linear response theory answers this question, and will be introduced in the second section of this chapter. In particular the linear response of a system can be described by a suitable derivative which represent the rate of change of the invariant measure with respect to the perturbation.

In the same spirit, in the last section, we will see some property of stability under suitable perturbation for random system: in a nutshell, if a system satisfies a particular notion of mixing, there is a whole neighborhood of nearby systems satisfying the same notion.

Let M = T n = (S 1 ) n the n-dimensional torus identified with the n-dimensional interval [0, 1],

as measure spaces with the Lebesgue measure λ. Let us define the convolution between two functions f, g ∈ L 1 (λ), which will play a central role.

Definition 4.2 . Let t = (t 1 , . . . , t n ) ∈ R n , let π : R → [0, 1] n the retraction π(x 1 , . . . , x n ) := (x 1 -x 1 , . . . , x n -x n ),
and consider the family of rotations τ t : L 1 (λ) → L 1 (λ) defined as

τ t f (x 1 , . . . , x n ) = f (π(x 1 -t 1 , . . . , x n -t n )).
Let f, g ∈ L 1 (λ), then the convolution f * g of f and g is defined in the following way

( f * g)(x) := M (τ t f )(x)g(t)dλ(t) = M f (t)(τ t g)(x)dλ(t),
for every x ∈ M, where in the equality above we used translational invariance of the Lebesgue measure.

4.1/ THE BOUNDED VARIATION SPACE

We will discuss random dynamical system with additive noise, where the noise belongs to the space of bounded variation functions, BV(M), which will now define. Our definition takes in account that we are working on a torus.

In the following recall that

C 1 c (U, R n ) is the space of all continuously differentiable functions ψ : U → R n such that {ψ > 0} is compact and ψ L ∞ = sup U |ψ(x)| ≤ 1.
In perspective, the work of this thesis will be applied to multidimensional contexts. As we will see in the next chapter, a fundamental role will be played by Fourier's analysis, which will allow to have estimates of errors of exponential order. With this motivation, and because it is not technically complicated, we now introduce the BV space in several dimensions, but we remark that we will work in dimension 1.

Definition 4.3 . Let U ⊂ R n be an open set, let f ∈ L 1 (U), the variation of f on U is defined by D f (U) := sup ψ∈C 1 c (U,R n ) U f (x) div ψ(x)d(x). Let f ∈ L 1 (λ), let f = f • π, then the variation of f is Var( f ) := lim U↓M D f (U) = inf U⊃M D f (U), (4.1)
where the limit and the infimum are taken over the open sets U ⊃ M. If I ⊂ M, then

var I ( f ) := Var(χ I ). Finally BV(M) := { f ∈ L 1 (λ) : Var( f ) < +∞}.
Observe that if I ⊂ M, then var I ( f ) := Var(χ I ). In the following when we write f ∈ C 1 (M),

we mean that f • π belongs to C 1 (R n ).
Proposition 4.4 . Let f ∈ BV(M), the following holds:

1.
Var is a seminorm on BV(M).

let

f ∈ C 1 (M) ∩ BV(M), then Var( f ) = |∇ f |dλ: 3. there exists a sequence of f i ∈ C ∞ (M) such that f i → f in L 1 (λ) and Var( f i ) → Var( f ). Proof. 1. Let f, g ∈ BV(M) and U ⊃ M an open set, then D( f + ĝ) (U) = sup ψ∈C 1 c (U,R n ) U ( f + ĝ)(x) div ψ(x)dx ≤ sup ψ∈C 1 c (U,R n ) U f (x) div ψ(x)dx + sup φ∈C 1 c (U,R n ) U ĝ div φ(x)dx = D f (U) + Dĝ (U).
Taking the limit U ↓ M we obtain Var( f + g) ≤ Var( f ) + Var(g). Analogously we see that for a ∈ R, Var(a f ) = |a| Var( f ); thus Var( f ) is a seminorm on BV(M).

Let U ⊃ M be an open set and let

g ∈ L 1 (R n , R n ) defined by g(x) =          ∇ f (x) |∇ f (x)| , if x ∈ M, |∇ f (x)| > 0; 0 otherwise. Observe that sup x∈R n |g(x)| ≤ 1; fix ρ ∈ C ∞ (R n ) such that ρdλ = 1 and {ρ > 1} = B(0, 1/2).
For every ξ > 0, let ρ ξ (t) = ξ n ρ(t/ξ). For every i ∈ N let

φ i := ρ 1/i (t)g(x -t)dt = ρ 1/i (x -t)g(t)dt.
We remark that sup x∈U |phi(x)| ≤ ρ 1/i (t) sup |g(y)|dt ≤; since M is compact, there exists i 0 ∈ N such that B 1/i 0 (x) ⊂ U for every x ∈ M. Let i > i 0 , then corollary 1.14 implies that φ ∈ C 1 c (U, R N ) and Lebesgue's density theorem ensures that

φ i → g in L 1 (UR n ). Hence U f div φ i (x)dx = U ∇ f (x) • φ i (x)dx → M |∇ f (x)|dx. Thus D f (U) ≥ M |∇ f (x)|dx; at the same time if φ ∈ C 1 (U, R n ), with φ ∞ ≤ 1, then U f div φ(x)dx = U ∇ f (x) • φ(x)dx ≤ U |∇ f (x)|dx,
and by taking the supremum over all such φ we obtain

D f (U) ≤ U |∇ f (x)|dx.
Putting together the two inequalities and taking the limit U ↓ M, we get

Var( f ) = M |∇ f (x)|dx.

For i ∈ N, define the open sets

U i := ∪ x∈M B 1/i (x); consider f i (x) := ρ 1/i (t) f (x -t)dt = ρ 1/i (x -t) f dt.
For each fixed i 0 , we have that for

i > i 0 , f i ∈ C ∞ (U i 0 ), f i → f in L 1 (U i 0 ) and in particular f i | M → f in L 1 (λ). Furthermore, for any t ∈ R n , for every α ∈ N n 0 and for every x, y ∈ R n , since f (x -t) = f (y -t), we have ∂ α f i (x) = ∂ α f i (y); thus f i |M ∈ C ∞ (M).
By item 2,

Var( f i |M ) = |∇ f i (x)|dλ(x) = | ρ 1/i (t)∇ f (x -t)dt|dλ(x) ≤ U i |∇ f (x)|dx ρ 1/i (t)dt = D f (U),
in fact xt ∈ U i and t ∈ {ρ 1/i > 0}. We just proved that Var(

f i | M ) ≤ D f (U i ) → Var( f ).
For the converse, let > 0, let ı 0 ∈ N, then there exists

φ ∈ C 1 c (U i 0 , R N ) such that U i 0 f i |M (π(x))divφ(x0)dx → U i 0 f (x) div φ(x)dx ≥ D f (U i 0 ) - thus lim inf i→+∞ D( f i |M ) (U i 0 ) ≥ D f (U i 0 ) -≥ Var( f ) -, which implies that lim inf i→+∞ Var( f i |M ) ≥ Var( f ) -.
We now describe some properties which hold in the one-dimensional case; we will make use of them in the next section, when we will approach the problem of the regularity of the stationary densities in systems with additive noise.

Proposition 4.5 . Let f : [0, 1] → R; x is said to be a point of approximate continuity of f if

f (x) = f (x -) + f (x + ) 2 where f (x ± ) = lim h→0 + f (π(x ± h)).
Then

1. If g ∈ C ∞ (S 1
), then V(g) = Var(g), where

V(g) := sup {x j } k-1 j=0 k-1 j+0 |g(x j+1 ) -g(x j )|, x k := x 0 ,
where all the {x j } k-1 j=0 are increasing sequences in [0, 1] of points of approximate continuity of g. Thus V(g) ≤ Var(g) and moreover the Lebesgue integral is equivalent to a Riemann one;

2. if f ∈ L 1 (λ), then V( f ) = Var( f ). 3. if f ∈ BV(S 1 ) then there exist increasing functions f 1 , f 2 : [0, 1] → R such that f (x) = f 1 (x) -f 2 (x),
hence for every fixed > 0 there exists δ > 0 such that for any increasing sequence {y j } k+1 j=0 , with y 0 = 0,

y k+1 = 1, |y j+1 -y j | < δ for 0 ≤ j ≤ k, we have k j=0 |g(y j+1 -g(y j )| > |∇g|dλ -,
and since [0, 1] is compact and g is continuous, we can choose δ such that every term of the above sum is less than . Almost everywhere any point x of [0, 1] is a point of approximate continuity of g, hence there exists an increasing sequences {x j } k-1 j=0 of such points such that x 0 < δ,

x k > 1 -δ, x j+1 -x j | < δ for 0 ≤ j ≤ k -2. We deduce that k-1 j=0 |g(x j+1 ) -g(x j )| > k j=0 |g(y j+1 ) -g(y j )| -2 > |∇g|dλ -3 ,
where x k = x 0 , y 0 = 0, y k+1 = 1 and y j = x j+1 for 1 ≤ j ≤ k; V(g) ≥ Var(g) and the claim follows.

By item 3 of the last proposition, there exists a sequence { f i } i∈N such that f i|M → f , in L 1 (λ). Take any sequence of points {x j } k j=0 of approximate continuity of f , then since λa.e. x ∈ [0, 1] is a point of approximate continuity of f , also for λ-a.e. s ∈ [0, 1], π(x js) are points of approximate continuity of f . Furthermore, up to cyclical permutation, {π(x j -s)} k-1 j=0 is increasing, thus

k-1 j=0 | f i (x j+1 ) -f i (x j )| = k-1 j=0 | 1/2 -1/2 ρ 1/i (s)( f (π(x j+1 -s)) -d(π(x j -s)))ds| ≤ 1/2 -1/2 ρ 1/i (s) k-1 j=0 | f (π(x j+1 -s)) -f (π(x j -s))|ds ≤ V( f ) 1/2 -1/2 ρ 1/i (s) = V( f ).
From the arbitrariety of the increasing sequence follows that V( f i | M ) ≤ V( f ) and we can apply item 1 to obtain Var(

f i | M ) ≤ V( f ); in fact f i | M → f in L 1 (λ) and thus Var( f ) = lim i→+∞ Var( f i | M ) ≤ V( f ).

Now since for any x point of approximate continuity of f holds

f i (x) → f (x), we deduce that k-1 j=0 | f (x j+1 ) -f (x j )| = lim i→+∞ k-1 j=0 | f i (x j+1 ) -f i (x j )| ≤ lim i→+∞ Var( f i | M ) = Var( f ), thus V( f ) ≤ Var( f ), which implies V( f ) = Var( f ).
Let c = lim inf y→0 f (y), where y belongs to the set of the points of approximate continuity

of f . Let f 1 , f 2 : [0, 1] → R be f 1 (x) = c + sup {x j } k-1 j=0 max{ f (x j+1 ) -f (x j ), 0} f 2 (x) = sup {x j } k-1 j=0 max{ f (x j ) -f (x j+1 ), 0},
where as before, we take the supremum over all increasing sequence {x j } k-1 j=0 in [0, 1] of points of continuity of f such that x j ≤ x. f 1 , f 2 are increasing functions; fix > 0, let x be any point of approximate continuity and let {x 1 j } k-1 j=0 , {x 2 j } l-1 j=0 be increasing sequences in [0, 1] upper bounded by x, such that

f 1 (x) ≥ c + k-1 j=0 max{ f (x 1 j+1 ) -f (x 1 j ), 0} > f 1 (x) - f 2 (x) ≥ l-1 j=0 max{ f (x 2 j ) -f (x 2 j+1 ), 0} > f 2 (x) -. Let x 0 < min{x 1 0 , x 2 0 } such that | f (x 0 ) -c| < .
Since max{a, +b, 0} ≤ max{a, 0} + max{b, 0} and max{a, 0}max -a, 0 = a, we can consider an increasing sequence {x j } m-1 j=0 , made by joining together the two sequences {x

1 j } k-1 j=0 , {x 2 j } l-1 j=0 , such that ( f 1 (x) -) -f 2 (x) < c + m-1 j=0 f (x j+1 ) -f (x j ) < f 1 (x) -( f 2 (x) -). Finally | f (x) -( f 1 (x) -f 2 (x))| ≤ |c + m-1 j=0 f (x j+1 ) -f (x j ) -( f 1 (x) -f 2 (x))| + | f (x 0 ) -c| < 2 .
Let N ξ : L 1 (M) → L 1 (M) be the operator defined by the convolution

N ξ f = ρ ξ * f.
Proposition 4.6 . The Perron-Frobenius operator L ξ of T ξ is N ξ L, where L is the (deterministic) Perron-Frobenius operator of T .

Proof. Let φ ∈ L 1 (M) and let B ⊂ N be a measurable set; then

B L ξ φdλ = Ω T -1 (B-ω 0 ) φdµ(x) = S T -1 (B-t) φ(v)ρ ξ (t)dλ(x)dt = S B Lφ(x + t)ρ ξ (-t)dλ(x)dt = B N ξ Lφdλ. (4.2)

4.2/ EXISTENCE AND REGULARITY OF STATIONARY DENSITIES

We first investigate the existence of a stationary measure for system with additive noise, which is a consequence of proposition 3.18.

Theorem 4.7 . Let F : Ω × M → Ω × M, M = [0, 1] n , be a random dynamical system with additive noise, where the noise has density ρ ∈ L 1 (λ) with respect to Lebesgue and λ({ρ > 0}) > 0. Then there is a stationary measure η << λ.

Proof. Let δ = 1 2 λ({ρ > 0}), we want to apply proposition 3.18. Let B be a set such that

λ(B) > 1 -δ, let x ∈ M λ({ f ω (x) ∈ B : ρ(ω > 0)}) ≥ λ(B) + λ({F ω x) : ρ(ω) >)}) -1 > δ ⇒ λ({ω ∈ {ρ > 0} : F ω (x) ∈ B}) > δ. Let > 0 such that λ({ω ∈ {ρ > } : F ω (x) ∈ B}) > λ({ω ∈ {ρ > 0} : F ω (x) ∈ B}) - δ 2 , thus for every x ∈ M µ({ω ∈ Ω : F ω (x) ∈ B}) ≥ λ({ω ∈ {ρ > } : F ω (x) ∈ B}) > δ 2
and the hypothesis of proposition 3.18 are satisfied.

Lemma 4.8 . Let f ∈ BV(M) and let h ∈ R n , then τ h f -f L 1 ≤ |h| Var( f ). Proof. Let φ ∈ C 1 (R n , R) and e = h/|h| ∈ R n and let φ = φe ∈ C 1 (R n , R n ); for t = |h| we have (τ h f (x) -f (x))φ(x)dλ(x) = f (x)(φ(x + h) -φ(x))dλ(x) = f (x) t 0 ∇φ(x + se) • edsdλ(x) = t 0 f (x) div φ(x + se)dλ(x)ds ≤ t Var( f ). Since C 1 (R n , R) is dense in L ∞ (R n ) we deduce τ h f -f L 1 ≤ |h| Var( f ). Lemma 4.9 . If ρ in BV(M) and f ∈ L 1 (M) then ρ * f ∈ BV(M). Proof. BV(M) ⊂ L 1 (M), hence ρ * f ∈ L 1 (M) by Young's inequality. Let φ ∈ C 1 c (M) with 2. if ρ ξ ∈ C k (M) then for any φ ∈ L 1 (M), L ξ φ ∈ C k (M) 3. if ρ ξ ∈ BV(M)
|τ -h N ξ Lφ(x) -N ξ Lφ(x)| = | ρ ξ (t)(τ t τ -h Lφ(x) -τ t Lφ(x))dλ(t)| ≤ |ρ ξ (t)(τ -t τ t Lφ(x) -τ t Lφ(x))|dλ(t) ≤ ρ ξ L ∞ |h| Var(τ t Lφ) = |h| ρ ξ L ∞ var(Lφ),
where we used 4.8, thus N ξ Lφ is Lipschitz continuous.

2.

We apply corollary 1.14 to f (ω, x) = ρ(xω)φ(ω).

3.

If f is stationary then f = L ξ f = N ξ Lφ is in BV(M) by lemma 4.9, thus it is Lipschitz continuous by item 1.

4.

We claim that if f ∈ BV(M) then L f = f • T is in BV (m) ⊂ BV(M), as in lemma 4.10.

By proposition 4.5, up to a null measure set, there are two increasing functions f 1

and

f 2 such that f = f 1 -f 2 . If [a, b] ⊂ [0, 1], then f -1 ([a, b]) = [c, d] and (L f ) -1 ([a, b]) = T -1 ( f -1 ([a, b])) = T -1 ([c, d])
is union of m intervals, thus L f ∈ BV (m).

4.3/ LINEAR RESPONSE

The goal of this section is to provide an introduction to the linear response theory and to enunciate theorem 4.21 ([22]) which we will apply in the study of the one-dimensional Arnold map in the next chapter. To do so we need to introduce the space of Borel signed measure and the associated regularization properties of the convolution, in the same taste of the last section. Most of the proof are standard or contained in [START_REF] Galatolo | Linear response for dynamical systems with additive noise[END_REF], and they will be omitted.

Definition 4.12 . Let BS (S 1 ) be the vector space of the Borel signed measures on S 1 endowed with the Wasserstein-Kantorovich norm defined on BS as

µ W = sup g ∞ ≤1,Lip(g)≤1 S 1 g(x)dµ(x),
where Lip(g) is the best Lipschitz constant of g.

By some abuse of notation, in the following we will identify a measure which is absolutely continuous with respect to the Lebesgue measure with its density.

Remark 4.13 . BS is not complete with respect to • , the completion leads to a distributions space, that is the dual of the space of the Lipschitz function.

Definition 4.14 . Let f, g ∈ BS (S 1 ), we define the convolution f * g ∈ BS (S) 1 as

f * g(A) := S 1 S 1 χ A (x + y)d f (x)dg(y).
Remark 4.15 . If f ∈ BS (S 1 ) is absolutely continuous with respect to λ, then

f * g(t) = S 1 f (t -τ)dg(τ),
and in this case the convolution f * g is a L 1 function.

Definition 4.16 . Let µ be a finite Borel measure with sign on S 1 . The total variation of µ is defined as

µ = µ + (S 1 ) + µ -(S 1 ),
where µ = µ + + µ -is the decomposition of µ as the difference of two positive measures.

The next lemmas provide regularization properties of the convolution, as in the last section.

Lemma 4.17 . Under the above conditions, the following inequality holds:

f * g 1 ≤ ||g|| * || f || 1 Proof. Suppose first that g is positive f * g 1 ≤ sup h ∞ ≤1 S 1 h(t) ( f * g)(t)dt = sup h ∞ ≤1 S 1 h(t) S 1 f (t -τ)dg(τ) dt ≤ sup h ∞ ≤1 S 1 S 1 h(t) f (t -τ)dt dg ≤ S 1 f 1 dg(τ) ≤ f 1 • g(X)
The general case follows by the linearity of the convolution considering g = g +g -and the fact that g -, g + are positive measures.

Lemma 4.18 . Let f ∈ BS (S 1 ) such that f (S 1 ) = 0 and g ∈ L 1 . We have

f * g W ≤ f W • g 1 . (4.3) Lemma 4.19 . Let f ∈ BS (S 1 ), such that f (S 1 ) = 0, g ∈ BV f * g 1 ≤ 2 f W • g BV . (4.4) Lemma 4.20 . Let f ∈ L 1 , g ∈ BV f * g BV ≤ f 1 • g BV . (4.5)
Proof. Let us suppose first that f, g ∈ C 1 (S 1 ). In this case f * g ∈ C 1 and

Var( f * g) = S 1 ( f * g) (t) dt = S 1 f * g (t) dt
and by Lemma 4.17

Var( f * g) ≤ || f || 1 ||g || 1
from which we get directly the statement. Now suppose f ∈ C 1 and g ∈ BV, let us consider as before

g ε ∈ C 1 such that g ε -g 1 ≤ ε and g ε BV = g BV . Now Var( f * g) ≤ Var( f * g -g ) + Var( f * g ) ≤ Var( f * g -g ) + || f || 1 ||g || 1 but Var( f * g -g ) ≤ Var( f )||g -g || ≤ Var( f )
, which is arbitrarily small; hence we proved the partial statement when f ∈ C 1 and g ∈ BV.

Now by approximating f ∈ L 1 by a f ε ∈ C 1 such that f εf 1 ≤ ε and using again Lemma 4.17 we get the full statement.

We are finally ready to state the following linear response result. In the statement, (B w , • w ) play the role of a weak Banach space; considering a weak and a strong space (in this case L 1 ) is a common strategy in many areas of ergodic theory, for instance in the study of Lasota-York inequalities. Please remark that we use the following notation: if A, B are two normed vector spaces T : A → B, we write

T A→B := sup f ∈A, f A ≤1
T f B Theorem 4.21 . Suppose that the family of operators L δ satisfies the following four conditions:

(LR0) f δ ∈ BV(S 1
) is a probability measure such that L δ f δ = f δ for each δ ∈ 0, δ . Moreover there is M ≥ 0 such that f δ BV ≤ M for each δ ∈ 0, δ .

(LR1) (mixing for the unperturbed operator) For each g ∈ BV(S 1 ) with g dm = 0 lim n→∞ L n 0 g|| L 1 = 0.

(LR2) (regularization of the unperturbed operator) L 0 is regularizing from B w to L 1 and from L 1 to Bounded Variation i.e. L 0 : (B w , • w ) → L 1 , L 0 : L 1 → BV are continuous.

(LR3) (small perturbation and derivative operator) There is K ≥ 0 such that

||L 0 -L δ || L 1 →(B w , • w ) ≤ Kδ, and ||L 0 -L δ || BV→V ≤ Kδ. There is L f 0 ∈ V w such that lim δ→0 (L 0 -L δ ) δ f 0 -L f 0 w = 0. (4.6)
Then (Id -L 0 ) -1 : V w → V w is a continuous operator and we have the following linear response formula

lim δ→0 f δ -f 0 δ -(Id -L 0 ) -1 L f 0 w = 0. (4.7)
Thus (Id -L 0 ) -1 L f 0 represents the first-order term in the change of equilibrium measure for the family of systems L δ .

Remark 4.22 . Observe that condition LR0 is always satisfied by systems with additive noise and furthermore, the stationary measure f 0 has a density of bounded variation (see [START_REF] Galatolo | Linear response for dynamical systems with additive noise[END_REF], Lemma 23), which is coherent with the theory developed so far from now.

Moreover by conditions LR1 and LR2 it follows that f 0 is the unique fixed probability measure of L 0 in BS (S 1 ).

We stress on the fact, that condition LR2 (regularization property) is required only for the unperturbed operator L 0 as well as condition LR1 (mixing assumption).

We finally remark, that condition LR1 can be verified via computer-aided proof for a certain class of systems, as we shall see in the next chapter.

4.4/ RATE OF MIXING AND PERTURBATIONS

In concrete applications, see for instance Chapter 6, we need to verify that a families of random systems are mixing in the sense of Assumption LR1 of Theorem 4.21. Hence this assumption must be satisfied in some large set of examples, not in just one. A solution to this problem is to show that if a system is mixing, then there exists an open set of nearby systems which are mixing. In the next subsection we provide the theoretical estimates, and in the next chapter we will make advantage of them to study the rotation number of a family of Arnold maps (see for instance proposition 6.8). These estimates are from [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF] and more details may be found there.

4.4.1/ PERTURBING THE MAP

In this subsection we show that the aforementioned notion of mixing is stable under suitably perturbation. In particular if a given system with additive noise is proved to be mixing, then we can extend the mixing to nearby system, and we provide quantitative estimates in the || || ∞ norm.

||(NL T 1 ) n f -(NL T 2 ) n f || L 1 ≤ 2n T 1 -T 2 L ∞ • ρ BV • f L 1 .
Let us state some preliminary lemmas.

L T 1 ( f ) -L T 2 ( f ) W ≤ T 1 -T 2 L ∞ • f || L 1 .
Lemma 4.26 . Let T 1 and T 2 : [0, 1] → [0, 1] be piecewise continuous nonsingular maps and ρ ∈ BV. Let the associated transfer operators with additive noise given by the kernel ρ be NL T 1 , NL T 2 , then for any f ∈ L 1 it holds

NL T 1 ( f ) -NL T 2 ( f )|| L 1 ≤ 2 T 1 -T 2 L ∞ • ρ|| BV • f || L 1 .
Proof of Proposition 4.24. We have that

(NL T 1 ) n -(NL T 2 ) n = n k=1 (NL T 1 ) n-k (NL T 1 -NL T 2 )(NL T 2 ) k-1 ||(NL T 1 ) n -(NL T 2 ) n || L 1 →L 1 ≤ n||NL T 1 -NL T 2 || L 1 →L 1 .
We can estimate ||NL T 1 -NL T 2 || L 1 →L 1 by Lemma 4.26 we get the statement.

The following corollary shows how to estimate the rate of mixing of a nearby system.

Corollary 4.27 . If ||(NL T 1 ) n f || V→L 1 ≤ α < 1 (4.8) then ||(NL T 2 ) n f || V→L 1 ≤ α + 2n T 1 -T 2 L ∞ • ρ BV .
Indeed Corollary 4.27 implies that, if we have computed n, α for which 4.8 is satisfied for the operator NL T 1 , then all the operators T 2 such that

T 1 -T 2 L ∞ < 1 -α 2n ρ BV (4.9)
are still mixing. We will use the latter equation in Proposition 6.8.

4.4.1.1/ PERTURBING THE NOISE

Another thing we can do, is to provide mixing and mixing rate of a system when the noise distribution is changed: the Fourier-based algorithm that we will present in this thesis can be applied to random dynamical system with additive gaussian noise, i.e. noise with a gaussian kernel. The result of this subsection shows how to recover the mixing rate for the same system with a different noise kernel, with a small perturbation in L 1 .

If ρ 1, ρ 2 ∈ BV are two kernels we denote by N 1 , N 2 the associated convolution operators.

Proposition 4.28 . For each n ∈ N

||(N 1 L) n f -(N 2 L) n f || L 1 ≤ n||ρ 1 -ρ 2 || L 1 || f || L 1 .
Proof. The proof is straightforward

(N 1 L) n -(N 2 L) n = n k=1 (N 1 L) n-k (N 1 L -N 2 L)(N 2 L) k-1 ||(N 1 L) n -(N 2 L) n || L 1 ≤ n||N 1 -N 2 || L 1 →L 1 ≤ n||ρ 1 -ρ 2 || L 1 .
Using Proposition 4.28 we can show how to estimate the rate of mixing of a perturbation with respect to the noise of the operator.

Corollary 4.29 . If ||(N 1 L) n f || V→L 1 ≤ α < 1 then ||(N 2 L) n f || V→L 1 ≤ α + n||ρ 1 -ρ 2 || L 1 .

RIGOROUS FINITE SCHEMES OF APPROXIMATION

In this chapter we introduce two rigorous finite schemes of approximations and their applications; let us emphasize with a list what is, in a nutshell, the core-idea of a rigorous approximation • we choose a finite base of functions of a suitable subspace (for instance in the Ulam method they will be indicator functions as basis of V, the zero-average space of L 1 ), and we compose an infinite dimensional operator L with the projection operator on this base, yielding to a finite dimensional operator, i.e. a matrix L δ

• now we search for a bound on the norm of the iterates of the discretized operator; indeed this kind of bound, which quantifies in a sense the rate of mixing of the operator L δ , implies a bound on the norm of the difference between the stationary density of L and the fixed point of L δ (see lemma 5.6). Furthermore, this bound can be established with a rigorous computation, in particular we will search for an α < 1

and n ∈ N such that L n δ ≤ α.

• all the computation are made in the framework of Interval Arithmetic, and not in floating point arithmetic, which means that the results of our computations are not floating point numbers, but intervals which contain the exact solution to the problem.

If these intervals are really small (and they will be), we can then speak properly of rigorous approximation.

We stress on the fact that since we are working with interval arithmetic, the results of our computations are mathematical statements proved with a computer aided proof, and not simulations. In the next chapter we will briefly introduce interval arithmetic, but let us remark this concept with an example. The latter implies L δ ≤ α, with α = b.

In the following, we first introduce a rigorous Ulam approximation ( [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF]), which yield to a finite stationary density (a vector) and a rigorous (small) error bound on it. Then we introduce a Fourier finite scheme of approximation which gives a rigorous approximation of the Perron-Frobenius operator (i.e. a matrix, with a rigorous error bound on it) with exponential bounds; thus, at least empirically, we should be able to manage system of dimension more than 1, which is not possible with the quadratic bounds of the Ulam approximation. The study of the multidimensional setting will be a future work.

In the next chapters we then describe three original applications, in which we use finite rigorous finite scheme of approximation to investigate (family of) random dynamical systems, using both the Ulam and Fourier approximation (the Ulam-based applications appeared in [44; 48]). Working at the crossroad of mathematics (linear response theory)

and computer science (interval arithmetic) yields not only to concrete results (e.g. we compute up to a certain approximation the Lyapunov exponents of a random system) but also to theoretical results (e.g. the rotation number of the Arnold map is a differentiable map).

5.1/ ULAM APPROXIMATION

In this section we describe part of the work contained in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF] [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF], which is at the core of the thesis, and we will use this framework to present the work of the next section. In particular we will try to explain, without going through all the details (which again, are contained in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF], [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF]), the ingredients of a rigorous computation, so that the reader can be prepared to approach the next section, in which we present a new scheme of approximation (in its entirety).

Setting 5.3 . For the rest of this section, L ξ = N ξ L will be the Perron Frobenius operator of the random dynamical system with additive noise T ξ (see proposition 4.6), and the noise is distributed according to a kernel ρ ξ ∈ BV(M), with support in [-ξ 2 , ξ 2 ]. We also know that there exists a stationary density f ξ , such that L ξ f ξ = f ξ .

In 1960 (see [START_REF] Ulam | A collection of mathematical problems[END_REF]) Ulam introduces a scheme of approximation, which perhaps is still the most popular one, for the discretization of a Perron-Frobenius operator. Definition 5.4 . Let {B 1 , . . . , B k } be a partition of M by a finite number of disjoint sets, let T a non singular transformation over M, then the Ulam's matrix of order k is the matrix (p i j ) = P ∈ M(k, R) whose entries are defined by the following relation

p i j = λ(T -1 (B j ) ∩ B i ) λ(B i ) . (5.1)
The definition above is justified from the fact that one can look at the entries p i j as the probabilities of being mapped from box B i to box B j by the dynamical system T . P is a row-stochastic matrix since the denominator λ(B i ) normalizes the entries and thus P defines a finite Markov chain and has a left eigenvector with eigenvalues 1; whenever or not this eigenvector approximates the invariant measure of the Perron-Frobenius operator associated to T , is an open question, called the Ulam's conjecture, which has been solved, for instance, in the one-dimensional case ( [START_REF] Dellnitz | On the approximation of complicated dynamical behavior[END_REF], [START_REF] Froyland | Approximating physical invariant measures of mixing dynamical systems[END_REF], [START_REF] Li | Finite approximation for the Frobenius-Perron operator. A solution to Ulam's conjecture[END_REF], [START_REF] Murray | Discrete approximation of invariant densities[END_REF]).

Actually the Ulam's method is a Galerkin projection of the Perron-Frobenius operator to the subspace spanned by the functions

ψ i = 1 λ(B i )) χ B 1 .
Someone could ask if using higherorder functions in the Galerkin projection could improve the approximation of the operator:

the answer is that in some case it is convenient, however high order approximations do have the disadvantage that the discretized operator is not, in general, a Markov operator (i.e. a stochastic matrix, [START_REF] Koltai | Efficient approximation methods for the global long-term behavior of dynamical systems -Theory, algorithms and examples[END_REF], Section 3). In [START_REF] Ding | Markov finite approximation of the Frobenius-Perron operator[END_REF] specific Petrov-Galerkin methods which use piecewise first or second order polynomial as bases functions, are able to recover the Markov property for the approximated operator.

Thus let us redefine the Ulam's method as a Galerkin projection, to adapt it to our context. Definition 5.5 . Let M = T n , let I δ = {I j } l j=1 be a δ-partition of M (i.e. for every j, the I j -s are convex and diam(I j ) ≤ δ); given an operator L :

L 1 (M) → L 1 (M) the associated discretized (Ulam) operator is L δ : L 1 (λ) → L 1 (λ) defined by L δ = π δ Lπ δ , where π δ : L 1 (λ) → L 1 (λ) is the projection π δ h(x) = l i=1 E(h|I i ) χ I i .
Thus, our purpose is to study the properties of the discretized operator π δ L ξ π δ ; given the particular nature of L ξ , which is the product of the two operators N ξ and L, for computational purpose we consider the following discretization

L δ,ξ := π δ N ξ π δ Lπ δ = (π δ N ξ π δ )(π δ Lπ δ ).
Indeed with this definition, we compute once and for all the matrix π δ Lπ δ , which is expensive from a computational point of view, but leads to a sparse matrix. We then apply the operator π δ N ξ π δ which is independent of the dynamics. Another reasonable discretization could be π δ N ξ lπ δ , but this definition implies that we must recompute the discretized operator for each size of the noise.

Observe that the invariant measure of L δ,ξ (the eigenvector of eigenvalue 1), f δ,ξ , can be computed up to any precision, because L δ,ξ is a finite operator: hence the problem becomes how to estimate effectively

f δ,ξ -f ξ L 1 .

5.1.1/ BOUNDING THE RATE OF MIXING

Let V be the zero average subspace of L 1 . We start with a very simple but powerful lemma, which explains why it is useful, for our purpose, to have a bound on the norms of the iterates of a Markov operator (see definition 3.7).

Lemma 5.6 . Suppose that there exists n ∈ N and α > 0 such that

L n δ,ξ | V L 1 →L 1 ≤ α < 1, then f ξ -f δ,ξ L 1 ≤ 1 1 -α (L n δ,ξ -L n ξ ) f ξ L 1 . (5.2)
Proof. Since both f ξ and f δ,ξ are fixed points

f δ,ξ -f ξ L 1 = L n δ,ξ f δ,ξ -L n ξ f ξ L 1 + L n δ,ξ f δ,ξ -L n δ,ξ f ξ + L n δ,ξ f ξ -L n ξ f ξ L 1 ≤ L n δ,ξ ( f δ,ξ -f ξ L 1 + (L n δ,ξ -L n ξ ) f ξ L 1 .
(5.3)

Then the claim follows because

f ξ -f δ,ξ L 1 ≤ α f ξ -f δ,ξ L 1 + L n δ,ξ -L n ξ ) f ξ L 1 .
Indeed with the useful lemma we reduce the problem to finding a good upper bound on

(L n δ,ξ -L n ξ ) f ξ L 1 .
The following lemma, via telescopic decomposition, will show that this is equivalent to the study of three quantities, which are way easier to be bounded. Lemma 5.7 . Let L i δ,ξ | V L 1 ≤ C i and let f ξ be an invariant probability measure for L ξ , it holds

L n δ,ξ -L n ξ ) f ξ L 1 ≤ (π δ -1) f ξ L 1 + ( n-1 i=0 C i ) • ( N ξ (π δ -1)L f ξ L 1 + N ξ π δ L(π δ -1) f ξ L 1 ).
(5.4)

Proof. We proceed by telescopic decomposition

L δ,ξ = π δ N ξ π δ -N ξ L = N ξ L -π δ N ξ L + π δ N ξ L -π δ N ξ π δ L + π δ N ξ π δ L -π δ N ξ π δ Lπ δ .
With a similar decomposition on L n δ,ξ = (π δ N ξ π δ L) n π δ , we obtain:

(L n δ,ξ -L n ξ ) f ξ L 1 = ((π δ N ξ π δ L) n π δ -(N ξ L) n ) f ξ L 1 ≤ n i=0 (π δ N ξ π δ L) i (π δ -1)(N ξ L) n-i f ξ L 1 + n-1 i=0 (π δ N ξ π δ L) i π δ N ξ (π δ -1)L(N ξ L) n-i-1 f ξ L 1 = n i=0 (π δ N ξ π δ L) i (π δ -1) f ξ L 1 + n-1 i=0 (π δ N ξ π δ L) i π δ N ξ (π δ -1)L f ξ L 1 .
We can shift the indexes by 1 in the first sum, thus

(L n δ,ξ -L n ξ ) f ξ L 1 ≤ ≤ (π δ -1) f ξ ) L 1 + n-1 i=0 (π δ N ξ π δ L) i π δ | V L 1 →L 1 • N ξ π δ L(π δ -1) f ξ L 1 + n-1 i=0 * π δ N ξ π δ L) i π δ | V L 1 →L 1 • N ξ (π δ -1)L f ξ L 1 = (π δ -1) f ξ L 1 + ( n-1 i=0 C i ) • ( N ξ (π δ -1)L f ξ L 1 + N ξ π δ L(π δ -1) f ξ L 1 ).
Looking at the three terms, it is easy to realize that what we really need to bound are the quantities

(1 -π δ )N ξ L 1 , N ξ (1 -π δ ) L 1 .
The following theorem (5.8), provides these bounds; we report it in its completness since it provides other bounds that may be useful to the reader in other situations. Within lemma 5.7 and lemma 5.6, we can use part of theorem 5.8, to deduce an initial bound on

f δ,ξ -f ξ L 1 .
Theorem 5.8 . Let I δ be a partition of M into convex sets, let π δ be the associated Ulam projection, let I be a finite union of sets from I δ and let N ξ be the convolution operator; then

1. 1 -π δ var→L 1 ≤ δ/2 2. 1 -π δ L 1 →W ≤ δ/2; 3. 1 -π δ var I →W(I) ≤ δ 2 /8 4. N ξ L 1 →var ≤ ξ -1 Var(ρ ξ ) 5. N ξ W→L 1 ≤ ξ -1 Var(ρ ξ ) 6. (1 -π δ )N ξ L 1 ≤ 1 2 δξ -1 Var(ρ ξ ) 7. N ξ (1 -π δ ) L 1 ≤ 1 2 δξ -1 Var(ρ ξ ).
Lemma 5.9 . If there exist n, α < 1 such that

L n δ,ξ | V L 1 ≤ α < 1 then if 0 ≤ C i ≤ 1 are such that L i δ,ξ L 1 ≤ C i , we have f δ,ξ -f ξ L 1 ≤ 1 + 2 n-1 i=0 C i 2(1 -α) δξ -1 Var(ρ). (5.5)
Proof. Theorem 5.8 implies that

N ξ (1 -π δ ) L 1 →L 1 ≤ 1 2 δξ -1 Var(ρ) (1 -π δ )N ξ L 1 →L 1 ≤ 1 2 δξ -1 Var(ρ).
We observe that on the right hand side of 5.4 all the items have either N ξ (1 -π δ ) or

(1 -π δ )N ξ . Indeed since f ξ L 1 ≤ 1, (π δ -1) f ξ L 1 = (π δ -1)N ξ L f ξ L 1 ≤ 1 2 δξ -1 Var(ρ),
and similarly for the other summands. Finally applying 5.6 we get the statement.

5.1.2/ STRONGER BOUNDS AND COARSE-FINE STRATEGY

Usually we are going to work with large matrices, hence it would be useful to compute some of the properties of these matrices (for instance its rate of mixing) on smaller matrices. Indeed, if the noise has already been applied to the deterministic system, this is possible; the following lemma, which bounds the distance between the powers of L ξ and L δ,ξ (provided that the noise has been applied at least once), yields to a bound on the contraction rate of a certain operator using the computed contraction rate of a coarser one.

Furthermore, assuming some regularity on the deterministic map T , it is possible to strengthen the previous bounds via a coarse-fine strategy.

This strategy depends from several estimates, and we will resume them without reporting their proof, which can be found in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF]; please remark, that we will develop a similar strategy (in a different taste) in the next section, in the Fourier context, and there we will provide the full details.

Lemma 5.10 .

Let L i δ,ξ | V L 1 ≤ C i ; let σ be a linear operator such that σ L 1 ≤ 1, σ 2 = σ and σπ δ = π δ σ = π δ ; let Λ = σN ξ σL. Then for all n ≥ 0 (L n δ,ξ -Λ n )N ξ L 1 ≤ δ ξ • (2 n-1 i=0 C i + 1).
In particular the hypothesis are satisfied if

1. σ = Id and Λ = L ξ 2. σ = π δ and Λ = L δ ,ξ .
Proof. Since σgπ δ g = σ(1 -π δ )g, applying theorem 5.8, we have

σg -π δ g L 1 ≤ Var(g)δ/2, σg -π δ g W ≤ g L 1 δ/2.
Then we have

(L n δ,ξ -Λ n )N ξ L 1 ≤ (π δ N ξ π δ L) n L 1 • (π δ -σ)N ξ L 1 + n-1 i=0 (π δ N ξ π δ L) i L 1 (π δ -σ)N ξ L 1 • (σLσN ξ ) n-i L 1 + n-1 i=0 (π δ N ξ π δ L) i π δ L 1 • N ξ (π δ -σ) L 1 • LσN ξ (σLσN ξ ) n-i-1 L 1 ≤ (π δ -σ)N ξ L 1 + n-1 i=0 C i (π δ -σ)N ξ L 1 • (σLσN ξ ) n-i L 1 + n-1 i=0 C i N ξ (π δ -σ) L 1 • LσN ξ (σLσN ξ ) n-i-1 L 1 , (5.6)
and the thesis follows because

L L 1 ≤ 1, N ξ L 1 ≤ 1 and σ L 1 ≤ 1.
The estimate given at 5.9 depend on the ratio δξ -1 and is obtained only with the information about the approximated transfer operator L δ,ξ (in particular its contraction rate). In order to obtain stronger bounds we need to assume some regularity of the deterministic part T .

Setting 5.11 . In this subsection, the map T is assumed to be piecewise C 1+γ , γ > 0, and monotonic on a partition {C j } of [0,1]. If we denote T i = T |C i , then for each density g ∈ L 1 (M) we denote by L i g = L(gχ i ) the component of Lg coming from the i-th branch, in order to have

Lg = i Lg.
We can now use theorem 5.8 and the regularity of T to give better bounds on the terms appearing in 5.4.

Theorem 5.12 . Each term in 5.4 admit a bound of the form

A i f ξ -f L 1 + B i ,
for i = 1, 2, 3. This implies the following bound

f ξ -f L 1 ≤ 1 1 -D • ( f δ,ξ -f L 1 ) + C .
Proof. The three bounds for each term of 5.4 will be proven in the next three lemmas.

Plugging these estimates in 5.4 lead to

(L n δ,ξ -L n ξ ) f ξ L 1 ≤ A • f ξ -f L 1 + B,
where

A = A 1 + (A 2 + A 3 ) n-1 i=0 C i B = B 1 + (B 2 + B 3 ) n-1 i=0 C i .
If C = A/(1 -α) and D = B/(1 -α) (where α comes from 5.6), using 5.2 we obtain

f ξ -f δ,ξ L 1 ≤ C + D • f ξ -f L 1
and then

f ξ -f L 1 ≤ f δ,ξ -f L 1 + C D • f ξ -f L 1 which implies f ξ -f L 1 ≤ 1 1 -D • ( f δ,ξ -f L 1 + C).
For the sake of completeness we report the constants A i , B i , and we remark again that they are taken from [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF].

•

A 1 = δ 2 ξ -1 Var(ρ) and B 1 = δ 2 Var(N ξ L f ) • A 2 = δ 2 Var(ρ ξ ) and B 2 = δ 2 Var(ρ ξ ) I∈Π i min δ 4 , Var I (L i f ), L i f L 1 (I) • A 3 = δ 2 ξ -1 Var(ρ) • B 3 = I∈Π min δ 2 8 ξ -1 Var(ρ) • T L ∞ (I) , δ 2 Var I (N ξ L f ) + δ 2 4 ξ -1 Var(ρ) • Var(N ξ L f ).
Please remark that in the second and third item Π is a uniform partition of [0, 1] whose parts have size that is an integer multiple of δ and T is piecewise monotonic with L i defined above.

5.2/ FOURIER APPROXIMATION

The Ulam method proposed in the last section is not suitable to work with multidimensional systems, because the size of the matrices involved becomes too large to be handle. Moreover, one of the advantage of the Ulam method, which is that it does not require regularity of the map, it is also its disadvantage, since this does it means also that the Ulam method cannot exploit the regularity of the map if there is any. The idea is then to switch bases of function and instead of considering characteristic functions, we will consider the classic Fourier basis; the regularity of the system will come from the convolution with the noise, that we suppose, in this section, to have a Gaussian kernel. As we will see, this approach, which is slightly different from a computational point of view from the Ulam one, leads to exponential bounds, which are exactly what we want in the perspective of a multidimensional applications. This is a work in progress: here we present the theoretical bounds and in the last chapter we will see an application of this method; further examples will be presented in [START_REF] Marangio | A posteriori validated numerical method for the computation of stationary measures based on Fourier approximation[END_REF].

Let us introduce this new setting.

Let ∞ be the space of bilateral bounded sequences and let F be the operator

F ( f )[k] = S 1 f (x)e -2kπix dx.
This operator, is a version of the well known Fourier transform.

Lemma 5.13 . The operator F is continuous from L 1 to ∞ and

||F || L 1 → ∞ = 1.
Proof. Since |e 2kπix | = 1 we have that for all k:

|F ( f )[k]| = | S 1 f (x)e -2kπix dx| ≤ S 1 | f (x)||e 2kπix |dx ≤ || f || L 1 .
To simplify the notations, let γ σ = 1 √ 2πσ 2 and let ρ σ (x) = γ σ e -x 2 2σ 2 . These constants will appear through the rest of this section.

Let f ∈ L 1 and let N σ f be the convolution of ρ σ with the periodic extension of f , i.e.

N σ f = ρ σ * f = +∞ j=-∞ 1 0 ρ σ (x + j -y) f (y)dy,
By definition N σ f is a periodic function and ∀x ∈ S 1 we have that

N σ f (x) ≤ 2 +∞ j=0 ρ σ (x + j)|| f || L 1 ,
which we can bound uniformly by

2|| f || L 1 +∞ j=0 ρ σ ( j),
since the sum is upper bounded, for instance, by ∞ 0 ρ σ < +∞.

The following lemma explains the relationship between the Fourier transform and the operator N σ . Lemma 5.14 . There exists an operator D σ : ∞ → ∞ such that

D σ F = F N σ
Proof. By direct computation we have

F N σ f (x) = 1 0 +∞ j=-∞ 1 0 f (x -y)ρ σ (y + 2k j)dye -2kπix dx.
Since the series in the integral is uniformly bounded, the integral above is equal to

+∞ j=-∞ 1 0 1 0 f (x -y)ρ σ (y + 2k j)e -2kπix dydx. Let z = x -y then +∞ j=-∞ 1 0 1 0 f (z)ρ σ (y + 2k j)e -2kπi(z-y) dydx = +∞ j=-∞ 1 0 1 0 f (z)e -2kπiz ρ σ (y + 2k j)e +2kπiy dydz = 1 0 f (z)e -2kπiz dz +∞ j=-∞ 1 0 ρ σ (y + 2k j)e +2kπiy dy.

Which implies that

D σ e j = 1 0 ρ σ (y + 2k j)e 2kπiy dye j = e -k 2 σ 2 2 e j .
Indeed, we have something stronger:

Corollary 5.15 . Let exp = {(a k ) k∈Z | a k ≤ Ce -|k| }.
Then D σ maps ∞ into exp .

Proof. Since each sequence in ∞ is bounded, this follows from the fact that e -k 2 σ 2 2 decays exponentially. Now recall (it is a standard result in Fourier analysis) that if a sequence belongs to exp , then the associated Fourier series converges uniformly to an analytic function.

Theorem 5.16 . Let {a k } k∈Z be a sequence in exp . Then

F -1 ({a k }) = +∞ -∞ a k e 2πix
converges uniformly to an analytic function. Moreover, if f is in L 2 , we have that

F -1 F ( f ) = f .
We are now ready to define the projection π of a function over a finite Fourier basis, and to exploit the properties of π in relation to the operators F and D σ .

Definition 5.17 . Let π k : L 1 → L ∞ be defined as

π k f = k j=-k 1 0 f (x)e -2iπ jx dx e -2iπ jx = k j=-k F ( f )[ j]e -2iπ jx .
Definition 5.18 . We denote by πk : ∞ → ∞ the operator that sends {a j } j∈Z to the sequence

{b j } j∈Z such that b j = a j for | j| ≤ k, b j = 0 for | j| > k.
Lemma 5.19 . The following are true 1. D σ commutes with πk and (1πk ),

2. F -1 πk F = π k f.
Remark 5.20 . Since it has only a finite number of Fourier coefficients, the convergence of

F -1 πk F f is trivial.
As we already saw in the last section, a central role is played by the quantities,

||N σ (1-π k )||
and ||(1 -π k )N σ ||, and our goal is to bound them. We have now all the tools to prove the following theorem, which provides exponential bounds. k ; the following are true

1. ||N σ (1 -π k )|| L 1 →L ∞ ≤ 2 +∞ j=k e -j 2 σ 2 2 ≤ Γ σ,k , 2. ||(1 -π k )N σ || L 1 →L ∞ ≤ 2 +∞ j=k e -j 2 σ 2 2 ≤ Γ σ,k .
Proof. We prove the first item; we proceed with a formal computation, which will be proved to be well defined then, by showing that F -1 is defined.

3N σ (1 -π k ) = F -1 F N σ (1 -π k ) = F -1 D σ F (1 -π k ) = = F -1 D σ (1 -πk )F . Since D σ maps ∞ into exp we have that F -1 D σ (1 -πk )F f is an analytic function whose
Fourier coefficients are such that a j = 0 for | j| ≤ k and

|a j | ≤ || f || L 1 e -j 2 σ 2 2
for |i| > k. This proves also that

||N σ (1 -π k )|| L 1 →L ∞ = ||F -1 D σ (1 -πk )F || L 1 →L ∞ ≤ 2 +∞ j=k e -j 2 σ 2 2 ≤ e -k 2 σ 2 2 kσ √ 2π = Γ σ,k .
Observe now that

(1 -π k )N σ = F -1 F (1 -π k )N σ = F -1 (1 -πk )D σ F = F -1 D σ (1 -πk )F
hence the proof can be adapted also to the second item.

5.2.1/ BOUNDING THE RATE OF MIXING

In this section we do the analogous of what we did for the Ulam method, in a new taste, using the new bounds we just obtained.

We start by proving the following lemma.

Lemma 5.22 .

π k N σ π k Lπ k = π k N σ Lπ k
Proof. Let use the Fourier transform,

π k N σ π k Lπ k = F -1 F π k N σ π k Lπ k = F -1 πk D σ πk F Lπ k = F -1 πk πk D σ F Lπ k = F -1 πk D σ F Lπ k = π k N σ Lπ k .
We used that D σ commutes with πk and π2 k = πk .

To proceed in our treatment, we need a bound on the quantity Nπ k , provided by the next lemma.

Lemma 5.23 .

||N σ π k || L 1 = ||π k N σ || L 1 ≤ 1 + Γ σ,k
Proof. We observe that

π k N σ = N σ + (π k -1)N σ .
Then

||π k N σ || L 1 = ||N σ || L 1 + ||(π k -1)N σ || L 1 ≤ 1 + Γ σ,k ,
where we used

||(1 -π k )N σ || L 1 ≤ ||(1 -π k )N σ || L 1 →L ∞ .
Thus if we consider f σ , the fixed point of L σ this implies the following corollary.

Corollary 5.24 .

||π k f σ || L 1 = ||π k N σ L f σ || L 1 ≤ 1 + Γ σ,k || f σ || L 1 Lemma 5.25 . ||(L n σ,k -L n σ ) f σ || L ∞ ≤ N-1 i=0 C i 1 + Γ σ,k + ||ρ σ || ∞ Γ σ,k
Proof. We start by observing:

(π k N σ Lπ k -N σ L) f σ = (π k N σ Lπ k -N σ Lπ k + N σ Lπ k -N σ L) f σ ,
which gives us

(1 -π k )N σ Lπ k f σ -N σ L(1 -π k ) f σ
that can be estimated using

||(1 -π k )N σ || L 1 →L ∞ ≤ Γ σ,k which implies ||(1 -π k )N σ Lπ k f σ || L ∞ ≤ 1 + Γ σ,k Γ σ,k ,
and the fact that

||(1 -π k ) f σ || L 1 ≤ ||(1 -π k )N σ L f σ || L ∞ ≤ Γ σ,k
which implies that

||N σ L(1 -π k ) f σ || ∞ ≤ ||ρ σ || ∞ Γ σ,k .
With a telescopic argument we obtain

L n σ,k -L σ = N-1 i=0 L i σ,k (L σ,k -L σ )L N-i-1 σ So, thanks to L σ f σ = f σ we have || N-1 i=0 L i σ,k (L σ,k -L σ )L N-i-1 σ f σ || ∞ ≤ N-1 i=0 C i 1 + Γ σ,k + ||ρ σ || ∞ Γ σ,k
Lemma 5.26 . Let f σ be the unique fixed point of L σ and f σ,k be the unique fixed point of

L σ,k .
Then

|| f σ -f σ,k || ∞ ≤ 1 1 -α N-1 i=0 C i 1 + Γ σ,k + ||ρ σ || ∞ Γ σ,k
Proof. This follows from

|| f σ -f σ,k || ∞ ≤ ||L n σ,k ( f σ -f σ,k )|| ∞ + ||L n σ,k -L n σ f σ || L ∞ .
So far from now, we obtained an effective way to bound the quantity || f σf σ,k || ∞ , which was our purpose. Let us prove, again, a coarse-fine inequality; as we already explained this kind of inequalities are extremely useful during the computations.

Lemma 5.27 .

||(L n σ,k -L n σ,k )N σ || L 1 →L ∞ ≤ n-1 i=0 C i 1 + ||ρ σ || ∞ + Γ σ,k + Γ σ,k Γ σ,k 1 + Γ σ,k n
Proof. We may use again a telescopic decomposition

(L n σ,k -L n σ,k )N σ = n-1 i=0 L i σ,k (L σ,k -L σ,k )L n-i-1 σ,k N σ .
We already proved that

||(1 -π k )N σ || L 1 →L ∞ ≤ Γ σ,k ,
which in turn implies that

||π k N σ f || L 1 ≤ ||N σ f || L 1 + ||(1 -π k )N σ f || L 1 ≤ || f || L 1 + ||(1 -π k )N σ f || L ∞ ≤ 1 + Γ σ,k || f || L 1 .
We rewrite now

(π k N σ Lπ k ) j N σ = π k N σ (Lπ k N σ ) j .
The computation above implies that

||(Lπ k N σ ) j || L 1 ≤ 1 + Γ σ,k j+1 .
We observe now that π k π k = π k . We bound now

(L k,σ -L k ,σ )π k N σ = π k N σ Lπ k N σ -π k N σ Lπ k N σ = π k N σ Lπ k N σ -π k N σ Lπ k N σ + π k N σ Lπ k N σ -π k N σ Lπ k N σ .
We observe that

||(π k -π k )N σ || L 1 ≤ ||(π k -π k )N σ || L 1 →L ∞ ≤ Γ σ,k
Then

||π k N σ Lπ k N σ -π k N σ Lπ k N σ || L 1 →L ∞ ≤ ||(π k -π k )N σ || L 1 →L ∞ ||L|| L 1 ||π k N σ || L 1 ≤ Γ σ,k 1 + Γ σ,k and
||π k N σ Lπ k N σ -π k N σ Lπ k N σ || L 1 →L ∞ ≤ ||π k N σ || L 1 →L ∞ ||L|| L 1 ||(π k -π k )N σ || L 1 ≤ (||N σ || L 1 →L ∞ + ||(1 -π k )N σ || L 1 →L ∞ )Γ σ,k ≤ ||ρ σ || ∞ + Γ σ,k Γ σ,k

5.2.2/ ERROR BY USING THE DFT

The Fourier transform of course cannot be exactly implemented in a laptop, anyway we may use the Discrete Fourier Transform instead, which provides a fast way (thanks to the FFT algorithm, Fast Fourier Transform) to compute an approximation of the Fourier coefficients we want. Thus, we need to take care of the error we are making by using a FFT of order say N, to compute a coefficient of order k << N. We end this section providing an exponential bound on the so-called aliasing error, i.e. the difference between a Fourier coefficient and the same coefficient computed via DFT.

Lemma 5.28 . Let f ∈ BV, let {x i } N-1 i=0 be equispaced points on S 1 ; consider the two coefficients

X k = N-1 n=0 f ( n N )e -2πikn/N and f (k) = F f (x)e -2πikx
Then we have that

|X k -f (k)| ≤ 2 +∞ p=1 e -(k+pN) 2 σ 2 2 ≤ Γ σ,N (5.7)
Proof.

X k = 1 N N-1 n=0 ∞ j=-∞ f (i)e 2 jπin/N e -2kπin/N = 1 N ∞ j=-∞         N-1 i=0 e 2 jπin( j-k)/N        
Now, the sum into parenthesis is different from 0 only when jk is a multiple of N.

Therefore

X k = +∞ p=-∞ f (k + pN) = f (k) + +∞ p=1 f (k + pN) + f (k -pN).
We can choose N such that f (k + N) is really small, since our Fourier coefficients decay fast. We have indeed

|X k -f (k)| ≤ 2 +∞ p=1 e -(k+pN) 2 σ 2 2 ≤ Γ σ,N

III

EXPERIMENTS AND RESULTS

APPLICATIONS

In this chapter and in the last section of chapter 7 we will apply the rigorous schemes of approximation described so far, to three significative examples. The first two dynamical systems under consideration belong to the family of the so-called Arnold Maps ( [START_REF] Liberalquino | Chaotic Itinerancy in Random Dynamical System Related to Associative Memory Models[END_REF], [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF]), and they comes from two different natural phenomena; indeed Arnold's standard circle maps are widely used to study the quasi-periodic route to chaos. We will use the first one as an introductory example to the Ulam method, explaining how the theory made so far, is being applied in a concrete example. We will turn then to a more complicated example, in which rigorous computations, co-aided by linear response theory, will led to non-trivial results, such as the differentiability of the rotation number. Arnold's standard circle maps are widely used to study the quasi-periodic route to chaos and other phenomena associated with nonlinear dynamics in the presence of two rationally unrelated periodicities.

Finally in the last example we apply the Fourier scheme of approximation (section 5.2) to a perturbed doubling map; as we said before this is a work in progress and many, more meaningful, other examples will be produced in the future. Still, even in this easy but non trivial case, we can appreciate the power of the Fourier method, obtaining bounds of the order of 10 -80 . We choose to report this last example at the end of the numerical discussion of the Fourier algorithm, 7.2.3.

6.1/ ASSOCIATIVE MEMORY IN THE HIPPOCAMPUS AS RANDOM DYNAMICAL SYSTEM

The first example that we want to study is a random dynamical system T ξ , with a deterministic component given by an Arnold circle map (see Figure 6.2) and a stochastic part given by a random additive noise, defined as This map was proposed in [33; 57] as a model of the evolution of a macrovariable, related to the activity of an asynchronous neural network in absence of external stimulus, related to a rule of successive association of memory. Indeed a macrovariable, related to the "activity" of the network (see Figure 6.1), was observed to evolve as a noisy one dimensional map in the case that the network receives no external stimulus (its definition of can be found in [START_REF] Tsuda | Memory dynamics in asynchronous neural networks[END_REF] (p. 6).). This was regarded in [START_REF] Tsuda | Dynamic link of memory. Chaotic memory map in nonequilibrium neural networks[END_REF] as related to a rule of successive association of memory, exhibiting chaotic dynamics.

x n+1 = T (x n ) + ξ n (mod 1), where T (v) = v + A sin(4πv) + C, (6.1)
We recall that the Perron-Frobenius operator associated to this system is given by L ξ = N ξ L, where N ξ is a convolution operator and L is the Perron-Frobenius operator of T .

N ξ f (t) = ξ -1 ξ/2 -ξ/2 f (t -τ). (6.2)
As explained in the lasts chapters, this operator admits an invariant probability density in L 1 , which can be rigorously approximated. We want to compute, up to some error, this density, using lemma 5.7, lemma 5.9 and theorem 5.12; we recall that in these statements there are bounds which depend from properties of the discretized operator, e.g. its rate of mixing. Since the discretized operator is a matrix, we can rigorously compute via interval arithmetics these quantities, leading to rigorous bounds on the error on the computed stationary density (lemma 5.7). All the algorithm and the numeric details are reported in the next chapter.

If we apply this black box described so far, we obtained data summarized in Table 6.1, 6.2; in figure 6.3d, 6.4d, you may see the plot of the computed stationary densities. In the tables, • ξ is the size of the noise

• n contr and α contr are such that L n contr δ ,ξ ≤ α contr , these are the bounds obtained on a coarser partition δ

• via coarse-fine strategy we obtain the bounds for the finer partition: α, and the related C i

• finally l1apriori and l1err, are the bounds on the L 1 error.

Remark 6.1 . The images below show a rigorous estimate of the density of probability of visits of typical trajectories near the attractors, showing that this is relatively high with respect to the density of probability of visits in other parts of the space. In particular we can observe that the trajectories concentrate in certain "weakly attracting" and "low chaotic" regions of the space.

The presence of these "weakly attracting" and "low chaotic" regions is in concordance with the concept of chaotic itinerancy, a concept which still did not have a complete mathematical formalization. The results presented in this section aim to bring some light on this concept, which is so widely used in the applied literature: chaotic itinerancy is used to refer to a dynamical behavior in which typical orbits visit a sequence of regions of the phase space called "quasi attractors" or "attractor ruins" in some irregular way. This behavior was observed in several models and experiments related to the dynamics of neural networks and related to neurosciences. We invite the reader to consult [START_REF] Tsuda | Chaotic Itinerancy[END_REF] for a wider introduction to the subject and to its literature. Here τ := 2π/ω and ω := ω i /ω e is the driving frequency, while ≥ 0 parameterizes the magnitude of nonlinear effects. By Arnold map with additive noise we mean the stochastic process {X n } n∈N on S 1 defined by

ξ
X n+1 = T τ, (X n ) + Ω n mod 1. (6.4)
At each iterate of T τ, (x), an independent identically distributed (i.i.d.) noise Ω n , that is uniformly distributed on [-ξ/2, ξ/2], is added to the deterministic term on the right-hand side of equation 6.4; in particular, the noise is independent of the point X n ∈ S 1 .

In the case = 0, ξ = 0, the system is simply a rotation of the circle. In the deterministic case, where ξ = 0, and ∈ (0, 1) we get the classical Arnold circle map, which is one of the most used models in several scientific areas: models of coupled oscillators [60; 38], model for cardiac arrhythmias [61; 28] or sleep-wake regulation cycle [START_REF] Bailey | Circle maps with gaps: Understanding the dynamics of the two-process model for sleep-wake regulation[END_REF].

In the deterministic case, one of the most remarkable feature of this model is the modelocking phenomenon, but let us first introduce the concept of rotation number. Let us recall two general classical results about the properties of the rotation number, in the particular case of deterministic and orientation-preserving diffeomorphism of the circle; for further details we refer to [30; 37].

• the rotation number is independent of x ∈ S 1 .

• the Denjoy theorem : it states that an orientation-preserving diffeomorphism (for our maps T τ, this corresponds to the weakly nonlinear case < 1) having an irrational rotation number is topologically conjugate to an irrational rotation in S 1 (see [37; 62]).

Something surprising happens around the rational values of the driving frequency: the rotation number is locally constant. In other words: the map "rotation number vs driving frequency" is a devil's staircase (see Fig. 6.5 for one example). Furthermore the graph of the rotation number seems to go through a "smoothing" process, i.e the map τ → ρ τ becomes smooth.

In the case ∈ (0, 1) (what we called weak nonlinearity), this was rigorously proved in [START_REF] Zmarrou | Bifurcations of stationary measures of random diffeomorphisms[END_REF]. Hence we may ask wether or not the map ρ τ admits a derivative with respect to the parameter τ. A classical result asserts that this derivative is defined in a point τ 0 when the corresponding rotation number is irrational (ρ τ 0 Q) [START_REF] Herman | Mesure de Lebesgue et nombre de rotation[END_REF])); other results can be found in [START_REF] Matsumoto | Derivatives of the rotation number of one parameter families of circle diffeomorphisms[END_REF], [START_REF] Luque | Computation of the derivatives of the rotation number for parametric families of circle diffeomorphisms[END_REF].

If > 1, i.e. in the case of strong nonlinearity, the methods of [START_REF] Zmarrou | Bifurcations of stationary measures of random diffeomorphisms[END_REF] cannot work. As in the diffeomorphism case we can numerically observe that the action of the noise makes the rotation number smoother. In [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF], with the methods illustrated so far from now, it was proved that

• the rotation number is differentiable at every value τ for which the system is mixing (and the existence of intervals for which this assumption is verified is proved as well); this was done by using linear response theory, in particular theorem 4.21 and using the Ulam algorithm for the rigorous computation of the rate of mixing

• the rotation number is not always monotonic. Here a certified approximation of the stationary measure, with a small error on L 1 , leads to a certified estimate on the rotation number.

In the next sections we are going to review these results, showing the effectiveness and the power of our rigorous computations.

L δ : L 1 → L 1 is given by [L δ f ](t) = [ρ ξ * L T δ ( f )](t). (6.6)
We start now to verify the assumption of theorem 4.21, this is done in the following two lemmas. Assumption LR1 will be computationally verified, and we are going to show it at the end of the section.

Lemma 6.3 . The limit defined at (4.6) exists in BS and the limit converges in the W-norm.

lim δ→0 (L 0 -L δ ) δ f 0 - [δ -ξ -δ ξ ] 2ξ * L T 0 ( f 0 ) W = 0.
Proof. We remark that L T 0 ( f 0 ) ∈ L 1 (S 1 ) furthermore

L 0 f 0 (t) = [ρ ξ * L T 0 ( f 0 )](t) = S 1 ρ ξ (t -τ)[L T 0 ( f 0 )](τ)dτ and
L δ f 0 (t) = [ρ ξ * L T δ ( f 0 )](t) = S 1 ρ ξ (t -τ)[L T 0 ( f 0 )](τ -δ)dτ = S 1 ρ ξ (t -c -δ)[L T 0 ( f 0 )](c)dc hence L δ -L 0 δ f 0 (x) = S 1 ρ ξ (t -δ -τ) -ρ ξ (t -τ) δ [L T 0 ( f 0 )](τ)dτ. (6.7)
moreover we need to verify that there exists an interval on which assumption LR1 of theorem 4.21 is true. For the first fact, we report the following proposition from [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF], but this result was already in [START_REF] Zmarrou | Bifurcations of stationary measures of random diffeomorphisms[END_REF]. Proposition 6.6 . Let T τ, be the Arnold map with parameters (τ, ) and uniformly distributed noise of size ξ, suppose the system satisfies the assumption LR1, let µ τ be the corresponding stationary measure and ρ τ be the associated rotation number. Then

ρ τ (ω, x) = S 1
ϕ τ dµ τ . (6.10)

In particular, ρ τ is P ⊗ µ τ almost surely constant.

Hence, so far from now, we have shown that Corollary 6.7 . The rotation number of the Arnold maps with uniformly distributed additive noise is differentiable at each value of the parameter τ for which the associated system is mixing (in the sense stated in assumption LR1 and Proposition 6.5). Furthermore if τ 0 is such a parameter we get the following formula for the derivative of the rotation number

computed at τ 0 [ d dτ ρ τ ](τ 0 ) = 1 + S 1 ϕ τ 0 d[(Id -L τ 0 ) -1 [δ -ξ -δ ξ ] 2ξ * L T τ 0 (µ τ 0 )] (6.11)
where L T τ 0 , is the pushforward operator of the map T τ 0 , .

Proof. By Proposition 6.6 the rotation number is the integral of a Lipschitz observable.

Considering the increment of ρ τ we get

ρ τ (τ 0 -h) -ρ τ (τ 0 ) h = 1 h S 1 ϕ τ 0 +h dµ τ 0 +h - S 1 ϕ τ 0 dµ τ 0 = 1 h S 1 ϕ τ 0 +h dµ τ 0 +h - S 1 ϕ τ 0 dµ τ 0+h + 1 h S 1 ϕ τ 0 dµ τ 0 +h - S 1 ϕ τ 0 dµ τ 0 . Here 1 h S 1 ϕ τ 0 +h dµ τ 0 +h - S 1 ϕ τ 0 dµ τ 0+h = S 1 ϕ τ 0 +h -ϕ τ 0 h dµ τ 0+h = 1 and 1 h S 1 ϕ τ 0 dµ τ 0 +h - S 1 ϕ τ 0 dµ τ 0 = S 1 ϕ τ 0 d[ µ τ 0 +h -µ τ 0 h ]
and the statement directly follows from Proposition 6.5.

We will now compute an explicit example of case in which the system is mixing and (6.11)

holds. As already pointed out in chapter 4 when considering a family of systems (as in this case), it is not sufficient to provide the rate of mixing of just one of them. This is why we provided results about the rate of mixing of a perturbed system (section 4.4), and we are going now to use them: we use the Ulam-based strategy of chapter 5 to verify assumption LR1, i.e to find n and α such that

||L n ξ || V→L 1 ≤ α < 1, (6.12)
and we take advantage of section 4.4 to deduce that this assumption is satisfied by nearby systems. Proof. Suppose we have proved the mixing for a system with parameters ( 0 , τ 0 , ξ 0 ) and we have α and n such that (6.12) is satisfied, then (4.9) implies that there exists θ 0 > 0 and a whole interval I 0 = [τ 0 -θ 0 , τ 0 + θ 0 ], such that all the systems with parameters ( 0 , τ, ξ 0 ), τ ∈ I 0 , are still mixing. Moreover (4.9) gives an explicit formula for θ 0 which depends from α and n. These constants are explicitly computable, hence we can explicitly compute θ 0 .

To show that the mixing property holds for every system of parameters (1. it is well known that if τ 2 > τ 1 then ρ τ 2 > ρ τ 1 (see [START_REF] Wiggins | Introduction to Applied Dynamical Systems and Chaos[END_REF]). This is false if > 1 and we are going to show it now for a particular example with = 1.4 and ξ = 0.01.

Again we can rigorously approximating the value of the rotation number for several values of τ, since it can be computed as the integral of a Lipschitz observable with respect to the (rigorously) computed stationary measure. Indeed, there exist τ 1 < τ 2 with corresponding rotation numbers ρ 1 ∈ I 1 , ρ 2 ∈ I 2 , where I 1 and I 2 are the rigorous computed intervals in which the rotation numbers lie, and furthermore, these intervals are such that max(I 2 ) < min(I 1 ). We conclude that ρ 2 must be smaller then ρ 1 . Proposition If we compute the powers by successive multiplications using, single, doubling or extended precision (this was done by Rump on an IBM 370 system), we obtain

• single precision: f = 1.17260361 . . .

• double precision: f = 1.17260394005317847 . . .

• extended precision: f = 1.17260394005317863185 . . .

The correct result is f = -0.827396 . . ., not even a positive number.

This example shows us how, a priori, we cannot trust numerical simulations based on floating point arithmetic. This is normal, for who is used to the scientific simulations:

roundoff error can destroy a numerical simulation. A possible solution to this problem is to represent intervals instead of numbers, a bit like the polygonal approximations of Archimede for π; in this way, the result of a numerical calculation, it will be an interval, instead of a number, and not an ordinary interval, but an interval that contains the exact solution of our problem.

The idea behind this method, just stated, is quite clear; however, it is clear that the goodness of this strategy depends strictly on the ability to obtain a very small interval at the end. The Fourier based method presented in this thesis, is able to obtain errors of the order of 10 -86 (in the next section we will specify what we mean by error, since the final error in our situation does not arise just from the computation itself, you must take in account the error coming from the discretization of the transfer operator, for instance, for which we developed bounds in the last chapters).

We have already mentioned the packages used in our algorithms, and we will talk about some aspects of them later; as for the theory underlying the interval arithmetic (algebraic properties, interval functions and so on) we refer to [START_REF] Moore | Introduction to Interval Analysis[END_REF].

Before starting the study of the algorithms, let us remember what these algorithms do and what are the errors that come into action, to which we must be careful. In a nutshell

• Input : map T , size of the noise ξ, size of the discretization δ, size of a coarser discretization δ

• Output: a function v and a number ; v is represented by the vector of its basis coefficients and if f is the stationary density of the system, then fv ≤ , for some suitable norm.

The intermediate steps, will then serve to calculate a discretization of the transfer operator, calculate its fixed point v, and its bound on the error, . As we pointed out before, we have three sources of error, we must take in account:

• Discretization error: we project the transfer operator on a finite base, thus there is an error on the output coming from this discretization process

• Approximation error: the discretization of the transfer operator is a finite linear dimensional operator which we represent with a matrix that cannot be exactly computed; hence we have an error on the output coming from this approximation.

• Eigen error: the error coming from the numerical computation of the eigenvector.

The third part is somewhat a solved problem: given a matrix, we may compute rigorously its steady vector, and the bound on the error depends from the machine epsilon, which can be arbitrarily increase up to any reasonable level. We refer to the section 8.3 of [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF].

Hence in the next sections, providing the full details and the pseudocode for the Fourier based method, we will describe the algorithms for the computation of the aforementioned approximation of the stationary density and the relative bounds on the error, with the respect to the "true" stationary density.

To obtain the matrix Pk , we are going to use a markovization process: compute the sum of the elements on each row, subtract 1 and spread the result uniformly on each nonzero elements of the row. In this way we have that for every i, j

| Pi j -P i j | < 2 × ,
where it was already defined (and computed) as the maximum of the errors | P i j -P i j |. If nz i is the number of nonzero elements of the i-th row and nz = max i nz i , we have

P k -Pk 1 < 2 × nz × .
This process will ensure that the biggest eigenvalue of Pk is 1. We will now move to the estimation of the errors.

7.1.2/ BOUNDING THE ERRORS

Let us recall the notations • f ξ is the fixed point of L ξ , the transfer operator associated to the random system • v k is the fixed point of P k , the Ulam approximation of L ξ (in chapter 5 we called it L δ,ξ )

• ṽk is the fixed point of Pk , the matrix we computed • w the numerical approximation of ṽk .

With this notation, we have that

f -ṽ L 1 ≤ f ξ -v k L 1 + v k -ṽk L 1 + ṽk -w L 1 .
Remark 7.2 . In [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF], methods to obtain similar estimates in the L ∞ norm are considered.

The third term of the latter equation, comes from the numerical computation of the eigenvector of the matrix Pk and we already treated this issue. The discretization error, fv k L 1 , was addressed in section 5.1.1, theorem 5.9, and it depends from the contraction rate of the discretized operator. We also see how to improve this estimates with a coarse fine strategy 5.1.2. For the approximation error, v kṽk L 1 , once we have computed the rate of mixing of Pk , i.e. n, α such that Pn k L 1 ≤ α, using lemma 5.6 we have that

v k -ṽk L 1 ≤ n 1 -α P k -Pk L 1 v k L 1 ≤ 2n 1 -α × nz × .
As we can see, the only real computation which is needed in these estimates is the rate of mixing of a matrix (remember that if you are applying a coarse fine strategy, you need to compute the contraction rate of the two matrices). Remember that these computation are done in interval arithmetics, so the matrix Pk is an interval matrix. To compute n, α such that Pn | V L 1 ≤ α, we have two strategies. The trivial one, we proceed via matrix multiplications: this way is only practicable if you are dealing with small size matrices (up to 2 14 ). The size of the discretization to use depends on the system you are considering;

for example in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF], the matrices used are in the order of 2 27 , very large, so not only a smarter strategy was used, but this strategy was implemented through OpenCl to be executed on gpu Nvidia. Still some computation has required a time of the order of a week, on an Asus GeForce GTX 1050Ti, 4GB of Ram GPU installed in a desktop computer with an AMD A4-6300 3.4 Ghz processor and 8 Gb of Ram.

In the case of the Arnold maps (section 6.2), the experiments were performed on the supercomputer facilities of the M ésocentre de calcul de Franche-Comt é. The size of the matrices in this case is between 2 16 and 2 19 ; we chose to perform the computations on a supercomputer, because we were able to perform approximately one hundred rigorous calculations in parallel (see proposition 6.8). This parallel computation could not make advantage of the gpu, so each simulation was slower, but despite this there was a significant gain of time. We emphasize the fact that with matrices of size 2 27 , this strategy would not have been feasible, the calculation without gpu is prohibitive.

The smarter strategy comes from [START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF], in which the following inequality about roundoff error in matrix vector multiplication is shown

f loat(Av) -Av ≤ γ k • A v ,
where

γ k = ku 1 -ku ,
and U is the machine precision.

Hence, instead of a matrix multiplication, we consider the vector matrix products Pn k • v i , where v i are zero averages basis vectors, which can be computed just iterating a matrix vector product, without computing Pn k . This is done in floating point arithmetics, thus we have to convert with a simple script the matrix Pk from interval arithmetic to floating point.

The rate of mixing can be then bounded as Pn | V L 1 ≤ max i Pn k • v i . We implement a stopping criterion by choosing the desired rate of mixing α; once we fixed α, when we find an integer s such that max i Ps k • v i + err ≤ α the algorithm stops (err is the roundoff error computed as explained before).

7.2/ FOURIER-BASED SCHEME OF APPROXIMATION

The algorithm presented in this section is a part of an original work still in progress; the code can be found at https://bitbucket.org/luigimarangio/phd thesis/. We will now project the transfer operator associated to a random system on the Fourier basis, defined in Chapter 5. Let b j = e 2 jπix , for -k ≤ j ≤ k, a Fourier basis of 2k + 1 elements. We will use the fact that the j-th coloumn of Lb j is made by the "first" 2k + 1 Fourier coefficients of Lb j (from -k to k); we will represent the matrix relabeling the frequencies in the following way 0, 1, 2, . . . , k -1, k, -k, -k + 1, . . . , -1. The computation of these columns is done by using the explicit action of the transfer operator, given by (see for instance [START_REF] Baladi | Positive transfer operator and decay of correlations[END_REF], [START_REF] Boyarsky | Laws of Chaos: Invariant Measures and Dynamical Systems in One Dimension[END_REF])

[L f ](x) = y∈T -1 (x) f (y) |T (y)| , (7.1)
to evaluate the function L σ b j at N >> k interpolation nodes. We stress on the fact that this is the only point in which we need some regularity assumption on the map T and in the future work we hope to remove this assumption by using the duality relation of the transfer operator to compute L σ b j . However, plenty of interesting random dynamical system have a smooth deterministic part. We then perform a Fast Fourier Transform to recover the Fourier coefficients of L σ b j ; the coefficients obtained in this way are really close to the "true" coefficients, and the error is known as aliasing error and it was analyzed in section 5.2.2.

Once we have computed the matrix, we have to compute its rate of mixing, the approximation error and the discretization error; we now present the algorithms and the relative explanations.

7.2.1/ BUILDING THE FOURIER MATRIX

To compute the column of the Fourier matrix, we need an interval version of the Fast Fourier Transform; this problem was solved by emulating the FFT with the package Arb-Complex.jl; this latter is a package that uses the Arb C Library, and adapts some C library interface work from Nemo; furthermore it exports the types needed to work in the interval analysis framework (e.g. ArbReal and ArbComplex). In the author's knowledge, until now there was not in the literature an interval version of the FFT, which has now been added to the package ArbComplex.jl.

Another important remark is about the enumeration of the frequencies. We choose to put at index 1 in the matrix the 0th-frequency, then the positive frequencies from 1 to k and the theory presented so far.

We consider a perturbed doubling map T (x) = 2x + 0.001 sin(2πx), This simple example allows us to observe the potential of the proposed method. As can be reasonably expected, figure 7.1 shows the density of the invariant measure of the system. We conclude by pointing out that the only thing that currently prevents us from applying this method to more complex systems is the computation of C i , for which we need better theoretical estimates.

Definition 3 . 5 .

 35 we denote by φλ the Borel measure with density φ, i.e. the unique measure such that ∀ψ ∈ C 0 (M) : ψd(φλ) = ψφdλ. A non singular random transformation F induced an operator L : L 1 (M) → L 1 (M) defined by Lφ = d(U * (φλ)) dλ .

Proposition 3 . 13 .

 313 If for every φ ∈ L 1 (M) and ψ ∈ L ∞ (M) lim n→∞ M L n (φ)ψdλ = M φdλ M ψhdλ, (3.3) then Fis mixing for η. The opposite is true if supp(η) = M. Proof. Suppose 3.3 holds; by hypothesis φh ∈ L 1 (M) and ψχ h>0 ∈ L ∞ (M). Evaluating 3.3 in these functions we obtain lim n∈N ML n (φh)ψχ h>0 dλ = this implies 3.2 because the first integral is equal to M P n (φ)ψdη.Now suppose 3.2 and that supp

Definition 3 . 19 .

 319 Let F : Ω × M → Ω × M be a random transformation and let B ⊂ M andx ∈ M. The transition probability of x to B is p(x, B) = U χ B (x) = µ({ω ∈ Ω : f ω (x) ∈ B}).Proposition3.20 . The map (x, B) → p(x, B), for every fixed x ∈ M defines a probability on M and for every fixed B ∈ B defines a measurable map (sometimes such a map is called a transition kernel). Furthermore, if F is non singular and B countably generated, then there exists a transition density p ∈ L 1 (M × M) such that p(x, B) = B p(x, ω)dλ(ω), for λ-a.e. x ∈ M.

Proposition 3 . 21 .

 321 defines a measure µ over M × M. µ is absolutely continuous with respect to λ × λ: if A × B has zero λ × λ measure, then either λ(A) = 0 or λ(B) = 0, i.e. µ(A × B) = 0 or p(x, B) = 0 for a.e. x ∈ M. Then µ admits a density p ∈ L 1 (M × M). Moreover, for every fixed B ∈ B µ x (B) = B p(x, ω)dλ(ω), for λ-a.e. x ∈ M. By hypothesis B admits a countable generator, hence there exists a set S ⊂ M of full measure such that the expression above is true for every B ∈ B. Let F be a non singular random transformation and suppose B to be countably generated. If φ ∈ L ∞ (M), then for λ-a.e. x ∈ M, Uφ(x) = M p(x, •)φdλ and Lφ(x) = M p(•, x)φdλ.

Definition 4 . 1 .

 41 Let T : M → M be a non-singular transformation and let ρ ξ ∈ BV(M) be a probability density (ξ ∈ [0, 1] is a fixed parameter, which represents the "size of the noise").

1 0

 1 for every x point of approximate continuity of f Proof. Consider the periodic extension ĝ ∈ C ∞ (R) of g and note that g(x 0 ) = ĝ(1 + x 0 ), for any sequence {x j } k-1 j=0 satisfying the hypothesis. Let y j = x j for j ≤ k -1 and y k = 1 + x 0 . Then k-1 j=0 |g(x j+1 )g(x j )| = |∇ ĥ(y)|dy = |∇g|dλ = Var(g).

4 .Proof. 1 .

 41 and L(BV(M)) ⊂ BV(M), then every stationary density is Lipschitzcontinuous let M = S 1 and ρ ξ ∈ BV(M). If for every interval [a, b] ⊂ [0, 1], T -1 can be expressed as a union of m intervals, for some fixed integer m, then every stationary density is Lipschitz-continuous. If Lφ ∈ BV(M), then for every x, h ∈ M,

Definition 4 . 23 .Proposition 4 . 24 .

 423424 A piecewise continuous map T on [0, 1] is a function T : [0, 1] → [0, 1] such that there is partition {I i } 1≤i≤k of [0,1] made of intervals I i such that T has a continuous extension to the closure Īi of each interval. Let T 1 and T 2 : [0, 1] → [0, 1] be piecewise continuous nonsingular maps and ρ ∈ BV. With the notations introduced above, for any f ∈ L 1 it holds

Lemma 4 . 25 .

 425 Let T 1 and T 2 : [0, 1] → [0, 1] be piecewise continuous nonsingular maps and let L 1 , L 2 the associated deterministic transfer operators, let f ∈ L 1 . Then

Example 5 . 1 .

 51 When we say "we compute n, α, with α < 1, such that L δ ≤ α, we actually mean that, based on the properties of the interval arithmetic, we proved the following theorem Theorem 5.2 . There exists a, b ∈ Q, with b < 1, such that L δ ∈ [a, b].

Theorem 5 . 21 .

 521 Let Γ σ,k := γ σ e -k 2 σ 2 2

Figure 6 . 1 :

 61 Figure 6.1: Data collected in [33].

6. 1 .Figure 6 . 2 :

 162 Figure 6.2: Deterministic component of Equation (6.1).

  f ξ,δ for T ξ , with δ = 2 -19 and A = 0.08. (a) ξ = 0.732 × 10 -1 ; (b) ξ = 0.488 × 10 -1 ; (c) ξ = 0.305 × 10 -1 ; (d) ξ = 0.214 × 10 -1 . See remark 6.1. f ξ,δ for T ξ , with δ = 2 -19 and A = 0.07. ( a) ξ = 0.732 × 10 -1 ; (b) ξ = 0.488 × 10 -1 ; ( c) ξ = 0.305 × 10 -1 ; ( d) ξ = 0.214 × 10 -1 . See remark 6.1.6.2/ THE ROTATION NUMBER OF THE ARNOLD MAPThe El Ni ño-Southern Oscillation (ENSO) phenomenon is a crucial component of climate variability on interannual time scales and it is dominated by the seasonal cycle, on the one hand, and an intrinsic oscillatory instability with a period of a few years, on the other. The role of meteorological phenomena on much shorter time scales, such as westerly wind bursts, has also been recognized and modeled as additive noise. Arnold's standard circle maps are widely used to study this kind of phenomena, in which two rationally unrelated periodicities are in competition; they are defined in the following way: let T τ, : S 1 → S 1 be the deterministic circle map defined by T τ, (x) := x + τ -2π sin(2πx) mod 1 . (6.3)

Definition 6 . 2 .

 62 The rotation number ρ = ρ τ measures the average rotation per iterate of 6.3 on S 1 and is defined asρ τ := lim n→∞ T n τ, (x) nwhere T n τ, : R → R is the lift of T τ, to R, defined by Tτ, (x) := x + τ -2π sin(2πx). (6.5)We need to adapt this definition to our random contest, by considering a stochastic pro-cess X on R defined by Xn+1 = Tτ, ( Xn ) + Ω n and ρ τ := lim n→∞ Xn n .

Figure 6 . 5 :

 65 Figure 6.5: Plot of the rotation number ρ = ρ τ for = 0.9. The black line corresponds to the absence of uniformly distributed noise, while the red line shows this dependence in the presence of such noise, with amplitude ξ = 0.05. Recall that τ = 2π/ω, where ω is the driving frequency. The lower panel is a blow-up of the dependence near the value τ = 0.5.

Figure 6 . 6 : 3 /

 663 Figure 6.6: Same as Fig. 6.5 but for = 1.4 and for noise amplitude ξ = 0.01. Here the lower panel is a blow-up of the dependence near τ = 0.7.

Proposition 6 . 8 .

 68 Let = 1.4 and ξ = 0.1. Then, for each τ ∈ [0.75, 0.8], the corresponding Arnold map with noise and parameters ( , τ, ξ) satisfies assumption LR1 of Theorem 4.21.

Example 7 . 1 .

 71 Let f = 333.75b 6 + a 2 (11a 2 b 2 )b 6 -121b 4 -2) + 5.5b 8 + a 2bwith a = 77617.0 and b = 33096.0.

(7. 2 )

 2 and we choose the following parameters for the computation • k = 250 is the size of the coarse discretization (thus we work with matrix of size 501), used to compute the C i (see also remark 7.3) • k = 2000 is the size of a finer discretization, combined with the latter via lemma 5.27 to obtain better estimates • N = 10000 is the number of interpolation points • σ = 0.01, where σ 2 is the variance of the gaussian kernel. Applying the results described so far we obtain the following estimate on the rate of mixing α = 0.0100808 N = 6 and N-1 i=0 C i = 57.355, which leads to an approximation error of f σf σ,k ∞ ≤ 6.5381 × 10 -86 an error on the dft of k • Γ σ,N ≤ 10 -300 .

Table 6 .

 6 -19 is used to compute the invariant density via power method; δ contr = 2 -14 , is used to find the estimates on the contraction rate and δ est = 2 -12 is used to estimate the L 1 error of the invariant density . 1: Summary of the L 1 bounds on the approximation error obtained for the range of noises ξ, with parameters A = 0.8, C = 0.01.-19 is used to compute the invariant density via power method; δ contr = 2 -14 , is used to find the estimates on the contraction rate and δ est = 2 -12 is used to estimate the L 1 error of the invariant density .

		n contr α contr	α	C i	l1apriori	l1err
	0.732 × 10 -1	126	0.027 0.05	56.64 0.313 × 10 -2 0.715 × 10 -4
	0.610 × 10 -1	167	0.034 0.067 78.66 0.530 × 10 -2 0.105 × 10 -3
	0.488 × 10 -1	231	0.051	0.1	120.56 0.106 × 10 -1 0.184 × 10 -3
	0.427 × 10 -1	278	0.068 0.14 156.45 0.163 × 10 -1 0.268 × 10 -3
	0.366 × 10 -1	350	0.087 0.19 213.17 0.273 × 10 -1 0.432 × 10 -3
	0.305 × 10 -1	453	0.12	0.26 307.03 0.523 × 10 -1 0.813 × 10 -3
	0.275 × 10 -1	532	0.14	0.32 380.64 0.776 × 10 -1 0.122 × 10 -2
	0.244 × 10 -1	596	0.19	0.41 467.70	0.124	0.202 × 10 -2
	δ = 2 ξ	n contr α contr	α	C i	l1apriori	l1err
	0.732 × 10 -1	183	0.03 0.059 83.57 0.466 × 10 -2 0.255 × 10 -4
	0.610 × 10 -1	237	0.046 0.089 119.31 0.822 × 10 -2 0.282 × 10 -4
	0.488 × 10 -1	332	0.069 0.14 186.80 0.170 × 10 -1 0.323 × 10 -4
	0.427 × 10 -1	406	0.087 0.18 244.95 0.267 × 10 -1 0.358 × 10 -4
	0.366 × 10 -1	494	0.12	0.25 330.89 0.459 × 10 -1 0.419 × 10 -4
	0.305 × 10 -1	500	0.3	0.46 419.92 0.974 × 10 -1 0.646 × 10 -4
	0.275 × 10 -1	596	0.32	0.52 517.97	0.151	0.807 × 10 -4
	0.244 × 10 -1	600	0.49	0.73 573.04	0.326	0.189 × 10 -3
	δ = 2

Table 6 .

 6 2: Summary of the L 1 bounds on the approximation error obtained for the range of noises ξ, with parameters A = 0.8, C = 0.01.

Table 6 .

 6 Let = 1.4, ξ = 0.1 then, for each τ ∈ [0.75, 0.8] the rotation number corresponding to the Arnold map with noise and parameters ( , τ, ξ) is differentiable as τ varies and (6.11) holds. 3: Given the Arnold map with noise of magnitude ξ and parameters (τ 0 , 0 ), for which we have already proved mixing, the table shows the computed intervals I 0 = [τ 0θ 0 , τ 0 + θ 0 ], such that if τ ∈ I 0 then the Arnold map with parameters (τ, 0 ) is mixing

	Once we have Assumption LR1 of Theorem 4.21 satisfied for this family of systems,
	applying Corollary 6.7 we directly get
	Corollary 6.9 .

4, τ, 0.1), with τ ∈ [0.75, 0.8], a strategy is to consider a finite sequence of points {τ i } ⊂ [0.75, 0.8] such that the systems with parameters (1.4, τ i , 0.1) are mixing, for every i, and the associated intervals I i := [τ i -θ i , τ i + θ i ], defined as above, cover the interval [0.75, 0.8].

In Table

6

.3 we show the computer aided estimates about the values of θ 0 by the method described above for each example. As it can be seen, since the union of all this computed intervals is equal to (a, b), with a = 0.749399418088000 and b = 0.800715949198087, we have then proved the desired property in the whole interval [0.75, 0.8].

Table 6 .

 6 4: This table shows the computed intervals in which the rotation number lies for each value of the parameters in consideration.

	(τ, )	ξ	ρ τ
	(0.707, 1.4) 0.01 [0.780594, 0.780604]
	(0.708, 1.4) 0.01 [0.778348, 0.778361]
	(0.709, 1.4) 0.01 [0.775291, 0.775302]
	(0.710, 1.4) 0.01 [0.771833, 0.771844]
	(0.711, 1.4) 0.01 [0.768335, 0.768348]
	(0.712, 1.4) 0.01 [0.765170, 0.765183]
	(0.713, 1.4) 0.01 [0.762568, 0.762590]
	(0.714, 1.4) 0.01 [0.760585, 0.760612]
	(0.715, 1.4) 0.01 [0.759288, 0.759344]
	(0.716, 1.4) 0.01 [0.759915, 0.759970]
	6.3.1/ NON-MONOTONIC ROTATION NUMBER FOR STRONG NONLINEARITY

For < 1, the monotonicity of the rotation number of the Arnold map is a classical result:

  Proof. As explained above, we use the Ulam based algorithm to estimate the stationary measure for = 1.4 and for each τ ∈ {0.707, 0.708, ...., 0.716}. We estimate the expected value of the observable Tτ, (x)x with respect to the stationary measure for each example. This gives a certified interval in which the rotation number ρ τ of each example lies (see Proposition 6.6). The results are reported in Table6.4. The inspection of these, disjoint, decreasing, intervals shows that the rotation number decreases for τ ∈ {0.707, 0.708, ....0.715}. The last estimate at (0.716, 1.4) shows an increasing behavior, showing non monotonicity. 96 CHAPTER 7. NUMERICAL ASPECTS language in which the Fourier approximation method we present has been implemented. LinearAlgebra.jl and Plots.jl, implement the obvious basic functions we expect. We will discuss ArbNumerics.jl directly in section 2, while as you can guess from the name, In-tervalArithmetic.jl and IntervalRootFinding.jl implement the aforementioned Interval Arithmetic. To explain what it is, let's start with an example from ([START_REF] Moore | Introduction to Interval Analysis[END_REF]), first given by Rump.

	The packages used in this work are
	• LinearAlgebra.jl, Plots.jl
	• IntervalArithmetic.jl, IntervalRootFinding.jl
	• ArbNumerics.jl

6.10

. Let = 1.4 and ξ = 0.01, then the rotation number ρ τ , as function of the parameter τ, is not monotonic in the interval [0.707, 0.716].

SAGE, "System for Algebra and Geometry Experimentation", is a computer algebra system with features covering many aspects of mathematics; the first version of SageMath was released on

February 2005[START_REF] Arnold | Random Dynamical Systems[END_REF] Julia is a high-level, high-performance, dynamic programming language. While it is a general-purpose language and can be used to write any application, many of its features are well suited for numerical analysis and computational science.

32, avenue de l'Observatoire

ACKNOWLEDGEMENTS

I would like to thank my supervisors Christophe and Stefano. In addition to their academic skills, I met two great people and I believe that now more than ever the world needs people like them. I'm grateful to both departments where I did research during these years and, of course, Figure 7.1: Density of the computed invariant measure of 7.2 BIBLIOGRAPHY

φ ∞ ≤ 1, then (ρ * f ) div φdλ = τ t ρ(x) f (t) div φ(x)dλ(t)dλ(x) = τ t ρ(x) div φ(x)dλ(x) f (t)dλ(t) ≤ Var(τ t ρ) f (t)dλ(t) ≤ Var(τ t ρ) f L 1 .

ρ has bounded variation and Var(τ t ρ) = Var(ρ) < +∞, hence we deduce that ρ * f ∈ BV(M). Suppose for an absurdum to have Var(h) > 4c(m + 1), then there exists an increasing sequence {x j } k-1 j=0 such that

Every interval of the form [h(x j ), h(x j+1 )] or [h(x j+1 , h(x j )] is contained in [-m, m], thus there exists an interval [a , b ] ⊂ [-m, m] that is contained in at least 2(m + 1) of this intervals, and at least m + 1 are of the same type [h(x j ), h(x j+1 )] or [h(x j+1 , h(x j )]; assuming the first type without loss of generality we have

where j(0), . . . , j(m) is now an increasing sequence in {0, . . . ,

We deduce that h -1 ([a, b]) contains at least m + 1 intervals, each one of them contains one of the x j(i) , and thus g BV (M), which is a contradiction.

We are now ready to show that every stationary density is Lipschitz continuous. Then the following holds:

where δ -ξ and δ ξ are the delta measures placed on ±ξ.

Then by (4.3)

(recall that T 0 is nonsingular and then L T 0 ( f 0 ) ∈ L 1 ) with convergence in the || || W norm.

Lemma 6.4 . The remaining assumptions of Item LR3 of Theorem 4.21 are satisfied:

Since there is a K such that ||[R -δ ρ ξ -ρ ξ ]|| L 1 ≤ Kδ by Lemmas 4.17 and 4.18 we directly get the statement.

These estimates are leading to the following linear response statement adapted to our situation. Proposition 6.5 . Let T 0 : S 1 → S 1 be a nonsingular map. Let T δ defined as T δ (x) = T 0 (x) + δ, let L δ : L 1 → L 1 be the transfer operator defined as in (6.6). Let f δ ∈ L 1 be such that L δ f δ = f δ (a stationary measure for the system L δ ).

Suppose L 0 is mixing: for every g ∈ BV[0, 1] with I g dm = 0, then

(see Assumption LR1 of Theorem 4.21) Then (Id -L 0 ) -1 is a continuous operator on the space of zero average Borel measures equipped with the || || W norm and

To conclude our proof, we still need to exploit the fact that the rotation number can be computed as the integral of a Lipschitz observable with respect to the stationary measure;

NUMERICAL ASPECTS

In this last chapter we discuss the computational details associated to the theory developed so far; we will try to make this part of the thesis accessible, as far as possible, even to those who do not have a mathematical background and are more interested in computer science aspects, or simply want to learn how to use the code we will present without being able or need to go into the details of the theory.

There are two sections, dedicated respectively to the approximation scheme based on

Ulam, and the one based on Fourier. We have already seen some theoretical differences, but the algorithms differ, quite substantially, even in numerical aspects, for instance the matrices of Ulam are sparse, those of Fourier are not. We will focus more on the exposure of the second method, for several reasons:

• the Ulam-based strategy, which is at the basis of this work, has already been described in full details in [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF], [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF] and then in [START_REF] Liberalquino | Chaotic Itinerancy in Random Dynamical System Related to Associative Memory Models[END_REF], [START_REF] Marangio | Arnold Maps with Noise: Differentiability and Non-monotonicity of the Rotation Number[END_REF].

• the Ulam-based algorithm, used for example to obtain the results in Chapter 7, is implemented in SageMath 1 , meanwhile we have chosen to work with Julia 2 with the new Fourier-based algorithm.

Before moving on to the description of the two algorithms, let us introduce Julia and the main packages that were used during this work, and the concept of interval arithmetic, which is the basis of our rigorous calculations.

Working at the crossroad of mathematics, computer science and applied sciences, it can sometimes be difficult to find the right programming language to accomplish your tasks.

In the author's opinion, an excellent compromise between facility of use, versatility, speed and community presence has been achieved by Julia in the last years, the programming

7.1/ ULAM-BASED SCHEME OF APPROXIMATION

In the next sections we provide the details of the rigorous approximation algorithm. This algorithm can be found in different versions, one of them for instance in https://bitbucket. org/luigimarangio/arnold map/. As we have already observed, for several reasons, we will focus on the full exposition of the Fourier based method; all the details that are omitted here, can be found in [START_REF] Galatolo | An elementary approach to rigorous approximation of invariant measures[END_REF], [START_REF] Galatolo | Existence of Noise Induced Order, a Computer Aided Proof[END_REF].

Remember that the steps to perform are :

• construct a matrix, which is an approximation of the transfer operator associated with our random system

• calculate the discretization error and approximation error; this is done by rigorously estimating the rate of mixing of the approximate transfer operator.

In the next two subsections, we will describe how to deal with the above mentioned steps.

Finally, we will briefly describe how to estimate the average of an observable, algorithm used for example of the rigorous computation of the rotation number of the Arnold maps.

7.1.1/ BUILDING THE ULAM MATRIX

Let P k be the matrix of the Ulam approximation, where k is the size of the approximation;

if we partition the interval [0,1] in k intervals I 1 , . . . , I k then, the i, j-th entry of P k is given by equation 5.1. As already pointed out we cannot compute exactly P k , but we can compute a matrix Pk which is equal to P k up to an approximation error. Indeed, we first fix a small β > 0 and we compute a row matrix P k : for each I i , consider a partition in m smaller intervals J 1 , . . . , J m ; we look at the images T (J l ), and we test whether or not these images are contained in I j . The only problems comes if T (J l ) overlaps I j but is not contained. In this case we partition again, until the "problematic" interval has a measure smaller than β; we denote this measure by i, j , and at the end we will obtain a row matrix P i, j with an associated error = max i, j i, j .

Furthermore observe that we can always split the interval [0, 1] in monotonic branches for the map T ; hence we can suppose that either T is monotonic on I j or has a discontinuity point.

Algorithm 1: Computing the row Ulam Matrix P

i j : T is monotone on I i . Result: P i j , P i j = 0 ; i j = 0; Partition I i in m intervals I i,k for k = 0, . . . , m -1; The computation of the noise matrix is particularly easy. Let us stress that in this section we are considering noises with gaussian kernel, meanwhile before we considered uniform distributed kernels; since the gaussian function is an eigenfunction of the Fourier transform, the noise matrix D σ is diagonal with entries D σ,k ( j, j) = e (-(σπ j ) 2 ) , where as usual we shift the indexes to j to select the proper frequency. The finite dimensional operator L σ,k is then approximated by the matrix H k = D σ,k M k In the next subsection we end this work by describing how to estimate the errors arising from this scheme of approximation.

7.2.2/ BOUNDING THE ERRORS

In this first version of the algorithm, we are computing the contraction rate of H k by iterative multiplications. This is possible because we have exponential bounds: thanks to coarsefine strategy, it is possible to obtain bounds of order 10 -80 with relative small matrices. In the example shown in Chapter 6 we consider a fine partition of size 2000 and a coarser partition of size 500: multiplying interval matrices of size 500 is not a big deal.

Remark 7.3 . Of course we must be careful to the accumulation of the numeric error, which the interval analysis takes automatically in account. Indeed, we bound the L ∞ -norm on the zero average space with the sum of all the elements of H k , except for the first row and the first column (these corresponds to the 0th-frequency); founding a more effective way to bound this norm is a problem on which we are working on.

Let H k and H k f ine be the two approximation matrices computed with algorithm 7.2.1 for two partitions of different size. The following algorithm bounds the mixing rate of H k f ine using information on H k ; as said before, the norm of a matrix means the sum of all the elements of the matrix except for the first row and the first column. the approximation error is given by lemma 5.26 and we just need to compute the following quantity

the discretization error in the Fourier case is given by the aliasing error, equation 5.7, which is equal to Γ σ,N .

7.2.3/ AN INTRODUCTORY EXAMPLE

We are finally ready to apply this Fourier scheme to an easy but non trivial example; more examples will come in future works. As already mentioned at the beginning of Chapter 6, this is a first technical and explanatory example, which has no practical relevance (it is not a toy-model of a natural phenomenon); obviously then its complexity is not comparable to that of the models presented above, and this example is intended as a first application of