在这里整理几个不动点定理, 并说一说他们的应用.

一般来说, 对于一个集合 XX 和一个映射 T:X↦XT:X \mapsto X, 如果存在 x∈Xx \in X 满足 T(x)=xT(x) = x, 那么 xx 就是一个不动点, 即它在映射下保持不变. *在很多领域中, 不动点是稳定（stability）和均衡（equilibrium）的代表——博弈（game）中的纳什均衡（Nash equilibrium）、阿罗-德布鲁经济体（Arrow-Debreu economy）中的一般均衡（general equilibrium）和马尔可夫链（Markov chain）的平稳分布（stationary distribution）都是不动点. *

巴拿赫不动点定理

巴拿赫不动点定理（Banach fixed point theorem）通常被叫作压缩映像原理原理（contraction mapping principle）, 它用构造性的方法证明了度量空间（metric space）中某些特殊映射（压缩映射）不动点的存在性和唯一性.

巴拿赫不动点定理 令 (X,d)(X,d) 为一个完备的（complete）度量空间, 即任何柯西序列（Cauchy sequence）收敛, 并令 T:X↦XT:X \mapsto X
满足 d(T(X),T(y))≤kd(x,y)∀x,y∈Xd(T(X),T(y)) \le kd(x,y) \forall x,y \in X, 其中 k∈(0,1)k \in (0,1), 那么 TT 存在一个唯一的不动点 x∗x^* 使得 T(x∗)=x∗T(x^*) = x^*.

证明 任意选取 x0∈Xx_0 \in X, 并定义 xn+1=xn∀n∈Nx_{n+1} = x_n \forall n \in \mathbb{N}.

  • 证明 {xn}\{x_n\} 是一个柯西序列, 即极限存在.

d(xm+1,xm)=d(T(xm),T(xm−1))≤kd(xm,xm−1)≤⋯≤kmd(x1,x0).d(x_{m+1},x_m) = d(T(x_m), T(x_{m-1})) \le k d(x_m, x_{m-1}) \le \cdots \le k^m d(x_1,x_0).

对于任意 n≥mn \ge m, 由三角不等式,

d(xm,xn)≤d(xm,xm+1)+⋯+d(xn−1,xn)≤(km+km−1+⋯+kn−1)d(x0,x1)=km1−kn−m1−kd(x0,x1)≤km1−kd(x0,x1)\begin{align*} d(x_m, x_n) &\le d(x_m,x_{m+1}) + \cdots + d(x_{n-1},x_n) \\ &\le (k^m + k^{m-1} + \cdots + k^{n-1})d(x_0,x_1) = k^m\frac{1 - k^{n - m}}{1 - k}d(x_0,x_1) \\ &\le \frac{k^m}{1 - k}d(x_0,x_1) \end{align*}

当 mm 足够大时, 上式中两项的差趋向于 00, 由定义知{xn}\{x_n\} 是一个柯西序列, 并记 lim⁡n→∞xn=x\lim_{n \rightarrow \infty} x_n = x.

  • 证明 $x = \lim_{n \rightarrow \infty} x_n $ 是一个不动点.

d(x,T(x))≤d(x,xm)+d(xm,T(x))=d(x,xm)+d(T(xm−1),T(x))≤d(x,xm)+kd(xm−1,x)d(x,T(x)) \le d(x,x_m) + d(x_m,T(x)) = d(x,x_m) + d(T(x_{m-1}),T(x)) \le d(x,x_m) + kd(x_{m-1},x)

令 m→∞m \rightarrow \infty, 可得 d(x,T(x))=0d(x,T(x)) = 0.

  • 证明此不动点唯一.

如果还存在另外的不动点 x′x', 则 T(x,x′)=d(T(x),T(x′))≤k(d(x,x′))T(x,x') = d(T(x),T(x')) \le k(d(x,x')), 所以d(x,x′)=0d(x,x') = 0, 即 x′=xx' = x.

注意此处的 xx 可以是一个高维的变量.

应用

求解方程的数值解 f(x)=0f(x) = 0 时, 可以考虑求 g(x)=f(x)+xg(x) = f(x) + x 不动点.

  • 如果函数 𝑔∈𝐶[a,b]𝑔 \in 𝐶[a,b], 对于所有x∈[a,b],g(x)∈[a,b]x \in [a,b],g(x) \in [a,b], 则函数 𝑔𝑔 在[a,b][a,b] 上存在不动点.

  • 如果 g′(x)g'(x) 存在且满足 ∣g′(x)∣<k≤1∀x∈[a,b]|g'(x)| < k \le 1 \forall x \in [a,b], 则不动点唯一. 可以从区间上的任意初始值逼近到不动点.

构建不动点的方式有很多种, 例如求解方程 x3+x−1=0x^3 + x - 1 = 0, 直接构造会发现 g(x)=x3−1g(x) = x^3 - 1 的导数在解附近大于1, 所以迭代求解并不收敛到不动点. 但是如果构造 x=(1−x)1/3x = (1 - x)^{1/3}, 此时就可以做迭代了.

牛顿方法是更精确的不动点迭代方法, 将 f(x)f(x) 在 x0x_0 点作泰勒展开, 得到

f(x)=f(x0)+f′(x0)(x−x0)+f′′(ξ)2(x−x0)2f(x) = f(x_0) + f'(x_0)(x -x_0) + \frac{f''(\xi)}{2}(x - x_0)^2

假设解 pp 和 x0x_0 的距离足够小, 舍弃二阶余项, 可得

0=f(p)≈f(x0)+f′(x0)(p−x0)0 = f(p) \approx f(x_0) + f'(x_0)(p - x_0)

考虑迭代 pn=pn−1−f(pn−1)f′(pn−1)p_n = p_{n - 1} - \frac{f(p_{n - 1})}{f'(p_{n - 1})}, 就是牛顿方法.

对于高维的情形F(x)=0F(x) = 0, 仍然可以用相似的思路处理. 高维问题的牛顿方法为求解 G(x)=x−A(x)−1F(x)=xG(x) = x - A(x)^{-1}F(x) = x 的不动点, 其中 A=JA = J 是 F(x)F(x) 的雅可比矩阵. 此时并不需要真的计算这个矩阵的逆, 只需要求解使得 J(x)y=−F(x)J(x)y = -F(x) 成立的 yy, 并更新 xnew=x+yx_{new} = x + y 直到更新的距离小于阈值就好了.

布威劳尔不动点定理

就现在学习的内容来说, 布威劳尔不动点定理对博弈论和一般均衡理论的均衡存在性起到了重要的作用, 它的定义如下：

布劳威尔不动点定理： 若 K⊂RK \subset \mathbb{R} 为紧（compact）凸（convex）集, 且 f:K↦Kf: K \mapsto K 为连续函数, 那么存在不动点 x∈Kx \in K 使得 f(x)=xf(x) = x.

对于定理的证明（低维以及高维）可以参考这篇文章, 这里仅仅对定理做一些说明.

这里要求定义域是紧致的凸集, 紧集简单理解就是包含了所有的边界点, 例如一维情形 [0,1][0,1] 是一个紧集但是 (0,1)(0,1) 并不是. 凸集就是要求任意两个集合内的点的“连线”都在集合内. 博弈论中所有的混合策略正好满足这些要求. 首先, 对于所有的边界点, 也就是纯策略都在集合中；其次, 任何两个策略 s1,s2s_1,s_2 的组合 ts1+(1−t)s2t s_1 + (1 - t) s_2 仍然是每个人在自己策略空间上的一个概率分布, 因此该集合是凸的. 最后这样的分段线性收益构成的函数一定是连续的, 这样的要求都满足后就可以构造一个神奇的函数（参考纳什的论文）, 运用布劳威尔不动点定理得出一定存在一个不动点, 对应的就是纳什均衡.

角谷静夫不动点定理

布劳威尔不动点定理的另一个延伸结论是角谷不动点定理（Kakutani fixed point theorem）. 布劳威尔不动点定理处理的是函数的情况, 而角谷不动点定理处理的是多值函数（correspondence）的情况. 函数是从点到点的映射, 而多值函数是从点到集合的映射, 所以角谷不动点定理可以看作布劳威尔不动点定理的一般化.

角谷静夫不动点定理： 令 KK 是一个紧 (compact) 凸 (convex) 集, 定义 F:K↦RF:K \mapsto \mathbb{R} 是一个上半连续的凸的多值函数, 那么存在一个点 x∗∈Kx^* \in K 使得

x∗∈F(x∗).x^* \in F(x^*).

这个定理的理解已经超出了我的数学范围, 所以我不想多做解释近在这里记录下来, 或许之后会补课. 如果运用这个定理, 不需要纳什巧妙的函数构造直接就可以得到均衡的存在性. 每个人的效用函数是连续的, 定义域如上述论证是非空的紧凸集, 此时个体的最优反应是非空、紧值、上半连续的, 当然也会是凸的. 此时, 考虑所有人对所有策略的最优反应 B:Σ↦2ΣB: \Sigma \mapsto 2^\Sigma, 其中 Σ\Sigma 是策略集, 满足所有条件, 因此存在不动点 σ∗∈Σ\sigma^* \in \Sigma 使得 σ∗∈B(σ∗)\sigma^* \in B(\sigma^*), 即所有人都作出了最优反应, 这是一个纳什均衡.

x=v0cos⁡θty=v0sin⁡θt−12gt2\begin{align*} x &= v_0\cos\theta t \\ y &= v_0\sin\theta t - \frac{1}{2}gt^2 \end{align*}

x=v0cos⁡θty=v0sin⁡θt−12gt2\begin{aligned} x &= v_0\cos\theta t \\ y &= v_0\sin\theta t - \frac{1}{2}gt^2 \end{aligned}

x˙=Ax+Bu,x(0)=x0y=Cx+Du\begin{equation} \begin{aligned} &\dot{\boldsymbol{x}}=A \boldsymbol{x}+B \boldsymbol{u} , \quad \boldsymbol{x}(0)=\boldsymbol{x}_{0}\\ &y=C x+D u \end{aligned} \end{equation}

x˙=f(x)={f1(x)x∈S1f2(x)x∈S2\begin{equation} \dot{\boldsymbol{x}}=f(\boldsymbol{x}) =\left\{ \begin{array}{ll} f_{1}(\boldsymbol{x}) & \boldsymbol{x} \in S_{1} \\ f_{2}(\boldsymbol{x}) & \boldsymbol{x} \in S_{2} \end{array}\right. \end{equation}