反復法(はんぷくほう、英: iterative method)とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法(英: direct method)と呼ばれる[1][2][3]。反復法では、適当な初期点 x 0 {\displaystyle x_{0}} から出発して反復式 x i + 1 = x i + d i {\displaystyle x_{i+1}=x_{i}+d_{i}} によって点列 { x i } {\displaystyle \{x_{i}\}} を生成し最終的に最適解に収束させようとする[1][2][3]。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族 { f ( X ) } {\displaystyle \{f(\mathbf {X} )\}} が提案されてきた。
アルゴリズム

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

漸化式 x i + 1 = g ( x i ) {\displaystyle x_{i+1}=g(x_{i})} によりxi + 1 を求める。ここでg はf より決まる関数である。

適当な判断基準 r ( x i , x i + 1 ) ≤ ϵ ( ϵ > 0 ) {\displaystyle r(x_{i},x_{i+1})\leq \epsilon \quad (\epsilon >0)} が成り立てば（このことを収束と表現する）停止し、xi を解とする。そうでなければi → i + 1 とし、ステップ2へ戻る。通常、判断基準には r ( x i , x i + 1 ) = 。 x i + 1 − x i 。 {\displaystyle r(x_{i},x_{i+1})=|x_{i+1}-x_{i}|} などが採られる。

例

関数g の取り方によって種々の方法がある。
ニュートン法詳細は「ニュートン法」を参照

関数f が適当に滑らかな関数ならば、f の零点を求めるための関数g を g ( x ) = x − f ( x ) f ′ ( x ) {\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}

ととれば、これはニュートン法となる[2]。これは収束する場合は2次収束 (英: Quadratic convergence) となる[2]。すなわち、根を a {\displaystyle a} 、 Δ x i ≜ x i − a {\displaystyle \Delta x_{i}\triangleq x_{i}-a} とし、 Δ x i + 1 = f ′ ′ ( a ) 2 f ′ ( a ) ( Δ x i ) 2 + O [ Δ x i ] 3 {\displaystyle \Delta x_{i+1}={\frac {f^{\prime \prime }(a)}{2f^{\prime }(a)}}(\Delta x_{i})^{2}+O[\Delta x_{i}]^{3}}
ハレー法

ハレー法（英語版）では g ( x ) = x − f ( x ) f ′ ( x ) − f ″ ( x ) f ( x ) 2 f ′ ( x ) {\displaystyle g(x)=x-{\frac {f(x)}{f'(x)-{\frac {f''(x)f(x)}{2f'(x)}}}}}

ととる。これは収束する場合は3次の収束となる。すなわち、 Δ x i + 1 = 3 ( f ′ ′ ) 2 − 2 f ′ f ′ ′ ′ 12 ( f ′ ) 2 ( Δ x i ) 3 + O [ Δ x i ] 4 {\displaystyle \Delta x_{i+1}={\frac {3(f^{\prime \prime })^{2}-2f^{\prime }f^{\prime \prime \prime }}{12(f^{\prime })^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4}}
その他「固有値問題の数値解法」、「数値線形代数」、および「求根アルゴリズム」も参照

固有値問題に対するべき乗法[2]

ヤコビ法 (固有値問題)[2][3]

数値線形代数における共役勾配法[3][4]

二分法

デュラン＝カーナー法[2]

ブレント法

区間ニュートン法[5]

不動点反復法

上記アルゴリズムでは、i +1 回目の近似解 xi+1 は直前の近似解 xi のみの関数であるが、これを一般化した不動点反復法[2][6]または l 点反復法は x i + 1 = g ( x i , x i − 1 , … , x i − l + 1 ) , l ≥ 1 {\displaystyle x_{i+1}=g(x_{i},x_{i-1},\ldots ,x_{i-l+1}),\qquad l\geq 1}

という形で表される。ニュートン法は l = 1、割線法は l = 2 の場合である。反復関数 g は f (α) = 0 を満たす真の解 α に対し g ( α , α , … , α ) = α {\displaystyle g(\alpha ,\alpha ,\ldots ,\alpha )=\alpha }

を満たす。このことから α は g の不動点 (英: Fixed point) と呼ばれる[2][5]。

l = 1 の場合、この反復法の収束性についての十分条件として、次の不動点定理が成り立つ：不動点反復法 x i + 1 = g ( x i ) {\displaystyle x_{i+1}=g(x_{i})}