不動点定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数学における不動点定理(ふどうてんていり、: fixed point theorem, fixpoint theorem)とは、ある条件の下で自己写像 f : AA は少なくとも 1 つの不動点、すなわち f(x) = x となる点 xA を持つことを主張する定理の総称を言う。

不動点を利用した定理は応用範囲が広く、分野を問わず様々なものがある。

解析学において[編集]

たとえば、余弦関数 cos は、区間 [ −1, 1 ] において連続であり、この区間に対するも [ −1, 1 ] である。このことから、cos には不動点が存在するとわかる。実際、余弦関数のグラフを考えれば、余弦曲線 y = cos ( x ) が直線 y = x と交わる箇所において、明らかに関数 cos の不動点、つまり x = cos ( x ) を満たす点が存在する。この不動点は、数値的にはおよそ x = 0.73908513321516 である。

バナッハの不動点定理英語版という定理があり、これによれば、ある条件のもとでは必ず、関数の繰り返し適用によって不動点を得ることができる。一方、ブラウワーの不動点定理英語版は、実際の構成の仕方はわからないが、「n 次元ユークリッド空間における閉単位球から同じ球への連続関数は必ず不動点をもつ」ことを述べている。ただし、その不動点の求め方については何も言及しない(スペルナーの補題英語版も参照)。

代数的位相幾何学におけるレフシェッツの不動点定理(および{{仮リンク|ニールセンの不動点定理]])は、ある意味で「不動点の個数を数える方法」を示すものであるため重要である。

また、不動点定理は、バナッハ空間や他のさらに抽象的な空間への一般化が数多く知られており、偏微分方程式論に応用されている。詳しくは無限次元空間における不動点定理英語版を参照されたい。

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

離散数学において[編集]

解析学の範疇からは少し離れ、クナスター・タルスキーの定理英語版は連続関数を扱わない定理である。この定理は、完備束の上の単調関数には必ず不動点が存在し、したがって「最小の不動点」が存在することを述べている。詳しくはブルバキ・ヴィットの定理英語版を参照されたい。

ラムダ計算における共通のテーマの一つとして、「与えられたラムダ式の不動点を求める」というものがある。ラムダ式には必ず不動点が存在し、「ラムダ式を入力すると、その式の不動点が出力として得られる」という関数が不動点コンビネータである。不動点コンビネータの1つにYコンビネータがあり、これは再帰的定義を記述する際に用いられる重要なものである。

不動点定理を適用する対象の関数は、論理的な観点からは同一の関数だが、その理論の展開は多岐にわたっている。プログラム言語表示的意味論の分野では、再帰的定義の意味論を構築するために、クナスター・タルスキーの定理のある特別な場合を用いている。また、計算可能性理論においても、クリーネの再帰定理を使えば、再帰的関数を同様に定義することができる。

なお、これらの各分野で用いている定理は等価ではなく、クナスター・タルスキーの定理というのは、表示的意味論で用いている定理よりもずっと強い定理である[1]。ただし、チャーチ・チューリングのテーゼの観点では、これらの直感的な意味合いは同じであり、「再帰関数は、関数を関数にうつすある汎関数の最小の不動点として表すことができる」ということに他ならない。

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

各不動点定理の言明とその応用[編集]

角谷の不動点定理(Kakutani's fixed point theorem)[編集]

ブラウワーの不動点定理は位相空間上の連続写像に対して成り立つが、連続関数ではない離散的関数に対して成り立つようにブラウワーの不動点定理を一般化した定理を角谷の不動点定理と呼ぶ。角谷静夫によって導入された。

主要な応用は、ゲーム理論におけるゲームの一般的な解概念であるナッシュ均衡の存在証明である。

クナスター・タルスキの定理(Knaster-Tarski theorem)[編集]

完備束上に定義された単調関数の集合に対して定まる単調関数の不動点の集合は完備束を成すという定理である。

主要な応用は、デイナ・スコットクリストファー・ストレイチーによる表示的意味論である。

関連項目[編集]

脚注[編集]

  1. ^ 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 で練習問題となっている。

参考文献[編集]

外部リンク[編集]