反復法 (数値計算)

反復法：数値解析における反復計算手法

数値解析において、問題の解を反復計算によって近似的に求める手法を反復法といいます。これは、有限回の計算で解を得る直接法と対照的です。反復法は、初期値から出発し、反復式を繰り返し適用することで解に近づいていくアプローチです。そのアルゴリズムの簡潔さから古くから利用され、多様な関数族に対して適用できるよう、様々な改良が加えられてきました。

反復法のアルゴリズム

反復法の目的は、与えられた関数 f(x) = 0 を満たす x を求めることです。一般的なアルゴリズムは以下の通りです。

1. 初期値の設定: n 次元空間内の初期値 x₀ を設定します。
2. 反復計算: 次の漸化式を用いて xᵢ₊₁ を計算します。
xᵢ₊₁ = g(xᵢ)
ここで、g は関数 f から導かれる関数です。
3. 収束判定: 予め定めた閾値 ϵ を用いて、収束条件
r(xᵢ, xᵢ₊₁) ≤ ϵ
を満たすかどうかを判定します。r は xᵢ と xᵢ₊₁ の差を表す関数で、例えば、|xᵢ₊₁ - xᵢ| を用いることが多いです。収束条件を満たせば計算を停止し、xᵢ を解とします。
4. 反復の継続: 収束条件を満たさない場合は、i を i+1 に更新し、ステップ2に戻ります。

反復法の具体例

関数 g の選び方によって、様々な反復法が生まれます。代表的な例として、ニュートン法とハレー法があります。

ニュートン法

関数 f が滑らかな場合、ニュートン法は次の関数 g を用います。

g(x) = x - f(x) / f'(x)

これは、関数の接線を用いて零点を近似する方法です。収束する場合は2次収束を示し、解に非常に高速に近づきます。

ハレー法

ハレー法は、ニュートン法をさらに改良した方法で、次の関数 g を用います。

g(x) = x - f(x) / (f'(x) - (f''(x)f(x)) / (2f'(x)))

これは、関数の接線だけでなく曲率も考慮することで、より高精度な近似を行います。収束する場合は3次収束を示します。

その他の反復法

他にも多くの反復法が存在します。

固有値問題: べき乗法、ヤコビ法
数値線形代数: 共役勾配法
求根アルゴリズム: 二分法、デュラン＝カーナー法、ブレント法、区間ニュートン法
不動点反復法: これは、上記アルゴリズムを一般化したもの。直前の近似解だけでなく、それ以前の複数回の近似解を用いて次の近似解を計算します。

不動点反復法と不動点定理

不動点反復法は、xᵢ₊₁ = g(xᵢ, xᵢ₋₁, ..., xᵢ₋ₗ₊₁) の形で表されます。ここで l は用いる過去の近似解の数です。この反復法の収束性について、不動点定理が重要な役割を果たします。不動点定理は、特定の条件下で、反復法が唯一の不動点に収束することを保証する定理です。その条件は、反復関数 g が連続であり、区間 I 内で自己写像であり、かつ I 内で縮小写像であることです。

参考文献

本記事の内容をより深く理解するためには、以下の参考文献が役立ちます。

和文: 矢部博『工学基礎 最適化とその応用』、藤野清次, 張紹良『反復法の数理』
英文: Saad, Y. (2003). Iterative methods for sparse linear systems. SIAM.、その他多数（最適化、数値線形代数、求根アルゴリズムに関する書籍）

もう一度検索