反復法 (数値計算)

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

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

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

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

ニュートン法 

関数f が適当に滑らかな関数ならば、f の零点を求めるための関数g を
 
ととれば、これはニュートン法となる。これは収束する場合は2次収束 () となる。すなわち、根を、とし、

ハレー法 
では
 
ととる。これは収束する場合は3次の収束となる。すなわち、

その他 

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

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

という形で表される。ニュートン法は 、割線法は  の場合である。反復関数  は  を満たす真の解  に対し

を満たす。このことから  は  の不動点 () と呼ばれる。

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

は、反復関数  が以下の条件を満たすとき唯一の不動点  に収束する。
  は区間  で連続。
 すべての  に対して 。
 すべての  に対して

を満たす、 に無関係な定数  が存在する。

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

脚注

出典

参考文献

和文

藤野清次, & 張紹良. (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.

数値解析
数値線形代数
アルゴリズム
数学に関する記事