反復法 (数値計算)

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

アルゴリズム

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

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

   [math]x_{i+1}=g(x_i)[/math]

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

3. 適当な判断基準

   [math]r(x_i, x_{i+1})\leq \epsilon \quad ( \epsilon \gt 0) [/math]

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

   [math]r(x_i, x_{i+1}) = |x_{i+1}- x_i|[/math]

   などが採られる。

例

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

ニュートン法

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

[math] g(x)=x-\frac{f(x)}{f'(x)}[/math]

ととれば、これはニュートン法となる。これは収束する場合は2次の収束となる。すなわち、根を[math]a[/math]、[math]\Delta x_i \triangleq x_i - a [/math]とし、

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

ハレー法

ハレー法では

[math] g(x)=x-\frac{f(x)}{f'(x)-\frac{f''(x)f(x)}{2f'(x)}}[/math]

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

[math] \Delta x_{i+1} = \frac{3 (f^{\prime\prime})^2 - 2 f^\prime f^{\prime\prime\prime}}{12 (f^\prime)^2} (\Delta x_{i})^3 + O[\Delta x_{i}]^4 [/math]

その他

• 固有値問題に対する冪乗法
• 二分法
• ブレント法