デッカー法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/20 18:26 UTC 版)
二分法と割線法を組み合わせるという考えは、デッカーによるものである。 ここでは、方程式 f(x) = 0 の解を求めたいとする。まず、二分法と同様に、f(a0) と f(b0) が互いに逆符号を持つような a0 と b0 の2点を初期値とする。f が区間 [a0, b0] で連続であるとき、中間値の定理により、a0 と b0 の間に解が存在する。 反復計算の k ステップ目において、以下の3点が用いられる: bk は現在の反復での値、つまりその時点で推定される f の解。 ak は "反対点"、つまり f(ak) と f(bk) が逆符号を持つような点であり、したがって区間 [ak, bk] に解が含まれる。また、|f(bk)| は |f(ak)| と等しいか、またはより小さい値とする。したがって bk は ak よりも求める解に近い。 bk−1 は1つ前の反復での値(最初の反復計算 (k = 0) では b−1 = a0 とする)。 次の反復値を求めるため、2つの値が計算される。1つは割線法により以下の式で求められる。 s = b k − b k − b k − 1 f ( b k ) − f ( b k − 1 ) f ( b k ) , {\displaystyle s=b_{k}-{\frac {b_{k}-b_{k-1}}{f(b_{k})-f(b_{k-1})}}f(b_{k}),} 2つめは二分法により求められる。 m = a k + b k 2 {\displaystyle m={\frac {a_{k}+b_{k}}{2}}} 割線法を用いた場合の s が bk と m の間にある場合は次の反復で bk+1 = s となり、そうでない場合は中間点が使用され bk+1 = m となる。 そして、f(ak+1) と f(bk+1) とが逆符号を持つような、新しい反対点 ak+1 が選ばれる。f(ak) と f(bk+1) が逆符号である場合、反対点は移動せず ak+1 = ak となる。両者が同符号であれば、f(bk+1) と f(bk) が逆符号となり、新たな反対点は ak+1 = bk となる。 最終的に、|f(ak+1)| < |f(bk+1)| となった場合は、ak+1 は bk+1 よりよい解の候補値となり、その結果 ak+1 と bk+1 の値が交換される。 以上がデッカー法による反復計算の1回分である。
※この「デッカー法」の解説は、「ブレント法」の解説の一部です。
「デッカー法」を含む「ブレント法」の記事については、「ブレント法」の概要を参照ください。
- デッカー法のページへのリンク