根探索アルゴリズム

数値解析において、根探索アルゴリズムとは、連続関数の零点（「根」とも呼ばれる）を見つけるためのアルゴリズムである。関数fの零点とは、 f ( x ) = 0となる数xのことである。一般に、関数の零点は正確に計算することも閉じた形で表現することもできないため、根探索アルゴリズムは零点の近似値を提供する。実数から実数への関数、または複素数から複素数への関数の場合、これらは誤差範囲のない浮動小数点数として、または誤差範囲付きの浮動小数点値として表現される。後者の誤差範囲付き近似値は、実根の場合は小さな分離区間、複素根の場合はディスクに相当する。^{[ 1 ]}

方程式f ( x ) = g ( x )を解くことは、関数h ( x ) = f ( x ) – g ( x )の根を求めることと同じです。したがって、根を求めるアルゴリズムは、連続関数の任意の方程式を解くために使用できます。ただし、ほとんどの根を求めるアルゴリズムは、関数のすべての根を見つけることを保証するものではなく、そのようなアルゴリズムが根を一つも見つけなかったとしても、必ずしも根が存在しないことを意味するわけではありません。

数値解法の大半は反復法であり、理想的には極限値として根に収束する数列を生成します。これらの方法では、根の初期推定値として1つ以上の値が必要となり、アルゴリズムの各反復によって根への近似値が徐々に精度を高めていきます。反復はどこかの時点で停止する必要があるため、これらの方法は根への近似値を生成するのであって、厳密解を生成するわけではありません。多くの方法では、先行する値に対して補助関数を評価することによって後続の値を計算します。したがって、極限値は補助関数の不動点となり、この補助関数は元の方程式の根を不動点とし、かつこれらの不動点に急速に収束するように選択されます。

一般的な根探索アルゴリズムの挙動は数値解析で研究されています。しかし、特に多項式の場合、根探索アルゴリズムの研究はコンピュータ代数に属します。なぜなら、多項式の代数的性質は最も効率的なアルゴリズムにとって基本となるからです。アルゴリズムの効率と適用性は、与えられた関数の特性に大きく依存する場合があります。例えば、多くのアルゴリズムは入力関数の導関数を使用しますが、他のアルゴリズムはすべての連続関数で動作します。一般に、数値アルゴリズムは関数のすべての根を見つけることを保証するものではないため、根が見つからなかったからといって根が存在しないとは証明されません。しかし、多項式の場合、代数的性質を利用して根が見落とされていないことを保証し、各区間（またはディスク）内の唯一の根への数値的方法（通常はニュートン法）の収束を保証するのに十分小さい別々の区間（または複素根の場合はディスク）に根を配置する特定のアルゴリズムがあります。

括弧法は、根を含むより小さな区間（括弧）を順次決定します。区間が十分に小さくなると、根が見つかったとみなされます。これらの方法は一般的に中間値の定理を使用します。中間値の定理は、連続関数が区間の両端で反対の符号を持つ場合、その関数はその区間内に少なくとも1つの根を持つと主張します。したがって、関数が区間の両端で反対の符号を持つような区間から始める必要があります。ただし、多項式の場合、区間内の根の数を制限または決定するための他の方法として、デカルトの符号法則、ブダンの定理、シュトゥルムの定理などがあります。これらは、多項式の実根を分離するための効率的なアルゴリズムにつながり、すべての実根を保証された精度で見つけることができます。

多くの根探索プロセスは補間法によって行われます。これは、最後に計算された根の近似値を用いて、これらの近似根で同じ値をとる低次の多項式で関数を近似するというものです。次に、その多項式の根を計算し、関数の根の新しい近似値として使用し、このプロセスを繰り返します。

2 つの値を補間すると直線が得られます。これは 1 次多項式です。これが割線法の基礎です。Regula falsiも 2 つの点を一度に補間する補間方法ですが、必ずしも最後に計算された 2 つの点ではない 2 つの点を使用する点で割線法とは異なります。3 つの値で放物線曲線が定義されます。これは二次関数です。これがミュラー法の基礎です。

根を求めるアルゴリズムはすべて反復処理によって進行しますが、反復根探索法では一般的に、補助関数を定義し、それを根の直近の近似値に適用して新たな近似値を得るという、特定の反復処理方法が用いられます。反復処理は、補助関数の固定点が所望の精度に達したとき、すなわち、新たに計算された値が先行する値に十分近づいたときに停止します。

二分法は高次元に一般化されており、これらの方法は一般化二分法と呼ばれています。^{[ 4 ] [ 5 ]}各反復で、領域は 2 つの部分に分割され、アルゴリズムは少数の関数評価に基づいて、これらの 2 つの部分のうちどちらに根が含まれる必要があるかを決定します。 1 次元では、決定の基準は関数の符号が反対であることです。 この方法を多次元に拡張する際の主な課題は、簡単に計算でき、根の存在を保証する基準を見つけることです。

ポアンカレ・ミランダの定理は、長方形内に根が存在するための基準を与えるが、長方形の境界全体で関数を評価する必要があるため、検証は困難である。

もう一つの基準はクロネッカーの定理によって与えられます。^{[ 6 ]}この定理によれば、矩形上の関数fの位相次数がゼロでない場合、矩形にはfの根が少なくとも 1 つ含まれなければなりません。この基準は、ステンガー^{[ 7 ]やカーフォット[ 8 ]}などのいくつかの根探索方法の基礎となっています 。ただし、位相次数を計算するには時間がかかる場合があります。

3つ目の基準は特性多面体に基づいています。この基準は特性二等分法と呼ばれる方法で使用されます。^{[ 4 ]： 19--}位相次数を計算する必要はなく、関数値の符号を計算するだけで済みます。必要な評価回数は少なくとも${\displaystyle \log _{2}(D/\epsilon )}$ここで、Dは特性多面体の最長辺の長さです。^{[ 9 ] : 11、補題4.7} Vrahatis と Iordanidis ^{[ 9 ]}は評価回数の下限を証明しており、上限を証明していないことに注意してください。

4つ目の方法は単体の中間値定理を使用する。^{[ 10 ]}ここでもクエリ数の上限は示されていない。

• Victor Yakovlevich Pan: 「多項式方程式の解法：歴史と最近の進歩」、SIAM Review、第39巻、第2号、187-220ページ（1997年6月）。
• ジョン・マイケル・マクナミー：多項式の根を求めるための数値計算法 - パート I、エルゼビア、ISBN 978-0-444-52729-5 (2007)。
• John Michael McNamee および Victor Yakovlevich Pan: Numerical Methods for Roots of Polynomials - Part II、Elsevier、ISBN 978-0-444-52730-1 (2013)。