(this is a parsing test with js/lua)
#import "conf.typ": *
#show: doc => conf(display:false, doc)
// header
#title[Contraction mapping principle.]
Contraction mapping principle is a type of fixed point theorem. Fixed point theorems are results that guarentees the existence of something, often in a nonconstrutive way. However, in the case of a contraction mapping in a cobmplete metric space, one can give a procedure to obtain a fixed point (within reason). We will look at this contraction mapping principle and some applications.
= Contraction mapping theorem (Banach).
Let $(X,d)$ be a metric space. A function $f:X -> X$ is said to be a *contraction* if there exists some $lambda < 1$ such that for all $x,y in X$, we have $d(f(x),f(y)) <= lambda dot d(x,y)$. Note implicitly $lambda >= 0$. Note, a contraction is Lipschitz continuous by its definition.
And recall a metric space $X$ is *complete* if every Cauchy sequence in $X$ converges in $X$. We then have:
#theorem[Contraction mapping theorem.][Suppose
$(X,d)$ is a nonempty complete metric space and $f:X -> X$ is a contraction, then there exists a unique fixed point $x^ast in X$ such that $f(x^ast)=x^ast$.
]
Sometimes this is called *Banach fixed point theorem*.
#start Proof. We construct such a fixed point first, then show that it is unique. Since $X$ is nonempty, we have some $x_0 in X$. Apply $f$ iteratively and we get a sequence of points $(x_n)$ where
$
x_n = f^((n))(x_0)=(f compose f compose dots.c compose f) (x_0) = f(x_(n-1))
$
for each $n >= 0$. We claim that $(x_n)$ is a Cauchy sequence.
Indeed, first note that for any $n >= 0$, the adjacent terms have distance
$
d(x_n,x_(n+1)) <= lambda ^n dot d(x_0,x_1)
$
as $f$ is a contraction. Next note that for $n < m$ we have by triangle inequality and geometric series with $0 <= lambda < 1$,
$
d(x_n , x_m) & <= d(x_n , x_(n+1)) + d(x_(n+1) , x_(n+2))+ dots.c+ d(x_(m-1),x_m) \
& <= lambda^n dot d(x_0,x_1) + lambda^(n+1) dot d(x_0,x_1)+ dots.c lambda^(m-1) dot d(x_0,x_1) \
& = lambda^n (1 + lambda^1+ dots.c + lambda^(m-1-n))dot d(x_0,x_1) \
& <= lambda^n/(1-lambda) dot d(x_0,x_1).
$
So for any fixed $epsilon > 0$, take $N$ large enough that $lambda^N/(1-lambda)d(x_0,x_1) < epsilon$. Then for any $m > n >= N$, we have
$
d(x_n,x_m) <= lambda^n/(1-lambda) d(x_0,x_1) <= lambda^N/(1-lambda) d(x_0,x_1) < epsilon.
$
This shows $(x_n)$ is Cauchy.
And since $X$ is a complete metric space, $x_n -> x^ast$ for some limit $x^ast in X$. We now claim $x^ast$ is a fixed point of $f$, and that it is unique.
To see that $x^ast$ is a fixed point of $f$, note that
$
x^ast = lim_n x_n = lim_n f(x_(n-1)) = f(lim_n x_(n-1)) = f(x^ast)
$
where we use the fact that the contraction $f$ is continuous to interchange the limit.
Finally, we claim $x^ast$ is the unique fixed point of $f$. Suppose $x'$ is another fixed point of $f$, where both $f(x^ast) =x^ast$ and $f(x') = x'$. Then note that
$
d(x^ast , x') = d(f(x^ast),f(x')) <= lambda dot.c d(x^ast , x').
$
If to the contrary that $d(x^ast,x') > 0$, then $1 <= lambda$, contradicting the fact that $lambda < 1$. Hence we must have $d(x^ast , x') = 0$, namely $x^ast = x'$. So $f$ has a unique fixed point. #qed
Remark. This in fact also shows that if we have a contraction mapping $f:X -> X$ on some nonempty complete space $X$, we can find or approximate this unique fixed point by following the iterates $x_(n+1) = f(x_n)$ with any starting $x_0 in X$!
== Newton's method and finding square roots.
Let us demonstrate a quick example with Newton's method. Consider some differentiable real-valued function of one real variable $f=f(x)$, and we are interested in finding a root of $f$. Then with a starting point $x_0$, construct the sequence
$
x_(n+1) = x_n - f(x_n)/(f'(x_n))
$
But whether this converges depends on the nature of $f$. Let us look at the situation of finding square roots.
Say we have some positive $N$ and we want to find its square root $sqrt(N)$. Then we can look at this as finding the root of the function $f(x) = x^2 - N$. Let us consider the mapping
$
T(x)=x-f(x)/(f'(x)) = x - (x^2-N)/(2x) = 1/2 (x+N/x),
$
the "Babylonian method". Note the fixed point of $T$ is a square root of $N$. But what domain should we consider it on? We claim $T:D -> D$ is a well-defined operator on the complete domain $D = [sqrt(N),oo)$. Indeed, if $x >= sqrt(N)$, then by AM-GM inequality,
$
T(x)=1/2 (x+N/x) >=sqrt(x dot N/x) = sqrt(N),
$
so $x in D => T(x) in D$ and $T:D -> D$ is well-defined continuous function.
Next we show $T$ is a contraction. For any $x,y >= sqrt(N)$, note
$
abs(T(x)-T(y)) &= abs(1/2 (x-y)+N/2 (1/x - 1/y)) \
&= 1/2 abs(x-y) dot abs(1 - N/(x y))<= 1/2 abs(x-y),
$
so $T$ is a contraction.
Hence by contraction mapping theorem, $T$ has a unique fixed point, which can be found by taking any starting $x_0 in [sqrt(N), oo)$ and iterating it by $T^((n))(x_0)$.
Also, for any $x in (0,sqrt(N))$, we have again by AM-GM
$
T(x) = 1/2 (x + N/x) >= sqrt(N),
$
this means if we take any starting $x_0 >0$, we are guarenteed that $T(x_0) = x_1 >= sqrt(N)$, which the successive interates would continue to converge to the unique fixed point $sqrt(N)$!
To summarize, we have the following result and method:
#proposition[Finding square root][
For any positive $N > 0$, take any positive number $x_0 > 0$. Then the iterates
$
x_(n+1) = 1/2(x_n + N/x_n)
$
will converge to $sqrt(N)$. #qed
]
Now, under specific conditions, Newton's method is a contraction.
*Exercise.*
Let $f: RR -> RR$ to be sufficiently differentiable, and that
- $f''$ exists,
- $f'(x) != 0$ for all $x in RR$,
- There exists $lambda in (0,1)$ such that $|f(x)f''(x)| <= lambda |f'(x)|^2$ for all $x in RR$.
Show $T: RR -> RR$ where
$
T(x)= x - f(x) / (f'(x))
$
is a contraction. (Hint. Apply MVT on $T$.)
== Existence and uniqueness of first order ODEs (Picard-Lindelof).
Consider the first order initial value problem
$
y'(x) = f(x,y), quad y(x_0)=y_0,
$
for some function $f(x,y)$ and some initial point $(x_0,y_0)$. When can we say that there exists a solution $y=y(x)$ to this differential equation, and if so, is it unique?
There are various forms of such existence and uniqueness theorem. We demonstrate one variation of it.
#theorem[Picard-Lindelof.][
Suppose $f(x,y)$ is continuous on some closed rectangle $R=I times J$, and $(x_0,y_0)$ is a point in the interior of $R$, where $I,J$ some closed intervals with interior.
And suppose that $f(x,y)$ is *Lipschitz* in the $y$-coordinate, namely there is some positive $lambda > 0$ where
$
abs(f(x,y)-f(x,z)) <= lambda abs(y-z)
$
for all $(x,y)$,$(x,z)$ in $R$. Then the IVP
$
y'(x)=f(x,y), quad y(x_0) = y_0
$
has a unique solution on the interval $[x_0-h,x_0+h]$ for some positive $r > 0$.
]
We first observe that $f$ is continuous on compact rectangle $R$, so it is bounded on $R$. Say we have $abs(f) <= M$ on $R$, for some $M > 0$.
Next, pick a small enough $r > 0$ such that $[x_0-r,x_0+r] subset I$ and $[y_0 - r,y_0+r] subset J$.
Now take $h > 0$ such that
$
h < min {r, r / (M + lambda r)}.
$
#align(center, ipefig[picard])
Denote the closed interval $K = [x_0-h , x_0 + h] subset I $. Now let us consider the subspace $Y subset C(K)$ where
$
Y={y in C(K) : y(K) subset J}.
$
endowed with the sup norm $norm(y)_oo = sup_(x in K)abs(y(x))$ from the complete space $C(K)$.
Let us believe for now that $Y$ is a closed subspace of $C(K)$, so $Y$ itself is a complete space. Also note the constant function $y(x)=y_0$ is in $Y$, so $Y$ is not empty.
This $Y$ is chosen so (along with $h$) so that the mapping
$
& T:Y -> Y \
& T [y](x) = y_0 + integral_(x_0)^x f(t,y(t)) d t
$
is a well-defined contraction.
To see this is well-defined. Take $y in Y$, so $y(K) subset J$. We need $T[y](K) subset J$.
Since for any $x in K = [x_0 - h , x_0 + h]$
$
abs(T[y](x) - y_0) = abs(integral_(x_0)^x f(t,y(t)) d t) <= M h < (M r) / (M+lambda r) < r
$
So $T[y](K) subset [y_0- r , y_0 + r] subset J$. Thus $T:Y -> Y$ is well-defined.
Now we show $T$ is a contraction.
Take $y,z in Y$, then
$
norm(T[y]-T[z])_oo &= sup_(x in K) abs(integral_(x_0)^x f(t,y(t))d t- integral_(x_0)^x f(t,z(t))d t) \
&= sup_(x in K) abs(integral_(x_0)^x f(t,y(t))-f(t,z(t))d t) \
&<= h dot sup_(x in K) abs(f(x,y(x))-f(x,z(x))) \
&<= h dot sup_(x in K) lambda dot abs(y(x)-z(x)) \
=> norm(T[y]-T[z])_oo&<= h lambda norm(y-z)_oo.
$
Now with how $h$ was chosen,
$
h lambda < (lambda r)/(M+lambda r) < 1,
$
hence $T$ is a contraction!
By contraction mapping principle, $T$ has a unique fixed point $y^ast in Y$, a function defined on the interval $K = [x_0 - h, x_0 +h]$, such that for all $x in K$ we have
$
y^ast (x) = y_0 + integral_(x_0)^x f(t,y^ast (t)) d t,
$
which we see that $y^ast (x_0) = y_0$, and by fundamental theorem of calculus,
$
(y^ast)'(x) = f(x,y^ast (x)),
$
whence solving the desired IVP. #qed
It remains to show that for any closed intervals $K,J$, the subspace $Y = {y in C(K): y(K) subset J}$ is a closed subspace of $C(K)$, with respect to sup norm, $norm(dot)_oo$.
This is _quick_ to see. Let us write $J=[a,b]$, and consider a sequence $y_n in Y$ such that $norm(y_n - y)_oo -> 0$ for some $y in C(K)$. To show $y in Y$ we need to show $y(x) in J$ for all $x in K$.
Note we have for each $n$ and each $x in K$, $a <=y_n (x) <= b$. Now for any $x in K$
$
& y(x) -y_n (x) <= norm(y-y_n)_oo \
& => y(x) <= norm(y-y_n)_oo +y_n (x)<= norm(y-y_n)_oo +b,
$
and since $norm(y-y_n)_oo -> 0$, so we have $y(x) <= b$.
Similarly, for any $x in K$,
$
& y_n (x) - y(x) <= norm(y_n - y)_oo \
& =>y(x) >= y_n (x) -norm(y_n -y)_oo >=a-norm(y_n-y),
$
so in the limit we see that $y(x) >=a$. Thus, $y(K) subset J$, and that $y in Y$ as desired. #qed