反復法 (数値計算)

反復法（はんぷくほう、英: iterative method）とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法（英: direct method）と呼ばれる^[1]^[2]^[3]。反復法では、適当な初期点 $x_{0}$ から出発して反復式 $x_{i+1}=x_{i}+d_{i}$ によって点列 $\{x_{i}\}$ を生成し最終的に最適解に収束させようとする^[1]^[2]^[3]。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族 $\{f(\mathbf {X} )\}$ が提案されてきた。

アルゴリズム

与えられた関数 f について f (x) = 0 を満たす値 x を得ることを目的とする。反復法の一般的なアルゴリズムは以下のようになる：

初期値x₀ ∈ Rⁿ を定める。i = 0 とおく。
漸化式
$x_{i+1}=g(x_{i})$

によりx_{i + 1} を求める。ここでg はf より決まる関数である。
適当な判断基準
$r(x_{i},x_{i+1})\leq \epsilon \quad (\epsilon >0)$

が成り立てば（このことを収束と表現する）停止し、x_i を解とする。そうでなければi → i + 1 とし、ステップ2へ戻る。通常、判断基準には
$r(x_{i},x_{i+1})=|x_{i+1}-x_{i}|$

などが採られる。

例

関数 g の取り方によって種々の方法がある。

ニュートン法

→詳細は「ニュートン法」を参照

関数 f が適当に滑らかな関数ならば、f の零点を求めるための関数 g を

g(x)=x-{\frac {f(x)}{f'(x)}}

ととれば、これはニュートン法となる^[2]。これは収束する場合は2次収束 (英: Quadratic convergence) となる^[2]。すなわち、根を $a$ 、 $\Delta x_{i}\triangleq x_{i}-a$ とし、

\Delta x_{i+1}={\frac {f^{\prime \prime }(a)}{2f^{\prime }(a)}}(\Delta x_{i})^{2}+O[\Delta x_{i}]^{3}

ハレー法

ハレー法（英語版）では

g(x)=x-{\frac {f(x)}{f'(x)-{\frac {f''(x)f(x)}{2f'(x)}}}}

ととる。これは収束する場合は3次の収束となる。すなわち、

\Delta x_{i+1}={\frac {3(f^{\prime \prime })^{2}-2f^{\prime }f^{\prime \prime \prime }}{12(f^{\prime })^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4}

その他

→「固有値問題の数値解法」、「数値線形代数」、および「求根アルゴリズム」も参照

不動点反復法

上記アルゴリズムでは、 $i +1$ 回目の近似解 $x i +1$ は直前の近似解 $x i$ のみの関数であるが、これを一般化した不動点反復法^[2]^[6]または $l$ 点反復法は

x_{i+1}=g(x_{i},x_{i-1},\ldots ,x_{i-l+1}),\qquad l\geq 1

という形で表される。ニュートン法は $l = 1$ 、割線法は $l = 2$ の場合である。反復関数 $g$ は $f (α) = 0$ を満たす真の解 $α$ に対し

g(\alpha ,\alpha ,\ldots ,\alpha )=\alpha

を満たす。このことから $α$ は $g$ の不動点（英: Fixed point）と呼ばれる^[2]^[5]。

$l = 1$ の場合、この反復法の収束性についての十分条件として、次の不動点定理が成り立つ：不動点反復法

x_{i+1}=g(x_{i})

は、反復関数 $g$ が以下の条件を満たすとき唯一の不動点 $α$ に収束する。

$g (x)$ は区間 $I = [a, b]$ で連続。
すべての $x \in I$ に対して $g (x) \in I$ 。
すべての $x, y \in I, x \neq y$ に対して
$|g(x)-g(y)|<L|x-y|$

を満たす、 $x, y$ に無関係な定数 $L (0 ≦ L < 1)$ が存在する。

不動点定理の条件が成り立つならば、適当な初期値 $x 0 \in I$ を選んで反復計算を行うと、 $x i$ は区間 $I$ 内に唯一つ存在する不動点 $α$ に収束することが示せる^[2]^[5]。

反復法 (数値計算)

アルゴリズム

例

ニュートン法

ハレー法

その他

不動点反復法

脚注

出典

参考文献

和文

英文

数値線形代数

求根アルゴリズム

最適化問題

Related Articles