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

不動点反復法

2017年10月6日

不動点反復法 (fixed-point iteration) は、集合 $X$ からそれ自身への写像 $f:X \to X$ が与えられたとき、方程式 $x = f(x)$ の解を求めるための数値解析的手法。このとき $x$ を不動点 (fixed-point) と呼ぶ。初期値 $x_0$ から開始し、漸化式 $x_{n+1} = f(x_n)$ を反復適用することで不動点への収束列を構成する。

定義と性質

集合 $X$ 上の写像 $f:X \to X$ に対し、 $f(x^*) = x^*$ を満たす点 $x^* \in X$ を $f$ の不動点または固定点と定義する。不動点反復法は、任意の初期値 $x_0 \in X$ に対して列 $x_{n+1} = f(x_n), \quad n=0,1,2,\ldots$ を生成し、この列が収束する極限として不動点を近似的に求める手法である。

グラフ上では、連続関数 $f:\mathbb{R} \Rightarrow \mathbb{R}$ の不動点は曲線 $y=f(x)$ と対角線 $y=x$ の交点の $x$ 座標である。また集合 $X$ 上に群 $G$ が作用しているとき、どの $g \in G$ に対しても $gx=x$ となる $x \in X$ をこの作用の不動点と言う。

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

実数で定義される関数 $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$ (黄金比の比率) として求めることができる。

初期設定: 初期値 $x_0$ を適当な値に設定する。ここでは例として $x_0 = 1$ とする。
反復適用: 反復関数 $g(x)=\sqrt{x+1}$ を適用して式 ( $\ref{ex1}$ ) の計算を繰り返す。 $\begin{equation} x_{i+1} = \sqrt{x_i + 1} \label{ex1} \end{equation}$
収束判定: 収束条件 (例えば $|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$ の閉凸部分集合を値とする写像は、上半連続ならば不動点を持つ。数理経済学におけるナッシュ均衡の解の存在に適用されている。

参照

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

不動点反復法

定義と性質

Table of Contents

例1. 反復関数 ​​ の不動点

不動点定理

参照

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