反復法 (数値計算)

反復法（はんぷくほう、テンプレート:Lang-en-short）とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法（テンプレート:Lang-en-short）と呼ばれる。反復法では、適当な初期点 $x_0$ から出発して反復式 $x_{i+1}=x_i+d_i$ によって点列 $\{x_i\}$ を生成し最終的に最適解に収束させようとする。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族 $\{f(𝐗)\}$ が提案されてきた。

アルゴリズム

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

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

   $x_{i+1}=g(x_i)$

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

3. 適当な判断基準

   $r(x_i,x_{i+1})\le ϵ(ϵ>0)$

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

   $r(x_i,x_{i+1})=|x_{i+1}-x_i|$

   などが採られる。

例

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

ニュートン法

テンプレート:Main 関数 f が適当に滑らかな関数ならば、f の零点を求めるための関数 g を

$g(x)=x-\frac{f(x)}{f^{\prime }(x)}$

ととれば、これはニュートン法となる。これは収束する場合は2次収束 (テンプレート:Lang-en-short) となる。すなわち、根を $a$、$\mathrm{\Delta }{x}_i\triangleq x_i-a$ とし、

$\mathrm{\Delta }{x}_{i+1}=\frac{f^{\prime \prime }(a)}{2f^{\prime }(a)}(\mathrm{\Delta }{x}_i{)}^2+O[\mathrm{\Delta }{x}_i{]}^3$

ハレー法

テンプレート:仮リンクでは

$g(x)=x-\frac{f(x)}{f^{\prime }(x)-\frac{f^{″}(x)f(x)}{2f^{\prime }(x)}}$

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

$\mathrm{\Delta }{x}_{i+1}=\frac{3(f^{\prime \prime }{)}^2-2f^{\prime }{f}^{\prime \prime \prime }}{12(f^{\prime }{)}^2}(\mathrm{\Delta }{x}_i{)}^3+O[\mathrm{\Delta }{x}_i{]}^4$

その他

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

不動点反復法

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

$x_{i+1}=g(x_i,x_{i-1},\dots ,x_{i-l+1}),l\ge 1$

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

$g(\alpha ,\alpha ,\dots ,\alpha )=\alpha$

を満たす。このことから テンプレート:Math は テンプレート:Math の不動点（テンプレート:Lang-en-short）と呼ばれる。

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

$x_{i+1}=g(x_i)$

は、反復関数 テンプレート:Math が以下の条件を満たすとき唯一の不動点 テンプレート:Math に収束する。

1. テンプレート:Math は区間 テンプレート:Math で連続。
2. すべての テンプレート:Math に対して テンプレート:Math。
3. すべての テンプレート:Math に対して

   $|g(x)-g(y)|<L|x-y|$

   を満たす、テンプレート:Math に無関係な定数 テンプレート:Math が存在する。

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

参考文献

和文

• テンプレート:Cite book
• 藤野清次、張紹良. (1996). 反復法の数理. 朝倉書店.
• Richard Barrett, et al.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM，テンプレート:ISBN2 (1994年).
  • 上記書籍の長谷川里美、長谷川秀彦、藤野清次(訳）：「反復法 Templates」、朝倉書店、テンプレート:ISBN2 (1996年3月10日)。

英文

数値線形代数

• 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.