不动点理论与函数迭代方程的一点总结

kastin

一、函数迭代

函数迭代就是函数自身的复合，记作 `f^n= \underbrace {f\circ \cdots \circ f}_{n个f}`
性质
加法：`f^{n+m}=f^n \circ f^m=f^m \circ f^n`
幺元：`f^0(x)=x`
逆元：`f^{-n}(f^n(x))=f^n(f^{-n}(x))=x`
乘法：`\D \underbrace {f^{1/n}\circ \cdots \circ f^{1/n}}_{n个}=f=(f^n)^{1/n}`

函数迭代常常用在非线性方程求根，以及非线性映射中。下面是非常重要的一个定理。

Koenigs不动点定理`~~~~`若函数 `\phi(x)` 在包含不动点 `x_0` 的区域 `G\subseteq \bar{\CC} ` 内解析，且 `|\phi'(x_0)|<1`（符合这个条件的不动点被称为吸引不动点），则对于 `x_0` 邻域`D` 中的任意点 `p`，有$$\lim_{n \to \oo} \phi^n(p)=x_0$$可以看出，之所以被称为“吸引不动点”，就是由于邻域内任意点迭代，最终会收敛到该不动点——它就像是具有吸引作用一般。

注意，上面这个定理是严格局部(strictly local)的，它并未谈及吸引不动点邻域之外区域的相关性质。


并且还有Koenigs不动点定理的不完全逆命题形式：
定理（Koenigs）`~~~~`若对于所有 `D` 内的点 `x`，数列 `\{\phi^n(x)\}` 仍然在 `D` 内部(interior)，并且收敛于一个固定点 `x_0`（不一定有 `x_0 \in D`），那么 `|\phi(x_0)| \leqslant 1`

简单来说，这个定理表述的是——不动点要么在`D`内，要么在`D`的边界上。（这里的 `D` 应该理解成开的连通集。）

1. Newton迭代法

牛顿给出方程 `f(x)=0` 求根的迭代公式 $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\tag{1}$$这个方法的动机来自于 `f(x)` 在 `x=x_n` 处的一阶泰勒展开（毕竟对于流数术，牛顿很是擅长）。
可以证明，上述迭代在简单根（非重根）附近是以不低于二阶的速度收敛的，在重根附近则是线性收敛的。

2. 改进Newton法

为了加快收敛速率，一种Newton下山法出现了。基本思想是，每次迭代时乘上一个因子来改变搜索步长，保证高度是下降的（这便是“下山”名称的来源）：$$x_{n+1}=x_n-t_n\frac{f(x_n)}{f'(x_n)}\tag{2}$$其中 `t_n\in(0,1)` 是下山因子，且满足 `|f(x_{k+1}|<|f(x_k)|`以保正收敛。本质上来说，该方法是最速下降法的一维版本。

不过，对于导数过于复杂，或者导数不存在的情形——这在最优化计算过程中经常碰到——就需要使用无导数方法(derivative-free)。一般的策略是，使用割线代替切线（自然地，代价是牺牲收敛速度，不过可以使用数列的加速收敛技术来解决这个问题，比如Aitken加速收敛方法等）。其中值得提一下的是Steffenson的改进方法，即用$$\frac{f(x_n+f(x_n))-f(x_n)}{f(x_n)}$$代替`(1),(2)`中的 `f'(x_n)`。这种技巧我们在微分方程数值求解中也常看到。

2. 广义Newton法

将Newton的方法推广，思路有两种。一种是从泰勒级数的角度，保留高阶项。很显然这种方法将会带来隐式迭代的问题，仍然要求解一个非线性方程的根（而且根不止一个），这无益于问题的解决。另一种思路就是从Koenigs不动点定理来做文章。

我们发现，只要找到一个迭代函数 `M(x)` 满足下面两个条件：

(1)  `M(x_0)=x_0`，这里的 `x_0` 是给定函数 `f(x)` 的一个简单根；
(2)  `|M'(x_0)|<1`.

那么，根据Koenigs不动点定理，在 `x_0` 的邻域内任一点开始迭代，最后都会收敛到 `f(x)=0` 的根。

假设有一个函数 `\phi(x)`，它有一个不动点是 `x_0`。考虑在 `x=x_0` 处的泰勒展开$$\phi(x)=x_0+\phi'(x_0)(x-x_0)+\frac{\phi''(x_0)}{2!}(x-x_0)^2+\cdots$$观察发现，假若在 `x=x_0` 点处 `\phi(x)` 的前 `m-1` 阶导数都为零：$$\phi'(x_0)=\phi''(x_0)=\cdots=\phi^{(m-1)}(x_0)=0,\quad \phi^{(m)}\neq 0$$那么$$\phi(x)-x_0=\frac{\phi^{(m)}(\xi)}{m!}\varepsilon^m<A\varepsilon,\quad \varepsilon=x-x_0\\
\phi^2(x)-x_0=\phi(\phi(x))-x_0<\frac{\phi^{(m)}(x_0)}{m!}(A\varepsilon)^m\\
\cdots\\
\phi^n(x)-x_0<(\frac{\phi^{(m)}(x_0)}{m!})^{mn}(A\varepsilon)^{mn}$$由于`\varepsilon/m！`减小速率很快，当`0<|\phi^{(m)}(x_0)|<M\varepsilon`时，`m` 越大，迭代函数 `\phi(x)` 的收敛得非快。

因此，快速收敛的广义Newtion法可以描述为，若找到函数 `N_m(x)` 满足下面两个条件：
(1)  `N_m(x_0)=x_0`，这里 `f(x_0)=0`；
(2)  `N_m^{(i)}(x_0)=0\enspace(i<m)`，且 `N_m^{(m)}(x_0)\neq 0`

对于 `f(z)=0` 的简单根 `x`，我们来构造 `N_2(z)`。
令 `N_2(z)=z-f(z)\varphi(z)`，这里的 `\varphi(z)`是解析函数。根据上面的两个条件$$N_2'(x)=1-f(x)\varphi'(x)-f'(x)\varphi(x)=0$$因为 `f(x)=0` 但 `f'(x)\neq 0`，所以 `\varphi(x)=1/f'(x)`，即$$N_2(x)=x-\frac{f(x)}{f'(x)}$$
验证：如果 `f(x)` 存在简单根 `x_0`，此时 `f'(x_0)\neq 0`，那么 `N_2'(x_0)=0`；若 `x_0` 是 `f(x)` 的 `p` 重根，则 `N_2'(x_0)=1-1/p`。所以 `|N(x_0)|<1`， 满足Koenigs不动点定理的条件，并且不动点 `N_2(x)=x` 恰好就是 `f(x)=0` 的根。我们便得到了经典的Newton迭代法。

当然，可以构造更高阶的。出发点有两种：一是使用类似摄动分析中的渐近级数形式来构造迭代函数 $$N_m(z)=z-f(z)\varphi_1(z)-f(z)^2\varphi_2(z)-\cdots-f(z)^{m-1}\varphi_{m-1}(z)\tag{3}$$高阶的形式相当复杂，例如$$N_5(z)=z-\frac{f}{1!}\frac{1}{f'}-\frac{(f)^2}{2!}\frac{f''}{(f')^3}-\frac{(f)^3}{3!}\frac{3(f'')^2-f'f'''}{(f')^5}-\frac{(f)^4}{4!}\frac{15(f'')^3-10f'f''f'''+(f')^2f^{(4)}}{(f')^7}\tag{4}$$

第二种是反复应用 Newton迭代公式中的步长项 `f(x)/f'(x)` 项。比如，若 `f'(z)\neq 0`，于是 `g(z)=f(z)/f'(z)=0` 与 `f(z)=0`，等价。因此迭代公式是$$x_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}=x_n-\frac{f(x_n)f'(x_n)}{f'(x_n)^2-f(x_n)f''(x_n)}\tag{5}$$这种方法比上一种形式更加简单，而且在 `f(x)=0` 的重根附近不会像经典Newton法（`N_2(x)`）那样收敛速率降低。

kastin

二、函数迭代方程

首先最基本的方程是 `f^n(x)=x`。这是一个周期自映射(self-mapping)，相当于一个有向图，里面会形成n-周期回路，解当然可以是无穷多个。对于这个方程，前人研究出结论：
1) `n` 若为奇数，则其单调解必唯一，且是 `f(x)=x`；
2) 若 `n` 为偶数，则单调解必然满足 `f^2(x)=x`。
当然，对于非单调解的情况，有可能解是p-周期的（即`f^p(x)=x`），且`p\mid n`。

举几个例子，比如`f^2(x)=x`，解有很多，最简单的`f(x)=\pm x`（单调解），`f(x)=c/x`（非单调解）；而对于 `f(f(f(x)))=x`，解可以是 `\D f(x)=\frac{x-3}{x+1}` 或者 `\D f(x)=-\frac{2x+3}{x+1}`等。
另外还有更加复杂的，比如`f(g(x))=g(f(x))`。一般情况下，该方程只能通过幂级数求解。特别地，若`g\circ f`是一个多项式，那么`f(x)=z\exp(2\pi \text{i}\,m/n)+b`，其中`m,n`为正整数。

下面重点介绍一下Schroder方程，这个方程在函数迭代方程中很有重要。

Schroder方程：`\varphi(f(x))=f'(x) \varphi(x) \D\tag{1}`
更常用的是它的正规形式： `\varphi(f(x))=s\,\varphi(x)\D\tag{2}`其中`f(x)`有不动点`x_0`，且`f'(x_0)=s`。

这个方程之所以重要，是因为很多问题归结为解决这个问题，比如

Abel方程：$$f(g(x))=f(x)+1 \tag{3}$$
Bottcher方程：$$f(g(x))=f(x)^{\small m} \tag{4}$$
Poincare方程：$$f(sx)=F(f(x)) \tag{5}$$
以上三个方程分别可以通过变换 `\psi(x)=s^{f(x)}`，`\psi(x)=\ln f(x)`，`\psi(x)=f^{-1}(x)` 就能化为正规Schroder方程。

将Schrode方程两边取 `\varphi^{-1}`，然后反复迭代 `n` 次，利用Koenigs不动点定理便可推出求解Schroder方程的一个非常有用结论：

定理`~~~~`若 `f(z)` 是复变函数，在原点附近解析，且 `f(0)=0`，`f'(0)=s`，`0<|s|<1`。则有唯一解 `\varphi(z)` 在0点附近处解析，且有 `\varphi'(0)=1`，$$\D \varphi(z)=\lim_{n\to \oo}s^{-n}f^n(z) \tag{6}$$

下面就用几个例子总结一下函数迭代方程的几种常用的求解方法。

第一种方法：相似函数法
这种方法就是利用这里的定理一。
一般来说，`\varphi(x)`的选取比较难找，常常考虑使用 `\cos,\cosh,\ln,\exp,\tan`以及线性分式`\D\frac{ax+b}{cx+d}`等。
例如 `f(f(x))=x^2-2x` ，考虑使用`\varphi(x)=\cos x,\cosh x`。于是给出解 $$f(x)=\begin{cases}\D 2 \cos(\sqrt{2} \arccos \frac{x-1}{2})+1 &&(0 \leqslant |x| \leqslant 1)\\ \D 2\cosh(\sqrt{2}\, \mathrm{arccosh}\frac{x-1}{2})+1 &&(|x|>1)\end{cases}$$

第二种方法：映射构造法
以`f(f(x))=\exp(x)`为例，根据映射关系构造分段函数。具体参见下面文献Baker_1955中的第177页内容。另外这里也有描述。

第三种方法：幂级数法
若 `f(x)` 存在实不动点，则可以考虑在不动点处写成幂级数的形式，然后代入方程，求出各项系数。

第四种方法：Carleman矩阵法
相关知识链接
例如`f^2(x)=x^2-2`，参见Gottfried Helms在这里的回答。他给出的结果是$$f(x)  = 2+ 2 (x-2) + \frac16 (x-2)^2 - \frac190 (x-2)^3 + \frac1720 (x-2)^4 - \frac732400 (x-2)^5 \\ + \frac{161}{4276800} (x-2)^6 - \frac{391}{55598400} (x-2)^7 + O(x^8)$$


函数方程(包括函数迭代方程)的研究历史、研究方法与一些文献（下载）：
http://zakuski.utsa.edu/~jagy/other.html
推荐阅读上面链接中的
Baker_1955
Baker_Obituary
Erdos_Jabotinsky_1960
D_S_Alexander_1994
K_C_G_book_excerpts
Kuczma_Survey_1964
上面第一个是Baker对f(f(z))=F(z)在复数域的详细研究；第二个是对Baker一生研究贡献的总结。第三个是关于解析迭代的研究，给出了几个重要的定理。剩下的是函数方程的研究历史与成果综述。

282842712474

将Newton的方法推广，思路有两种。一种是从泰勒级数的角度，保留高阶项。很显然这种方法将会带来隐式迭代的问题，仍然要求解一个非线性方程的根（而且根不止一个），这无益于问题的解决。

保留高阶项，不一定要这样展开。请看：
http://spaces.ac.cn/index.php/archives/590/
（这篇文章写于高一，有些表述不大妥当，标题也夸大了，但是里边改进牛顿法的思路，我觉得还是可以用的）

求方程$f(y)=0$的根，相当于求用$x=f(y)$隐式确定的函数$y=y(x)$在x=0的值，然后我们可以用泰勒级数展开
$$y=y(x_0)+y'(x_0)(x-x_0)+\frac{1}{2}y''(x_0)(x-x_0)^2+...$$
根据$x=f(y)$求各阶导数$\frac{d^n y}{dx^n}$，然后取有限项迭代（取到一阶就是牛顿法），就不会出现求解非线性方程的现象了。取到二阶是：
$$y_{n+1}=y_n-\frac{f(y_n)}{f'(y_n)}-\frac{f''(y_n)}{f'(y_n)^3}\frac{f(y_n)^2}{2}$$

kastin

282842712474 发表于 2014-8-31 22:37
保留高阶项，不一定要这样展开。请看：
http://spaces.ac.cn/index.php/archives/590/
（这篇文章写于 ...

对于一阶的是`(f^{-1})'=1/f'`，那么依次求`(f^{-2})',(f^{-3})',...`与`f',f'',f''',...`之间有什么样的关系呢？

另外，对于迭代，我之前探究了一下`n`次迭代根`f^{1/n}(x)`的各阶导数与`f`的各阶导数之间的关系，所以才有了在另一个帖子中给出的结果。