非线性方程求解 不动点迭代法
Solution

Knowledge
收敛定理一



可以尝试证明一下

1、不动点的存在性

2、不动点的唯一性

3、序列收敛
收敛定理二



这个的条件2更加简洁
可以尝试证明

1、不动点的存在性（其实同定理一的证明过程一样的）

2、不动点的唯一性

3、收敛性证明
误差估计（有公式）


如何判断迭代函数是否收敛


还有一个局部收敛的定义


example

Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void out_put(double x){
    printf("%.5f\n", x);
}
double cal_1(double x){///x = exp(-x)
    return exp(-x);
}
double cal_2(double x){/// x = -ln(x);
    if(x < 0.0){
        printf("ERROR, log a negtive number\n");
        exit(-1);
    }
    return -log(x);
}
int main(){
    double x = 0.5;
    int n = 20;
    for(int i = 1; i <= n; i++){
        out_put(x);
        x = cal_1(x);
    }
    printf("The ans is: %.4f\n", x);

    x = 0.5;
    for(int i = 1; i <= n; i++){
        out_put(x);
        x = cal_2(x);
    }
    printf("The ans is: %.4f\n", x);
    return 0;
}

不动点迭代法
将原先的

$f(x) = 0$

转化成

$x = h(x)$

的方式进行求解。
不动点的存在性定理
定理1
如果 $f(x)$ 为区间$[a, b]$上的连续函数，且满足下面两个条件：


压缩性：对于 $x \in [a, b]$, $a \leq f(x) \leq b$


大L性质：存在正常数L<1, 使得，对于任意的$x, y \in [a, b]$ 都有，

$|f(x) - f(y)| \leq L|x-y|$


则存在有唯一的不动点。
构造$h(x) = f(x) - x$，再用连续函数的介值定理就可以证明存在性，唯一性代入就可证明。
局部收敛定理：
若有这样的不动点 $x^*$ ，如果存在有在不动点附近的某个领域，满足有$h'(x) < 1$，则迭代法：

$x_{t+1} = h(x_t)$

局部收敛。

$h'(x^*)$数值越接近0，收敛速度越快。
如果对于小于n次的导数在不动点出都为0，且$h^{(n)}(x)$ 不一定为0，则称为n阶收敛

举列子

求根号数的迭代（不妨取根号3）

迭代方式有很多种比如:

$\begin{aligned}
x^2 - 3 =& 0 \\
x =& x - \lambda (x^2 - 3)  & \lambda  \in [0, 1] \\
x_{k+1} =& x_{k} - \lambda (x_{k}^2 - 3)\\ 
\end{aligned}$
代码：
x = 1
for i in range(100):
    x = x - 0.1 * (x ** 2 - 3)
print(x)

输出：
1.7320508075688772

$\begin{aligned}
x^2 - 3 =& 0 \\
nx^2 =& (n-1)x^2 + 3 & n \in N \\
x =& \frac{(n-1)x}{n} + \frac{3}{nx} \\
x_{k+1} =& \frac{(n-1)x_k}{n} + \frac{3}{nx_k}\\ 
\end{aligned}$
代码：
x, n = 2, 2
for i in range(100):
    x = (n - 1) / n * x + 3 / (n * x)
print(x)

输出：
1.7320508075688772


实际上的$\sqrt{3}$

import math
math.sqrt(3)


输出：1.7320508075688772

尾记

本文链接: https://blog.csdn.net/a19990412/article/details/80814435
对应github: https://github.com/Sean16SYSU/Algorithms4N

一、不动点算法
又称固定点算法。所谓不动点，是指将一个给定的区域A,经某种变换ƒ(x),映射到A时,使得x=ƒ(x)成立的那种点。最早出现的不动点理论是布劳威尔定理(1912)：设A为Rn中的一紧致凸集, ƒ为将A映射到A的一连续函数，则在A中至少存在一点x，使得x=ƒ（x）。其后，角谷静夫于1941年将此定理推广到点到集映射上去。设对每一x∈A ，ƒ(x)为A的一子集。若ƒ(x)具有性质：对A上的任一收敛序列xi→x0，若yi∈ƒ(xi)且yi→y0，则有y0∈ƒ(x0),如此的ƒ(x)称为在A上半连续，角谷静夫定理：设A为Rn中的一紧致凸集，对于任何x∈A，若ƒ(x)为A的一非空凸集，且ƒ(x)在A上为上半连续，则必存在x∈A,使x∈ƒ(x)。J.P.绍德尔和J.勒雷又将布劳威尔定理推广到巴拿赫空间。 
　　不动点定理在代数方程、微分方程、积分方程、数理经济学等学科中皆有广泛的应用。例如，关于代数方程的基本定理，要证明ƒ(x)=0必有一根，只须证明在适当大的圆│x│≤R 内函数ƒ(x)+x有一不动点即可；在运筹学中，不动点定理的用途至少有二：一为对策论中用来证明非合作对策的平衡点的存在和求出平衡点；一为数学规划中用来寻求数学规划的最优解。对于一个给定的凸规划问题：min{ƒ(x)│gi(x)≤0，i=1,2,…,m}，在此,ƒ和g1,g2,…,gm皆为Rn中的凸函数。通过适当定义一个函数φ,可以证明：若上述问题的可行区域非空，则φ的不动点即为该问题的解。 
　　在1964年以前，所有不动点定理的证明都是存在性的证明，即只证明有此种点存在。1964年，C.E.莱姆基和 J.T.Jr.豪森对双矩阵对策的平衡点提出了一个构造性证明。1967年，H.斯卡夫将此证法应用到数学规划中去。其后，不动点定理的构造性证明有了大的发展和改进。 
　　H.斯卡夫的证明是基于一种所谓本原集，后来的各种发展皆基于某种意义下的三角剖分。现以n 维单纯形Sn为例来说明这一概念，在此,。对每一i, 将区间0≤xi≤1依次分为m1,m2…等分，m1<m2<…,mi→,是给定的一列正整数。对于固定的i,过分点依次作平行于xi=0的平面。 这些平面将Sn分成若干同样大小的n维三角形。它们的全体作成的集 Gi,称为Sn的一三角剖分。设ƒ(x)为 Sn→Sn的一连续函数，x＝(x1,x2,…,xn+1),ƒ（x）=（ƒ1（x），ƒ2（x），…，ƒn+1（x））。定义。由于ƒ(x)和x皆在Sn上,若有则显然有ƒ(x)=x,即x为ƒ(x)的一不动点。 
　　对每一点y∈Sn赋与标号l(y)=k=min{j│y∈Cj,且yj>0}。由著名的施佩纳引理,在Gi中必存在一三角形σi，它的n+1个顶点yi(k)的标号分别为k(k=1,2,…,n+1)于是可得一列正数ij(j→),使得(k)→yk,k=1,2,…,n+1。根据σi的作法，当ij→时,收敛成一个点x。故yk=x,k=1,2,…,n+1。因 (k)的标号为k,故yk∈Ck,因而即x为所求的不动点。因此,求ƒ(x):Sn→Sn 的不动点问题就化为求 σi(i=1,2,…) 的问题。为了计算上的效果，除了上述的标号法之外，还有标准整数标号法、向量标号法等等。关于如何求σi，有变维算法、三明治法、同伦算法、变维重始法等等，通过适当定义,可将上之Sn改为Rn或Rn中之一凸集。求一凸函数在一凸集上的极值问题也可化为求不动点问题。一般说来，这条途径适用于维数不高但问题中出现的函数较为复杂的情况。 
　　参考书目 
　A.J.J.TalmanVariable Dimension Fixed Point Algorithms and Triangulations, Mathematisch Centrum, Amsterdam, 1980.
 
二、Prof. Yuguang Xu (徐裕光 教授)（ Kunming University, China (雲南省昆明學院)）
Fixed point theory and its applications（在台湾成功大学所作的报告）
 
不动点理论研究的内容属于数学的非线性泛函分析和一般拓扑学范畴。研究出的结果被广泛应用于分析数学，力学，微分方程，控制理论，最优化理论，非线性规划，数理经济学和博弈论等应用性学科。
(一)．不动点理论的发展进程
•  一个简单的不动点问题（微积分中）；
•  1909 年， Brouwer 的著名的 不动点定理 及一系列的论文创立了不动点理论；
•  1922 年 , 波兰著名数学家 S. Banach 给出了一个既简单又实用的 压缩映射原理， 它也是一个不动点定理。在简单的条件下， Banach 压缩映射原理不仅指出了映射不动点的存在性和唯一性，还提供了一种逼近不动点的方法；
•  1967 年，美国数学家 H. E. Scarf 找到了计算单纯形连续映射不动点的组合拓扑有限算法，这也就是 Brouwer 不动点定理的构造性证明；
•  1941 年，日本数学家角谷静夫（ Kakutani ）的集值不动点定理为博弈论建立在数学基础上作了理论准备；
•  1968 年的 Fan － Browder 不动点定理， 1972 年的 Himmelberg 不动点定理以及 Tarafdar 在 1987 年和 1992 年分别在拓扑线性空间和 H －空间建立的不动点定理；
•  美国数学家 Michael （ 1956 年）， Deutsch 和 Kenderov （ 1983 年），应用集值分析中的连续选择原理在拓扑空间建立集值不动点定理和几乎不动点定理；
•  1990 年以后，关于不动点理论的研究达到一个高潮，在各种映射或空间条件下，讨论不动点，随机不动点，几乎不动点等，每年有上百篇论文发表，新的不动点定理和各种迭代逼近方法不断涌现。
(二)．不动点理论的四个研究方向
1. 在拓扑空间研究“不动点性质”（使用同伦群），不动点的有限算法（组合拓扑）；
•  丹麦数学家 Nielsen 研究不动点的个数（ Nielsen 数），开创不动点类理论的研究，大陆数学家的工作；
•  一般度量空间或拓扑向量空间的连续映射的不动点问题

不动点的存在性问题研究


映射的连续性，紧性，空间的紧性，凸性，单值或集值


不动点的迭代逼近问题研究


多种迭代方法，收敛性（强，弱），收敛速度，误差分析，稳定性

 
•  应用集值分析中的连续选择原理在拓扑空间建立集值不动点定理和几乎不动点定理并应用于博弈论研究。
(三)． 不动点理论主流方向的研究现状，及研究前沿期待解决的问题
“ 一般度量空间或拓扑向量空间映射的不动点问题”是研究的主流。近 20 年来的研究发展主线：
•  迭代逼近算法的研究（从 Mann 迭代到杂交迭代等）；
•  强伪压缩映射的不动点，强增生算子方程的迭代解（两者的联系）；
•  迭代误差分析和稳定性研究；
•  有待解决的几个问题（一般情况下的收敛性问题， 迭代收敛的等价性问题，不动点存在性和迭代逼近的条件的协调性问题，关于 Schauder 猜想）。
其次为“应用连续选择原理建立集值不动点定理和几乎不动点定理”的研究。
现有的最好结果和需要解决的问题：
a ） 上（下）半连续集值映射与其不动点存在性的拓扑同伦关系；
b) 具备弱于上（下）半连续性的集值映射与其不动点的存在唯一性的充要条件；
c) 探索几乎均衡解与几乎不动点存在性的关系。
三、维基百科中关于Kakutani fixed point theorem
http://en.wikipedia.org/wiki/Kakutani_fixed_point_theorem


应用领域之一：博弈论
 
Mathematician John Nash used the Kakutani fixed point theorem to prove a major result in game theory. Stated informally, the theorem implies the existence of a Nash equilibrium in every finite game with mixed strategies for any number of players. This work would later earn him a Nobel Prize in Economics.
In this case, S is the set of tuples of mixed strategies chosen by each player in a game. The function φ(x) gives a new tuple where each player's strategy is her best response to other players' strategies in x. Since there may be a number of responses which are equally good, φ is set-valued rather than single-valued. Then the Nash equilibrium of the game is defined as a fixed point of φ, i.e. a tuple of strategies where each player's strategy is a best response to the strategies of the other players. Kakutani's theorem ensures that this fixed point exists.
 
 
翻译：数学家约翰.纳什应用角谷静夫不动点理论证明了博弈论中的大量的结论。可以说角谷静夫不动点理论意味着在每个具有任意数量玩家的混合策略有限博弈中纳什均衡是存在的！此项工作将在未来（1994年）为他赢得诺贝尔经济学奖。
在这种情况下，S是博弈中每个玩家所选择的混合策略元组的集合。方程 φ(x)给出一个新的元组，其中每个玩家的策略是在X中她对其他玩家所选策略的最优选择。由于可能有许多选择是不相上下的，所以φ是集值而不是单值。博弈中的纳什均衡被定义为φ的不动点，比如，一个策略元组，其中针对其他玩家的策略每个玩家的策略都是最优的。角谷静夫的理论确保了此不动点是存在的！
四、我的理解
角谷静夫不动点理论的重要性在与将布劳威尔定理中的存在某一个点x∈A,使得x=f(x)在A范围中成立扩展到存在A上的一个子集X*使得x=f(x),x∈X*。（数学表达不准确，大概是这个意思。O(∩_∩)O~）
这个理论正好为纳什证明“所有有限博弈至少有一个纳什均衡”提供了有力的理论工具！
 
五、有趣的地方
在《纳什博弈论论文集》序言部分第七页最下边的注释，序言作者Ken Binmore讲了一个小故事，有次角谷静夫做演讲，演讲结束后，角谷静夫问Kin Binmore为啥这么多人来听演讲，Ken Binmore解释说许多经济学家是来看作出如此重要的角谷静夫不动点理论的作者的。角谷静夫却回答说：“什么是角谷静夫不动点理论”。
看完这里，我笑半天，角谷静夫都不知道自己的理论被别人叫啥了，也许可能太谦虚了，也许故意为之！想不明白！
 

 
角谷静夫（1911年8月28日-2004年8月17日）是日本著名数学家 ，他最知名的角谷静夫不动点定理 。

本文使用 Zhihu On VSCode 创作并发布
从不动点迭代到牛顿法
为了利用不动点迭代法求解函数零点，我们需要对
做一定的变形，得到
的形式。
当然我们可以简单变形为
，但是这么做不一定能保证
不动点迭代收敛定理中的导数条件
成立。
一个简单的改进是
，我们设想其中K是我们选定的能使导数条件成立的常数。
但是很可惜这种策略不能应对
符号发生变化的情形：当
变号时，K不能跟着变号，这就造成了
进一步的，我们想到可以把常数K换成一个函数
,也就是将方程变形为
.只要在
变号的时候
也变号，那么我们也许就有办法让导数条件成立。
最简单的选择就是直接取
，于是我们就得到了
牛顿法：
设想将
当作常数处理，我们能得到
当然按照商的导数法则我们不能这么办，但这暗示我们取
可能是某种意义下的最优选择
牛顿法
从上一节的讨论中，我们可以看到牛顿法是不动点方法的一个变种.
在牛顿法中,我们取
,也就是说我们有迭代式:
现在我们重新审查这个迭代式，我们可以发现它具有很好的性质。从几何和分析的角度出发，我们可以重新解释牛顿法（这也是科普牛顿法时通常的切入点）
几何意义: 切线法
GIF动图演示
分析意义: 泰勒近似
众所周知
在
处的一阶泰勒展开式为：
若
为
的根，则
假设
很小，那么我们可以忽略掉高阶小量
于是我们就有
从而
牛顿法的局部收敛性
即便采用了种种策略，我们仍然发现牛顿法迭代并不能时刻满足导数条件
对于一些离根较远的初始估计，牛顿法常常不能收敛到我们想要的根，如下图↓
只有对于足够接近
的初值
才能收敛到我们想要的解。
这点表明，牛顿法是一种局部收敛的方法
定义(局部收敛).
如果存在函数零点
的某个邻域
，迭代方法对在该邻域内所有的初值
都收敛到
，则称该迭代方法
局部收敛到
牛顿法收敛定理
设
.若
是
在
上的零点，且满足
. 那么牛顿法
局部收敛到
证明.
我们只需验证
满足不动点收敛定理的条件
(
) 由
知
，即
连续
(
)
由
的连续性知存在
的邻域
,
(
)
牛顿法的收敛速度
定义(二次收敛).
令
表示迭代过程中第
步的误差，如果
则该方法称为满足二次收敛
牛顿法的二次收敛
在满足收敛定理的条件下，牛顿法二次收敛到函数的零点。
证明.
于是
Note.
牛顿法能比二分法和FPI更快地收敛到根，这是因为它使用了函数更多的信息（例如切线的方向）