不动点迭代以及其收敛性
 
对于迭代的理解
不动点迭代
迭代的收敛性
区间收敛
局部收敛
   
  
 

 
对于迭代的理解
 
  所谓迭代就是反复使用执行某一个过程，并且用本次执行该过程的结果作为下一次执行的起点，不断推进，直到得到满足要求的结果。
   在使用计算机解非线性方程，尤其三次及以上的非线性方程（因为二次方程的求根公式很简单，可以轻易得到根）时，如果利用求根公式的话，求根公式本身只是完成了降次，还需要进行消元才能得出结果。而且从一元六次方程开始，就没有求根公式了。而迭代法的出现，近乎完美地解决了这个问题，首先，迭代法是简单方法的不断重复，这很符合计算机的底层逻辑。其次，迭代公式如果是收敛的，那么理论上可以无限逼近根，也就是可以获得任意精度的根的近似值，这能很好的解决实际问题。
 
不动点迭代
 
  不动点迭代法又称迭代法或简单迭代法，是一种逐次逼近的方法，它是用某个固定公式反复矫正根的近似值，使之逐步精确，最后得到满足精度要求的结果。
   
 
迭代的收敛性
 
区间收敛
 
区间收敛定理：设函数 $\phi (x)$ 在区间 $[a,b]$ 内具有连续的一阶导数，而且该函数 $\phi (x)$ 满足以下两个条件：1. 映内；2.一阶导数的上界存在且在 [0,1] 内，那么方程 $x=\phi (x)$ 在区间[ a, b ] 上的解存在且唯一，对任意的 $x_0\in [a,b]$，迭代格式对应的迭代过程均收敛于根。
 区间收敛定理是充分条件而不是必要条件。
 映内：如果迭代格式 $\phi (x)$ 的值域包含于定义域，那么该迭代格式映内。可见映内是函数的一个属性。
 
局部收敛
 
设 $\phi (x)$ 在 $x=\phi (x)$ 的根 $x^{\ast }$的领域内有连续的一阶导数，而且满足一个条件：$|{\phi }^{‘}(x)|<1$，那么对任意的 $x_0\in$该领域，迭代格式对应的迭代过程均收敛于根 $x^{\ast }$。

 
文章目录
 
1. 不动点定理
Banach 不动点定理
  
2. 不动点定理的应用
2.1. 非线性常微分方程解的存在性
2.1.1. 单摆方程
   
2.2. 非线性两点边值问题的(经典)解的存在性
 

 
1. 不动点定理
 
$f:X\to X$ 是集合X到自身的一个映射，不动点就是指满足 $f(x)=x$ 的任意点 $x\in X$
 
压缩映射： $(X,d)$ 是一个距离空间，对映射 $f:X\to X$ 如果存在常数k，使得 $0<k<1$ ,且对任何 $x,y\in X$ 有 $d(f(x),f(y))\le kd(x,y)$ ，则称f为压缩映射。
 
字面意思理解的话，就是在映射之后两点的距离变短了(0< k < 1)，就是压缩了
 
 
Banach 不动点定理
 
设 $(X,d)$ 是完备的距离空间，则任何压缩映射 $f:X\to X$ 有且仅有一个不动点 $x\in X$
 此外任意给定点 $x_0\in X$ ,由 $x_{n+1}=f(x_n),n\ge 0$ 定义的序列 $(x_n{)}_{n=0}^{\infty }$ 在 $n\to \infty$ 时收敛于 $x$，且有
 
$$||x_n-x||\le C{k}^n,n\ge 0,C:=\frac{d(f(x_0),x_0)}{1-k}$$
 
简单的证明
 
由 $x_{n+1}=f(x_n),n\ge 0$ 定义的序列 $(x_n{)}_{n=0}^{\infty }$ 对任何的 $p\ge 1$ 有(压缩映射嗷)
 $$d(x_{p+1},x_p)\le kd(x_p,x_p-1)\le \cdots \le k^{p}d(x_1,x_0)$$
 因此对任意的 $m>n\ge 0$ 有
 $$\begin{gathered} d(x_m,x_n)\le \sum _{p=n}^{m-1}d(x_{p+1},x_p)\le (\sum _{p=n}^{m-1}{k}^p)d(x_1,x_0)\le \\ {k}^n(\sum _{p=0}^{m-n-1}{k}^p)d(x_1,x_0)\le \frac{k^n}{1-k}d(x_1,x_0) \end{gathered}$$
 
(用了距离的不等式、前面的不等式以及一个等比数列求和)
 
所以这是一个Cauchy序列。(对任何正实数r>0 存在一个正整数N使得对所有的整数 $m,n\ge N$ 都有 $d(x_m,x_n)<r$)
 
完备的空间 $(X,d)$ 存在 $x\in X$ 使 ${\lim }_{n\to \infty }{x}_n=x$ ，因此
 $$f(x)=\underset{n\to \infty }{\lim }f(x_n)=\underset{n\to \infty }{\lim }{x}_{n+1}=x$$
 
因此x是f的不动点，设 $y\in X$ 也是 f 的一个不动点，则 $d(x,y)=d(f(x),f(y))\le kd(x,y)$ 所以y=x，f有唯一的不动点。
 
2. 不动点定理的应用
 
2.1. 非线性常微分方程解的存在性
 
Cauchy-Lipschitz定理(又称皮卡-林德勒夫定理 Picard-Lindelöf Theorem)： 若 $||\cdot ||$ 是 ${\mathbb{R}}^N$ 上的任意一个范数， $T>0,\mathbf{g}\in \mathcal{C}([0,T]\times {\mathbb{R}}^N;{\mathbb{R}}^N)$ 是一个映射，且存在常数 $\gamma >0$ 使得 $||g(t,\omega )-g(t,v)||\le \gamma ||\omega -v||$ 对一切的 $t\in [0,T],\omega ,v\in {\mathbb{R}}^N$ 成立，又设 $u_0\in {\mathbb{R}}^N$ 为给定的向量，则初始问题或Cauchy问题
 
$$u^{\prime }(t)=g(t,u(t))$$
 $$u(0)=u_0$$
 
有且仅有一个解 $u\in {\mathcal{C}}^1([0,T];{\mathbb{R}}^N)$
 
嗯，简而言之就是是满足条件的常微分方程只有一个解。
 
 
推论:
 
对某个 $T>0$ ，给定一个矩阵场 $A\in \mathcal{C}([0,T];{\mathbb{M}}^N)$ 和向量场 $b\in \mathcal{C}([0,T];{\mathbb{R}}^N)$ ，给定向量 $u_0\in {\mathbb{R}}^N$ ，则初值问题
 
$$u^{\prime }(t)=A(t)u(t)+b(t),0\le t\le T$$
 $$u(0)=u_0$$
 
有且仅有一个解 $u\in {\mathcal{C}}^1([0,T];{\mathbb{R}}^N)$
 
2.1.1. 单摆方程
 
一个”理想摆“是一个长为 $l$ 的无重量刚性棒，一端可以绕着O点自由转动，质量m集中于另一端，在单摆于垂直面上运动的附加假设下，在时刻t其位置可完全通过O点垂直向下的轴于单摆自身的夹角 $\theta (t)$ 确定，如图所示(百度百科)
 
 
可导出牛顿运动方程为 $-mg\sin \theta (t)=ml{\theta }^{\prime \prime }(t)$ ，有 ${\theta }^{\prime \prime }(t)=-\frac{g}{l}\sin \theta (t)$
 初始条件 $\theta (0)={\theta }_0,\omega (0)={\omega }_0$
 
证明其有且仅有一个解 $\theta \in {\mathcal{C}}^{\infty }([0,\infty [)$
 
定义向量场 $u:[0,\infty [\to {\mathbb{R}}^2$ 为 $u(t)=(u_i(t){)}_{i=1}^2$
 
(这里的 $(u_i(t){)}_{i=1}^2$ 可不是平方，而是 $(x_j{)}_{j=1}^n$ 里面x取u，n取2，在这里 $u_0,u_1,u_2分别是\theta ,{\theta }^{\prime },{\theta }^{\prime \prime }$)
 
其中对所有的 $t\ge 0,u_1(t):=\theta (t),u_2(t):={\theta }^{\prime }(t)$ ，这个向量场
 $$u^{\prime }(t)=g(t,u(t)),t\ge 0u^{\prime }(0)=u_0$$
 
向量值函数 $g:[0,\infty ]\times {\mathbb{R}}^2\to {\mathbb{R}}^2$ 定义为
 $g(t,\theta ):=({\theta }_2,-\frac{g}{l}\sin \theta ({\theta }_1)),(t,\theta )\in [0,\infty [\times {\mathbb{R}}^2,u_0:=({\theta }_0,{\omega }_0)$
 
这个形式和Cauchy-Lipschitz定理的形式一样，又有
 
    
     
      
       
        ∣
       
       
        ∣
       
       
        g
       
       
        (
       
       
        t
       
       
        ,
       
       
        ω
       
       
        )
       
       
        −
       
       
        g
       
       
        (
       
       
        t
       
       
        ,
       
       
        v
       
       
        )
       
       
        ∣
       
       
        
         ∣
        
        
         1
        
       
       
        =
       
       
        ∣
       
       
        
         ω
        
        
         2
        
       
       
        −
       
       
        
         v
        
        
         2
        
       
       
        ∣
       
       
        +
       
       
        
         g
        
        
         l
        
       
       
        ∣
       
       
        sin
       
       
        ⁡
       
       
        
         ω
        
        
         1
        
       
       
        −
       
       
        sin
       
       
        ⁡
       
       
        
         v
        
        
         1
        
       
       
        ∣
       
       
        ≤
       
       
        m
       
       
        a
       
       
        x
       
       
        {
       
       
        1
       
       
        ,
       
       
        
         g
        
        
         l
        
       
       
        }
       
       
        ∣
       
       
        ∣
       
       
        ω
       
       
        −
       
       
        v
       
       
        ∣
       
       
        
         ∣
        
        
         1
        
       
      
      
       ||g(t,\omega) - g(t,v)||_1 = |\omega_2-v_2| + \frac{g}{l}|\sin\omega_1 - \sin v_1|\le max\{1,\frac{g}{l}\}||\omega-v||_1
      
     
    ∣∣g(t,ω)−g(t,v)∣∣1​=∣ω2​−v2​∣+lg​∣sinω1​−sinv1​∣≤max{1,lg​}∣∣ω−v∣∣1​
 满足该定理的条件，因此对任意正的T存在唯一的解 $u\in {\mathcal{C}}^1([0,\infty [;{\mathbb{R}}^2)$
 
2.2. 非线性两点边值问题的(经典)解的存在性
 
经典解 在I是二阶连续可微在 $\overline{I}$ 上连续的解。 而"弱"解是属于 $L^2(I)$ 且在分布意义下导数也属于 $L^2(I)$ 的解，先不用。
 
定理： 设 $I=]0,1[$ ，函数 $f\in \mathcal{C}(\overline{I}\times \mathbb{R})$ 且存在常数 $\gamma$ 使得
 $0\le \lambda <8,|f(x,u)-f(x,v)|\le \gamma |u-v|$
 对一切 $0\le x\le 1,u,v\in \mathbb{R}$ 均成立，$\alpha ,\beta \in \mathbb{R}$ 是常数，则两点边值问题
 $$-u^{\prime \prime }(x)=f(x,u(x)),0<x<1$$
 $$u(0)=\alpha ,u(1)=\beta$$
 有且仅有一个解 $u\in \mathcal{C}(\overline{I})\cap {\mathcal{C}}^2(I)$
 
其形式与非线性常微分方程解的存在性的区别是换成了加符号的二阶导数，然后多了一个点，自变量的范围限制在了(0，1)，$\gamma$ 的数值也被限制了。

压缩映射与巴拿赫不动点定理
 


 
文章目录
 
压缩映射与巴拿赫不动点定理
压缩映射
定义：映射
定义：压缩映射
例题：求证T是压缩映射
   
   
不动点定理
定义：不动点
不动点定理
证明：不动点
    
不动点定理的应用：投入产出分配方程组
证明：投入产出分配方程组有唯一解
例题：投入产出分配方程组是否有唯一解
   
  
 

 
压缩映射
 
定义：映射
 
 
分析：
 
宏观上，映射是集合到集合的关系
微观上，是俩元素之间的元素的关系
 
定义：压缩映射
 
 
分析：
 
经过映射后，两点间距离更小
问题：距离怎么定义？任取一种距离还是对于任何距离都成立？
答：$(X,d)$是完备的距离空间，则有一种$d$使其完备，就行
 
例题：求证T是压缩映射
 

 
 
分析：
 
只要取一种$d$就行
证明的目标当然是定义：$d(Tx,Ty)<\alpha d(x,y),\alpha \in [0,1)$
 
不动点定理
 
定义：不动点
 
$$Tx=x$$
 
$x$为$T$的不动点。
 
给出例子：
 
无穷多不动点：$f(x)=x$映射
没有不动点：$f(x)=x^2+1$
 
不动点定理
 
 
完备距离空间内，压缩映射具有唯一不动点。
 
证明：不动点
 
证明如下。
 
 
 
分析：
 
证明的最终目标：得出$Tx=x$，且$x$唯一
$Tx=x$可以由$d(x,Tx)=0$得到（$d(x,Tx)=0$可以由距离性质（三角不等式）、压缩映射性质（引出$\alpha$）、完备性（收敛到$x$）得到）
$x$唯一可以由反证法得到，假设存在另一个不动点$\bar{x}$，最终导出$d(x,\bar{x})=0$，由距离性质，$x=\bar{x}$，不动点唯一
 
不动点定理的应用：投入产出分配方程组
 
 
看定理有点费解，先证明，如何应用看例题。
 
证明：投入产出分配方程组有唯一解
 
 
如上，我们使用了一个距离$d(x,y)={\max }_{1\le i\le n}|x_i-y_i|$。为了使用压缩映射的性质（完备距离空间内，压缩映射具有唯一不动点），我们查看$T$是否是压缩映射。于是构造$d(T(x),T(y))$，看什么条件下$T$是压缩映射。也就是说，看什么条件下该方程组有唯一解。
 
例题：投入产出分配方程组是否有唯一解
 
 
如上，对于每行，求绝对值的和，判断是否小于1。

 
在数学中，不动点定理(Fixed point
 
theorem)是一个结果表示函数F在某种特定情况下，至少有一个不动点存在，即至少有一个点x能令函数
 
F(x)= x。
 
在数学中有很多定理能保证函数在一定的条件下必定有一个或更多的不动点，而在这些最基本的定性结果当中存在不动点及其定理被应用的结果具有非常普遍的价值。
 
分析领域的不动点定理
 
在博拉奇不动点定理中给出了一般标准：如果不满意迭代函数程序就产生一个固定点。
 
布劳尔不动点定理的结果说：任何封闭单位点的连续函数在n维欧几里德空间本身必须有一个不动点，但它并没有说明如何找到不动点(见：斯苯纳引理)。
 
例如，余弦函数在[ -1,1 ]区间连续和画入[ -1 ， 1
 
]区间
 
，故须一个不动点。描绘余弦函数图时这是清楚的；该不动点发生在余弦曲线
 
y = cos(x) 与直线 y = x 交点上。在数值上，不动点是x
 
= 0.73908513321516。
 
代数拓扑的莱夫谢茨不动点定理(和尼尔森不动点定理)值得注意，它在某种意义上给出了一种计算不动点的方法。
 
存在对博拉奇空间的概括和一般化，适用于偏微分方程理论。见：无限维空间的不动点定理。
 
分形压缩拼贴定理证明，对许多图像存在一个相对较小函数的描述，当迭代适用于任何起始分形可迅速收敛在理想分形上。
 
离散数学和理论计算机科学领域的不动点定理
 
某种程度上分析克拉斯特尔-塔斯基定理不涉及连续函数。它指出有最小不动点的函数。见布尔巴基-维特定理。
 
拉姆达计算的共同主题是找到给出拉姆达表达式的不动点。每个拉姆达表达式都有一个不动点，不动点组合是一个“函数”即：输入一个拉姆达表达式并输出该表达式的一个不动点。一个重要的不动点组合是Y染色体组合，它使用递归定义。
 
克拉斯特尔-塔斯基定理用于建立程序语言语义的递归定义。不动点定理虽然适用于“不变”函数(从逻辑的角度来看)，但其理论发展完全不同。
 
递归函数的相同定义可用克莱尼递归定理在可计算性理论中给出。这些结果并不等于说克拉斯特尔-塔斯基定理是个比程序语言指称语义计算效果更好。
 
然而，它却与丘奇-图灵论题的直观含义相同：一个递归函数可描述特定函数的最少不动点，这就是它描绘的函数。
 
迭代函数找不动点的技术还可用在集理论；定点引理的正常函数，任何d严格递增的函数从序到序有一个(实际上有许多)不动点。
 
在偏序集上的每个闭包算子都有许多不动点；存在关于闭包算子的“封闭要素”，它们是闭包算子首先被定义的主要理由。
 
其它领域的不动点定理
 
阿蒂亚-鲍特不动点定理
 
波莱尔不动点定理
 
布劳尔不动点定理
 
卡若斯梯不动点定理
 
对角线引理
 
不动点性质
 
射度量空间
 
角谷不动点定理
 
克莱尼不动点定理
 
伍兹霍尔不动点定理
 
拓扑度理论
 
分析领域
 
巴拿赫不动点定理(Banach fixed point theorem)，
 
又称为压缩映射定理或压缩映射原理，是度量空间理论的一个重要工具；它保证了度量空间的一定自映射的不动点的存在性和唯一性，并提供了求出这些不动点的构造性方法。这个定理是以斯特凡·巴拿赫(1892–1945)命名的，他在1922年提出了这个定理。
 
离散数学和理论计算机科学的领域
 
克纳斯特-塔斯基定理(Knaster–Tarski
 
theorem)在数学领域序理论和格理论中，克纳斯特-塔斯基定理，得名于
 
克纳斯特(Bronis?aw
 
Knaster)和阿尔弗雷德·塔斯基(Alfred
 
Tarski)，它声称：设 L 是完全格并设 f : L → L
 
是次序保持函数。则 f 在 L
 
中的不动点的集合也是完全格。
 
因为完全格不能是空的，这个定义特别保证 f
 
的至少一个不动点的存在，甚至一个“最小”(或“最大”)不动点的存在。在很多实际情况中，这是这个定理最重要的蕴涵。
 
λ演算(lambda
 
calculus)是一套用于研究函数定义、函数应用和递归的形式系统。它由丘奇(Alonzo
 
Church)和他的学生克莱尼(Stephen Cole
 
Kleene)在20世纪30年代引入。Church
 
运用λ演算在1936年给出判定性问题(Entscheidungsproblem)的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个
 
lambda
 
演算表达式是否等价的命题无法通过一个“通用的算法”来解决，这是不可判定性能够证明的头一个问题，甚至还在停机问题之先。Lambda
 
演算对函数式编程语言有巨大的影响，比如 Lisp
 
语言、ML 语言和 Haskell 语言。Lambda
 
演算可以被称为最小的通用程序设计语言。它包括一条变换规则(变量替换)和一条函数定义方式，Lambda
 
演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的。尽管如此，Lambda
 
演算强调的是变换规则的运用，而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。
 
邱奇-图灵论题(The Church-Turing
 
thesis)是计算机科学中以数学家阿隆佐·邱奇(Alonzo
 
Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。
 
其它领域
 
克莱尼不动点定理(Kleene fixed-point
 
theorem)在数学中，序理论的克莱尼(Kleene)不动点定理声称给定任何完全格
 
L 和任何连续的(因此单调的)函数
 
f: L → L
 
f 的最小不动点(lfp)是 f 的升 Kleene
 
链的最小上界