ブレント法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/26 19:20 UTC 版)
ブレント法（英: Brent's method）は、二分法、割線法、逆2次補間を組み合わせた、複雑ではあるが広く用いられている、数値解析における求根アルゴリズムの1つである。二分法の安定さを有し、かつ安定でない他の手法と同程度に高速に解が求められる場合もある。可能な限り、より収束の早い割線法や逆2次補間を用い、必要に応じてより安定な二分法に切り替えて解を求めるという手法である。ブレント法は、1969年のセオドラス・デッカーによる初期のアルゴリズムを元にして、1973年にリチャード・ブレントにより考案されたものである[1] 。
デッカー法
二分法と割線法を組み合わせるという考えは、デッカーによるものである。
ここでは、方程式 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つは割線法により以下の式で求められる。
関数 f(x) = (x + 3)(x − 1)2 のグラフ - 最初の収束計算では、以下の2点 (b−1, f(b−1)) = (a0, f(a0)) = (−4, −25) と (b0, f(b0)) = (1.33333, 0.48148) の間で線形補間を行い、s = 1.23256 を得る。(3a0 + b0) / 4 と b0 の間にあるため、この値は採用される。さらに f(1.23256) = 0.22891 であるため、a1 = a0、b1 = s = 1.23256 となる。
- 2回目の収束計算：(a1, f(a1)) = (−4, −25) と (b0, f(b0)) = (1.33333, 0.48148) と (b1 を用いて逆2次補間を行い、f(b1)) = (1.23256, 0.22891) を得る。これにより、(3a1 + b1) / 4 と b1 の間にある 1.14205 が求められる。不等式 1.14205 − b1 ≤ b0 − b−1 / 2 を満たすため、この値を採用する。さらに f(1.14205) = 0.083582 であるため、a2 = a1、b2 = 1.14205 となる。
- 3回目の収束計算：(a2, f(a2)) = (−4, −25) と (b1, f(b1)) = (1.23256, 0.22891) と (b2, f(b2)) = (1.14205, 0.083582) で逆2次補間を行う。収束値として (3a2 + b2) / 4 と b2 の間にある 1.09032 が得られる。しかし、ここでブレントによる追加条件が加わる。不等式 1.09032 − b2 ≤ b1 − b0 / 2 を満たさないため、この値は採用されない。代わりに、区間 [a2, b2] の中間点 m = −1.42897 を計算しこれを採用する。f(m) = 9.26891 であり、a3 = a2、b3 = −1.42897 となる。
- 4回目の収束計算：(a3, f(a3)) = (−4, −25) と (b2, f(b2)) = (1.14205, 0.083582) と (b3, f(b3)) = (−1.42897, 9.26891) で逆2次補間を行う。収束値として 1.15448 が得られるが、この値は区間 (3a3 + b3) / 4 と b3) には存在しない。したがって、中間点 m = −2.71449 に置き換わる。f(m) = 3.93934 であり、したがって a4 = a3、b4 = −2.71449 となる。
- 5回目の収束計算：逆2次補間により、区間内にある −3.45500 を得る。しかし、1つ前の計算に二分法を用いたため、不等式 −3.45500 − b4 ≤ b4 − b3 / 2 を満たす必要がある。この不等式は偽であるため、中間点 m = −3.35724 を採用する。f(m) = −6.78239 であるので、m は新たな反対点 (a5 = −3.35724) となり、収束値は (b5 = b4) のままである。
- 6回目の収束計算：b5 = b4 であるため逆2次補間を使用できない。したがって、(a5, f(a5)) = (−3.35724, −6.78239) と (b5, f(b5)) = (−2.71449, 3.93934) の2点で線形補間を行う。s = −2.95064 が得られ、この値はすべての条件を満たしている。しかし1つ前のステップから収束値が変わっていないので、この結果は採用せず、再度、二分法を用いる。s = -3.03587、f(s) = -0.58418 となる。
- 7回目の収束計算：再度、逆2次補間を行う。s = −2.99436 であり、すべての条件を満たしている。f(s) = 0.089961 であるので、a7 = b6、 b7 = −3.00219 となる（条件 |f(b7)| ≤ |f(a7)| を満たすよう、a7 と b7 の値が交換される。）
- 8回目の収束計算：a7 = b6 であるため逆2次補間は使用できない。線形補間により s = −2.9999、f(s) = 0.0016 を得る。条件は満たしている。
- 以降の収束計算で、b9 = −3 + 6·10−8 と b10 = −3 − 3·10−15 となり、得られる解が x = −3 に急速に近づく。
（訂正：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
ブレント法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/01 02:18 UTC 版)
二分法、割線法、逆2次補間を組み合わせた手法で、各ステップでどの手法が最も適しているかを判別し、適した手法を選択する。安定かつ高速で、広く用いられている。
※この「ブレント法」の解説は、「求根アルゴリズム」の解説の一部です。
「ブレント法」を含む「求根アルゴリズム」の記事については、「求根アルゴリズム」の概要を参照ください。
- ブレント法のページへのリンク
