反復法 (数値計算)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数値計算分野における反復法(はんぷくほう、: iterative method)とは、求根アルゴリズムの手法のうち、反復計算を使うもの。アルゴリズムが単純であるために古くから用いられている。

アルゴリズム[編集]

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

  1. 初期値x0Rn を定める。i = 0 とおく。
  2. 漸化式
    x_{i+1}=g(x_i)
    によりxi + 1 を求める。ここでgf より決まる関数である。
  3. 適当な判断基準
    r(x_i, x_{i+1})\leq \epsilon \quad ( \epsilon > 0)
    が成り立てば(このことを収束と表現する)停止し、xi を解とする。そうでなければii + 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次の収束となる。

ハレー法[編集]

ハレー法英語版では

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

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

その他[編集]