反復法 (数値計算)
数値解析分野における手法のうち、反復計算を用いるものの総称 ウィキペディアから
反復法(はんぷくほう、英: iterative method)とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法(英: direct method)と呼ばれる[1][2][3]。反復法では、適当な初期点 から出発して反復式 によって点列 を生成し最終的に最適解に収束させようとする[1][2][3]。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族 が提案されてきた。
アルゴリズム
要約
視点
与えられた関数 f について f (x) = 0 を満たす値 x を得ることを目的とする。反復法の一般的なアルゴリズムは以下のようになる:
例
要約
視点
関数 g の取り方によって種々の方法がある。
ニュートン法
→詳細は「ニュートン法」を参照
関数 f が適当に滑らかな関数ならば、f の零点を求めるための関数 g を
ととれば、これはニュートン法となる[2]。これは収束する場合は2次収束 (英: Quadratic convergence) となる[2]。すなわち、根を 、 とし、
ハレー法
ハレー法では
ととる。これは収束する場合は3次の収束となる。すなわち、
その他
不動点反復法
要約
視点
上記アルゴリズムでは、i +1 回目の近似解 xi+1 は直前の近似解 xi のみの関数であるが、これを一般化した不動点反復法[2][6]または l 点反復法は
という形で表される。ニュートン法は l = 1、割線法は l = 2 の場合である。反復関数 g は f (α) = 0 を満たす真の解 α に対し
を満たす。このことから α は g の不動点(英: Fixed point)と呼ばれる[2][5]。
l = 1 の場合、この反復法の収束性についての十分条件として、次の不動点定理が成り立つ:不動点反復法
は、反復関数 g が以下の条件を満たすとき唯一の不動点 α に収束する。
- g(x) は区間 I = [a, b] で連続。
- すべての x ∈ I に対して g(x) ∈ I。
- すべての x, y ∈ I, x ≠ y に対して
- を満たす、x, y に無関係な定数 L (0 ≦ L < 1) が存在する。
不動点定理の条件が成り立つならば、適当な初期値 x0 ∈ I を選んで反復計算を行うと、xi は区間 I 内に唯一つ存在する不動点 α に収束することが示せる[2][5]。
脚注
参考文献
Wikiwand - on
Seamless Wikipedia browsing. On steroids.