41. Contraction Mapping Theorem
41. 压缩映射定理
定义 41.1（压缩映射） 设 \((X,d)\) 为度量空间。映射 \(T:X\to X\) 称为 \(X\) 上的压缩映射，若存在常数 \(q\in[0,1)\) 使 $$ > d(T(x),T(y))\le q\,d(x,y),\quad \forall x,y\in X > $$
定理 41.1（压缩映射定理 / Banach 不动点定理） 设 \((X,d)\) 为非空完备度量空间、\(T:X\to X\) 为其上的压缩映射。则 \(T\) 有唯一不动点 \(x^{\star}\in X\)（即 \(T(x^{\star})=x^{\star}\)）。此外，\(x^{\star}\) 可如下求得：从 \(X\) 中任意元素 \(x_0\) 出发，定义序列 \(\{x_n\}\)，\(x_n=T(x_{n-1})\)，则 \(x_n\to x^{\star}\)。
证明 构造序列 \(x_n=T(x_{n-1})\)。因 \(T\) 是压缩映射， $$ > d(x_n,x_{n-1})=d(T(x_{n-1}),T(x_{n-2}))\le q\,d(x_{n-1},x_{n-2}) > $$ 故 \(\forall\varepsilon>0\)，构造 \(N=\left\lceil\log_q\!\left(\dfrac{d(x_1,x_0)}{\varepsilon}\right)\right\rceil\)，则 \(\forall m,n\ge N\)，\(d(x_m,x_n)<\varepsilon\)。因此 \(\{x_n\}\) 是 \(X\) 中的柯西序列，由完备度量空间的定义，它在 \(X\) 中收敛，证明了 \(x^{\star}\) 的存在。
唯一性：反证。设不然，\(\exists x_1\ne x_2\) 使 \(T(x_1)=x_1\)、\(T(x_2)=x_2\)。则 $$ > d(T(x_1),T(x_2))=d(x_1,x_2) > $$ 与 \(T\) 是压缩映射矛盾。\(\blacksquare\)
41. Contraction Mapping Theorem
Definition 41.1 (Contraction Mapping) Let \((X,d)\) be a metric space. Then a map \(T:X\to X\) is called a contraction mapping on \(X\) if there exists a constant \(q\in[0,1)\) such that $$ > d(T(x),T(y))\le q\,d(x,y),\quad \forall x,y\in X > $$
Theorem 41.1 (Contraction Mapping Theorem or Banach Fixed Point Theorem) Let \((X,d)\) be a non-empty complete metric space with a contraction mapping \(T:X\to X\). Then \(T\) admits a unique fixed-point \(x^{\star}\) in \(X\) (i.e. \(T(x^{\star})=x^{\star}\)). Furthermore, \(x^{\star}\) can be found as follows: start with an arbitrary element \(x_0\) in \(X\) and define a sequence \(\{x_n\}\) by \(x_n=T(x_{n-1})\), then \(x_n\to x^{\star}\).
Proof Construct a sequence \(x_n=T(x_{n-1})\). Since \(T\) is a contraction mapping, $$ > d(x_n,x_{n-1})=d(T(x_{n-1}),T(x_{n-2}))\le q\,d(x_{n-1},x_{n-2}) > $$ So, for \(\forall\varepsilon>0\), construct \(N=\left\lceil\log_q\!\left(\dfrac{d(x_1,x_0)}{\varepsilon}\right)\right\rceil\), then we have that \(\forall m,n\ge N\), \(d(x_m,x_n)<\varepsilon\). Therefore, \(\{x_n\}\) is a Cauchy sequence in \(X\) and thus, by definition of complete metric space, converges in \(X\), which proves the existence of \(x^{\star}\).
For uniqueness, let's prove by way of contradiction. Suppose not, \(\exists x_1\ne x_2\) s.t. \(T(x_1)=x_1\) and \(T(x_2)=x_2\). Then consider $$ > d(T(x_1),T(x_2))=d(x_1,x_2) > $$ which contradicts with that \(T\) is a contraction mapping. \(\blacksquare\)