反復法 (数値計算)
関数f が適当に滑らかな関数ならば、f の零点を求めるための関数g を
g ( x ) = x − f ( x ) f ′ ( x ) {\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}
ととれば、これはニュートン法となる。これは収束する場合は2次収束 (英: Quadratic convergence) となる。すなわち、根を 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}}
反復法(はんぷくほう、英: iterative method)とは、数値解析分野における手法のうち、反復計算を用いるものの総称。これに対し、有限回の手順で解を得る数値解法は直接法(英: direct method)と呼ばれる。反復法では、適当な初期点 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}\}} を生成し最終的に最適解に収束させようとする。アルゴリズムが単純であるために古くから用いられ、これまで様々な関数族 { f ( X ) } {\displaystyle \{f(\mathbf {X} )\}} が提案されてきた。
l = 1 の場合、この反復法の収束性についての十分条件として、次の不動点定理が成り立つ:不動点反復法
x i + 1 = g ( x i ) {\displaystyle x_{i+1}=g(x_{i})}
は、反復関数 g が以下の条件を満たすとき唯一の不動点 α に収束する。
g(x) は区間 I = [a, b] で連続。
すべての x ∈ I に対して g(x) ∈ I。
すべての x, y ∈ I, x ≠ y に対して | g ( x ) − g ( y ) | < L | x − y | {\displaystyle |g(x)-g(y)|<L|x-y|} を満たす、x, y に無関係な定数 L (0 ≦ L < 1) が存在する。
不動点定理の条件が成り立つならば、適当な初期値 x0 ∈ I を選んで反復計算を行うと、xi は区間 I 内に唯一つ存在する不動点 α に収束することが示せる。