The capstone project of my Real Analysis class was to pick a topic and learn it independently. I chose contraction mapping because of its importance in dynamic programming and optimization problems. I am grateful to many keen bloggers who wrote out more thorough proofs than many textbooks. Below is my contribution to the internet: a full write up of Banach’s Fixed Point Theorem, with no proofs left to the reader.
To start, let us review the definitions of contraction mapping and fixed points:
Let be a metric space and . is a contraction mapping if there exists a real number , such that
, where the term is called a Lipschitz coefficient for .
Let be a complete metric space and let be a contraction. There there is one unique fixed point such that
The trick to this proof is to claim an inductive sequence by composing with some times.
We show that the set is convergent to a limit by showing it is Cauchy in a complete metric space. That limit point will be our unique fixed point.
Because we have a complete metric space, we can use the following triangle inequality ,
Because is a contraction, we use the definition to obtain the second inequality.
Consider two points in the sequence such as . We can bound their distance using the simplified inequality from above by substituting such that
We can prove the second inequality through a proof by induction. See the Appendix. For now we conclude
where . We know by the metric space definition and the fraction because is bounded by . Therefore, our arbitrary points, is a Cauchy sequence for some . Cauchy sequences are convergent in a complete space so there exists
The next step is to show that is a fixed point. Recall the definition of fixed point . Since we can now define , let us substitute the following
These steps work because we so the limit of one is equal to the limit of the other. This shows is a fixed point. Lastly, we must show this point is unique. Suppose we have another fixed point such that , then we have
This is a contradiction because cannot be both greater and lower than itself. Therefore we claim is a unique fixed point.
This section is focusing on the claim that
The condition we show is
We hope to do this intuitively by showing a pattern and then claiming by induction that this is true for any
This inequality is from the definition of contraction mapping. Let us extend this inequality
Notice the pattern of the power. One less of the power is the th iteration of the first function and the power matches the th interation of the second function. By simplifying the last inequality, we have