反復法 (数値計算)

反復法(はんぷくほう、)とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法()と呼ばれる。反復法では、適当な初期点formula_1から出発して反復式 formula_2によって点列formula_3を生成し最終的に最適解に収束させようとする。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族formula_4が提案されてきた。
アルゴリズム.
与えられた関数"f" について"f" ("x") = 0 を満たす値"x" を得ることを目的とする。反復法の一般的なアルゴリズムは以下のようになる：
例.
関数"g" の取り方によって種々の方法がある。
ニュートン法.
関数"f" が適当に滑らかな関数ならば、"f" の零点を求めるための関数"g" を
ととれば、これはニュートン法となる。これは収束する場合は2次収束 () となる。すなわち、根をformula_9、formula_10とし、
ハレー法.
では
ととる。これは収束する場合は3次の収束となる。すなわち、
不動点反復法.
上記アルゴリズムでは、 回目の近似解 は直前の近似解 のみの関数であるが、これを一般化した不動点反復法または 点反復法は
という形で表される。ニュートン法は 、割線法は の場合である。反復関数 は を満たす真の解 に対し
を満たす。このことから は の不動点 () と呼ばれる。
 の場合、この反復法の収束性についての十分条件として、次の不動点定理が成り立つ：不動点反復法
は、反復関数 が以下の条件を満たすとき唯一の不動点 に収束する。
不動点定理の条件が成り立つならば、適当な初期値 を選んで反復計算を行うと、 は区間 内に唯一つ存在する不動点 に収束することが示せる。