Chapter 3 The Contraction Mapping Principle

1 Chapter 3 The Contraction Mapping PrincipleThe notion of a complete space is introduced in Section 1 where it is shown that everymetric space can be enlarged to a complete one without further condition. The importanceof complete metric spaces partly lies on the Contraction Mapping Principle , which isproved in Section 2. Two major applications of the Contraction Mapping Principle aresubsequently given, first a proof of the Inverse Function Theorem in Section 3 and, second,a proof of the fundamental existence and uniqueness theorem for the initial value problemof differential equations in Section Complete Metric SpaceInRna basic property is that every Cauchy sequence converges. This property is calledthe completeness of the Euclidean space.

2 The notion of a Cauchy sequence is well-definedin a metric space. Indeed, a sequence{xn}in (X,d) is aCauchy sequenceif for every >0, there exists somen0such thatd(xn,xm)< , for alln,m n0. A metric space(X,d) iscompleteif every Cauchy sequence in it converges. A subsetEiscompleteif(E,d E E) is complete, or, equivalently, every Cauchy sequence inEconverges with (X,d)be a metric space.(a) Every complete set inXis closed.(b) Every closed set in a complete metric space is particular, this proposition shows that every subset in a complete metric space iscomplete if and only if it is 3. THE Contraction Mapping PRINCIPLEP roof.(a) LetE Xbe complete and{xn}a sequence converging to somexinX.

3 Sinceevery convergent sequence is a Cauchy sequence,{xn}must converge to somezinE. Bythe uniqueness of limit, we must havex=z E, soEis closed.(b) Let (X,d) be complete andEa closed subset ofX. Every Cauchy sequence{xn}inEis also a Cauchy sequence inX. By the completeness ofX, there is somexinXtowhich{xn}converges. However, asEis closed,xalso belongs toE. So every Cauchysequence inEhas a limit 2050 it was shown that the spaceRis complete. Consequently, asthe closed subsets inR, the intervals [a,b],( ,b] and [a, ) are all complete sets. Incontrast, the set [a,b), b R,is not complete. For, simply observe that the sequence{b 1/k},k k0,for some largek0, is a Cauchy sequence in [a,b) and yet it does not havea limit in [a,b) (the limit isb, which lies outside [a,b)).]]]]

4 The set of all rational numbers,Q, is also not complete. Every irrational number is the limit of some sequence inQ, andthese sequences are Cauchy sequences whose limits lie 2060 we learned that every Cauchy sequence inC[a,b] with respectto the sup-norm implies that it converges uniformly, so the limit is again ,C[a,b] is a complete space. The subsetE={f:f(x) 0, x}is alsocomplete. Indeed, let{fn}be a Cauchy sequence inE, it is also a Cauchy sequence inC[a,b] and hence there exists somef C[a,b] such that{fn}converges uniform convergence implies pointwise convergence,f(x) = limn fn(x) 0, sofbelongs toE, andEis complete. Next, letP[a,b] be the collection of all polynomialsrestricted to [a,b].

5 It is not complete. For, taking the sequencehn(x) given byhn(x) =n k=0xkk!,{hn}is a Cauchy sequence inP[a,b] which converges toex. Asexis not a polynomial,P[a,b] is not obtain a typical non-complete set, we consider the closed interval [0,1] inR. Takeaway one pointzfrom it to formE= [a,b]\{z}.Eis not complete, since every sequenceinEconverging tozis a Cauchy sequence which does not converge inE. In general,you may think of sets with holes being non-complete ones. Now, given a non-completemetric space, can we make it into a complete metric space by filling out all the holes?The answer turns out to affirmative. We can always enlarge a non-complete metric spaceinto a complete one by putting in sufficiently many ideal (Completion Theorem).

6 * Every metric space has a THE Contraction Mapping PRINCIPLE3 This theorem will be further explained and proved in the The Contraction Mapping PrincipleSolving an equationf(x) = 0,wherefis a function fromRnto itself frequently comesup in application. This problem can be turned into a problem for fixed points. Literally,a fixed point of a Mapping is a point which becomes unchanged under this Mapping . Byintroducing the functiong(x) =f(x) +x, solving the equationf(x) = 0 is equivalent tofinding a fixed point forg. This general observation underlines the importance of findingfixed points. In this section we prove the Contraction Mapping Principle , one of the oldestfixed point theorems and perhaps the most well-known one.

7 As we will see, it has a widerange of mapT: (X,d) (X,d) is called acontractionif there is a constant (0,1)such thatd(Tx,Ty) d(x,y), x,y X. A pointxis called afixed pointofTifTx=x. Usually we writeTxinstead ofT(x).Theorem ( Contraction Mapping Principle ).Every Contraction in a completemetric space admits a unique fixed theorem is also calledBanach s Fixed Point a Contraction in the complete metric space (X,d). Pick an arbitraryx0 Xand define a sequence{xn}by settingxn=Txn 1=Tnx0, n 1. We claimthat{xn}forms a Cauchy sequence inX. First of all, by iteration we haved(Tnx0,Tn 1x0) d(Tn 1x0,Tn 2x0) n 1d(Tx0,x0).( )Next, forn NwhereNis to be specified in a moment,d(xn,xN) =d(Tnx0,TNx0) d(Tn 1x0,TN 1x0) Nd(Tn Nx0,x0).

8 4 Chapter 3. THE Contraction Mapping PRINCIPLEBy the triangle inequality and ( ),d(xn,xN) Nn N j=1d(Tn N j+1x0,Tn N jx0) Nn N j=1 n N jd(Tx0,x0)<d(Tx0,x0)1 N.( )For >0, chooseNso large thatd(Tx0,x0) N/(1 )< /2. Then forn,m N,d(xn,xm) d(xn,xN) +d(xN,xm)<2d(Tx0,x0)1 N< ,thus{xn}forms a Cauchy sequence. AsXis complete,x= limn xnexists. By thecontinuity ofT, limn Txn=Tx. But on the other hand, limn Txn= limn xn+1=x. We conclude thatTx= there is another fixed pointy X. Fromd(x,y) =d(Tx,Ty) d(x,y),and (0,1), we conclude thatd(x,y) = 0, ,x= , we point out that this proof is a constructive one. It tells you how tofind the fixed point starting from an arbitrary point. In fact, lettingn in ( )and then replacingNbyn, we obtain an error estimate between the fixed point and theapproximating sequence{xn}:d(x,xn) d(Tx0,x0)1 n, n following two examples demonstrate the sharpness of the Contraction the mapTx=x/2 which maps (0,1] to itself.)

9 It is clearly acontraction. IfTx=x, thenx=x/2 which impliesx= 0. ThusTdoes not have a fixedpoint in (0,1]. This example shows that completeness of the underlying space cannot beremoved from the assumption of the THE Contraction Mapping PRINCIPLE5 Example the mapSfromRto itself defined bySx=x log (1 +ex).We havedSdx=11 +ex (0,1), x the Mean-Value Theorem,|Sx1 Sx2|= dSdt(c) |x1 x2|<|x1 x2|,and yetSdoes not possesses any fixed point. It shows that the Contraction conditioncannot be removed from the assumption of the : [0,1] [0,1] be a continuously differentiable function satisfying|f (x)|<1 on [0,1]. We claim thatfadmits a unique fixed point. For, by the Mean-ValueTheorem, forx,y [0,1] there exists somez (0,1) such thatf(y) f(x) =f (z)(y x).)

10 Therefore,|f(y) f(x)|=|f (z)||y x| |y x|,where = supt [0,1]|f (t)|<1 (Why?). We see thatfis a Contraction . By the ContractionMapping Principle , it has a unique fixed fact, by using the mean-value theorem one can show thatevery continuous func-tionfrom [0,1] to itself admits at least one fixed point. This is a general fact. Moregenerally, according to Brouwer s Fixed Point Theorem, every continuous maps from acompact convex set inRnto itself admits at least one fixed point. However, when theset has non-trivial topology , fixed points may not exist. For instance, takeXto beA={(x,y) : 1 x2+y2 4}andTto be a rotation. It is clear thatThas no fixedpoint inA. This is due to the topology ofA, namely, it has a describe a common situation where the Contraction Mapping Principle can beapplied.