跳至內容

不動點定理

維基百科,自由的百科全書

在數學中,不動點定理是一個結果表示函數F在某種特定情況下,至少有一個不動點存在,即至少有一個點x能令函數

在數學中有很多定理能保證函數在一定的條件下必定有一個或更多的不動點,而在這些最基本的定性結果當中存在不動點及其定理被應用的結果具有非常普遍的價值。

分析領域

巴拿赫不動點定理中給出了一般準則:如果滿足該準則,保證迭代函數程序可以產生一個固定點。

布勞爾不動點定理的結果說:任何封閉單位球連續函數在n維歐幾里德空間本身必須有一個不動點,但它並沒有說明如何找到不動點(見:斯苯納引理英語Sperner's lemma)。

例如,餘弦函數在[−1, 1]區間連續且映射到[−1, 1]區間上,須一個不動點。描繪餘弦函數圖時這是清楚的;該不動點發生在餘弦曲線 與直線 交點上。在數值上,不動點是

代數拓撲萊夫謝茨不動點定理英語Lefschetz fixed-point theorem(和尼爾森不動點定理英語Nielsen fixed-point theorem)值得注意,它在某種意義上給出了一種計算不動點的方法。存在對博拉奇空間的概括和一般化,適用於偏微分方程理論。見:無限維空間的不動點定理。

分形壓縮拼貼定理英語collage theorem證明,對許多圖像存在一個相對較小函數的描述,當迭代適用於任何起始分形可迅速收斂在理想分形上。

離散數學和理論計算機科學領域

克納斯特-塔斯基定理某種程度上從分析移除,而且不涉及連續函數。它指出在完全格上的任何次序保持函數都有一個不動點,甚至是一個最小不動點。見布爾巴基-維特定理英語Bourbaki–Witt theorem

λ演算的共同主題是找到給出λ表達式的不動點。每個λ表達式都有一個不動點,不動點組合子是一個「函數」,即輸入一個λ表達式並輸出該表達式的一個不動點。一個重要的不動點組合是Y 組合子英語Fixed-point_combinator#Y_combinator,它使用遞歸定義。

在程式語言的指稱語義,一個克納斯特-塔斯基定理的特例用於建立遞歸定義的語義。不動點定理雖然適用於「相同」函數(從邏輯的角度來看),但其理論發展完全不同。

遞歸函數的相同定義可用克萊尼遞歸定理英語Kleene's recursion theorem可計算性理論中給出。這些結果並不是等價的定理,克拉斯特爾-塔斯基定理是個比那用於指稱語義的更強的結果。[1]然而,它卻與丘奇-圖靈論題的直觀含義相同:一個遞歸函數可描述為特定泛函的最小不動點,將函數映射至函數。

迭代函數找不動點的技術還可用在集理論;正常函數的定點引理英語fixed-point lemma for normal functions指出任何嚴格遞增的函數從到序有一個(甚至有許多)不動點。

偏序集上的每個閉包算子都有許多不動點;存在關於閉包算子的「封閉要素」,它們是閉包算子首先被定義的主要理由。

不動點定理列表

腳註

  1. ^ The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster–Tarski theorem is given to prove as exercise 4.3–5 on page 90.

參考文獻

外部連結