\( \def\vector#1{\boldsymbol{#1}} \)

不動点反復法

Takami Torao
  • このエントリーをはてなブックマークに追加

定義と性質

集合 \(X\) からそれ自身への写像 \(f\) が与えられたとき、\(f(x)=x\) を満たす元 \(x\) を不動点 (fixed-point) または固定点と言う。グラフ上では、連続関数 \(f:\mathbb{R} \Rightarrow \mathbb{R}\) の不動点は曲線 \(y=f(x)\) と対角線 \(y=x\) の交点の \(x\) 座標である。また集合 \(X\) 上に群 \(G\) が作用しているとき、どの \(g \in G\) に対しても \(gx=x\) となる \(x \in X\) をこの作用の不動点または固定点と言う。

不動点反復法 (fixed-point iteration) は不動点の近似解を求めるための数値解析手法である。

Table of Contents

  1. 定義と性質
    1. 例1. 反復関数 \(g(x)=\sqrt{x+1}\) の不動点
  2. 不動点定理
  3. 参照

実数で定義される関数 \(f\) と \(f\) 上の点 \(x_0\) が与えられたとき、不動点反復法は以下の数列で表される。\[ x_{n+1} = f(x_n), \ \ n = 1, 2, \cdots \] ここで \(x_0, x_1, \cdots\) は不動点 \(x\) に収束することを期待する数列である。

\(f(x) = 0\) の不動点近似を求める場合、\(x = g(x)\) と変形し \(x_{n+1} = g(x_n)\) という漸化式とみなして数列化を行う。

  • 反復関数 \(g(x)\) がリプシッツ連続であり、リプシッツ定数が 1 より小さいと反復法は収束しやすい。

  • 初期値が適切でないと、習得しなかったり他の不動点に収束することがある。

  • 初期値の選び方により収束が遅くなることがあるため、収束の早さを改善するための工夫が必要になることがある。

不動点反復法はニューラルネットワークの学習 (RNN)、固有ベクトル・固有値の算出 (PageRank アルゴリズム)、変分オートエンコーダー (VAE)、EM アルゴリズム、線形回帰など、さまざまなアルゴリズムや最適化プロセスで使われている。

例1. 反復関数 \(g(x)=\sqrt{x+1}\) の不動点

例として関数 \(g(x)=\sqrt{x+1}\) を用いて不動点反復法を説明する。この関数の不動点は \(x = \sqrt{x+1}\) を満たす \(x\) で、解析的に \(x = \frac{1+\sqrt{5}}{2} \simeq 1.6180\) (黄金比の比率) として求めることができる。

  1. 初期設定: 初期値 \(x_0\) を適当な値に設定する。ここでは例として \(x_0 = 1\) とする。

  2. 反復適用: 反復関数 \(g(x)=\sqrt{x+1}\) を適用して式 (\(\ref{ex1}\)) の計算を繰り返す。\[ \begin{equation} x_{i+1} = \sqrt{x_i + 1} \label{ex1} \end{equation} \]

  3. 収束判定: 収束条件 (例えば \(|x_{i+1}-x_i|\lt\delta\)、つまり前後の反復差が十分に小さい場合) を満たすまで反復を繰り返す。

この手順での値 \(x\) の収束を Table 1 に示す。9 回の反復で 1.6180 と近似した値に収束していることがわかる。

Table 1. 反復関数 \(g(x)=\sqrt{x+1}\) の不動点 \(x\) の収束
\(i\) \(x_i\) \(x_{i+1}\) \(\delta = 0.0001\)

不動点定理

不動点定理 (fixed-point theorem) は不動点が存在するための十分条件を与える定理の総称である。以下に有名な不動点定理とその十分条件を列挙する [1]。

バナッハの不動点定理 (縮小写像の原理)

\(X\) が完備な距離空間で \(f\) が縮小写像。

ブラウワーの不動点定理

\(X\) が \(\mathbb{R}^N\) 内の閉凸集合またはそれと同相な閉集合で、\(f\) が連続写像。

レフシェッツの不動点定理

\(X\) が有限多面体で、\(f\) が連続写像かつ \(f\) のレフシェッツ数が 0 でない。

シャウダーの不動点定理

\(X\) がバナッハ空間内の閉凸集合、\(f\) が連続関数で、その像 \(f(X)\) がコンパクト集合。

ティホノフの不動点定理

\(X\) がバナッハ空間内のコンパクトな凸集合で、\(f\) が連続写像。

角谷の不動点定理

\(\mathbb{R}^N\) 内のコンパクト凸集合 \(C\) 上で定義され、空でない \(C\) の閉凸部分集合を値とする写像は、上半連続ならば不動点を持つ。数理経済学におけるナッシュ均衡の解の存在に適用されている。

参照

  1. 青本和彦, et al. 岩波数学入門辞典. 岩波書店 2005.