Lecture 7: The Fixed Point Theorem and its ConsequencesMy heart is fixed... Psalm 57:71. Fixed Points and IterationWe are now going to solve the central mystery concerning fractals: why is it that the fractals generated both by recursive turtle programs and by iterated function systems are independent of the base case? The heart of the answer lies in the trivial fixed point theorem.A fixed point of a function F is a point P such that € F(P) = P. That is, P is a fixed point of F if P is unchanged by F. For example, if € f (x) = x2, then € f (0) = 0 and € f (1) =1, so 0 and 1 are fixed points of f. We are interested in fixed points of transformations because fractals are fixed points of iterated function systems.Fixed points are often generated by iteration. Consider the sequence, € P1= F (P0)P2= F2(P0) = F (P1) M M P∞= F∞(P0)where € F∞(P0) denotes the limit of € Fn(P0) = F(Pn−1) as n approaches infinity (assuming this limit exists). Suppose that we try to apply F to € P∞; informally,€ F(P∞) = F F∞(P0)( )= F∞+1(P0) = F∞(P0) = P∞.Thus the limit point € P∞ is a fixed point of the function F. The point € P0 with which the iteration begins does not matter; as long as the iteration converges, iteration converges to a fixed point.There are two important caveats here. First, there is no guarantee that the iteration must converge. For some starting values -- perhaps even for all starting values -- the iteration may diverge. Second, even if the iteration always converges, the fixed point need not be unique; different starting values may converge to different fixed points.In the next section we are going to establish conditions which guarantee that these two problems never arise. That is, we shall provide conditions which guarantee that the iteration always converges and that the iteration converges to a unique fixed point independent of the initial value. If this result sounds a lot like fractals, this similarity is no accident. Indeed this general result about iteration is at the heart of our observations that fractals generated from iterated function systems are independent of the base case.A word of caution before we proceed. Be forewarned: this lecture is by far the most mathematically challenging chapter in this text. We are going to prove a powerful mathematical theorem with applications to many different areas of Pure and Applied Mathematics, including root finding for transcendental functions, relaxation methods for solving large systems of linear equations, solution techniques for ordinary differential equations, and fractals. Therefore, we shall require some general mathematical machinery that we can apply in a wide range of diverse situations. The power of Mathematics is the ability to reduce many seemingly different problems to their common mathematical essence. The price we pay for this power is abstraction: a collection of mathematical terms, techniques, and theorems the significance of which may, at first, be difficult to understand. Cauchy sequences, complete spaces, compact sets, and Haussdorf metrics will all appear in this discussion. For each of these terms I will provide some informal intuition as well as a formal definition. For fractals, I will explain only the key ideas behind the proofs of the main theorems, providing references for those readers interested in all the fine details. Understanding this material may be difficult at first, and you may need to read this chapter more than once. It may be hard going, but hang in there; the final results will be well worth all the effort.2. The Trivial Fixed Point TheoremWe begin with a rigorous formulation of our informal argument in Section 1 that if iteration converges, iteration necessarily converges to a fixed point.Proposition 1: Let T be a continuous function and let € Pn+1= T(Pn) for all € n ≥ 0. If € P∞= Limn→∞Pn exists, then € P∞ is a fixed point of T.Proof: Since, by assumption, T is continuous, we can push T past the limit sign. Therefore € T(P∞) = T Limn→∞Pn( )= Limn→∞T(Pn) = Limn→∞Pn+1= P∞.For our applications, the most important continuous functions are contractive transformations. A transformation T is said to be contractive if there is a constant s, € 0 < s <1, such that for all points € P,Q€ Dist T( P),T (Q)( )≤ sDist(P,Q).That is, contractive maps bring points closer together. The canonical example of a contractive transformation is uniform scaling, where the absolute value of the scale factor is less than one. It follows from Proposition 1 that if we iterate a contractive transformation and if the iteration converges, then the iteration necessarily converges to a fixed point. Our next result asserts that for contractive maps, this fixed point is unique.2Proposition 2: If T is a contractive map, then T can have at most one fixed point.Proof: Suppose that P and Q are both fixed points of T. Then € T(P) = P and € T(Q) = Q. Therefore€ Dist T( P),T (Q)( )= Dist(P,Q).Hence T is not a contractive map. Contradiction.Proposition 2 guarantees the uniqueness, but not the existence, of fixed points for contractive maps. In order to establish existence, we need to introduce the notion of a cauchy sequence.Informally, a sequence of points € Pn{ } is a cauchy sequence if the points get closer and closer as n gets larger and larger. For example, the sequence € {2−n} is cauchy, but the sequence € {2n} is not cauchy. Formally, a sequence of points € Pn{ } is said to be cauchy if for every € ε> 0 there is an integer N such that€ Dist(Pn+m,Pn) <ε for all € n > N and all € m > 0.Our next result shows that one way to generate a cauchy sequence is by iterating a contractive map.Proposition 3: Suppose that T is a contractive transformation, and that € Pn+1= T(Pn) for all € n ≥ 0. Then € Pn{ } is a cauchy sequence for any choice of € P0.Proof: Since T is a contractive transformation, there is a constant s, € 0 < s <1, such that € Dist Pn+1,Pn( )= Dist T (Pn),T(Pn−1)( ) ≤ sDist Pn,Pn−1( )= sDist T( Pn−1),T(Pn−2)( ) M ≤ snDist P1,P0( ).Therefore, by the triangle inequality, for n sufficiently large € Dist Pn+m+1,Pn( )≤ Dist Pn+m