根を求めるアルゴリズム

数値解析において、根探索アルゴリズムは連続関数の零点（「根」とも呼ばれる）を見つけるアルゴリズムである。実数から実数へ、または複素数から複素数への関数fの零点は、 f ( x ) = 0となる数xである。一般に関数の零点は正確に計算できず、閉じた形式で表現することもできないため、根探索アルゴリズムは零点の近似値を提供し、浮動小数点数または小さな分離区間、または複素根の円板（区間または円板の出力は、誤差限界を伴う近似出力に等しい）として表現される。^[1]

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

数値根探索法のほとんどは反復法を使用して、うまくいけばその極限である根に収束する数列を生成します。これらの方法では、開始値として根の 1 つ以上の初期推定値が必要であり、アルゴリズムの各反復により、根へのより正確な近似値が連続的に生成されます。反復はある時点で停止する必要があるため、これらの方法では、正確な解ではなく、根への近似値が生成されます。多くの方法では、先行する値に対して補助関数を評価することによって後続の値を計算します。したがって、極限は補助関数の固定点であり、元の方程式の根を固定点として持ち、これらの固定点に急速に収束するように選択されます。

一般的な求根アルゴリズムの動作は、数値解析で研究されています。しかし、多項式の場合、最も効率的なアルゴリズムには多項式の代数的性質が基本となるため、求根の研究は一般にコンピュータ代数に属します。アルゴリズムの効率は、与えられた関数の特性によって大きく左右されることがあります。たとえば、多くのアルゴリズムは入力関数の導関数を使用しますが、他のアルゴリズムはすべての連続関数で機能します。一般に、数値アルゴリズムは関数のすべての根を見つけることが保証されていないため、根が見つからないことは根が存在しないことを証明することにはなりません。しかし、多項式の場合、代数的性質を使用して根が見落とされていないことを証明し、数値法 (通常はニュートン法)が確実に見つかった唯一の根に収束するのに十分な小ささの別々の区間 (または複素根の場合は円板) に根を配置する特定のアルゴリズムがあります。

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

最も単純な根を求めるアルゴリズムは二分法です。f を連続関数とし、区間[ a , b ]が分かっていて、 f ( a )とf ( b )が反対の符号（括弧）を持つものとします 。 c = ( a + b )/2 を区間の中央（中間点または区間を二分する点）とします。すると、f ( a )とf ( c )、またはf ( c )とf ( b )が反対の符号を持ち、区間のサイズが 2 で割られます。二分法は堅牢ですが、反復ごとに精度が 1ビットしか向上しません。したがって、 ε近似根を求めるために必要な関数評価の回数はです。適切な条件下では、他の方法の方が精度を速く向上させることができます。 ${\displaystyle \log _{2}{\frac {ba}{\varepsilon }}}$

偽位置法はレギュラ偽法とも呼ばれ、二分法に似ていますが、二分探索の区間の中央を使用する代わりに、区間の端点でプロットされた関数値を結ぶ線のx切片を使用します。つまり、

${\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}$

偽位置法はセカント法に似ていますが、最後の 2 つの点を保持する代わりに、ルートの両側に 1 つの点を保持する点が異なります。偽位置法は二分法よりも高速で、セカント法のように発散することはありません。ただし、丸め誤差によりf ( c )の符号が誤っているために、単純な実装では収束に失敗する場合があります。通常、これはルートの近傍で fの変化率が大きい場合に発生します。

ITP法は、二分法と同じ最悪のケースの保証で根を括弧で囲みながら、セカント法のように滑らかな関数の根への超線形収束を保証する唯一の既知の方法です。また、根の位置に関する任意の連続分布の平均で二分法よりも優れていることが保証されている唯一の既知の方法でもあります ( ITP 法#分析 を参照)。これは、括弧間隔と、その中の任意の点が二分法と同じ速さで収束する最小最大間隔の両方を追跡することによってこれを行います。照会された点 c の構築は、補間 (regula falsi と同様)、切り捨て (regula falsi をRegula falsi § regula falsiの改善と同様に調整)、次に最小最大間隔への射影という 3 つの手順に従います。これらのステップを組み合わせることで、滑らかな関数に対する補間ベースの方法と同様の保証を備えた同時最小最大最適方法が生成され、実際には滑らかな関数と滑らかでない関数の両方において二分法と補間ベースの方法の両方よりも優れたパフォーマンスを発揮します。

多くの根を求めるプロセスは補間によって機能します。これは、最後に計算された根の近似値を使用して、これらの近似根で同じ値を取る低次の多項式で関数を近似することです。次に、多項式の根が計算され、関数の根の新しい近似値として使用され、プロセスが繰り返されます。

2 つの値により、関数を 1 次多項式で補間できます (つまり、関数のグラフを直線で近似します)。これがセカント法の基礎です。3 つの値は2 次関数を定義し、関数のグラフを放物線で近似します。これがミュラー法です。

Regula falsiも補間法の一種で、線で補間する場合に必ずしも最後に計算された 2 つの点ではない 2 つの点を使用する点で、セカント法とは異なります。

すべての根探索アルゴリズムは反復によって進行しますが、反復根探索法では一般に、補助関数の定義からなる特定のタイプの反復を使用します。補助関数は、新しい近似値を得るために最後に計算された根の近似値に適用されます。補助関数の固定点(必要な精度まで) に到達すると、つまり新しく計算された値が前の値に十分近くなると、反復は停止します。

ニュートン法は、関数f が連続導関数を持つと仮定します。ニュートン法は、根から遠く離れたところから始めると収束しない場合があります。ただし、収束する場合は、二分法よりも速く、通常は 2 次式になります。ニュートン法は、高次元の問題に容易に一般化できるため、重要です。ニュートン法に似た高次収束法は、ハウスホルダー法です。ニュートン法の次に多いのは、収束が 3 次で あるハレー法です。

ニュートン法の導関数を有限差分に置き換えると、セカント法が得られます。この方法では、導関数の計算（および存在）は必要ありませんが、収束が遅くなります（次数は約 1.6（黄金比）です）。セカント法を高次元に一般化したものが、ブロイデン法です。

多項式近似を使用して、セカント法で使用される有限差分の二次部分を削除し、導関数をより適切に近似すると、ステフェンセン法が得られます。この方法は二次収束し、その動作（良い点と悪い点の両方）はニュートン法と本質的に同じですが、導関数を必要としません。

固定小数点反復法を使用して関数の根を求めることができます。根を求めるために をゼロに設定した関数 ( ) を考えると、方程式を で書き直すと は になります(各関数には多くの関数があることが多いことに注意してください)。次に、方程式の各辺を と再ラベル付けして、反復を実行できるようにします。次に、 の値を選択し、関数の根に収束するまで反復を実行します。反復が収束する場合は、根に収束します。反復が収束するのは の場合のみです。 ${\displaystyle f(x)}$${\displaystyle f(x)=0}$${\displaystyle x}$${\displaystyle f(x)=0}$${\displaystyle x=g(x)}$${\displaystyle g(x)}$${\displaystyle f(x)=0}$${\displaystyle x_{n+1}=g(x_{n})}$${\displaystyle x_{1}}$${\displaystyle |g'(root)|<1}$

を に変換する例として、関数 が与えられた場合、それを次の式のいずれかとして書き直します。 ${\displaystyle f(x)=0}$${\displaystyle x=g(x)}$${\displaystyle f(x)=x^{2}+x-1}$

${\displaystyle x_{n+1}=(1/x_{n})-1}$、

${\displaystyle x_{n+1}=1/(x_{n}+1)}$、

${\displaystyle x_{n+1}=1-x_{n}^{2}}$、

${\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}$、 または

${\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}$。

補間法における複素数値の出現は、 fの逆数を補間して逆二次補間法にすることで回避できます。この場合も、収束は漸近的に正割法よりも速くなりますが、反復が根に近くない場合、逆二次補間は動作が悪くなることがよくあります。

ブレント法は、二分法、正割法、逆二次補間法を組み合わせたものです。ブレント法は、反復ごとに、これら 3 つの方法のうちどの方法が最も効果的かを判断し、その方法に従って手順を進めます。この方法は堅牢で高速であるため、非常に人気があります。

リダーズ法は、区間の中間点における関数の値を使用して根への指数補間を実行するハイブリッド法です。これにより、二分法の最大 2 倍の反復回数で収束が保証され、高速収束が実現します。

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

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

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

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

4番目の方法は、単体の中間値定理を使用する。^[8]この場合も、クエリの数に上限は与えられていない。

• JM McNamee:「多項式の根の数値計算法 - パート I」、Elsevier (2007)。
• JM McNamee および Victor Pan:「多項式の根の数値計算法 - パート II」、Elsevier (2013)。