ブレント法

ブレント法（）は、二分法、割線法、逆2次補間を組み合わせた、複雑ではあるが広く用いられている、数値解析における求根アルゴリズムの1つである。二分法の安定さを有し、かつ安定でない他の手法と同程度に高速に解が求められる場合もある。可能な限り、より収束の早い割線法や逆2次補間を用い、必要に応じてより安定な二分法に切り替えて解を求めるという手法である。ブレント法は、1969年のによる初期のアルゴリズムを元にして、1973年ににより考案されたものである 。
デッカー法.
二分法と割線法を組み合わせるという考えは、デッカーによるものである。 
ここでは、方程式 の解を求めたいとする。まず、二分法と同様に、 と が互いに逆符号を持つような と の2点を初期値とする。 が区間 で連続であるとき、中間値の定理により、 と の間に解が存在する。
反復計算の ステップ目において、以下の3点が用いられる：
次の反復値を求めるため、2つの値が計算される。1つは割線法により以下の式で求められる。
2つめは二分法により求められる。
割線法を用いた場合の が と の間にある場合は次の反復で となり、そうでない場合は中間点が使用され となる。
そして、 と とが逆符号を持つような、新しい反対点 が選ばれる。 と が逆符号である場合、反対点は移動せず となる。両者が同符号であれば、 と が逆符号となり、新たな反対点は となる。
最終的に、 となった場合は、 は よりよい解の候補値となり、その結果 と の値が交換される。
以上がデッカー法による反復計算の1回分である。
ブレント法.
デッカー法では、関数 "f" が滑らかな形状であれば、効率的に解が求められる。しかし、毎回の収束計算で割線法が選択される場合もあるが、このときは "b""k" の収束が非常に遅い（特に "b""k" − "b""k"−1 が任意に小さい）この場合、デッカー法を用いると、二分法よりも非常に多くの収束計算が必要となる。 
ブレントは、この問題を解決する小さな修正を提案した。割線法で得られた値が次の収束値として採用される前に、満たすべき判定式を追加した。具体的には、以下の2つの不等式である：
さらにブレント法では、もし "f"("b""k")、"f"("a""k")、"f"("b""k"−1) が明確な差があれば、（割線法で使用される）線形補間の代わりに逆2次補間を使用する。これにより収束性がわずかに上がる。結果として、"s"（線形補間または逆2次補間で得られる値）が採用される条件は、以下のように変更される："s" が (3"a""k" + "b""k") / 4 と "b""k"の間に存在するかどうか
使用例.
関数 "f"("x") = ("x" + 3)("x" − 1)2 の解（"f"("x") = 0 となる x の値）を求める場合を例に挙げる。初期値として ["a"0, "b"0] = [−4, 4/3] を考える。"f"("a"0) = −25、"f"("b"0) = 0.48148 である（数値はすべて概数とする）したがって、条件 "f"("a"0)"f"("b"0) < 0 と |"f"("b"0)| ≤ |"f"("a"0)| を満たしている。
"（訂正：9回目の計算 : f(s) = -1.4E-07、10回目の計算 : f(s) = 6.96E-12）"
アルゴリズムの詳細.
 input "a", "b", and a pointer to a subroutine for "f"
 calculate "f"("a")
 calculate "f"("b")
 if "f"("a") "f"("b") >= 0 then error-exit end if
 if |"f"("a")| < |"f"("b")| then swap ("a","b") end if
 "c" := "a"
 set mflag
 repeat until "f"("b or s") = 0 or |"b" − "a"| is small enough "(convergence)"
 if "f"("a") ≠ "f"("c") and "f"("b") ≠ "f"("c") then
 formula_11 "(inverse quadratic interpolation)"
 else
 formula_12 "(secant rule)"
 end if
 if "(condition 1)" "s" is not between (3"a" + "b")/4 and "b"
 or "(condition 2)" (mflag is set and |"s"−"b"| ≥ |"b"−"c"| / 2)
 or "(condition 3)" (mflag is cleared and |"s"−"b"| ≥ |"c"−"d"| / 2)
 or "(condition 4)" (mflag is set and |"b"−"c"| < |formula_3|)
 or "(condition 5)" (mflag is cleared and |"c"−"d"| < |formula_3|)
 then
 formula_15 "(bisection method)"
 set mflag
 else
 clear mflag
 end if
 calculate "f"("s")
 "d" := "c" "(d is assigned for the first time here; it won't be used above on the first iteration because mflag is set)
 "c" := "b"
 if "f"("a") "f"("s") < 0 then "b" := "s" else "a" := "s" end if
 if |"f"("a")| < |"f"("b")| then swap ("a","b") end if
 end repeat
 output "b" " or s (return the root)"
アルゴリズムの実装.
ブレントは1973年にALGOL 60による記述でこのアルゴリズムを公開した。Netlibにはわずかな修正を行ったFortran版が公開されている。MATLAB関数 fzero にもブレント法が組み込まれている。PARI/GPのsolveについても同様である。その他の形で実装されたもの（C++、C言語、Fortran）は、書籍 Numerical Recipes (ISBN 4874085601) で参照できる。Apache Commons Math には、Java実装版が含まれている。GNU Scientific Library では gsl_root_fsolver_brent にて実装されている。