反復法 (数値計算)

反復法(はんぷくほう、英: 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]。

脚注

出典

^ ^a ^b 矢部2006、126頁。
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
^ ^a ^b ^c ^d 森正武. 数値解析第2版. 共立出版.
^ 戸川隼人. (1977). 共役勾配法. シリーズ新しい応用の数学.
^ ^a ^b ^c 『精度保証付き数値計算の基礎』大石進一編著、コロナ社、2018年。
^ 小澤一文『Cで学ぶ数値計算アルゴリズム』共立出版、2008年、41頁。ISBN 978-4-320-12221-5。

参考文献

和文

矢部博『工学基礎最適化とその応用』（初版）数理工学社、2006年3月25日。ISBN 4-901683-34-9。
藤野清次, & 張紹良. (1996). 反復法の数理. 朝倉書店.

英文

数値線形代数

Saad, Y. (2003). Iterative methods for sparse linear systems. SIAM.
Hageman, L. A., & Young, D. M. (2012). Applied iterative methods. Courier Corporation.
Traub, J. F. (1982). Iterative methods for the solution of equations. American Mathematical Society.
Greenbaum, A. (1997). Iterative methods for solving linear systems. SIAM.

求根アルゴリズム

Kelley, C. T. (1995). Iterative methods for linear and nonlinear equations. SIAM.
Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative solution of nonlinear equations in several variables. SIAM.

最適化問題

Kelley, C. T. (1999). Iterative methods for optimization. SIAM.
Samuel, J. L. S., & Pizzo, K. J. T. (1972). Iterative methods for nonlinear optimization problems. Prentice-Hall, Englewood Cliffs.

[矢部2006-126-1] 矢部2006、126頁。

[Yamamoto1-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。

[mori-3] 森正武. 数値解析第2版. 共立出版.

[4] 戸川隼人. (1977). 共役勾配法. シリーズ新しい応用の数学.

[oishi-5] 『精度保証付き数値計算の基礎』大石進一編著、コロナ社、2018年。

[6] 小澤一文『Cで学ぶ数値計算アルゴリズム』共立出版、2008年、41頁。ISBN 978-4-320-12221-5。

[1]

[2]

[3]

[4]

[5]

[6]