反復法 (数値計算)

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

アルゴリズム

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

1. 初期値x₀ ∈ Rⁿ を定める。i = 0 とおく。
2. 漸化式

   ${\displaystyle x_{i+1}=g(x_{i})}$

   によりx_{i + 1} を求める。ここでg はf より決まる関数である。

3. 適当な判断基準

   ${\displaystyle r(x_{i},x_{i+1})\leq \epsilon \quad (\epsilon >0)}$

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

   ${\displaystyle r(x_{i},x_{i+1})=|x_{i+1}-x_{i}|}$

   などが採られる。

例

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

ニュートン法

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

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

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

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

ハレー法

ハレー法（英語版）では

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

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

${\displaystyle \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}}$

その他

• 固有値問題に対するべき乗法^[2]
• ヤコビ法 (固有値問題)^[2][3]
• 数値線形代数における共役勾配法^[3][4]
• 二分法
• デュラン＝カーナー法^[2]
• ブレント法
• 区間ニュートン法^[5]

不動点反復法

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

${\displaystyle 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 を満たす真の解 α に対し

${\displaystyle g(\alpha ,\alpha ,\ldots ,\alpha )=\alpha }$

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

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

${\displaystyle x_{i+1}=g(x_{i})}$

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

1. g(x) は区間 I = [a, b] で連続。
2. すべての x ∈ I に対して g(x) ∈ I。
3. すべての x, y ∈ I, x ≠ y に対して

   ${\displaystyle |g(x)-g(y)|<L|x-y|}$

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

不動点定理の条件が成り立つならば、適当な初期値 x₀ ∈ I を選んで反復計算を行うと、x_i は区間 I 内に唯一つ存在する不動点 α に収束することが示せる^[2][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.