「囲い込み法」と「非区間法」の違いは何ですか？

囲い込み法 (bracketing) は符号が異なる 2 点 [a, b] (f(a)·f(b) < 0) を要求し、各反復で区間幅を縮小して必ず根に収束します。連続関数なら収束が保証される反面、速度は線形〜超線形が中心。非区間法 (open) は 1〜2 点の初期値のみを必要とし二次以上の収束が出せますが、発散することがあります。sangi の Brent/TOMS 748/ITP は囲い込み法、Newton/secant/Halley は非区間法に分類されます。

Brent 法とは何ですか？

Brent 法 (1973) は逆二次補間 (IQI) または割線法による速い候補と二分法のフォールバックを組み合わせたハイブリッドです。候補が区間内かつ十分縮むときは速い経路を、そうでなければ二分法に落とすことで、線形以上の収束を保ちつつ二分法の堅牢性を維持します。実用上は囲い込み法の事実上の標準で、sangi でも汎用の bracket 経路として使われます。

ITP 法は何が新しいのですか？

ITP 法 (Oliveira-Takahashi, 2020) は Interpolation-Truncation-Projection の 3 段階で、Brent と同等の超線形収束を保ちつつ、最悪ケースの反復回数が二分法を超えないことを厳密に保証します。Brent では病的入力 (Dekker のカウンタ例) で二分法より遅くなる可能性が知られており、ITP はその欠点を理論的に閉じた、近年で最良とされる選択肢です。

sangi の bracket 求根はどう選べばいいですか？

汎用なら brent_method、最悪反復回数の保証が欲しければ ITP 法 (計画中)、外れ値・病的曲線で安定が欲しければ toms748 を選びます。二分法は教育用または「最低限の保証だけ欲しい」場合のフォールバック。偽位置法・Illinois・Anderson-Björck は古典的選択肢で、片端が動かない場合の修正手段を含みますが、Brent/TOMS 748 にほぼ吸収されます。

1D 求根: 囲い込み法 (Bracketing)

Q: Brent 法とは何ですか？

Brent 法 (1973) は逆二次補間 (IQI) または割線法による速い候補と二分法のフォールバックを組み合わせたハイブリッドです。候補が区間内かつ十分縮むときは速い経路を、そうでなければ二分法に落とすことで、線形以上の収束を保ちつつ二分法の堅牢性を維持します。実用上は囲い込み法の事実上の標準で、sangi でも汎用の bracket 経路として使われます。

Q: ITP 法は何が新しいのですか？

ITP 法 (Oliveira-Takahashi, 2020) は Interpolation-Truncation-Projection の 3 段階で、Brent と同等の超線形収束を保ちつつ、最悪ケースの反復回数が二分法を超えないことを厳密に保証します。Brent では病的入力 (Dekker のカウンタ例) で二分法より遅くなる可能性が知られており、ITP はその欠点を理論的に閉じた、近年で最良とされる選択肢です。

Q: sangi の bracket 求根はどう選べばいいですか？

汎用なら brent_method、最悪反復回数の保証が欲しければ ITP 法 (計画中)、外れ値・病的曲線で安定が欲しければ toms748 を選びます。二分法は教育用または「最低限の保証だけ欲しい」場合のフォールバック。偽位置法・Illinois・Anderson-Björck は古典的選択肢で、片端が動かない場合の修正手段を含みますが、Brent/TOMS 748 にほぼ吸収されます。

概要

1 次元の方程式 $f(x) = 0$ を、符号の異なる 2 点 $[a, b]$ ($f(a) \cdot f(b) < 0$) を入力として確実に解く一群のアルゴリズム。中間値の定理により連続関数なら必ず根が存在し、各反復で区間幅を縮めるので収束は数学的に保証される。

二分法 (bisection)

区間の中点を取り、符号が変わる側に縮める。最も単純で最も確実。

while (b - a > tol) {
    T c = (a + b) / 2;
    if (sign(f(c)) == sign(f(a))) a = c;
    else                          b = c;
}

各反復で区間幅が半分になるので、目標精度 $\epsilon$ までの反復回数は厳密に $\lceil \log_2((b - a)/\epsilon) \rceil$。

収束次数: 線形 (収束比 $1/2$)

長所: 連続関数なら絶対に収束、最悪ケース反復数が厳密に予測可能

短所: 関数値を一切利用しないため遅い

偽位置法 (Regula Falsi)

中点ではなく、$f$ の値で重み付けした内分点を使う:

$$c = a - f(a) \cdot \frac{b - a}{f(b) - f(a)} = \frac{a f(b) - b f(a)}{f(b) - f(a)}$$

これは $(a, f(a))$ と $(b, f(b))$ を結ぶ直線の零点であり、割線法と同じ式に見えるが、二分法と同じく常に符号を保つ側に縮めることで区間を維持する点が異なる。

収束次数: 一般に超線形だが、$f$ が片側で強く凸/凹だと一方の端点が動かなくなり線形に劣化する。

Illinois 法と Anderson-Björck

偽位置法で「片端が動かない」状態を検知したら、動かない側の $f$ 値に縮小係数を掛けることで強制的に動かす変種。

Illinois 法: 同じ端点が連続採用されたら、その端点の $f$ を $1/2$ に縮める。
Anderson-Björck: 縮小係数を $f(c)/(f(c) + f_{\text{stuck}})$ から動的に決定。Illinois より頑健。

これらは偽位置法の超線形性を回復するための古典的修正で、Brent 法以前は標準的だった。現代では Brent / TOMS 748 にほぼ吸収されているが、外部依存を増やしたくない場合の選択肢として残る。

Ridders 法

Ridders (1979) は区間内の補助点 $m = (a+b)/2$ で $f$ を評価し、指数補正により実効的な「線形化」を行う:

$$c = m + (m - a) \cdot \frac{\mathrm{sign}(f(a)) \cdot f(m)}{\sqrt{f(m)^2 - f(a) f(b)}}$$

$c$ は必ず $[a, b]$ 内に入り、符号で縮める側を決める。反復ごとに 2 回の関数評価を行う代わりに、平均的に二分法より大幅に速い。

収束次数: $\sqrt{2} \approx 1.41$ (反復あたり); ただし関数評価 2 回なので 1 評価あたりでは $2^{1/2} \approx 1.19$。

Brent 法

Brent (1973) は逆二次補間 (IQI, inverse quadratic interpolation) または割線法による速い候補と、二分法のフォールバックを組み合わせる:

過去 3 点 $(a, f(a))$, $(b, f(b))$, $(c, f(c))$ から逆二次補間で次の候補 $s$ を計算
$s$ が区間内かつ「縮みが十分」「前回も縮んだ」等の条件を満たすなら採用
条件を満たさなければ二分法のステップを採用

これにより超線形収束と二分法の堅牢性を両立する。 Brent のオリジナル論文は 4 つの組合せ条件 (Brent's conditions) で安全な切替を厳密に定義している。

収束次数: 超線形 (実用上 1.6〜1.8 程度)

長所: 関数導関数なしで Newton 並みの速度

短所: Dekker の病的入力で二分法より遅くなる場合がある

sangi の brent_method は汎用の bracket 求根として推奨される経路。

TOMS 748 (Alefeld-Potra-Shi)

Alefeld, Potra, Shi (1995) による Brent の改良版で、ACM TOMS Algorithm 748 として配布されている。 Brent の逆二次補間の代わりに三次有理補間と双立方補間を使い、最悪ケースの反復数も改善する。

収束次数: 漸近的に約 $1.84$ (関数評価 1 回あたり)

外れ値や病的曲線で Brent より頑健。sangi の toms748 はこれを実装する。

ITP 法 (Interpolation-Truncation-Projection)

Oliveira-Takahashi (2020) による近年の囲い込み求根法。3 段階で次の点を決める:

Interpolation: 割線法 (Regula Falsi) で候補 $x_f$ を計算
Truncation: $x_f$ から中点方向に切り詰めて $x_t$
Projection: 二分法の収縮量を超えない範囲に投影して $x_{\text{ITP}}$

パラメータ $\kappa_1, \kappa_2, n_0$ を $\kappa_1 \in [0, \infty), \kappa_2 \in [1, (3+\sqrt 5)/2), n_0 \in \mathbb{N}$ から選び、 Brent と同等の超線形収束を保ちつつ、最悪ケース反復数が二分法以下であることが定理として保証される。これは Brent / TOMS 748 が原理上保証できない性質。

収束次数: 超線形 (Brent と同等)、最悪ケース反復数 $\leq$ 二分法

sangi では将来の bracket 経路として ITP の追加を検討中。現状の標準は Brent、最悪ケース保証が必須なら二分法を使う。

収束次数と最悪ケースの比較

アルゴリズム	関数評価/反復	収束次数	最悪反復数	備考
二分法	1	線形 (1/2)	$\log_2 \frac{b-a}{\epsilon}$	絶対安全だが遅い
偽位置法	1	超線形 (悪条件で線形)	無制限になり得る	素朴版は片端固定問題
Illinois	1	超線形	有界	偽位置の修正
Anderson-Björck	1	超線形	有界	Illinois の改良
Ridders	2	$\sqrt{2}$	有界	指数補正
Brent	1	1.6〜1.8	$\approx$ 二分法の数倍	事実上の標準
TOMS 748	1	$\approx 1.84$	Brent より良い	三次有理補間
ITP	1	超線形	$\leq$ 二分法	最悪保証付き

sangi の選択基準

デフォルトは Brent

関数が滑らかで「特に病的でない」と分かっているなら brent_method が汎用最良。 Newton 法に必要な導関数を提供しなくてよく、超線形収束で実用上 1.6〜1.8 の収束率を出す。

困難な入力には TOMS 748

関数が外れ値・段差・近接根を持つ場合は toms748 のほうが堅牢。三次有理補間で Brent より広い関数クラスに対応する。

最悪ケースの保証が必要なら二分法 (または将来の ITP)

確定的な最大反復数で打ち切りたい (組込み・リアルタイム制御) なら二分法を使う。計算量は予測可能だが速度は最遅。 ITP 法は速度と保証を両立するが、sangi ではまだ未提供。

Brent 系を使わない理由がある場合

外部依存を最小化したい教育用途や、関数評価が極端に高価な場合 (1 評価 = 数秒) は Ridders 法が選択肢になる。 Ridders は反復あたり 2 評価だが、平均的な反復数が少ない。

参考文献

Brent, R. P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall.
Alefeld, G. E., Potra, F. A., and Shi, Y. (1995). "Algorithm 748: enclosing zeros of continuous functions". ACM Transactions on Mathematical Software, 21(3), 327–344.
Ridders, C. (1979). "A new algorithm for computing a single root of a real continuous function". IEEE Transactions on Circuits and Systems, 26(11), 979–980.
Oliveira, I. F. D. and Takahashi, R. H. C. (2020). "An enhancement of the bisection method average performance preserving minmax optimality". ACM Transactions on Mathematical Software, 47(1), 1–24.