反復法 (数値計算)

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

アルゴリズム

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

  1. 初期値x0Rn を定める。i = 0 とおく。
  2. 漸化式
    によりxi + 1 を求める。ここでgf より決まる関数である。
  3. 適当な判断基準
    が成り立てば(このことを収束と表現する)停止し、xi を解とする。そうでなければii + 1 とし、ステップ2へ戻る。通常、判断基準には
    などが採られる。

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

ニュートン法

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

ととれば、これはニュートン法となる[2]。これは収束する場合は2次収束 (: Quadratic convergence) となる[2]。すなわち、根をとし、

ハレー法

ハレー法英語版では


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

その他

不動点反復法

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

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

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

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

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

  1. g(x) は区間 I = [a, b] で連続。
  2. すべての xI に対して g(x) ∈ I
  3. すべての x, yI, xy に対して
    を満たす、x, y に無関係な定数 L (0 ≦ L < 1) が存在する。

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

脚注

出典

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