标签:
杂谈 |
分类: 数学 |
在数学中,不动点定理(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 链的最小上界