前置基础
取一个完备度量空间 $\qty(X, d)$，“完备” 是指集合 $X$ 中任意 Cauchy 列均收敛于该空间中之一个点；“度量” 是 $X$ 上一个二元映射，$d: X \times X \to \mathbb{R}$，满足
- 非负性。$d\qty(x, y) \ge 0$，$d\qty(x, y) = 0 \Leftrightarrow x = y$，$\forall x, y \in X$。
- 对称性。$d\qty(x, y) = d\qty(y, x)$，$\forall x, y \in X$。
- 三角不等式。$d\qty(x, y) + d\qty(y, z) \ge d\qty(z, x)$，$\forall x, y, z \in X$。
$\qty(X, d)$ 上之压缩映射是指满足如下要求之映射 $T: X \to X$，
\begin{equation}
\begin{aligned}
\exists \lambda \in \left[0, 1\right)\ \mathrm{s.t.}\ d\qty(T\qty(x) – T\qty(y)) \le \lambda d\qty(x, y), \forall x, y \in X.
\end{aligned}
\end{equation}
不难证明，压缩映射一定连续（不仅连续，而且还一致连续）。$\forall \epsilon > 0, x, y \in X$，取 $\delta \equiv \epsilon$，当 $d\qty(x, y) < \delta$ 时，$d\qty(T\qty(x), T\qty(y)) \le d\qty(x, y) < \delta = \epsilon$，因而 $T$ 连续。由于 $\delta$ 仅与 $\epsilon$ 有关，而与 $x$、$y$ 等无关，因而 $T$ 还一致连续。事实上，压缩映射之定义即满足所谓 Lipschitz 连续性。而所有 Lipschitz 连续函数均一致连续，因而压缩映射必一致连续。
由于 $T$ 连续，因此 Heine 定理成立，即对于 $X$ 中之任意收敛序列 $\qty{x_{n}}$，均有 $\mathop{\lim}\limits_{n \to \infty} T\qty(x_{n})= T\qty(\mathop{\lim}\limits_{n \to \infty} x_{n})$。为证明这一点，考虑 $T$ 连续性之定义以及 $\qty{x_{n}}$ 收敛性之定义，
- $T$ 连续性之定义，
\begin{equation}
\begin{aligned}
\forall x \in X, \epsilon > 0, \exists \delta > 0\ \mathrm{s.t.}\ \forall y \in \qty{z\left|\right. d\qty(z, x) < \delta}, d\qty(T\qty(x) – T\qty(y)) < \epsilon.
\end{aligned}
\end{equation} - $\qty{x_{n}}$ 收敛性之定义，
\begin{equation}
\begin{aligned}
\exists x_{\ast} \in X, \forall \epsilon > 0, \exists N \in \mathbb{N}\ \mathrm{s.t.}\ \forall n > N, d\qty(x_{n}, x_{\ast}) < \epsilon.
\end{aligned}
\end{equation}
我们将 $\qty{x_{n}}$ 收敛性之定义中之 $\epsilon$ 取为 $T$ 连续性之定义中之 $\delta$。则 $\exists N \in \mathbb{N}\ \mathrm{s.t.}\ \forall n > N, d\qty(x_{n}, x_{\ast}) < \delta$，因而由 $T$ 连续性之定义即可知，$d\qty(T\qty(x_{n}) – T\qty(x_{\ast})) < \epsilon$。综合上述分析过程，即
\begin{equation}
\begin{aligned}
\forall \epsilon > 0, \exists N \in \mathbb{N}\ \mathrm{s.t.}\ \forall n > N, d\qty(T\qty(x_{n}) – T\qty(x_{\ast})) < \epsilon.
\end{aligned}
\end{equation}
这就意味着
\begin{equation}\label{eq:海涅定理}
\begin{aligned}
\mathop{\lim}\limits_{n \to \infty} T\qty(x_{n})= T\qty(\mathop{\lim}\limits_{n \to \infty} x_{n}).
\end{aligned}
\end{equation}
式 \eqref{eq:海涅定理} 即为 Heine 定理。
压缩映射原理
压缩映射原理（Banach 不动点定理）是说，如果 $T$ 是完备度量空间 $\qty(X, d)$ 上之一个压缩映射，那么存在唯一不动点 $x_{\ast} \in X$ 满足 $T\qty(x_{\ast}) = x_{\ast}$。
在 $X$ 中任取一点 $x_{0}$，构造序列 $x_{0}, x_{1}, x_{2} \cdots$ 其中
\begin{equation}
\begin{aligned}
x_{n} \equiv T^{n}\qty(x) = \underbrace{T\left(T\left(\cdots T\right.\right.}_{\text{$n$ 个 $T$}}\qty(x)\left.\left.\right)\right).
\end{aligned}
\end{equation}
由于 $T$ 是压缩映射，因此
\begin{equation}
\begin{aligned}
d\qty(x_{n + 1}, x_{n}) ={}& d\qty(T\qty(x_{n}), T\qty(x_{n – 1}))\\
\le {}& \lambda d\qty(x_{n}, x_{n – 1})\\
={}& \lambda d\qty(T\qty(x_{n – 1}), T\qty(x_{n – 2}))\\
\le {}& \lambda^{2} d\qty(x_{n – 1}, x_{n – 2})\\
\vdots\\
={}& \lambda^{n – 1} d\qty(T\qty(x_{1}), T\qty(x_{0}))\\
\le {}& \lambda^{n} d\qty(x_{1}, x_{0}), \forall n \in \mathbb{N}.
\end{aligned}
\end{equation}
再由三角不等式即可知
\begin{equation}\label{eq:三角不等式之推论}
\begin{aligned}
d\qty(x_{n + k}, x_{n}) \le {}& d\qty(T\qty(x_{n + k}), T\qty(x_{n + k – 1})) + d\qty(T\qty(x_{n + k – 1}), T\qty(x_{n + k – 2})) + \cdots + d\qty(T\qty(x_{n + 1}), T\qty(x_{n}))\\
\le {}& \qty(\lambda^{n + k – 1} + \lambda^{n + k – 2} + \cdots + \lambda^{n}) d\qty(x_{1}, x_{0})\\
={}& \frac{1 – \lambda^{k}}{1 – \lambda} \lambda^{n} d\qty(x_{1}, x_{0}).
\end{aligned}
\end{equation}
显然有
\begin{equation}
\begin{aligned}
\lim_{n \to \infty}d\qty(x_{n + k}, x_{n}) ={}& 0.
\end{aligned}
\end{equation}
因此 $\qty{x_{n}}$ 是 Cauchy 列。由于 $\qty(X, d)$ 完备，因此 $\qty{x_{n}}$ 收敛于一个极限 $x_{\ast}$，
\begin{equation}
\begin{aligned}
\lim_{n \to \infty} x_{n} ={}& x_{\ast}.
\end{aligned}
\end{equation}
由于 $T$ 连续，因此由式 \eqref{eq:海涅定理} 即可知
\begin{equation}
\begin{aligned}
T\qty(x_{\ast}) ={}& T\qty(\lim_{n \to \infty} x_{n})\\
={}& \lim_{n \to \infty} T\qty(x_{n})\\
={}& \lim_{n \to \infty} x_{n + 1}\\
={}& x_{\ast}.
\end{aligned}
\end{equation}
即 $x_{\ast}$ 为 $T$ 之不动点。为了证明其唯一性，假设存在两个不同之不动点 $x_{\ast}$、$y_{\ast}$。即
- $T\qty(x_{\ast}) = x_{\ast}$；
- $T\qty(y_{\ast}) = y_{\ast}$。
则
\begin{equation}
\begin{aligned}
d\qty(x_{\ast}, y_{\ast}) = d\qty(T\qty(x_{\ast}), T\qty(y_{\ast})) \le \lambda d\qty(x_{\ast}, y_{\ast}).
\end{aligned}
\end{equation}
由于假设 $x_{\ast} \neq y_{\ast}$，因此 $d\qty(x_{\ast}, y_{\ast}) \neq 0$，从而有
\begin{equation}
\begin{aligned}
\lambda \ge 1.
\end{aligned}
\end{equation}
这与 $0 \le \lambda < 1$ 矛盾。因此必有 $x_{\ast} = y_{\ast}$，即不动点唯一。
这样，我们便证明了压缩映射原理（Banach 不动点定理）。
压缩映射原理之一个应用 —— 方程之迭代求解
若我们需要在某完备度量空间 $\qty(\Omega, d)$ 内求解方程
\begin{equation}
\begin{aligned}
f\qty(x) = 0.
\end{aligned}
\end{equation}
可先将其转化为
\begin{equation}
\begin{aligned}
g\qty(x) = x,
\end{aligned}
\end{equation}
转化方式一般来说不唯一。例如可以令 $g\qty(x) \equiv f\qty(x) + x$，或 $g\qty(x) \equiv \qty[f\qty(x)]^2 + x$，等等。我们需要选择让 $g$ 为 $\qty(\Omega, d)$ 上之压缩映射（若不存在这样之 $g$，则该方程无法用压缩映射原理求解），
\begin{equation}\label{eq:为求解方程构造之压缩映射}
\begin{aligned}
\exists \lambda \in \left[0, 1\right)\ \mathrm{s.t.}\ d\qty(g\qty(x) – g\qty(y)) \le \lambda d\qty(x, y), \forall x, y \in \Omega.
\end{aligned}
\end{equation}
则根据压缩映射原理，可以在 $\Omega$ 中任取初值 $x_{0}$，并用 $g$ 反复迭代，
\begin{equation}
\begin{aligned}
x_{n + 1} = g\qty(x_{n}).
\end{aligned}
\end{equation}
随着迭代步数 $n$ 增加，$x_{n}$ 会不断接近方程之解。由式 \eqref{eq:三角不等式之推论} 可估计 $x_{n}$ 与精确解 $x_{\mathrm{sol}}$ 之误差之上界，
\begin{equation}
\begin{aligned}
d\qty(x_{n}, x_{\mathrm{sol}}) \le {}& \frac{\lambda^{n}}{1 – \lambda} d\qty(x_{1}, x_{0}).
\end{aligned}
\end{equation}
若欲将误差控制在 $\varepsilon > 0$ 内，即要求 $d\qty(x_{n}, x_{\mathrm{sol}}) \le \varepsilon$，则只需 $\frac{\lambda^{n}}{1 – \lambda} d\qty(x_{1}, x_{0}) \le \varepsilon$ 即可。亦即
\begin{equation}\label{eq:控制误差对迭代步数之要求}
\begin{aligned}
n > \frac{\ln\qty[\varepsilon \frac{1 – \lambda}{d\qty(x_{1}, x_{0})}]}{\ln \lambda}.
\end{aligned}
\end{equation}
式 \eqref{eq:控制误差对迭代步数之要求} 为对迭代步数之要求，即至少需要 $\lceil \frac{\ln\qty[\varepsilon \frac{1 – \lambda}{d\qty(x_{1}, x_{0})}]}{\ln \lambda} \rceil$ 步才能 “充分安全地” 将求解误差控制在 $\varepsilon$ 内（这并非意味着少于此步数就一定达不到所要求之精度，但是那样 “不安全”）。
举例来说，欲在区间 $\qty[0, \frac{\pi}{4}]$ 内求解方程
\begin{equation}\label{eq:欲求解之方程}
\begin{aligned}
\cos\qty(x) = x.
\end{aligned}
\end{equation}
在实数域 $\mathbb{R}$ 中，度量 $d$ 可定义为
\begin{equation}\label{eq:实数域中度量之定义}
\begin{aligned}
d\qty(x ,y) \equiv \abs{x – y}, \forall x, y \in \mathbb{R}.
\end{aligned}
\end{equation}
容易验证区间 $\qty[0, \frac{\pi}{4}]$ 是一个完备度量空间，其中任意 Cauchy 列都会收敛到该区间上之一个值，而不会超出该区间。先构造压缩映射 $g$。由于式 \eqref{eq:欲求解之方程} 已具有 $g\qty(x) = x$ 之形式，我们可尝试令 $g\qty(x) \equiv \cos\qty(x)$。但需要验证这样定义之 $g$ 在区间 $\qty[0, \frac{\pi}{4}]$ 内是否为压缩映射。即验证式 \eqref{eq:为求解方程构造之压缩映射} 在区间 $\Omega = \qty[0, \frac{\pi}{4}]$ 上是否恒成立。$g$ 在 $\qty[0, \frac{\pi}{4}]$ 上连续，在 $\qty(0, \frac{\pi}{4})$ 上可导，由微分中值定理，
\begin{equation}
\begin{aligned}
\forall x, y \in \qty[0, \frac{\pi}{4}], \exists \xi \in \qty(\min\qty(x, y), \max\qty(x, y))\ \mathrm{s.t.}\ g^{\prime}\qty(\xi) = \frac{f\qty(x) – f\qty(y)}{x – y}
\end{aligned}
\end{equation}
由于 $x, y \in \qty[0, \frac{\pi}{4}]$，因此 $\xi \in \qty(0, \frac{\pi}{4})$。由于 $0 \le \abs{g^{\prime}\qty(\xi)} = \abs{- \sin\qty(\xi)} < \frac{1}{\sqrt{2}}, \forall \xi \in \qty(0, \frac{\pi}{4})$，故 $0 \le \abs{\frac{f\qty(x) – f\qty(y)}{x – y}} < \frac{1}{\sqrt{2}}, \forall x, y \in \qty[0, \frac{\pi}{4}]$，从而可取 $\lambda \equiv \frac{1}{\sqrt{2}}$，即可满足式 \eqref{eq:为求解方程构造之压缩映射}。这就证明了 $g\qty(x) = \cos\qty(x)$ 在区间 $\qty[0, \frac{\pi}{4}]$
内为压缩映射。所以可在 $\qty[0, \frac{\pi}{4}]$ 内任意选取一个初始值，例如取 $x_{0} \equiv \frac{\pi}{8}$，并通过 $g$ 进行迭代。假设欲将求解误差控制在 $0.01$ 内，则由式 \eqref{eq:控制误差对迭代步数之要求} 即可知，至少需要迭代 $n = \lceil \frac{\ln\qty(0.01\frac{1 – \frac{1}{\sqrt{2}}}{\abs{\cos\qty(\frac{\pi}{8}) – \frac{\pi}{8}}})}{\ln\qty(\frac{1}{\sqrt{2}})} \rceil = 16$ 步。在 Wolfram 中验证：
Clear["Global`*"]
g[x_]:=Cos[x];
d[x_,y_]:=Abs[x-y];
varepsilon=0.01;
lambda=1/Sqrt[2];
x0=Pi/8;
x1=g[x0];
n=Ceiling[Log[varepsilon*(1-lambda)/d[x1,x0]]/Log[lambda]];
xsol=x/.NSolve[Cos[x]==x,x,Reals,WorkingPrecision->16][[1]];
x=N[x0,16];
Print["第 0 步，Subscript[x, 0] = ",x,"，误差为 ",Abs[x-xsol],"；"]
For[k=1,k<=n,k++,
x=N[g[x],16];
If[k==n,
Print["第 ",k," 步，",Subscript["x",k]," = ",x,"，误差为 ",Abs[x-xsol],"。"],
Print["第 ",k," 步，",Subscript["x",k]," = ",x,"，误差为 ",Abs[x-xsol],"；"]
]
]输出结果如下：
第 0 步，x₀ = 0.3926990816987242，误差为 0.346386051516436；
第 1 步，x₁ = 0.9238795325112868，误差为 0.184794399296126；
第 2 步，x₂ = 0.6027290430100576，误差为 0.136356090205103；
第 3 步，x₃ = 0.8237916098130910，误差为 0.084706476597930；
第 4 步，x₄ = 0.6794440903230020，误差为 0.059641042892159；
第 5 步，x₅ = 0.7779221507109940，误差为 0.038837017495833；
第 6 步，x₆ = 0.7123733109329119，误差为 0.026711822282249；
第 7 步，x₇ = 0.7568127374522154，误差为 0.017727604237055；
第 8 步，x₈ = 0.7270280988717409，误差为 0.012057034343420；
第 9 步，x₉ = 0.7471529792872789，误差为 0.008067846072118；
第 10 步，x₁₀ = 0.7336265405606350，误差为 0.005458592654526；
第 11 步，x₁₁ = 0.7427510776803315，误差为 0.003665944465171；
第 12 步，x₁₂ = 0.7366107481242736，误差为 0.002474385090887；
第 13 步，x₁₃ = 0.7407496445230298，误差为 0.001664511307869；
第 14 步，x₁₄ = 0.7379628750395965，误差为 0.001122258175564；
第 15 步，x₁₅ = 0.7398406342380913，误差为 0.000755501022931；
第 16 步，x₁₆ = 0.7385760077583078，误差为 0.000509125456853。求解结果符合所需要之精度。
