ブレント法

ブレント法 (Brent's Method)

ブレント法は、数値解析における求根アルゴリズムの一つで、主に二分法、割線法、逆2次補間を組み合わせた手法です。この手法は、二分法の安定性を保ちながら、他の不安定な手法と同じかそれ以上の速さで解を求めることができる特徴があります。ブレント法は、1969年にセオドラス・デッカーが提案した基本的なアイデアに基づいており、1973年にリチャード・ブレントによって具体的なアルゴリズムが発表されました。

アルゴリズムの概要

この手法は、まず二分法に似たアプローチで、与えられた方程式 f(x) = 0 の解を求めるための初期値を設定します。この初期値は、f(a0) と f(b0) が逆符号を持つような a0 と b0 の2点です。関数 f が区間 [a0, b0] で連続であれば、中間値定理により解が存在することが保証されます。

反復の各ステップでは、以下のステップを経て次の解を求めます：

1. まず、現在の解の推定値 bk や、その前の反復の値 bk−1 を使用します。
2. 割線法と二分法に基づいて新しい点 s と m を計算します。割線法による sが分割点 m と bk の間にある場合は、次の反復値を s に設定します。
3. 次に、新しい反対点 ak+1 を選定します。
4. 最終的に、|f(ak+1)| が |f(bk+1)| よりも小さくなった場合、ak+1 を解の候補として検討します。

このプロセスを繰り返して、解に収束するまで続けます。

デッカー法との違い

デッカー法では、主に二分法と割線法を用いますが、ブレント法はこれに逆2次補間機能を加えることによって収束性を向上させています。特に、滑らかな関数の場合、ブレント法は逆2次補間を用いて収束を早めることが可能です。しかし、関数の挙動が不安定な場合、ブレント法は二分法を使って回数を減らすための独自の判定基準を通じて、スムーズな収束を実現します。

使用例

例えば、関数 f(x) = (x + 3)(x - 1)² の解を求める場合、初期値として [-4, 4/3] を選定します。 f(a0) および f(b0) の値を確認し、収束計算を行います。最初の収束ステップで、割線法に基づいた値 s を計算し、次に逆2次補間も利用します。これを数回繰り返すことで、最終的に解に近づいていきます。

実装

ブレント法は、1973年に ALGOL 60 で広がり、様々なプログラミング言語に実装されています。例えば、Fortran、C++、MATLAB、Java などの多くのライブラリがこのアルゴリズムを含んでいます。これによって、数値解析の分野での解決策として広く支持されています。

参考文献

• - Atkinson, A. (1989). An Introduction to Numerical Analysis (2nd ed.). John Wiley and Sons.
• - Brent, R.P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall.
• - Dekker, T.J. (1969).

もう一度検索