Banach fixed point theorem

I came across the proof of Perron Frobenius theorem here and it used Banach fixed point theorem. So I spent some time to understand the fixed point theorem from the wiki.

Theorem

Banach fixed point theorem considers a complete metric space (with metric $d$ ) and for any contraction mapping $T$ , there will exist a unique fixed point. That is $T(x)=x$ .

By contraction mapping, we mean that $d(T(x),T(y))\le q d(x,y)$ for some $q \in [0,1)$ .

Proof

The main idea of the proof is to simply realize that the sequence $x_0, x_1=T(x_0), x_2=T(x_1), x_3=T(x_2),\cdots$ is a Cauchy sequence. And since the space is complete and so will converge to the fixed point.

To show the sequence is Cauchy, note that

$d(x_{n+1},x_n) \le q^n d(x_1,x_0)$

Consequently,

${\begin{aligned}d(x_{m},x_{n})&\leq d(x_{m},x_{m-1})+d(x_{m-1},x_{m-2})+\cdots +d(x_{n+1},x_{n})\\&\leq q^{m-1}d(x_{1},x_{0})+q^{m-2}d(x_{1},x_{0})+\cdots +q^{n}d(x_{1},x_{0})\\&=q^{n}d(x_{1},x_{0})\sum _{k=0}^{m-n-1}q^{k}\\&\leq q^{n}d(x_{1},x_{0})\sum _{k=0}^{\infty }q^{k}\\&=q^{n}d(x_{1},x_{0})\left({\frac {1}{1-q}}\right).\end{aligned}}$

Since $\frac{d(x_1,x_0)}{1-q}$ is finite and $0\le q<1$ , for any $\epsilon > 0$ , we have $d(x_m,x_n)<\epsilon$ for sufficiently large $N<m,n.$ Thus, the sequence is Cauchy and converges to the fixed point.

Now, the fixed point has to be unique, otherwise, say we have two fixed points $p_1,p_2$ ,

$d(p_1,p_2) = d(T(p_1),T(p_2)) \le q d(p_1,p_2)$ . Since $q<1$ , this leads to contradiction.

Prologue

Btw, as for my original motivation, Knill’s proof were very neat if it doesn’t seem to have a hole. It claims that $(A|w|)$ is a vector with length smaller than $\lambda L$ , where $L$ is the length of $w$ . Unfortunately, one can easily verify with octave or matlab that it is not true in general. $\frac{\|A |w| \|}{\|w\|} > \lambda$ is possible unless $A$ is symmetric.

Update: I went back and forth as I got rusty with the matrix “expansion” result. Indeed we have something like

$\|(A x)\| \le \sigma \|x\|$

but $\sigma$ is the singular value instead of the eigenvalue. Because if $A = U D V^\top$ , $\|A x\| = \|U D V^\top x\|$ , the vector length will scale the maximum when $x$ is proportional to the left singular vector of the maximum singular value. Of course, singular value is just the same as eigenvalue when a matrix is symmetric. So unfortunately, the proof still appears to have a hole.

M	T	W	T	F	S	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Theorem

Proof

Prologue

Leave a Reply Cancel reply