多項式根探索アルゴリズム

多項式の根を求めることは、歴史を通じて多くの研究の対象となってきた長年の問題です。その証拠として、19 世紀まで代数学は基本的に多項式方程式の理論を意味していました。

線形多項式(1 次)の根を求めるのは簡単で、1 回の割り算のみが必要です。つまり、一般方程式には解が存在します。 2 次多項式(2 次) の場合、2 次式によって解が生成されますが、数値評価では数値安定性を確保するために注意が必要な場合があります。 3 次と 4 次の場合、根号に関する閉じた形式の解がありますが、これは一般に数値評価には不向きです。複雑すぎるうえに、複数のn乗根の計算が必要であり、その計算は多項式の根を直接計算するよりも簡単ではありません (たとえば、3 次多項式の実根の表現には、実数でない3 乗根が含まれる場合があります)。 5 次以上の多項式の場合、アーベル・ルフィニの定理により、一般に根の根号表現は存在しないことが主張されています。 ${\displaystyle ax+b=0}$${\displaystyle x=-b/a.}$

したがって、非常に低い次数を除いて、多項式の根を求めることは、根の近似値を求めることです。代数の基本定理により、 n 次多項式には、重複度を数えるとちょうどn 個の実根または複素根があります。

したがって、多項式の根を求める問題は、3 つの異なる部分問題に分割できます。

• 一つのルートを見つける
• すべてのルートを見つける
• 複素平面の特定の領域内の根、通常は実根または指定された区間内の実根を見つけます (たとえば、根が物理量を表す場合、実数の正の根のみが対象となります)。

1 つの根を見つけるには、ニュートン法やその他の一般的な反復法が一般的にうまく機能します。

すべての根を見つけるための最も信頼性の高い方法は、おそらく、MATLAB の標準方法^[1]として実装されている、多項式に対応する伴行列の固有値を計算するフランシスQRアルゴリズムです。

すべての根を見つける最も古い方法は、単一の根を見つけることから始めることです。根rが見つかったら、二項式x – rを除算することで多項式から根を取り除くことができます。結果として得られる多項式には残りの根が含まれており、このプロセスを繰り返すことで見つけることができます。ただし、低次数を除いて、数値不安定性のため、この方法はうまく機能しません。ウィルキンソンの多項式は、1 つの係数をわずかに変更すると、根の値だけでなく、根の性質 (実数または複素数) も大幅に変化する可能性があることを示しています。また、近似値が良くても、近似根で多項式を評価すると、ゼロに非常に近い結果になることがあります。例えば、20次（ウィルキンソン多項式の次数）の多項式の根が10に近い場合、根における多項式の導関数は次数になる可能性があり、これは根の値の誤差が近似根における多項式の値が次数になる可能性があることを意味します。${\displaystyle 10^{20};}$${\displaystyle 10^{-10}}$${\displaystyle 10^{10}.}$

これらの問題を回避するために、すべての根を同時に、任意の精度で計算する方法が考案されました。現在、最も効率的な方法はAberth 法です。無料の実装はMPSolveという名前で利用できます。これはリファレンス実装であり、1,000 を超える次数、1,000 を超える有効小数桁の多項式の根を日常的に見つけることができます。

すべての根を計算する方法は実根を計算するのに使用できます。しかし、虚数部の小さい根が実根であるかどうかを判断するのは難しい場合があります。さらに、実根の数は平均して次数の対数に比例するため、^[2]実根に関心がある場合に非実根を計算するのはコンピュータリソースの無駄です。

実根の数と区間内の根の数を計算する最も古い方法は、シュトゥルムの定理から得られますが、デカルトの符号の規則とその拡張であるブダンの定理とヴィンセントの定理に基づく方法の方が一般的には効率的です。根を求める場合、根を検索する区間のサイズを縮小して、0 個または 1 個の根を含む区間が得られるまで進めます。次に、1 個の根を含む区間をさらに縮小して、ニュートン法が孤立根に 2 次収束するようにします。主要なコンピュータ代数システム( Maple、Mathematica、SageMath、PARI/GP ) には、多項式の実根のデフォルト アルゴリズムとして、この方法のバリエーションがそれぞれあります。

このクラスの方法は、多項式の根を求める問題を多項式の伴う行列の固有値を求める問題に変換することに基づいており、^[1]原理的には、任意の固有値アルゴリズムを使用して多項式の根を求めることができます。ただし、効率上の理由から、行列の構造を使用する方法、つまり行列を使用しない形式で実装できる方法が好まれます。これらの方法には、べき乗法があり、これを伴う行列の転置に適用すると、最大係数の根を求める古典的なベルヌーイ法が実現します。最初に最小の根を求めるシフトを伴う逆べき乗法は、ジェンキンス-トラウブ法の複素数 ( cpoly )バリアントを駆動し、数値的安定性をもたらします。さらに、クラスター化された根が存在する場合でも、次数(は黄金比)で高速に収束します。この高速収束には、ステップごとに 3 つの多項式評価のコストがかかり、残差はO (| f ( x )| ^{2+3 φ} )になります。これは、ニュートン法の 3 ステップよりも遅い収束です。 ${\displaystyle 1+\varphi \approx 2.6}$${\displaystyle \varphi }$

根を計算する最も広く使われている方法はニュートン法であり、これは以下の計算の繰り返しから成ります。

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},}$

適切に選択された値から開始することで${\displaystyle x_{0}.}$

fが多項式の場合、各反復で多項式とその導関数を計算するための 前処理を伴うホーナー法または評価を使用すると、計算が高速になります。

収束は一般に2 次ですが、収束が非常に遅い場合や、まったく収束しない場合もあります。特に、多項式に実根がなく、 が実数の場合、ニュートン法は収束できません。ただし、多項式に実根があり、その実根がその導関数の大きい方の実根よりも大きい場合、 がこの大きい方の根よりも大きい場合、ニュートン法はこの最大の根に 2 次収束します (根の上限を計算する簡単な方法があります。多項式の根の特性を参照してください)。これが、根を計算する ホーナー法の出発点です。${\displaystyle x_{0}}$${\displaystyle x_{0}}$

1 つの根rが見つかったら、ユークリッド除算を使用して多項式から因数x – r を取り除くことができます。結果として得られる商の根を計算し、そのプロセスを繰り返すと、原理的にはすべての根を計算することができます。ただし、この反復方式は数値的に不安定です。連続する因数分解中に近似誤差が蓄積されるため、最後の根は元の多項式の因数から大きく外れた多項式で決定されます。この誤差を減らすには、見つかった根ごとに、元の多項式とこの近似根を開始値として、ニュートン法を再開します。

ただし、これによってすべての根が見つかるという保証はありません。実際、多項式の根をその係数から見つける問題は、非常に条件が悪い場合があります。これは、ウィルキンソンの多項式によって示されます 。この 20 次多項式の根は、最初の 20 個の正の整数です。係数の 1 つ (-210 に等しい) の 32 ビット表現の最後のビットを変更すると、実根が 10 個、虚部が 0.6 より大きい複素根が 10 個のみの多項式が生成されます。

ニュートン法と密接に関連しているのが、ハレー法とラゲール法です。どちらも、多項式とその 2 つの最初の導関数を、3次収束する反復プロセスに使用します。これらの方法の 2 つの連続するステップを 1 つのテストに組み合わせると、収束率は9 になりますが、多項式評価が 6 回必要になります (ホーナーの定理を使用)。一方、ニュートン法の 3 つのステップを組み合わせると、収束率は 8 になりますが、多項式評価の回数は同じになります。これにより、これらの方法に若干の利点が生まれます (ラゲール法の場合は、各ステップで平方根を計算する必要があるため、あまり明確ではありません)。

これらの方法を実係数と実開始点を持つ多項式に適用する場合、ニュートン法とハレー法は実数直線の内側に留まります。複素根を求めるには複素開始点を選択する必要があります。対照的に、評価に平方根を含むラゲール法は、自動的に実軸から離れます。

与えられた多項式に実係数しかない場合、複素数を使った計算を避けたい場合があります。そのためには、共役複素根のペアの二次因数を見つける必要があります。このタスクに多次元ニュートン法を適用すると、ベアストウ法が得られます。

Jenkins-Traub アルゴリズムの実際の変種は、この方法の改良版です。

シンプルなデュラン・ケルナー法と、少し複雑なアベルト法は、単純な複素数演算のみを使用してすべての根を同時に求めます。高速フーリエ変換に似た、多点評価と補間の高速アルゴリズムは、多項式の大きな次数に対して高速化に役立ちます。非対称だが均等に分散された初期点のセットを選択することをお勧めします。無料ソフトウェア MPSolveでのこの方法の実装は、その効率性と精度の参考になります。

このスタイルの別の方法は、ダンデリン・グレーフェ法（ロバチェフスキー法とも呼ばれる）であり、多項式変換を使用して根を繰り返し暗黙的に二乗します。これにより、根の分散が大幅に拡大されます。ビエトの公式を適用すると、根の係数の近似値を簡単に得ることができ、さらに努力すれば根自体の近似値も得られます。

実数直線の線分または複素平面の領域に根が含まれていないかどうかを調べる高速テストがいくつかあります。根の係数を境界設定し、これらの境界によって示される初期領域を再帰的に細分化することで、根が含まれている可能性のある小さな領域を分離し、他の方法を適用してそれらの領域を正確に見つけることができます。

これらの方法はすべて、多項式のシフトおよびスケールされたバージョンの係数を見つけることを伴います。大きな次数の場合、FFTベースの高速化方法が実行可能になります。

実数ルートについては、次のセクションを参照してください。

Lehmer-Schur アルゴリズムは、円に対してSchur-Cohn テストを使用します。その変形であるWilf のグローバル二分アルゴリズムは、複素平面上の長方形領域に対して巻き数計算を使用します。

分割円法は、 FFT ベースの多項式変換を使用して、根のクラスターに対応する高次因数を見つけます。因数分解の精度は、ニュートン型反復を使用して最大化されます。この方法は、高次多項式の根を任意の精度で見つけるのに役立ち、この設定ではほぼ最適な複雑さを備えています。^{[引用が必要]}

実係数を持つ多項式の実根を求める問題は、19 世紀初頭から多くの注目を集めており、現在でも活発に研究されている分野です。ほとんどの根を求めるアルゴリズムは、いくつかの実根を求めることができますが、すべての根を見つけたことを証明することはできません。Aberth法などのすべての複素根を求める方法は、実根を提供できます。ただし、多項式の数値的不安定性 (ウィルキンソンの多項式を参照) のため、どの根が実根であるかを判断するために任意精度の演算が必要になる場合があります。さらに、実根がごくわずかである場合でも、すべての複素根を計算します。

したがって、実根を計算する標準的な方法は、まず分離区間と呼ばれる互いに素な区間を計算し、各区間に正確に 1 つの実根が含まれ、すべての実根が一緒に含まれるようにすることです。この計算は実根分離と呼ばれます。分離区間があれば、ニュートン法などの高速な数値法を使用して結果の精度を向上させることができます。

実根分離の最も古い完全なアルゴリズムは、シュトゥルムの定理から得られます。しかし、デカルトの符号規則やヴィンセントの定理に基づく方法に比べると、はるかに効率が悪いようです。これらの方法は、連分数を使用する方法と二分法を使用する方法の 2 つの主なクラスに分かれます。どちらの方法も、21 世紀初頭から劇的に改善されています。これらの改善により、すべての根を計算するための最良のアルゴリズムと同等の計算複雑度に達します(すべての根が実数の場合も含む)。

これらのアルゴリズムは実装されており、Mathematica (連分数法) とMaple (二分法) で利用できます。どちらの実装でも、1,000 次を超える多項式の実根を日常的に見つけることができます。

多重根は非常に敏感で、一般的に数値計算では条件が悪く不正確であることが知られています。MATLABパッケージとして実装されたZhonggang Zeng（2004）による方法は、係数が不正確であっても多項式の多重根とそれに対応する重複度を正確に計算します。^{[3] [4] [5]}

この方法は2つのステップにまとめられる。与えられた多項式をとする。最初のステップでは、数値最大公約数アルゴリズムによる平方分解を適用して多重度構造を決定する。 ^[5]これにより、次のように 書くことができる。 ${\displaystyle p}$${\displaystyle p}$

${\displaystyle (*)\;\;\;\;p(x)=a(x-z_{1})^{m_{1}}\cdots (x-z_{k})^{m_{k}},}$

ここで、 は個別の根の重複度です。この方程式は、 の係数と一致する変数を方程式に持つ過剰決定システムです(先頭の係数は変数ではありません)。ほとんどの場合、最小二乗解は悪条件ではなくなります。2 番目のステップでは、ガウス ニュートン アルゴリズムを適用して、個別の根の過剰決定システムを解きます。 ${\displaystyle m_{1},\ldots ,m_{k}}$${\displaystyle k}$${\displaystyle z_{1},\ldots ,z_{k}}$${\displaystyle n}$${\displaystyle k<n}$${\displaystyle a}$

多重根の感度は、ウィリアム・カーハン（1972）によって発見された多重根の幾何学的性質により正規化することができ、過剰決定システムモデルは多重度を維持します。 ${\displaystyle (*)}$${\displaystyle m_{1},\ldots ,m_{k}}$

係数が整数または有理数として正確に与えられている多項式の場合、それらを単純な根のみを持ち、係数も正確に与えられている因数に因数分解する効率的な方法があります。 この方法は、平方自由因数分解と呼ばれ、多項式の多重根が多項式とその導関数の最大公約数の根であることに基づいています。

多項式pの平方なし因数分解は、それぞれが1 または多重根を持たない多項式であり、2 つの異なる項に共通根がない 因数分解です。${\displaystyle p=p_{1}p_{2}^{2}\cdots p_{k}^{k}}$${\displaystyle p_{i}}$${\displaystyle p_{i}}$

この因数分解を計算する効率的な方法はYun のアルゴリズムです。