反復法 (数値計算)のソースを表示

'''反復法'''（はんぷくほう、{{lang-en-short|iterative method}}）とは、[[数値解析]]分野における手法のうち、[[ループ (プログラミング)|反復計算]]を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は'''直接法'''（{{lang-en-short|direct method}}）と呼ばれる<ref name="矢部2006-126">[[#矢部2006|矢部2006]]、126頁。</ref><ref name="Yamamoto1">{{Cite book |和書 |author=山本哲朗 |title=数値解析入門 |edition=増訂版 |date=2003-06 |publisher=[[サイエンス社]] |series=サイエンスライブラリ 現代数学への入門 14 |ISBN=4-7819-1038-6}}</ref><ref name="mori">[[森正武]]. 数値解析 第2版. [[共立出版]].</ref>。反復法では、適当な初期点 <math>x_0</math> から出発して反復式 <math>x_{i+1}=x_{i}+d_i</math> によって点列 <math>\{x_i\}</math> を生成し最終的に最適解に[[収束]]させようとする<ref name="矢部2006-126" /><ref name="Yamamoto1"/><ref name="mori"/>。[[アルゴリズム]]が単純であるために古くから用いられ、これまで様々な関数族 <math>\{ f(\mathbf{X})\}</math> が提案されてきた。

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

# 初期値''x''<sub>0</sub> &isin; '''R'''<sup>''n''</sup> を定める。''i'' = 0 とおく。
# [[漸化式]]
#:: <math>x_{i+1}=g(x_i)</math>
#: により''x''<sub>''i'' + 1</sub> を求める。ここで''g'' は''f'' より決まる関数である。
# 適当な判断基準
#:: <math>r(x_i, x_{i+1})\leq \epsilon \quad ( \epsilon > 0)  </math>
#: が成り立てば（このことを[[収束]]と表現する）停止し、''x<sub>i</sub>'' を解とする。そうでなければ''i'' → ''i'' + 1 とし、ステップ2へ戻る。通常、判断基準には
#:: <math>r(x_i, x_{i+1}) = |x_{i+1}- x_i|</math>
#: などが採られる。

== 例 ==
関数 ''g'' の取り方によって種々の方法がある。
=== ニュートン法 ===
{{main|ニュートン法}}
関数 ''f'' が適当に[[滑らかな関数]]ならば、''f'' の零点を求めるための関数 ''g'' を
: <math> g(x)=x-\frac{f(x)}{f'(x)}</math>
ととれば、これは[[ニュートン法]]となる<ref name="Yamamoto1"/>。これは収束する場合は2次収束 ({{lang-en-short|Quadratic convergence}}) となる<ref name="Yamamoto1"/>。すなわち、根を <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>

=== ハレー法 ===
{{仮リンク|ハレー法|en|Halley's method}}では
: <math> g(x)=x-\frac{f(x)}{f'(x)-\frac{f''(x)f(x)}{2f'(x)}}</math><br>
ととる。これは収束する場合は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>

=== その他 ===
{{seealso|固有値問題の数値解法|数値線形代数|求根アルゴリズム}}
* [[固有値]]問題に対する[[べき乗法]]<ref name="Yamamoto1"/>
* [[ヤコビ法 (固有値問題)]]<ref name="Yamamoto1"/><ref name="mori"/>
* [[数値線形代数]]における[[共役勾配法]]<ref name="mori"/><ref>戸川隼人. (1977). [[共役勾配法]]. シリーズ新しい応用の数学.</ref>
* [[二分法]]
* [[デュラン＝カーナー法]]<ref name="Yamamoto1"/>
* [[ブレント法]]
* [[区間ニュートン法]]<ref name="oishi">『精度保証付き数値計算の基礎』[[大石進一]] 編著、コロナ社、2018年。</ref>

== 不動点反復法 ==
上記[[アルゴリズム]]では、{{math|''i'' +1}} 回目の近似解 {{math|''x''<sub>''i''+1</sub>}} は直前の近似解 {{math|''x''<sub>''i''</sub>}} のみの関数であるが、これを一般化した'''不動点反復法'''<ref name="Yamamoto1"/><ref>{{cite|和書 |editor= |author=小澤一文 |title=Cで学ぶ数値計算アルゴリズム |edition= |publisher=[[共立出版]] |year=2008 |isbn=978-4-320-12221-5 |page=41}}</ref>または '''{{math|''l''}} 点反復法'''は
:<math>x_{i+1} = g(x_i, x_{i-1}, \ldots ,x_{i-l+1}),\qquad l\geq 1</math>
という形で表される。[[ニュートン法]]は {{math|''l'' {{=}} 1}}、[[割線法]]は {{math|''l'' {{=}} 2}} の場合である。'''反復関数''' {{math|''g''}} は {{math|''f'' (&alpha;) {{=}} 0}} を満たす真の解 {{math|&alpha;}} に対し
:<math>g(\alpha, \alpha,\ldots,\alpha)=\alpha</math>
を満たす。このことから {{math|&alpha;}} は {{math|''g''}} の'''不動点'''（{{lang-en-short|Fixed point}}）と呼ばれる<ref name="Yamamoto1"/><ref name="oishi"/>。

{{math|''l'' {{=}} 1}} の場合、この反復法の収束性についての十分条件として、次の'''[[不動点定理]]'''が成り立つ：不動点反復法
:<math>x_{i+1} = g(x_i)</math>
は、反復関数 {{math|''g''}} が以下の条件を満たすとき唯一の不動点 {{math|&alpha;}} に収束する。
# {{math|''g''(''x'')}} は区間 {{math|''I'' {{=}} [''a'', ''b'']}} で連続。
# すべての {{math|''x'' ∈ ''I''}} に対して {{math|''g''(''x'') ∈ ''I''}}。
# すべての {{math|''x'', ''y'' ∈ ''I'', ''x'' ≠ ''y''}} に対して
#::<math>|g(x)-g(y)|<L|x-y|</math>
#:を満たす、{{math|''x'', ''y''}} に無関係な定数 {{math|''L'' (0 ≦ ''L'' < 1)}} が存在する。

[[不動点定理]]の条件が成り立つならば、適当な初期値 {{math|''x''<sub>0</sub> ∈ ''I''}} を選んで反復計算を行うと、{{math|''x''<sub>''i''</sub>}} は区間 {{math|''I''}} 内に唯一つ存在する不動点 {{math|&alpha;}} に収束することが示せる<ref name="Yamamoto1"/><ref name="oishi"/>。

== 脚注 ==
===出典===
{{reflist}}

==参考文献==
===和文===
*{{Cite book |和書 |author=矢部博 |date=2006-03-25 |title=工学基礎 最適化とその応用 |publisher=数理工学社 |edition=初版 |isbn=4-901683-34-9 |ref=矢部2006 }}
* 藤野清次、張紹良. (1996). 反復法の数理. [[朝倉書店]].
* [https://www.netlib.org/templates/templates.pdf Richard Barrett, et al.: ''Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods''], SIAM，{{ISBN2|978-0-89871-328-2}} (1994年).
** 上記書籍の長谷川里美、長谷川秀彦、藤野清次(訳）：「反復法 Templates」、朝倉書店、{{ISBN2|4-254-11401-X}} (1996年3月10日)。

===英文===
====数値線形代数====
* Saad, Y. (2003). Iterative methods for sparse linear systems. [[SIAM (学会)|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 (学会)|SIAM]].
====求根アルゴリズム====
* Kelley, C. T. (1995). Iterative methods for linear and nonlinear equations. [[SIAM (学会)|SIAM]].
* Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative solution of nonlinear equations in several variables. [[SIAM (学会)|SIAM]].
====最適化問題====
* Kelley, C. T. (1999). Iterative methods for optimization. [[SIAM (学会)|SIAM]].
* Samuel, J. L. S., & Pizzo, K. J. T. (1972). Iterative methods for nonlinear optimization problems. Prentice-Hall, Englewood Cliffs.
{{最適化アルゴリズム}}
{{linear algebra}}

{{Normdaten}}
{{デフォルトソート:はんふくほう}}
[[Category:反復法|*]]
[[Category:数値解析]]
[[Category:数値線形代数]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]