ja.wikipedia.org

不動点定理 - Wikipedia

出典: フリー百科事典『ウィキペディア（Wikipedia）』

数学における不動点定理（ふどうてんていり、英: fixed-point theorem）は、ある条件の下で自己写像 f: A → A は少なくとも 1 つの不動点（f(x) = x となる点 x ∈ A）を持つことを主張する定理の総称を言う[1]。不動点定理は応用範囲が広く、分野を問わず様々なものがある[2]。

バナッハの不動点定理は、反復合成写像が不動点を持つことを保証するために満たすべき条件に関する一般的な判定法を与える[3]。一方、ブラウワーの不動点定理は構成的な方法ではなく、「n-次元ユークリッド空間における閉単位球からそれ自身への連続関数は必ず不動点をもつ」ことを述べる[4] が、どのように不動点を求めればよいかについて何も言及しない（スペルナーの補題（英語版）も参照）。

たとえば、余弦関数 cos は区間 [−1, 1] において連続な [−1, 1] への函数であるから、不動点を持たねばならない。グラフを書けば明らかに、余弦曲線 y = cos(x) は直線 y = x と交わり、そこに不動点を持つ。この不動点は、数値的にはおよそ x = 0.73908513321516… である。

代数的位相幾何学におけるレフシェッツの不動点定理[5]（およびニールセンの不動点定理[6]）は、ある意味で「不動点の個数を数える方法」を示すものであるため重要である。これらは、バナッハ空間や他のさらに抽象的な空間への一般化が数多く知られており、偏微分方程式論に応用されている。詳しくは無限次元空間における不動点定理を参照されたい。

このほか、コラージュ定理（英語版）はフラクタル圧縮の分野における定理であり、多くの画像に対して、ある比較的小さな式で表される関数が存在して「どんな初期値の画像から始めても、その関数を繰り返し適用すれば、急速に目的の画像に収束する」ようにできることが証明するものである[7]。

クナスター・タルスキーの定理（英語版）は、完備束上の任意の単調写像は少なくとも一つの不動点（実際には「最小の不動点」）が存在することを述べる[8]。詳しくはブルバキ・ヴィットの定理を参照されたい。この定理は静的コード解析の一つの形式である抽象解釈において応用を持つ。

ラムダ計算における共通のテーマの一つとして、「与えられたラムダ式の不動点を求める」というものがある。ラムダ式には必ず不動点が存在し、「ラムダ式を入力すると、その式の不動点が出力として得られる」という関数が不動点コンビネータである[9]。不動点コンビネータの1つにYコンビネータがあり、これは再帰的定義を記述する際に用いられる重要なものである。不動点定理を適用する対象の関数は、論理的な観点からは同一の関数だが、その理論の展開は多岐にわたっている。プログラム言語の表示的意味論の分野では、再帰的定義の意味論を構築するために、クナスター・タルスキーの定理のある特別な場合を用いている。また、計算可能性理論においても、クリーネの再帰定理[10]を使えば、再帰的関数を同様に定義することができる。なお、これらの各分野で用いている定理は等価ではなく、クナスター・タルスキーの定理というのは、表示的意味論で用いている定理よりもずっと強い定理である[11]。ただし、チャーチ・チューリングのテーゼの観点では、これらの直感的な意味合いは同じであり、「再帰関数は、関数を関数にうつすある汎関数の最小の不動点として表すことができる」ということに他ならない。

ところで、初めに紹介した「関数の繰り返し適用によって不動点を求める」という手法は、集合論でも用いる手法である。正規関数の不動点補題（英語版）では、「順序数から順序数への連続な狭義単調増加関数には、少なくとも1つの（実際には多数の）不動点が存在する」ことを述べている。また、半順序集合の閉包作用素（英語版）には必ずいくつかの不動点が存在し、それらが、この閉包作用素に関する意味で「閉」な元である（これが、閉包作用素を先に定義する最大の理由である）。

元の個数が奇数であるような有限集合上の任意の対合は不動点を持つ。より一般に、元の有限集合上の任意の対合に対して、不動点の数と元の数の偶奇性は一致する。ドン・ザギエはこれらの観察の下でフェルマーの二平方和定理の一文証明を与えた。これは整数の三つ組の成す同じ集合上の二つの対合を記述することで成り立っており、一方はただ一つの不動点を持つことが平易にわかるもので、他方は与えられた素数 (ただし mod 4 で 1 のもの) を二平方和でおのおの表現したものに対する不動点を持つ。前者は奇数個の不動点を持つから後者もそうで、従って必ず所期の形の表現が存在することがわかる[12]。

  1. ^ Brown, R. F. (Ed.) (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6
  2. ^ Dugundji, James; Granas, Andrzej (2003). Fixed Point Theory. Springer-Verlag. ISBN 0-387-00173-5
  3. ^ Giles, John R. (1987). Introduction to the Analysis of Metric Spaces. Cambridge University Press. ISBN 978-0521359283
  4. ^ Eberhard Zeidler, Applied Functional Analysis: main principles and their applications, Springer, 1995.
  5. ^ Solomon Lefschetz (1937). “On the fixed point formula”. Ann. of Math. 38 (4): 819–822. doi:10.2307/1968838.
  6. ^ Fenchel, Werner; Nielsen, Jakob; edited by Asmus L. Schmidt (2003). Discontinuous groups of isometries in the hyperbolic plane. De Gruyter Studies in mathematics. 29. Berlin: Walter de Gruyter & Co.
  7. ^ Barnsley, Michael. (1988). Fractals Everywhere. Academic Press, Inc.. ISBN 0-12-079062-9
  8. ^ Alfred Tarski (1955). “A lattice-theoretical fixpoint theorem and its applications”. Pacific Journal of Mathematics 5:2: 285–309.
  9. ^ Peyton Jones, Simon L. (1987). The Implementation of Functional Programming. Prentice Hall International
  10. ^ Cutland, N.J., Computability: An introduction to recursive function theory, Cambridge University Press, 1980. ISBN 0-521-29465-7
  11. ^ The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4。page 83 の theorem 4.24 が表示的意味論で用いている不動点定理であり、一方、クナスター・タルスキーの定理は page 90 の exercise 4.3–5 で練習問題となっている。
  12. ^ Zagier, D. (1990), “A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares”, American Mathematical Monthly 97 (2): 144, doi:10.2307/2323918, MR1041893.
  • Agarwal, Ravi P.; Meehan, Maria; O'Regan, Donal (2001). Fixed Point Theory and Applications. Cambridge University Press. ISBN 0-521-80250-4
  • Aksoy, Asuman; Khamsi, Mohamed A. (1990). Nonstandard Methods in fixed point theory. Springer Verlag. ISBN 0-387-97364-8
  • Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. ISBN 0-521-38808-2
  • Brown, R. F. (Ed.) (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN 0-8218-5080-6
  • Dugundji, James; Granas, Andrzej (2003). Fixed Point Theory. Springer-Verlag. ISBN 0-387-00173-5
  • Kirk, William A.; Goebel, Kazimierz (1990). Topics in Metric Fixed Point Theory. Cambridge University Press. ISBN 0-521-38289-0
  • Kirk, William A.; Khamsi, Mohamed A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. John Wiley, New York.. ISBN 978-0-471-41825-2
  • Kirk, William A.; Sims, Brailey (2001). Handbook of Metric Fixed Point Theory. Springer-Verlag. ISBN 0-7923-7073-2
  • Šaškin, Jurij A; Minachin, Viktor; Mackey, George W. (1991). Fixed Points. American Mathematical Society. ISBN 0-8218-9000-X
  • 山崎 進『計算論理に基づく推論ソフトウェア論』コロナ社、2000年。
  • Alfred Tarski (1955), A lattice-theoretical fixpoint theorem and its applications