前言

之前一段时间我稍微了解了一下泛函分析，其中最让我注目的就是其中的 Banach 不动点定理。这个定理通过迭代的方式近似求解难解的超越方程：只需要找到一个映射，并且不断迭代这个映射即可。在机器学习中，如果能够碰到这样的超越方程的话，或许可以让 Banach 不动点定理发挥它的力量。

这段时间，我倒是一直在备战高考。碰巧今天刷导数题，在令一个导函数等于零求极值的时候，发现是一个超越方程。虽然它的解能用瞪眼法看出来，但我不禁想到，万一它的解恰好不是那些特殊值呢，这样的超越方程该如何求解？本着这样一个工科生的一般化的思维（其实是注意力低下），我开始研究如何求解这样的超越方程。我首先就想到，既然不能用一个确定的数表示，那么可不可以构造一个极限，表示这个超越方程的解呢？于是，就有了今天的折腾（）

引入

一道很经典的导数题，来自 2020 年的新高考 I 卷第 21 题，简单的第一问我就省略啦：

(2020 新高考 I, 21) 已知函数 f(x) = a e^{x-1} - \ln x + \ln a，若 f(x) \ge 1，求 a 的取值范围。

不难看出，这是一个（下）凸函数，先减后增，定义域为大于 0 的全体实数。一个简单的思路是令导函数为 0，求出函数在哪里取极值，最后令极值大于等于 1 就可以了。最后我们只需整理不等式，就可以求出 a 的范围了。

话不多说，先求导：

f'(x) = a e^{x-1} - \frac{1}{x}

令导函数为 0，为了方便区分变量和常量，这里我们使 x* 满足这个条件：

a e^{x^*-1} - \frac{1}{x^*} = 0 \\ a e^{x^*-1} = \frac{1}{x^*}

补兑！超越方程，这该怎么整理出 x*(a) 并代回原函数呢？

标准答案是这样的，注意到存在一组解 x*=1, a=1，然后通过分析 f(x) 和 f(a) 发现，诶？确实没毛病嗷！

虽然还有另一个解法，但同样是通过超强的“注意力”连续构造两个函数，把原不等式 f(x) \ge 1 变成了 \ln a \ge 0。

但是，这两种解法还是太吃操作了，有没有更适合我这种注意力不足的人的做法（虽然大概率只是一些没用的奇技淫巧，是否实用还需进一步科研）？于是就有了今天的小探究。

PS: 这次心血来潮的数学小科研很可能为被炎德大联考狠狠拷打后的报复性科研（）

Banach Fixed-Point Theorem

Banach 不动点定理是定义在距离空间上的。我们知道， \R是一个距离空间，比如我们可以定义距离 d(x)=|x|。因此 Banach 定理并不是那么虚无缥缈，它可以丝滑地运用到数学分析当中。

铺垫了这么多，直接上定理！

设 (X, d) 为完备度量空间（距离空间）。设映射 T: X \rightarrow X 是一个压缩映射，即 \exist 0<q<1, \forall x,y \in X 使得：

d(T(x),T(y)) \le q \cdot d(x,y)

则映射 T 在 X 内有且仅有一个不动点 x^* （ x^* = Tx^* ）。并且可以定义一个序列 x_n = Tx_{n-1} \quad (n=1,2,3,...)，当 n 趋于整无穷时收敛于 x*。

收敛的速度可以用一个 q 相关的常数描述，感兴趣的可以查阅相关资料，这里不过多赘述。

在实数空间，我们可以做一下推广。首先是实数空间中的压缩映射 f：

对于距离空间 (X, |\cdot|)， X \in \R，设映射 f: X \rightarrow X， \exist 0<q<1, \forall x_1,x_2 \in X 压缩映射的推导如下：

d(f(x_1),f(x_2)) \le q \cdot d(x_1,x_2) \\ |f(x_2)-f(x_1)| \le q \cdot |x_2-x_1|

令 \Delta y = f(x_2)-f(x_1), \Delta x = x_2-x_1：

|\Delta y| \le q \cdot |\Delta x| \\ |\frac{\Delta y}{\Delta x}| \le q

这里变量的定义其实都是我们熟悉的 e-d 语言，所以当然可以用微积分的语言表示：

|\frac{dy}{dx}|<1

好好好，这下看懂了（）

现在我们的定理就可以变成：

对于集合 X \in \R，设函数 f: X \rightarrow X 满足 \forall x \in X, |f'(x)| < 1，则 x=f(x) 有且仅有唯一解 x^*，且 \forall x_0 \in X, x^* = f(f(f(f...f(x_0)...))).

定理变成现在这样，就可以直接拿来用了。

小试牛刀： x = \cos x 的迭代近似解

首先，我们需要找到一个区间 X，使得 cos(x) 在 X 内为压缩映射。我们可以找出一个区间 (0, \frac{\pi}{2})，cos(x) 在这个区间内的导数绝对值恒小于 1，并且根据 cos(x) 的增减性可以证明，x = cos(x) 的解正好在这个区间内。这说明这就是我们要找的区间。

接下来，在这个区间中我们就可以开始运用 Banach 不动点定理。我们设 f(x)=\cos x，方程的解 x^* = f(f...f(x_0)...) = \cos(\cos...\cos(x_0)...)，其中 x0 可以是任意 X 中的值，我们可以随便代一个 X 中的值进去算。

x = - \ln x 的迭代近似解

我们可以通过观察图像等方法发现，在 y=x 与 y=-lnx 的交点附近，-lnx 导数的绝对值大于 1。这时我们可以将右边的 x 分离，构造出新的 f：

x = - \ln x \\ -x = \ln x \\ e^{-x} = x

这时，我们再观察 f(x)=e^(-x)，就会发现它在 (0, +\infty) 上导数绝对值都小于 0，可以进行不动点逼近。

我的一点小推导：反函数与收缩映射

下面为了方便，我把区间上导函数绝对值恒大于 1 的映射称为膨胀映射。

对于方程 x=f(x)，如 f 为膨胀映射（|f'(x)|>1）且有反函数 f^{-1}(x)，可以证明 f^{-1}(x) 为收缩映射。

证明：

原方程推导：

x = f(x) \\ f^{-1}(x) = f^{-1}(f(x)) \\ f^{-1}(x) = x

导函数推导：

f^{-1'}(x) = \frac{1}{f'(f^{-1}(x))} \\ f^{-1'}(x) = \frac{1}{f'(x)} \\ |f^{-1'}(x)| = \frac{1}{|f'(x)|} \\ |f^{-1'}(x)| < 1

因此如果在方程的解附近 f(x) 的导数正好大于 1，但幸运的是 f(x) 存在反函数，我们可以转化为求解反函数的逼近。

Picard Fixed-Point Iterations

参考资料

https://en.wikipedia.org/wiki/Banach_fixed-point_theorem

https://mooseframework.inl.gov/bison/syntax/Executioner/FixedPointAlgorithms/index.html