kastin 发表于 2014-8-30 23:44:34

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

一、函数迭代

函数迭代就是函数自身的复合,记作 `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 发表于 2014-8-30 23:44:45

本帖最后由 kastin 于 2014-8-31 09:44 编辑

二、函数迭代方程

首先最基本的方程是 `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 发表于 2014-8-31 22:37:40

本帖最后由 282842712474 于 2014-8-31 23:07 编辑

将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 发表于 2014-8-31 23:29:22

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`的各阶导数之间的关系,所以才有了在另一个帖子中给出的结果。
页: [1]
查看完整版本: 不动点理论与函数迭代方程的一点总结