b .t, . . . . . .IXU-ILH .Il . . . . . . v...,Yk;. . . .. it. .v . .. . . . . I . .. z... :11. . . 4 r9,‘ . . . N‘fl'n "t I. . . 1 . . o. 50!. . . I . , . . . A . . . » . . A to. 51v. . . L 55...”... hitiyflruhf : .JIJIY. ill E :qu titty 70:. Do. '0 w u5!...r~.fis.|!l . . penuflmwfindh in...) II .. . '01-: I? . ‘npN-nrd.’ . . .niusvv 00¢... : rivetri .11]: . . .. . . . vii-.1711. t A i...v.vr‘o... , .. . ., oh)~.:5rJHu.tt . .. . . . . St 3|... . .. .. . 1. a _ . . . . v . . .21 in... 1 £5 {2231:1131 in... . ...I.(,......II.. . r :4» .t .i .0 liq. .315... {Int}. .6! . .‘ 0-1:..-1 I'... its-.17 “9.!!! .44.»... . gu ‘ ).v|.rla . 4'11}: 1.“ $1.1. (5.1 . 7x2. . . I (LP. rm“. rJ‘.’ ' ‘0 .. I...) if... 2.5.1 W"! ".1”. WW I. 7.1.0.) £71.). ‘. «if,» v.3? ; .. . . ’0‘} l- .i It’ll :9. 0 II I! . in: yr 0.! . ‘t‘ l .2... u . ‘n u. lot- .- :l?..£ . 1...; z. fizrawflh}? z. ¢ trlz. . ElstICC. .:......1.. . : . . 4..., . .- . . | u ..:-l’.. n .4? .-. .. "‘l‘fu'fl'" "annnv'v-H't'9uvf'11fl . . .. 3.731... . . , . . .311... .1. ... )vrl . . . .....Y|...... 4 u 9 lb .. 21...... . ground}! : . ........1 .a:..... .- F1. .rlz u ... . . n5’n51~.Pr|UI.crl t‘...’ :. .1...... :1... . . 1.... a . 1.....4... .: .. :téufimgm . 3n§r15fii¢1.1.?»i§3 . , x . -. E: ....m.:.... y c . , #2: 3, ! I: . WWII-trlfi 02¢. Y vv.0.!f:.u.v l .n. i 1 . 3E; Fl. Illlllllll1H||lUllllllllllllHHIHll‘ll \: 3 1293 009149 This is to certify that the dissertation entitled F!” {to A/rfi/hthtk‘fim} 7' ‘ ' . -, . . r V0 éenvM/J —’ Pk I ’ 7’ 7" presented by 3'). LL °j A (A4) 0f 6'"? Q’m’fil"$ Dill? has been accepted towards fulfillment of the requirements for ’) . F i 9’ degree in " ,LCQ‘I A, (Inf/lei I'm; «:0 ,4,” %M C Date MS U is an Affirmative Action/Equal Opportunity Institution Major professor 0-1277! 29753332212 * LIBRARY Mlchlgan State university, PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. DATE DUE DATE DUE DATE DUE ' :5” L \l 7mm. MSU Is An Affirmative Action/Equal Opportunity lnetittnton CMms-DJ h , - - —-~—*—*_ FINITE APPROXIMATIONS OF A CLASS OF FROBENIUS-PERRON OPERATORS J in Ding A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1990 @45~a‘31; ABSTRACT FINITE APPROXIMATION S OF A CLASS OF FROBENIUS-PERRON OPERATORS By Jiu Ding In this paper we construct first order and second order piecewise polynomial finite approximation schemes. These schemes are for the computation of invariant measures of nonsingular measurable transformations on the unit interval, and fall into two groups. The first one is based on the Galerkin projection method for Ll-spaces. The second one uses the idea of Markov approximations of finite rank to the Frobenius- Perron operator. These methods are proved to converge for a class of transformations satisfying the condition of the Lasota-Yorke theorem. Moreover the computational experiments show that these schemes converge faster than Ulam-Li’s method for most problems. To my mother Wang Liu-Feng iii Acknowledgments I am grateful to Professor Tien Yien Li, my thesis advisor, for his constant encouragement and support during my graduate study at Michigan State University. I would also like to thank him for introducing to me the ergodic theory through his excellent high level graduate course, for his suggestion of the problem, and for all of the helpful directions in making its solution possible. In addition his kind financial support last summer enabled me to concentrate on the research in this field. I would also like to thank Professor David H. Yen, my academic advisor, for his introduction to the essentials of the finite element method in his graduate course which I took. That course has given me much impetus for this research. iv Contents 1 Introduction 1 2 Frobenius-Perron Operators and Projection Methods 6 2.1 F robenius-Perron Operators ....................... 6 2.2 Galerkin’s Projection Method ...................... 11 3 Piecewise Linear Projection Approximations 12 3.1 Projection Operators ........................... 12 3.2 An Inequality for Variation ........................ 17 3.3 Convergence ................................ 19 4 Piecewise Quadratic Projection Approximations 23 4.1 Projection Operators ........................... 23 4.2 An Inequality for Variation ........................ 28 4.3 Convergence ................................ 32 . 5 Markov Finite Approximations 35 5.1 Piecewise Linear Markov Approximation ................ 35 5.2 Piecewise Quadratic Markov Approximation .............. 41 6 Numerical Results 47 6.1 Numerical Results with Projection Methods .............. 47 6.2 Numerical Results for Markov Finite Approximations ......... 51 7 Conclusions 55 List of Tables 6.1 Error Estimates for S; .......................... 49 6.2 Error Estimates for 53 .......................... 49 6.3 Error Estimates for S4 .......................... 50 6.4 Error Estimates for 55 .......................... 50 6.5 Error Estimates for 32 .......................... 52 6.6 Error Estimates for S3 .......................... 53 6.7 Error Estimates for S4 .......................... 53 6.8 Error Estimates for S5 .......................... 54 vi Chapter 1 Introduction Let I be the unit interval [0,1] and S : I —+ I be a mapping. Given :co 6 I, we recursively define a sequence {13,} by letting 93,,“ = S(:z:n) for n = 0, 1, 2,. . . . Suppose for a particular sequence of iterates {an}, we happen to have 5(12000) = $1000. Then eventually, the iterates will be in the set of finitely many elements {31000, $1001, . . . , x2000}. Thus we have a predictable behavior for the iterates. The study of chaotic dynamical systems has become very popular in sciences and engineering. The term “chaos” was first introduced by Li and Yorke in their seminal paper [6]. Various definitions have been given for “chaos” since then, but basically a common fundamental feature of “chaos” is “unpredictability”. A typical example of chaotic dynamical systems is given by the “logistic model” 5(3) = 4x(1 — :13). It is well-known that for almost all 2:0 6 [0, 1], the iterates are dense in I . Thus we cannot predict the limiting behavior of the iterates. We may look at a dynamical system from a different point of view. Given a set A, we determine the probability of the iterates entering A. For this purpose let X A be the characteristic function of A: 1 if a: E A XA($) = 0 otherwise. Starting at 1:0, if the nth iterate S”(xo) is in A, then XA(S"(:ro)) = 1. Otherwise XA(S'”(a:o)) = 0. Thus % 2,132? XA(S"($0)) gives the ratio of the points among the first N iterates in A. In ergodic theory 1 N-l 131330 IV "2::0 XA(5"($0)) is called the time average. A classic theorem of ergodic theory basically says: The time average coincides with the space average, that is #(A) _ 1 m - m/IXACIII, where p is a measure on I. Now the question arises: Is the measure invariant with respect to time? A more careful statement of the classic ergodic theorem should be: The time average equals the space average which is invariant with respect to time. Using mathematical terms, it simply says that the measure it is “invariant” with respect to S, or S “preserves” the measure p. That is, for any measurable set A, p(S"1(A)) = p(A). In this case, p is called an invariant measure. If in addition [1(1) = 1, we call it an invariant probability measure. Now the problem is: Is there any probability measure which is invariant with respect to S"? This leads to the concept of the Frobenius-Perron operator. This operator gives the way in which the probability distribution changes according to the transformation 5'. Now let m be Lebesgue measure and L1(m) the set of m-integrable functions. Suppose a probability measure p is given by a nonnegative L1(m)-function f, that is, [1(A) = [A fdm for every m-measurable subset A of I. Given a nonsingular measurable transformation 3 : I —+ I, we examine how the probability distribution is converted by S. For any measurable set A we would like this set A to have the probability of the set it comes from under 5'. Thus, A should have the probability fl(A) 2 L94”) f dm. Since 5' is nonsingular, [1 is absolutely continuous with respect to m. Thus by the Radon—Nikodym theorem, there exists a unique density f E L1(m) such that L, fdm = fS-1(A) fdm for any measurable subset A. The correspondence between f and f' defines the Frobenius-Perron operator P5 : L1(m) —r L1(m) associated with S: [Apsfdm = [9_1(A)fdm (1.1) It is apparent that if f 2 0 is a fixed point of P5, then the measure pf defined by MA) = f, fdm is invariant with respect to S. In this case we call f an invariant density. Thus to find an invariant measure we may instead find a fixed point of the corresponding Frobenius-Perron operator. To calculate fixed points of the Frobenius-Perron operator numerically, it is im- portant to make finite approximations of this operator. For this purpose divide I into n subintervals 11,12, . . . , In. Suppose a piecewise constant density f gives I.- the probability a.- for i = 1,2,. . . ,n. For 5 : I -+ I, it is easy to see that the probability of I.- induced by S is n 1 b.‘ = Z m(1j2(51'j)(1e))aj J=l for i = 1,2,...,n. Let P" = [pg] With pa = W,0 = [a1302)"°9an]T, and b = [b1, b2, . . . , bn]T. Then the relation b=Pna gives a finite approximation of the Frobenius-Perron operator. Since Pn is an n x n nonnegative matrix and the sum of each column of Pn is 1, Pn is a stochastic matrix. It is well known that a stochastic matrix has 1 as an eigenvalue with a nonnegative eigenvector. Therefore Pn has a fixed point which gives a nonnegative piecewise constant function fn. In 1960 S. Ulam conjectured [10]: The piecewise constant functions fn converge to an invariant density f of the Frobenius-Perron operator P5 as n approaches infinity under the stretching condition, i. e., infxg I S’(a:) [> 1. In 1976, Li proved this conjecture [5]. Numerical experiments show that the Ulam-Li’s method converges very slowly for most problems. This situation motivates the investigation of higher order approxima- tions of the Frobenius-Perron operator. It seems difficult to generalize the previous 3 argument based on probability analysis. However, we may consider this problem from a totally different point of view. To solve Pf = g for f and g in a Banach space X, we may employ Galerkin’s projection method [9]. That is, we project this equation into a finite dimensional subspace of X and solve the resulting finite dimensional problem in this subspace. To find the projection, we need an inner product between X and its adjoint space. For our fixed point problem P5 f — f = 0, we define the inner product of two functions f E L1(m) and g E L°°(m)= L1(m)‘ to be = [01 f(x)g(x)dw. (1.2) To construct a finite dimensional subspace, we divide the interval I into n subintervals 11,12,...,In. Fori: 1,2,...,n, let . _ 1L 1. _ m(I.-) (1.3) and A" = {22:1 ail; : a.- 6 33,1' = 1, . . . ,n}. Then An is the n-dimensional subspace of L1 which is made up of piecewise constant functions. Using Galerkin’s projection method to solve the equation P3 f — f = 0 in An, the function PA: 011:“) - Z 0111 i=1 i=1 should be orthogonal to each basis function, that is, < P5(Zaj1,-) — Zajlj,1.- >= 0, '=1 i=1 or, Zaj = Zaj<1j,1.->. (1.4) j=1 j=1 From (1.1), (1.2), and (1.3), < Pslj, l; > = [(lpsljflgdm = —-1—/1P51jdm / - d-m ——1—/ dm min”) -1(I) , ‘m(1.-)m(I.-) s-xm’“) mUj 3"( I1)) m(I.-)m(1j) ' On the other hand, 11 a - 1-,1.-> = .-<1.-,1.->=——'—/ . .11 Z31“ ’ “ m(I.-)2 1““ m a; a.- ’ mid” = m L1(0,1) defined by /AP3f(x)d:r = [9_1(A)f(:r)dx (2.1) is called the Frobenius-Perron operator associated with S. If there is no ambiguity, we shall write P for PS. Proposition 2.1.1. [ Properties of the F robenius-Perron operator ] (1) P is linear, i. e., for f1,f2 E L1(0, 1) and A1, A2 6 92 P(A1f1 + )0le = /\1Pf1+ A2Pf2o (2) IffZO, then PfZO. (3) In1 Pf($)d$ = fci f($)d$- (4) For the nth power 5”, P5»: = (P3)”. Proof. See [3]. It follows from (2) and (3) that the Frobenius-Perron operator P5 not only pre- serves nonnegative functions, but also preserves their norms. Thus P3 is a Markov operator. Hence [I PS I]: 1. Definition 2.1.3. Let (I,B,p) be a Borel measure space and S : I —+ I be a measurable transformation. We say that p is invariant under S, or S is measure- preserving with respect to u, if p(S‘1(A)) = [1(A) for all A E [3. Theorem 2.1.2. For f E L1(0,1) and f 2 O, the measure MA) = f. f(w)da= (2.2) is invariant under S if and only if P3 f =: f. Proof. Since pas-«A» = / s-2 (A) f(x)da: = A P5f(:1:)d:c, pf(A) = p;(S"1(A)) for any A implies Psf = f and vise verse. Q.E.D. The function f in (2.2) is usually called the density function of the measure pf. It is apparent that a measure can be calculated when its density is known. The density of an invariant measure is characterized by Theorem 2.1.2 as a nonnegative fixed point of the Frobenius-Perron operator. In this case it is called an invariant density. Therefore to calculate invariant measures for S, we may calculate instead invariant densities of the corresponding Frobenius-Perron operator. However, to find a fixed point of the Frobenius-Perron operator is, unfortunately, not so simple in general. First of all, the space L1(O, 1) is not reflexive. Moreover, the operator P5 is not compact. Let A = [0,1]. Then from the definition of the Frobenius-Perron operator, f0. P f(t)dt = / f(t)dt. S-1(0,1:) Differentiating it, we obtain the Frobenius-Perron operator explicitly: P f(x) = % Lam...) f(t)dt. (2.3) For the logistic model 5(a) = 4:1:(1 — x), (2.3) becomes Pf(w) = fill—3111a — ./—1 — x)) + f1§u+ ./—1 — as»). For a class of stretching transformations from I into itself, Lasota and Yorke [3] established the existence of invariant densities. In [7], Li and Yorke gave a sufficient condition for the uniqueness of the invariant density and thus the ergodicity of the mapping. Definition 2.1.4. A mapping S : [0,1] —-> [0,1] is called piecewise 02, if there exists a partition 0 = a0 < a1 < < a, = 1 of the unit interval such that for each integer k = 1,. . . ,r, the restriction 5;. of S to the open interval (ak_1,ak) is a 02-function which can be extended to the closed interval [ak_1, ak] as a 02-function. S need not be continuous at the points ak. Theorem 2.1.3. ( Lasota-Yorke ) Let S : [0,1] —) [0,1] be a piecewise 02-mapping satisfying the stretching condi- tion: there exists a constant A > 1 such that I S'(:r) [Z A,x 7é a;(i = 0,1,...,r). Then for any function f E L1(0,1), 1 "2::1 Pkf '— s n k=0 converges uniformly in L1(0, 1) to some f“ of bounded variation with Psf" = f ‘. Proof. See [4] . Theorem 2.1.4. (Li-Yorke) Under the condition of Theorem 2.1.3, if the mapping S has a single point of discontinuity, then the invariant density f‘ of the Frobenius-Perron operator P3 as- sociated with S is unique, and S is ergodic with respect to the measure [1" defined by MA) = f. f‘dm- Proof. See [7]. A straightforward numerical way to calculate invariant measures can be obtained from the classical Birkhoff Individual Ergodic Theorem which uses the Koopman operator instead of the Frobenius-Perron operator. By Birkhoff’s theorem if p is an ergodic invariant probability measure for S, then for any measurable set A C [0,1], the limit which measures the “average time” spent in A under iterations of S, exists and is p(A) for p-almost all 2:. Hence, to obtain p(A) one might choose almost any a: in [0, 1] and calculate the average time for iterates S k (at) to be in A. However, computer round-off error can completely dominate the calculation and make the implementation difficult. A typical example is given in [5]. For the purpose of overcoming this difficulty, Li proposed in [5] a rigorous numerical procedure which can be implemented on a computer with negligible round-off error. Piecewise constant approximations are used to reduce the original infinite-dimensional fixed point problem to a fixed point problem of a stochastic matrix, thus solving a conjecture of Ulam’s [10]. The numerical procedure proposed by Li is actually a Galerkin projection method with piecewise constant function approximations. We shall give a brief intro- duction to Galerkin’s projection method in the next section. 10 2.2 Galerkin’s Projection Method Let X be a Banach space. Suppose M and N are both closed subspaces of X. If X = M+N and MON = {0}, then we say X is a direct sum of M and N, or M and N are complementary to each other. In this case we may define a linear operator Q : X —) X by szu if x=u+v, uEM, vEN. This operator is continuous and satisfies Q2 = Q [1]. We call Q the projection of X onto M along N. Now let X and Y be two Banach spaces, T : X ——> Y be a bounded linear operator, and y E Y. We want to solve the operator equation Ta: = y. The general principle of projection methods is as follows. Choose two sequences of finite-dimensional subspaces Xn and Y, of X and Y, respectively. Let {Qn} be a sequence of projections of Y onto Y". We want to find 2:99 in X7, such that Qn(T:c(”) — y) = 0, or QnTrc(") = Qny- If we choose a basis of Xn and a basis of Y", then the above approximate operator equation of finite rank can be written as a system of linear algebraic equations. Thus we can use the usual numerical algorithms to solve the algebraic system and obtain approximate solutions to the original problem. This procedure is referred to as the projection method. In particular, if X = Y and if we choose Xn = Y, and the same basis in Yn as in X“, then the corresponding projection method is called Galerkin’s method. 11 Chapter 3 Piecewise Linear Projection Approximations Assume S : [0, 1] -—> [0, 1] is piecewise 02 satisfying inf IS’(:r)I > 1. In this chapter we look for approximate solutions of the F robenius-Perron operator equation P5 f = f in the space of piecewise linear functions. In Section 3.1 we define a sequence of pro- jection operators from L1(0, 1) to subspaces consisting of piecewise linear functions. Section 3.2 establishes the uniform boundedness of the variation of the projected functions. The convergence theorem is proved in Section 3.3. 3.1 Projection Operators Divide I = [0,1] into n subintervals II, 12,...,I,,. For i = 1,...,n, let I,- = (xg_1,:c,-) and l,- = x1i/m(I,-). Denote by A" the 2n-dimensional subspace of L1(0, 1) spanned by the basis {1,-, 9:13;]; i. e., An C L1(0, 1) is the set of all functions which are linear on each subinterval 1;. To define the projection Q" : L1(0, 1) —> An we require that, for 2' = 1,. . . ,n, =0 and 20. 12 Here for g E L1(0,l) and h E L°°(0,1) = [L1(O,1)]"', < g,h >= fol g(a:)h(:r)d;r. The following lemma shows that these requirements uniquely define (2,, and make Qn a projection from L1(0,1) to An along J"A" E {g E L1(0,l) : < g,h > = 0 for all h E An}. Because of the similarity in the “orthogonality condition” with the L2- space case, we may call Q" : L1(0, 1) —* An the orthogonal projection, even though its norm may not be 1. Lemma 3.1.1. Let 5:; = (25.1 + x,)/2, i: l,...,n. For any f E L1(0,l), w have an = 2(61' + d;.’1:)l i=1 where for i = 1,...,n, {a=t(an—mmnm¢ 2m)()h (m, d=.W.M( xvma Proof. Let an = 22;, (c,- + d,$)l,-. Then 1 '1' < an,1:' > — Ci < 11,1; > +di < $11,1i> = mm) 61+ m dz, < an,$1.' > = C.‘ < 15,151; > + d; < $1,314; > 53; $3 + Inter—1 + xi] = —— C; (1,. From the condition of the orthogonal projection, we have {finq+f‘7d'=—i—)II m... (3,, in x2+z..1:._1+x2_ ' We Ci + 3mm ’ d" T111.) f1.- ”(’3)“ The equation (3.2) has a unique solution {s=hme—:mdfl- avmm th=fi%hw—Muflwa Q.E.D. The next Lemma establishes the uniform boundedness of the sequence Q". Lemma 3.1.2. For all n, [I Q, I] _<_ 2. 13 Proof. Given n and f E L1(0,1), || an || /‘I(Q.f)(x))dx= / Z 1(c.+d.-.-xx)1( )Idx i=1 = i/.——m(1—)|c,-+dx|dx i=1 By (3.1), in the subinterval Ig, Qn f only depends on the values of f on 1,. Hence it is enough to estimate a typical W11.) f 1'. |c,- + d,-:L'| dz. Without loss of generality, we may assume d,- 7’: 0. For simplicity, let I = I,- = [a, b], 5: = in, c = e., d = d,- and f be defined on I. Let 0 and (0(a) < 0. The other case can be treated similarly. Thus we have /, mm = 312—.) Ma) + (b—z) 10122)) = g [(b + 3M)» + (a + §)w(a)), and, _ "2(1)? f1f($)d$ fl 5+6 d: 12f,(:1: — a:)f(:c)d:r + 2 ’ “+3 m(1)’f1fx( )1 _fl d 12 f1(:r - 5:)f(:r)d:1: 2 ’ 50(b)= 1 —(c+db)= — {/11 (——x)da=+ 6 ( —i‘)f(x)d:v] m(I) m( ()1 m(61) , 1 l - Span{1,:r} is the orthogonal projection mentioned above. From the above estimate, we obtain 11 CM 11 -—- flaws) )1dx=>_:/;n—(1,— 0.1c.-+dx1d:c s 22/.”(1: )1dw=2/ lf( )1dx=211111 i=1 15 i. e., for all n, 11 Q. IIS 2. Q.E.D. Lemma 3.1.3. When meshAn '-_= max{m(I,-) : 1 S i S n} -—> 0, an —) f in L1 norm for all f E L1(0,1). Proof. Given f E L1(0, l) and E > 0, there exists a continuous function g such that M f — g ]]< 6. Now 11 any-911 = 22/ 1112.9)1y)— g1y)1dy = :[k m(1 L)(ci+d1:)-g(y) dy = 2],, —1—_m) [191x d—n:(2+33 [1 -—a)g1x)dx + (Ki—1235A” — i1)9($)dw)y — 9(y)[ dy g 3,717)- fg1x)dx-g1y)[ dy m(—,—,31 1[ 1x- x.)g1x)dx)1y —x.-) dy 3 Z/,—————( h1:1x)—g1y)1dx)dy +2711»).- a)g1x)1dx- f1. 11—92111). Since g is uniformly continuous on [0,1], when mesh An is sufficiently small, for any 3:, y E 1;, i = 1, . . . ,n, we have |g(:r) — g(y)| < 8. Applying Hblder’s inequality, we get 11 Qua—all s 2E[gm—1”—.m(z.)§dy .. —1'm(.-)3 if (” ”mil/2 [+/::($ )2d$[1/: /I [31-513de x- 1/2 (:1? - 51;)3 l S §2( i=1m(112')3{l 3 ix,_1} [ [g1x)'~'dw]1/2- [mug/2r + 1m1I;)/2)J[ 16 = %+%§:m(1-)1/2{/Iig(x)2d:r]1/2. i=1 . l/2 . For n suffiaently large, ([1, g(:c)2da:) < 7‘5, 2 = 1,. . . ,n. Consequently, 32mm)” 5 5 Hag—9135+ + i=1 =5. [\Dlm From Lemma 3.1.2, M Q" ”S 2 for all n. Hence, for n sufficiently large, “0.1—1” 3 llan—Qngll+llQng—g|l+llg—fll s 2IIf—g||+€+ Ilf—glls4e- This proves limnnoo an = f. QWED 3.2 An Inequality for Variation The following result is essential for our convergence analysis. Lemma 3.2.1. For any f E L1(0, 1) of bounded variation and for all n Van_<_13Vf- Proof. By definition an= 2,-=1(c,- + d;a:)1,-, where {c,-,d,-} are given by (3.1). Since Qn f 18 piecewise linear, its variation is given by 1 1 \o/an = ,2; "115(1) |(C.' + (11351) - (Ci + 61131—1” C.+ d ___-’B.' Ci+1 + di+1$i + _ :61 m(—I—-) m(I.-+1) _ _ 61 _ cm ‘1‘ _ d‘“ :c' — Zld'l+zm(11') m(1i+1)+(m(1‘) nl(11+1)) 1| 1:1 i=1 : ildi|+ri—m(1))/1Wf m(Il.-+1) /11+1 f(1)d:1: i=1 {:1 125:; 1223; ~ ‘ W [1+1(x_ xi+l)f (3M1: _ m(11)3 /11($ — $1)f($)d1 121‘; 12.1); +—— m11)3 ,‘1x— w) 1x1dx— m [Ho—mvowm 17 f(fldm m(11_——i_—+1) 1+, =112($,+1=1_ 1:1) ... m(1;+1)31_+1(x _ x1+l)f($)dx +12—(—"”(——‘,’ “/11 1)df(x) 1 —m(11°+1) [6+1 6 ~ 6 - m =1:1(:B - $1+1)f($)d$ + REF/11'“: - $1)f($)d$ - From the definition of d,- we have f(fldrv + 1 \o/Qf <§Id :m—i—I) [1112: 11...) f1... 111111 + ":56: 1 d1+1 + %1‘(|—d 1=1rn(1_11+_1) /1 ~11 f(1)dx + £2: ldil° It is easy to see that the middle summation of the above inequality is not greater than V}, f (for a proof, see [5]). Hence, 1 n 1 Van S 22W +Vf. 0 i=1 0 Now we estimate 2?: 1.-|d I. Let F-(:13)=f,f_1 f(t )dt. Then the integration by parts formula for the Stieljes-Lebesgue integral [8] gives 11.. = 111—2131)?£f“5‘)f($)d3=fibx'wp‘m 12 = Wiw($—:HW( )—|:_1—/F.-(2:) )d(:1:—:13-)] ___ 1113027,“,1') 11(1) 12/1'_ mun] : mfI.)./If(t)dt— [U f() M) = 6l'nTII.)/zf (101—; f/m f(t)dtdx] 18 where Q,- = {(a:,t) : :1:,-_1 S a: S 22,-, 21,--1 S t S :r} is a triangular region in the (x,t)-plane and A,- = %m(I,-)2 is the area of 51,-. Using the same technique that was used in [5], we obtain 2 |d,-| = 6 1 i=1 2 m/Lfaldt - 311/11 f(t)dtdx ssvf. Therefore, 1 1 V an _<_ 13 V f- o o Q.E.D. 3.3 Convergence Let Pa = Q,, o PSlAn' Then Pu : An —1 An is linear. We want to find the fixed points of P,, in An. For this purpose we first investigate the representation of Pn using the basis {1;,:1:1,-},'-‘=1. Lemma 3.3.1. For i = 1,. . . ,n, Pal; :2 iCj(1g)1j+i:dj(lg)$1j Pn($1,') = i6j($lg)lj+i:dj($lg)$1j, where , _ _ m(5'1(11)011)_ 125131 —5:- . 1.“, c.11.) — mu.) 111111121.“ .11P1.>1)2, 12 ~ dj(1z') = YEW/11in: —$j)(Pli)(-T)d$1 c.1111) = /,1P1zl.-))1x)dx—n:(2:’,, 1.11-1.1110111111111111, d,-(:1:1,-) = m(112j)2/1(x_jj)(P($1i))(x)dx' j Proof. By definition Pnl, = QnoPlg, Pn(x1,-) = QnoP(:rl,-). From the definition of P, f,j(P1,~)($)d:1: = W. Using Lemma 3.1.1, we achieve the assertion. Q.E.D. 19 Lemma 3.3.2. P” has a nontrivial fixed point f,, in An. PPOOfo Let 01 = (41) = (6101)) 02 = (C21) = (Cj($11))1 D, = ((#1) = ((1,-(15)), D2 = ( 11,-): (d (:1:1,- )), where cj(1,-,) d (1,- ), c,(:1:1,-) and (1,-(3:1,) are as in Lemma 3.3.1. Then the function f,,(:1:) = L, 0,-1.- + 2;, d,:1:1,- is a fixed point of P” if and only if the column vector (c1, . . . ,c,,,d1, . . . ,d,,)T is a fixed point of the matrix Pa = 0; C2 D] D; We first prove that the row vector I = (1,...,1,:'1':1,...,:i,,) satisfies 1 = 1P”. In fact, from the first equality of (3.2), £31,0- )+:1:,-d ,(1,)) = :[J(P1,(xdx_Z/l(1),dx " m5( ‘(IWIO = 2 "1(11') :1’ j=l i(cj( (:1:1,-)+:1:J-d -,-(:1:1)) = 12:; IL(,-(Pa:1)) (:1::1:)d = LES/4(1).) 1:1,(:1:)d:1: z/Ll:1:1,-(x)d:r 1' 1 711711 mu.) 2 Hence the matrix 13,, has an eigenvalue 1 and it follows that Pnp = 11 has a nontrivial solution. Q.E.D. In [4], Lasota and Yorke prove that, if S : [0, 1] —1 [0, 1] is a piecewise C 2-function satisfying M = inf [5’] > 2, then for any f E L1(0, 1) of bounded variation, 1 1 VPsf S 0H fll +flVf (3-3) 0 o with a > 0 and fl = 737 < 1. With this result, we can prove the following: Lemma 3.3.3. Suppose S : [0, 1] —+ [0, 1] is piecewise C'2 with M = inf |S’| > 26. And for each 11 let fn be a fixed point of P,, such that I] fn H = 1. Then {V}, f,,} is bounded. 20 Proof. Since f,, is piecewise linear, it has bounded variation. From (3.3), P fn is a function of bounded variation. From the same inequality and the fact that fn = Pnfn = Qn o Pf", using Lemma 3.2.1, we obtain 1 Vi. 0 1 1 1 VQnon. :13VPf. _<_ 13(a II f1 ll +flan) 0 0 0 1 W- O 26 El 1 = 1311+ 13fl\/f,, = 1311+ 0 By assumption M > 26. Therefore for all n 1 130 <—————- . \o/f" ’1—26/M <+°° Q.E.D. Now we can prove our convergence theorem for the first order piecewise polynomial Galerkin approximation scheme of the F robenius-Perron operator equations. Theorem 3.3.1. Suppose .S' : [0,1] —+ [0, 1] is piecewise 02 satisfying M = ianS’I > 26. Then for any n, P“ has a fixed point fn with H fn II = 1 in An and when mesh An —+ 0, there exists a subsequence {fm} C {fn} such that f,“ converges to a fixed point of P3 in L1 norm. Proof. By Lemma 3.3.3 and Helly’s theorem [8], there is a subsequence {fm} C {fn} which converges in L1 norm to some f E L1(0,1). Now llPSf—fll S llf’fnill + llfn1_Qn1°Pan1ll + llQn1°Psfn.~-Qn.-°Psfll + H Qmopsf-Psf ll- Since U] Q", 0 P3 H} is uniformly bounded and Q", ong,,, = fm, lemma 3.1.3 implies that the right hand side of the above inequality approaches zero as 2' —> 00. Thus Psf = f. Q.E.D. Corollary 3.3.1. Let S : [0,1] —> [0, 1] be piecewise 02 satisfying inflS’l > 1. Then a sequence gn from the piecewise linear functions can be constructed which converges to a fixed point of P3. 21 Proof. Choose 11: > 0 such that for M = inflS’I, M" > 26. Let 1,9 = 5'". Then Pn(1p) has a fixed point ff,“ of unit length in A“. Define 1 k—l . 91' = ; ZWSYLST), i=0 where f”, is a convergent subsequence of {fn} obtained by applying above theorem. Then g,- converges, by Theorem 3.3.1, to 1 11.1 g = F 2(P3)jf(¢)1 1:1 where f”) is a fixed point of P(, = PS1. This g is a fixed point of P5. In fact, since (P5)"f(“’) = PSLfW) = owfio) = f(1p), 1 P59 = giPsfM + ' ° - + (Ps)"f(“’)} = 9- Q.E.D. 22 g “HLVLQ L Chapter 4 Piecewise Quadratic Projection Approximations In this chapter we will generalize the piecewise linear approximations of the pre- vious section to piecewise quadratic ones, that is, we look for approximate solutions of the Frobenius—Perron operator equation in the space of piecewise quadratic functions. As in the previous chapter, we divide the discussion into three sections. 4.1 Projection Operators Let 2:0 = 0 < :131 < - -- < £13,,_1 < 3,, = 1 be a finite partition of the interval [0, 1] as before. For i = 1, . . . ,n, I,- = (:1:,-1,:1:,-),:1':; = 1112-3. Let An = span{1,-,:1:1,,:1:"’1,-}?___1 where 1,- = RTIL-TXL’ and denote max,- m(I,-) by mesh (An). Then An C L1(0, 1) is a subspace of dimension 3n. Define the projection Qn : L1(0, 1) —> An by the orthogonal conditions for i = 1, . . . , n (f—an1li) =01 (f_an1$11') =01 (f_an,$211') =0 for 2' = 1, . . . ,n. Let an = 23:1(9' + (1,-:1: + ejx2)1j. We show that {cj,dj,eJ-};-‘=1 are uniquely determined by the above conditions. 23 Forz=1,...,n, 1 5: $2 + $13314 + 39—1 Q1f11. = — d1+ ‘ ‘ 611 f ) m(11q)m(h) 3m(11) 21 IE? +E1x1—1+$2_1 “(It +1312—1) 1, 1.- = —- ' d 1, (Q f a: ) 11111.)“ 3m11.) + 2111(1) ‘3 2 2 ~ 2 2 2 CC,- + 31931—1 + 171—1 $i($i + :1:,-_1) n 1 1' = 1 di (Q f x 1) 3m(I,-) C 2m(11') +5m1(11'?)($ +$$11+$1$11+$$11+$1 l)e" By the orthogonal condition we have c,'+:'1'3,-d,1+—3,-(:1:2+:1:,-:1:,-_1+:1:,-_1)e,- =fo(a:)d:1: 5101' + %(1‘? + 1031-1 + $3.1)d1 +1110” + $1-1)61'=.f1 $f($ )dx flat? + 3313614 + x?_1)c1- + 12101:? + x?_1)d1+ %(x‘1‘+m.-x.-1x?+x.1+xx.1+x.1)e.=.xf1 11m) Eliminating c,- from the above system yields %m(1)2d,-+ %,-m(1)2:1:,e,-= f1..(:c — i;)f(:1:)d:1: %m(Ig)2§:1d,- + 315m(I,-)2[4:1:? + 7:1:,-:1:,-_1 + 42:,?_1]e,- = f1.- $2f(x)d$ - %($? + 90131-1 + 1312.1) f1.- f($)d$- The solutions are given by I c.- = 311.. 11111:» —,,::,f—;—. f1 111 )dx —3,:',::,-1 f1. f(rv)drv+ ;%2,—1[2i? + $1$1_1]f1,(-’B — 3731')f(17)dl‘ i d1 = m(1 ——)2 f1,- $f($)d$ + 1(1)2 f1.- f($)d$— .1111. M 1.2-) 11211111 , 61' = fir f1.[(1' — 502 - 315m(11)2]f(x)dx Lemma 4.1.1. I] Qn I] _<_ 62 for all n. (4.1) (4.2) Proof. The values of Q“ f on the subinterval I,- depends only on the values of f on I,-. So we only need to estimate the integral fL|(Q,,f)(:1:)]d:1:. Let I = I,- = 24 [a, b], 51': = 1% and let 90(3) 2 W175“ + d1: + 6122) be the orthogonal projection of f onto Span{11,311, 2:211}. First of all assume f 2 0. We consider different cases. (i) 90 Z 0. Then from the first equality of (4.1), /I|99(x)|d:c = [f(ddx = —:—I)-/(c+ da: + 6:132)d$ = —1—)mI[ca:1}-dac(2 + §x3]b=c+dx+%(a2+ab+b2)e = [1) f(x) d2: = [I ”(1)1111. (ii) 1,0 2 0. Then 1p has two distinct zeros on the real axis. Without loss of generality, assume (3 > 0. We will deal with the different distribution of the zeros. Let (1 and (2 be the zeros of 1,0 with (1 < (2. First, assume (1 E (a, b) and (2 6 (a,b). Then (1 + C2 = —g, (1 ~(2 = 5.11; follows that £|¢P($)ld33 = 31%?) {/0416 + dx + 6x2)dx — [f(c + dx + 6x2)d;r b +/(c+dm+ex2)dar] (2 _ 1 d 2 6 30 d 2 e 3 C2 — m(1){[cx+2:c +3$L -[cx+2:r +32: (1 b + C$+£1-222+E$3 2 3 (2 1 d 2 2 e 3 3 = m[c(b—a)+-2-(b —a)+§(b -—a)] 2 d 2 2 e ~3 3 + m [C(Cl -' C2) + 5&1 ‘ C2) + 3(91—Czl] .—. [c+di‘+§-(a2+ab+b2)] "—2“? "1(1) (1) [0+g((:1 + C2) + §(Cl + (2)2 — C143] _ (C2 (I) d d 6’ d 2 c - I1 11—11111-1113171 ~21 25 _ C2—C1 d2—4cc ‘ Anna“ m(I) 3e Since (1— — ’d {22—6—— '4“ and C2 — -"——d+V2‘: “48° ,Cz — (1— —. flit—TE S m(I). Hence (d2 — 466); S 63m(1)3. So, (2 — (1 d2 — 46c _ 1 (at2 —4ec)3/=2 < 1 e3m(1)3 _ 1 m(I) 3e _m(1) 362 —m(1) 3e, —§em(1)2. From the last equality of (4.3), it is easy to see that éemU)2 = mfg—PrV/(H f()dx—5/f(x)d 5 m(I)2/4m(1)): “(x ”34/“; = 10/If(x)dx. Therefore, /1 |cp(:c)|d:z: s [I f(x)d:c+ 10 j] f(x)d:z: = 11 f1 f(x)dx = 11 f1 |f(:r)|d:z:. Second, assume there is only one zero of (,0 in (a, b). Say (1 E (a, b) without loss of generality. Now, /I|89($)ld93 = 1()([/0C16+d$+6$2 )dCI:+/C1 (c+dx+ea:2:z:)d] = —:T:{[0 ((1—a)+§(C12—a2)+§((13—a3)] c(1—b)+§(cf—b2)+ §(l bel2 (1)-€12) + (1(1) — (1) + 2(1) -C1)(6C1+ d)] From (4.3) we have 2eb+d = -r:——f(53:2/(x 59mm 3:)" ——),/fd(m)d ——(—2—m1),/m’(x [15:2fdm-:L—(z3:(/(x-é)2f(rv)dw z 31%/1(x_fl):(thIni(_L1:2/Wnzl(811))2/()df( +7nii?/W 1332/ f 180 1 2 _ 9 . = W [Io —:c) f(x)dx — W flu—mocha — E175]: mo. 27 Hence, 4 e_(———b (1)3 (5"Cll2 [Immune = /f( )dm+— —(—m1) ————m(,) [— 15—7073 f(x- We —-—1(——§) /,(b- x)f(w)dx 11—15137]??de _<_ / f(x)da: + -.m(1)2+ / (b <1)f sodas +9 /, f(x)d:v s [1+4.10+12+9]/If(a:)d:=62/If(()da: = 62 /1 | f(x)|da:. Therefore for f _>_ 0, H go H _<_ 62 [I f H. For general f E L1(0, 1) applying the above to f+ and f“ we conclude || (,0 H S 62 [I f H. Q...ED Lemma 4.1.2. For any f E L1(0,1), if mesh (An) —> 0, then an —> f in L1 norm. Proof. First assume f E L2(0, 1) C L1(0,1). From the definition of an we see that M f — an “2: min{|| f —- g ”2: g E An} where H - ”2 is the L2-norm. From the theory of the finite element method we have I] f — an ||2—» 0. By the Cauchy inequality || an - f H S H an - f ||2- Thus || an - f H —’ 0- Now for f E L1(0,1) and e > 0, there exists g E L2(0, 1) such that [I f -— g H < 5. From “an—f“ S llan—Qngll+llQng—gll+llg—fll S 52l|f~9|l+llQng-gll+||9-f|| and since || Qng—g||—>0, weobtain || an—f||—+0. Q.E.D. 4.2 An Inequality for Variation We establish the uniform boundedness of the variation of the projected functions as follows. 28 Lemma 4.2.1. If f E L1(0,1) is of bounded variation, then for all n, 1 1 Vans 121Vf. 0 0 Proof. Since Qn f is piecewise quadratic, we have 0 3:1 : d d g Ii) A; I + 2C :13] (B + ":1 Ci + di$i + 6m}? _ Ci+1 + di+1$i+ (Bi-HIE? : £17131) / Id +26 xlda: _ Ci+1 di di+1 ) + — $3. +2: (iii-IT) m(1i+1)) (m(Ii) m(Im) mf—H) )xz rn(i+l) : _ Idi + 26.-:1: dz: :2: (11.) )f, ' 1m(1i+1)31i+1 1+1 "H ' ' 2 3+1 +15%] f(x)d 3 1) + _—/I./I- 3602? IL" — 60 211::- + (I); :13; — 180$ m(1i+1)51.-+1 [ +1 ( +1 +1 ) :3] (37 — 53i+1)2 f(ar)dx m1; 3 1 +5 m—_(I.) )/Wf m(LH) /I.-+1f(x)d$) = gfimid +26 ml + Z Trl'(——16-m_..+l)2 zinc-10!:- ”hack? 6 3___0__ ~ 2 . —H%5£.+1(:—$i+1) f (3)61“ gm] f( 29 3 1 —§m(I.-+1) 1.41 f($)d$ . (4.4) Let Q.- = {(a:,t) : .1: E 1;, :c;..1 S t S :12}, V,- = {(x,t,s) : :L' E 1., 12,-_1 _<_ t S x, 23-1 5 s _<_ t}. Again the integration by parts formula for functions of bounded variation yields Hill-2.175 n+1 0. Then C_ — —— is the minimal point of go and cp (— 59%) = #7) (c — {—2) IS the minimum value of «,9. If a < C < b, then 1 \I/cp = WWW) + An using the basis {1g,$1g,$21}_10fAn,i. e.,P{11,:1:11,:c211, - ,ln,;r1n,:r21n} = {11,x11,.1:211,~--,1n, 32 xln,:c21n}13n. Let C = (1,i1,g}1,1,5:2,3]2,---,1,:T:,g,37,g) where 37.- = %($? + xgxg_1+ 2:34). Then for i = 1,... ,n, n “Pam—n+1 = Z(c,-(1.~)+:I:,-d,-(1.-)+gJ-e,(1,-)) j=l = 22/110031“ :c)d:r:_/1(P51g)(:c)dx = lo 1g(:v)d:c=1, (CPn)3(i-1)+2 = 2(CJ(31) + de J(~'81 i)+ yJeJ(xli )) j=1 = 123/! (P5(:1:1) :13)d$ — /01(Ps(:c1.-))(x)dx = [)1 xlg(a:)d:c = 53;, (CPnl3i = 2(CJ(3211‘)+ 33de$2(1€)+ .7>/J"3J(5'32 11'» j=l = Z f(p.(.21.))(.)d. = [01(Ps(93211))(17)d$ That is, C is a left eigenvector of the matrix I)“ corresponding to the eigenvalue 1. Therefore there is a nonzero c E .5123" such that 13,,c = c. Thus R, has a nonzero fixed point in An. Q.E.D. Theorem 4.3.1. Let S' : [0, 1] —+ [0, 1] be piecewise C2 with M 2 inf lS’I > 242. For each 71 let fn be a fixed point of Pn in An with H fn ll = 1. Then there exists a subsequence {fm} C {fa} convergent in L1 norm to a fixed point of P5. Proof. By inequality (3.3) in the previous section, we have for any n W o l l l VPnfn =VQnOPan S 121VPan 0 0 0 1 1 g 121 (a ll f. H +%Vf.) = 121a+B\/f.. with 5 = 313-} < 1. Hence \l/fnS 11210 < +00 0 -fl ' 33 From the Helly theorem there is a subsequence {fm} C {fn} which converges in L1 norm to some f E L1(0, 1). From ll Psf-fll S Ilf—fni II + ”fn.‘ -Qn.-°Psfn.- II + llQniOPani_Qni°PSf“ +||Qn1°Psf—Psfl| we immediately see that P5 f = f. Q.E.D. The proof of the following corollary is the same as that of Corollary 3.3.1. Corollary 4.3.1. Suppose S : [0, 1] —) [0, 1] is piecewise 02 satisfying inf IS’I > 1. Then a sequence gn from the piecewise quadratic functions can be constructed which converges to a nontrivial fixed point of PS. 34 Chapter 5 Markov Finite Approximations In this chapter we take a different approach. Since the Frobenius—Perron operator is also a Markov operator, it is natural to approximate it by Markov operators of finite rank. The “orthogonal projections” of the Galerkin scheme used earlier are not Markov operators in general except in the piecewise constant case in [5]. To overcome this defect, we use continuous piecewise linear and piecewise quadratic Markov approximation schemes to find an approximate fixed point of the Frobenius- Perron operator. The convergence of these methods will be shown for a general class of nonsingular measurable transformations. In section 5.1 we discuss piecewise linear Markov approximations and section 5.2 is devoted to piecewise quadratic ones. 5.1 Piecewise Linear Markov Approximation Assume S : [0, 1] —-) [0,1] is piecewise 02 satisfying inf | S" |> 1. In this section, we look for approximate solutions of the Frobenius-Perron operator equation P3 f = f in the space of continuous piecewise linear functions. For simplicity divide the interval [0, 1] into n equal parts. Let I,- = [33,-” 33,-], :22.- = %,i = 0, . . . , n. Each subinterval I,- has length '3". Denote by An the space of contin- uous, piecewise linear functions corresponding to the above partition. Then An is a linear subspace of L1(0,1) with dimension n + 1. First of all, we choose a basis for 35 An.Let 1+2: —15:1:SO 1M3): l—a: US$51 0 otherwise. Then z/2(a:) is the so-called hat function. For i = O, . . . , 12, let Nit) = W710? - $0)- Then (p.- is a continuous piecewise linear function with An is a Markov operator and hence llinl =1- Proof. From (5.1) it is easy to see that f 2 0 implies an Z 0. To prove Q, is a Markov operator, it remains to show that for f 2 0, IIan” = II fl] This can be done by the following computation. ”on!“ = flail: [01an = n[[If/Olsoo‘l'5::(jl‘f+/Ii+lf)/olioi+ Inf/0150"] z %[/Ilf+:(/hf+/Imf)+/Infl = Z/Iif=llfll. 36 It follows that “Qn” = 1. Q.E.D. Lemma 5.1.2. For all f E L1(0,1), limnnoo an = f. Proof. We first assume f is a continuous function on [0, 1]. Notice that [LG 1,9,(x) E 1. Hence, (n/ f) 0, there exists 6 > 0 such that if %< 5 and x,y E I;UI.-+1 for any i,|f(a:) — f(y)| < c. For i < 6, |nf,1 f — f(x)| < c for a: E II, Inflnf— f(at)| < c for :1: E In and l%(fz.f +f1i+1f) —- f(x)| < c for a: E I.-U I;+1,i=1,...,n — 1. Hence, |an($) - f($)| S 6:80:19?) = evil: 6 [0,1]- i=0 That is, for f E L1(0, 1) continuous, Qn f converges uniformly to f. Now let f E L1 be arbitrary. Given 6 > 0, there is a continuous function g satisfying ”f —g|| < 5;. Because ||Qn|| = 1, we have llan—fll s llan—Qngll+||Qng-g||+l|9-fll s 2||f - all + 1le — all < § +11% — all- From what we proved above, there is an N > 0 such that for n 2 N, ||Qng — g“ < :3. Therefore for n 2 N 11an — fll < g + ; = e. Q.E.D. We show now that Qn f will not increase the variation of a function f of bounded variation. 37 Lemma 5.1.3. If f 6 L1 is of bounded variation, then for any n, Vansz. Proof. Let an(:c) = 221:0 q, An is a Markov operator of finite rank. Let Pngo; = 2210 p;,-cp,~,i = 0,... ,n. Let 131: = (pij) be the corresponding (n+1) x (n+1) matrix. Let fn = 213:0 0190;. Then Pnfn = fn if and only if CE, = c with the row vector c = (c0, . . . , cn). Lemma 5.1.4. For each n there exists a nontrivial nonnegative function fn E An satisfying Pnfn = f... Proof. Since Paw; = QnOPs‘p.‘ 38 1 n-l = n{(/ P5101) 2. Then for nonnegative fixed points fn E An of P", the sequence {V}, fn} is uniformly bounded. Proof. By Lemma 5.1.3 and inequality (3.3), l l 1 an = VPnfn =VQnOPan S VPan 0 0 0 0 l I S allfn“ +16an =a+flan° Since ,8 = 734— < 1 by assumption, we have C! \:)/fn31_fl<00- Q.E.D. Now we can prove our main theorem. Theorem 5.1.1. Suppose S : [0, 1] —1 [0, 1] is piecewise C2 and M = inf IS’(:I:)] > 2. If the corresponding Frobenius-Perron operator P5 has a unique invariant density f, then the sequence {fn} of nonnegative piecewise linear fixed points of Pu in An converges to f in L1(0,1). 39 Proof. From Lemma 5.1.5, the sequence {fn} is bounded in variation. Helly’s theorem [8] implies that {fn} is precompact. Let {fnk} C {fn} converge in L1 norm to some 9 E L1(0,1). Then ”Psg —g” S ”g _ fnk” + “fflk — Q“): o Psfnk“ + ”anOPank—anOP5g“+”anOPSg—Psg”. Since Qn,‘ o Psfn,‘ = fnk and since “an 0 PS" 3 1, Psg = g. Obviously ”g“ = 1 and g 2 0. By the uniqueness of the fixed density of P5 we assert that g = f and that all the convergent subsequences of {fn} converge to f. This proves limn...)o fn = f. Q.E.D. By the following familiar trick we can ignore the condition M = inf IS" (:r)| > 2. Corollary 5.1.1. If S : [0, 1] —+ [0, 1] is piecewise 02 satisfying inf IS'] > 1 and P3 has only one invariant density, a sequence 9,, from the piecewise linear functions can be constructed which converges to the fixed density of P3. Proof. Choose 1:: such that Mk = (inf|5’(:r)|)" > 2. Let (15 = 5". Let fn(¢) be the fixed density of Pn(¢) as in the above theorem. Define 1 k-l . 9n 2 7c" 2(P5)an(¢)° i=0 Then 9.1 converges, by Theorem 2.1, to 1 k-l g = r §(Ps)jf(¢), where f ((25) is a fixed point of <15 = S". This 9 is the fixed density of P5. In fact, since (PS)'°f(¢) = P51f(¢) = P¢f(¢) = f(¢), P59 = $93111) + ---+ (Ps)"f(¢)} = g. Q.E.D. 40 5.2 Piecewise Quadratic Markov Approximation We generalize the method in the previous section to piecewise quadratic Markov approximations. As above, let I.- = [2314,23,] with 2:.- = %,i = 0,... ,n. Each subin- terval I.- has length :1“. Let 9,, be the corresponding space of continuous piecewise quadratic functions on [0, 1] associated with that partition. Then 0,, is a (2n + 1)- dimensional subspace of Ll(0,1). In order to construct a basis for (1,., we define (2:+l)2, —1<$SO 7(3): (x—1)2, 0_ 0 for all k and 2:20 45;.(23) _=_ l, 3. If f = 2,210 qk¢k, then f(x.) = Q2; for i = 0,... ,n. Define Qn : L1(0,1) —+ 9,, as follows 62.1: (n/f)¢o+nZ(/1)¢2._1;-l+ 2/1+/1)¢2.-+(n/1)¢2.. i=1 I' Lemma 5.2.1. Qn is a Markov operator and hence llQn” = 1 for any n. Proof. It is obvious that f 2 0 implies an Z 0. By direct computation, for f 2 0, no.1” = [0‘ 10.1) = [0‘ GM 41 = .111A‘1.+.<:/R1/;1._. i=1 + 3&1,“ 1...f)/01¢2‘+"/1.f/ol¢2" = é.f+£§t.f+a'§+%/.f = [011:]: |f| = llfll- Q.E.D. Lemma 5.2.2. lim,,__.oo an = f for any f E L1(0,1). Proof. We First assume f is continuous. Then, it n 71-1 62.1 — 1 = (nfh1)1o + n;(/R 1112.-. + 5 Ex]! 1 + f, 1)12. 271 + ("/1 f)¢2n — Ef¢j = ("/1 1 — 1110 + 2301/, 1 - 1112.-. + 7231qu Hf,“ f) — flab.- + ("/1. f — 1).»... i=1 For any 6 > 0, there is 6 > 0 such that for i < 6 we have |f(.r) — f(y)| < c for any 9313/ E I;UI;+1,i=1,...,n -1- Hence inf!l f — leh < 511%(f1.f+ f1,+1 f) — leL‘UIHq < 51i= 1, - - - ,n --1, and In f,” f— leIn < c, where XA is the characteristic function of A. It follows that for n sufficiently large and a: E [0, 1] 2n Ian(:c) — f(sv)! < 62 4510:) = 6, i=0 i. e. , Qn f converges to f uniformly as n —+ 00. Therefore ”Q” f — f I] —> 0. Now for arbitrary f E Ll(0,1), we can find a continuous function 9 such that ”f — g” < g for given 6 > 0. Since ”an — f” S “an — Qngll + ”621.9 — all + My - fl! 2 < 35+ ”Q39 — g“: from the first part of the proof, we conclude that limnnoo Qn f = f in Ll-norm. Q.E.D. 42 The next lemma is crucial to our convergence theorem. Lemma 5.2.3. If f E L1(0,1) is of bounded variation, then Van fs\;/1. Proof. On the interval I,- = [ax--1, 33,-] we have an($) = (121—24521-2(1‘) + (hi-115214“) + 421952433) = q21—2(n($ “ $1-1)-1)2 + q2.-_1[2n($ - $1-1)(1- "(95 — 31—1))14" 921("(17 — 1‘1) + 1)2 = q2,-_2(n:c — i)2 + 2q2,-_1(n:c —(i—1))(i— nx) + q2.-(n:r — (i — 1))2 = (421—2 - 2421—1 + q21)(m‘)2 — 21(421-2 - 2421—1 + q21)i + (121—1 — q21]nx + [(q21—2 — 2q21—1 + (121)2'2 + 2((121—1 — (121)1' + (121]- For simplicity, let a = q2;_2, b = q2.-_1,c = (12;. Then for a: E 1;, an(x) = (a — 2b+ c)(n:1:)2 — 2[(a — 2b+ c)i + b — c]na: + [(a — 2b+ c)z'2 + 2(b — c)i + c]. Denote the right hand side of the above equality by ¢(n:c). Then the extreme point of ¢(nx) is i_—2[(a—2b+c)i+b—c]_i+ b—c _ —2(a—2b+c)n — n (a—2b+c)n’ and the extreme value is [(a—2b+c)i+b-—c]2 ¢(n:i:) = [(a — 21) + c)i2 + 2(b — c)i + c] — a—2b+c _ 2 = [(a—2b+c)i2+2(b—c)i+c]—[(a—2b+c)i2+2(b—c)i+b%c_)|h—E] __fl’il: a—2b+c° We consider all the possible cases as follows. 05:615. Thenx;_—1< n+m 0, i. e. , the graph of 45 opens upward, then c — b > 0. Hence 0 < ———(c— b)2 —b. a—2b+ca—2b+c>c b In this case, we have _ (b—c)2 (b—c)2 Yan — (C—a—2b+c— )+(C_a—2b+c—C) _ 2(b—c)2 _ c—a—a__2b+ {In is a Markov operator of finite rank. Let Pngbk = 23201111,- for k = 0,... ,2n. Denote the (2n + 1) x (271 +1) matrix (ij) by ~ Pu. Lemma 5.2.4. Pu has a nontrivial nonnegative fixed point in (In. Proof. For k = 0,. . . ,2n, from P111511 = Q71 0 P5451; = n{(/Il P39150950 + Z:(/ PS¢k)¢2i-1 1. 1:3]! Ps¢k+/m Ps1.)12.-+ ”/1. P510111.) we have pko = nf,1 P5¢k,pk,2.-_1 = "fl.- P5¢k,i = 1,...,n,pk,2,- = %(f1,PS¢k + II,“ Ps¢k),i=1,...,n—l ,andpk,1n=nf1nPsqu;c fork=0,...,2n. Let C = (C0,...,C2n) where Co = C2,, =%,C2.-= 32,- fori=1,...,n—1,C2,-_1 = % for i=1,...,n. Then, 2n 1 1 n 5191143 = n{-/ PS¢k+§;£‘PS¢k + 2n—11/Ps¢k+/ Ps¢k)+ +§/ Ps¢kl = nl-l-l Ps¢k+-/ Ps¢kl =n/ (151- 3 o 3 o 0 Note that “452,” = 3%; for i = l,...,n — 1,||¢2.-_1]| = 51; for i = l,...,n, and ”450“ = ”(15211” = 51;, we have PnC = C. Therefore we can find a nonnegative row vector c ;£ 0 such that an— — c. This implies that fn— _ -_0 Cj¢j is a nontrivial nonnegative fixed point of Pn 1n (1,.. Q.E.D. The proofs of the following results follow exactly the same line of arguments as in the previous section. So we omit the corresponding proofs. 45 Lemma 5.2.5. If S : [0, 1] —+ [0, 1] is piecewise 0'2 with M = inf IS’(a:)| > 2,then the sequence {V3 fn} is uniformly bounded, where fn E 9,, is a nonnegative fixed point of P" for each 71. Theorem 5.2.1. Suppose S : [0, 1] —> [0,1] is piecewise 0'2 and M = inf IS’(x)| > 2. If the corresponding Frobenius-Perron operator P5 has unique invariant density f, then the sequence {fn} of nonnegative piecewise quadratic fixed points of Pa in 0,, converges to f in L1. Corollary 5.2.1. If S' : [0, 1] -—1 [0, 1] is piecewise 02 satisfying M = inf IS’(:1:)| > 1, and P5 has a unique fixed density, then a sequence gn from the piecewise quadratic functions can be constructed that converges to the unique invariant density of P5. 46 Chapter 6 Numerical Results In this chapter we present numerical results for some mappings from [0, 1] into itself with our new methods and compare them to Li’s original one. These calculations were performed on the IBM 3090 180VF at Michigan State University, using double precision. Section 6.1 gives the numerical results with the projection methods, while Section 6.2 gives those using the Markov approximation schemes. 6.1 Numerical Results with Projection Methods The test functions are as follows S() 29: OSx_<_% 133 = 2(1—11) %S$_<_1, 1 1 1 1 52(1) = (g—le—5l3)5+§1 2:: < < _1 33(13) = l—x: 0_$_\/i 1;: fi—ISxSI, The invariant densities ff of S; are given by f1'( 1. Based on the convergence analysis for the piecewise linear and piecewise quadratic 55 polynomial approximation methods, we believe that convergence can also be estab- lished for general higher order piecewise polynomial approximation methods, though it would not have much computational practicality due to instability. It is important to estimate the rate of convergence for a convergent numerical method. Further research will be focused on this aspect for our finite approximation methods for F robenius-Perron operator equations or more general Markov operator equations. 56 Bibliography [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] N. Dunford and J. Schwartz, Linear Operators I, Interscience, New York, 1958 T. Kohda and K. Murao, “Piecewise polynomial Galerkin approximation to in- variant densities of one-dimensional difference equations”, Elec. and Commu. in Japan, Vol. 65-A, No. 6 (1982), 1-11. A. Lasota and MC. Mackey, Probabilistic Properties of Deterministic Systems, Cambridge, 1985. A. Lasota and J. A. Yorke, “On the existence of invariant measures for piecewise monotonic transformations”, Trans. Amer. Math. Soc. 186 (1973), 481-488. T. Y. Li, “Finite approximation for the Frobenius-Perron operator, a solution to Ulam’s conjecture”, J. Approx. Theory, 17 (1976), 177-186. T. Y. Li and J. A. Yorke, “Period three implies chaos”, Amer. Math. Monthly, 82 (1975), 985-992 T. Y. Li and J. A. Yorke, “Ergodic transformations from an interval into itself”, Trans. Amer. Math. Soc. 235 (1978) 183-192. L. P. Natanson, “Theory of Functions of Real Variable”, Ungar, 1961. G. Strang and G. J. Fix, An Analysis of the Finite Element Method, Prentice- Hall, Inc., 1973. S. M. Ulam, A Collection of Mathematical Problems, Interscience Tracts in Pure and Applied Math. No. 8, Interscience, New York, 1960. 57 "111111111111111111711171“