Lecture 7: The Fixed Point Theorem and its ConsequencesMy heart is fixed... Psalm 57:71. Fixed PointsWe 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.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 a continuous function, € 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.Proposition 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 that2€ 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 triangular inequality, for n sufficiently large € Dist Pn+m+1,Pn( )≤ Dist Pn+m +1,Pn+m( )+L+ Dist Pn+1,Pn( ) ≤ (sn+m+L+ sn)Dist P1,P0( ) ≤ snDist P1,P0( )1− s <εThe main fact about cauchy sequences is that for many well known spaces every cauchy sequences converges to some limiting value. A space in which every cauchy sequence converges is said to be complete. Intuitively, a space is complete if it has no holes because if the points in a sequence are getting closer and closer to each other, they should be getting closer and closer to some limiting value. The standard Euclidean spaces in n-dimensions are examples of complete spaces. We are now ready to establish the main result of this section: the existence and uniqueness of fixed points for contractive transformations on complete spaces.Trivial Fixed Point TheoremSuppose thatT is a contractive transformation on a complete space€ Pn+1= T(Pn) for all € n ≥ 0.Then € P∞= Limn→∞Pn exists, and € P∞ is the unique fixed point of T for any choice of € P0!3Proof: This result follows from our previous propositions because:i. The sequence € Pn{ } is cauchy. (Proposition 3)ii. Therefore, since by assumption the space is complete, € Limn→∞Pn exists.iii. Hence, since T is continuous, € P∞= Limn→∞Pn is a fixed point of T. (Proposition 1)iv. But, since T is a contractive transformation, this fixed point is unique. (Proposition 2)3. Consequences of the Trivial Fixed Point TheoremThe trivial fixed point theorem has many important applications in Mathematics and Computer Science. Here we will