多項式方程式のシステム

多項式方程式系（単に多項式系と呼ばれることもある）は、 f ₁ = 0, ..., f _h = 0 という連立方程式 の集合であり、 f _{i は}、ある体k上の複数の変数（たとえばx ₁、 ..., x _n ）の多項式です。

多項式系の解は、 k の何らかの代数的に閉じた体拡大 K に属し、すべての方程式が成り立つような x i の値の集合です。kが有理数体である場合、各_解は複素数の部分体と同型であるkの体拡大に属するため、 Kは一般に複素数体であると想定されます。

この記事は、すべての解を見つける、またはそれらを記述する、つまり解決するための方法について説明しています。これらの方法はコンピューターで実装できるように設計されているため、計算（等式テストを含む）が簡単で効率的なフィールドk、つまり有理数フィールドと有限フィールドに重点が置かれています。

特定の集合に属する解を探すことは、一般にはるかに難しい問題であり、与えられた有限体における解の場合を除いて、この記事の範囲外です。すべての成分が整数または有理数である解の場合は、ディオファントス方程式を参照してください。

多項式方程式の簡単な例は

${\displaystyle {\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}}$

その解は、4 つのペア( x , y ) = (1, 2)、(2, 1)、(-1, -2)、(-2, -1)です。これらの解は代入によって簡単に確認できますが、他の解が存在しないことを証明するにはさらに作業が必要です。

この記事の主題は、そのような例の一般化の研究と、解を計算するために使用される方法の説明です。

多項式方程式のシステム、 または多項式システムは方程式の集合である。

${\displaystyle {\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}}$

ここで、各f _{h は}不定値x ₁、...、x _mの多項式で、整数係数を持つか、または何らかの固定体（多くの場合、有理数体または有限体）の係数を持ちます。^[1]実数などの他の係数体は、その要素をコンピュータで表現できないため、あまり使用されません（計算には実数の近似値のみを使用でき、これらの近似値は常に有理数です）。

多項式系の解は、多項式系のすべての方程式を満たす ( x 1 、...、 x m ) の値の組です。解は複素数、またはより一般的には係数を含む代数的に閉じた体で求められます。特に_、特性0_では、すべての複素解が求められます。実数または有理数の解を探すことは、この記事では考慮されていないはるかに難しい問題です。

解の集合は必ずしも有限ではない。例えば、システムの解は

${\displaystyle {\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}}$

は点( x , y ) = (1,1)と直線x = 0である。^[2]解の集合が有限であっても、一般に解の閉じた形式の表現は存在しない（単一方程式の場合、これはアベル・ルフィニの定理である）。

図に示されているバース面は、3 変数の 6 次方程式 1 つに簡約された多項式系の解の幾何学的表現です。多数の特異点のいくつかが画像上に表示されています。これらは、3 変数の 5 次方程式 4 つの系の解です。このような過剰決定系には、一般に解がありません (つまり、係数が特定でない場合)。解の数が有限である場合、ベズーの定理により、この数は最大で5 ³ = 125です。ただし、6 次曲面の特異点の場合、解の最大数は 65 であることが示されており、バース面によってその数に達します。

方程式の数が変数の数より多い場合、システムは過剰決定系です。複素解を持たない（または、係数が複素数でない場合、係数を含む代数的に閉じた体に解を持たない）場合、システムは矛盾しています。ヒルベルトの零点定理によれば、これは 1 が方程式の最初の要素の線形結合（係数として多項式を持つ）であることを意味します。過剰決定系のほとんど（すべてではない）は、ランダムな係数で構築された場合、矛盾しています。たとえば、システムx ³ – 1 = 0、x ² – 1 = 0は過剰決定系（方程式が 2 つあるが未知数が 1 つだけ）ですが、解x = 1を持つため矛盾ではありません。

方程式の数が変数の数より少ない場合、システムは不確定です。不確定システムは矛盾しているか、無限に多くの複素解（または方程式の係数を含む代数的に閉じた体における解）を持ちます。これは、特にヒルベルトの零定理とクルルの主イデアル定理を含む可換代数の重要な結果です。

システムが0 次元であるとは、有限個の複素解 (または代数的に閉じた体における解) を持つ場合です。この用語は、解の代数多様体が 0次元であるという事実に由来しています。無限個の解を持つシステムは、正の次元であると言われています。

変数と同じ数の方程式を持つゼロ次元システムは、行儀が良いと言われることがあります。^[3] ベズーの定理は、方程式の次数がd ₁、...、d _nである行儀の良いシステムには、最大でd ₁ ⋅⋅⋅ d _n個の解があると主張しています。この境界は明確です。すべての次数がdに等しい場合、この境界はd ⁿになり、変数の数に対して指数関数的になります。（代数の基本定理は、n = 1 の特別な場合です。）

この指数関数的な振る舞いにより、多項式システムを解くことが困難になり、ベズーの境界が例えば 25 を超えるシステムを自動的に解くことができるソルバーがほとんどない理由が説明されます (3 次 3 方程式または 5 次 2 方程式がこの境界を超えます)。^{[引用が必要]}

多項式系を解くために最初にすべきことは、それが矛盾しているか、ゼロ次元か、正次元かを判断することです。これは、方程式の左辺のグレブナー基底を計算することによって行うことができます。このグレブナー基底が 1 に縮約されている場合、系は矛盾しています。すべての変数に対して、この変数の純粋な累乗であるグレブナー基底の何らかの要素の主要単項式がある場合、系はゼロ次元です。このテストでは、最適な単項式順序(つまり、一般的に最も高速な計算につながる順序) は通常、段階的逆辞書式順序 (grevlex) です。

システムが正の次元である場合、解は無限に存在します。したがって、解を列挙することはできません。したがって、この場合、解を解くということは、「解の関連する特性を簡単に抽出できる解の記述を見つけること」のみを意味する可能性があります。一般に受け入れられているそのような記述はありません。実際には、代数幾何学のほぼすべてのサブフィールドに関連するさまざまな「関連する特性」があります。

正の次元システムに関するこのような問題の自然な例は次のとおりです。有理数上の多項式システムに有限個の実解があるかどうかを決定し、それらを計算し ます。この問題の一般化は、多項式システムの実解の集合の各連結成分で少なくとも 1 つの解を見つけることです。これらの問題を解くための古典的なアルゴリズムは円筒代数分解ですが、これは二重指数関数的な 計算量を持つため、非常に小さな例を除いて実際には使用できません。

ゼロ次元システムの場合、解くことはすべての解を計算することです。解を出力する方法は 2 つあります。最も一般的な方法は、実数または複素数の解に対してのみ可能で、解の数値近似値を出力することです。このような解は数値と呼ばれます。近似値の誤差の境界が提供され、この境界が異なる解を分離する場合、 解は認定されます。

解を表すもう 1 つの方法は代数的であると言われています。これは、0 次元システムの場合、解がシステムの係数の体kの代数閉包に属するという事実を利用します。代数閉包で解を表す方法はいくつかあり、以下で説明します。どの方法でも、1 つまたは複数の一変量方程式を解くことで、解の数値近似を計算できます。この計算では、近似係数を持つ多項式の根を計算することは非常に不安定な問題であるため、解ごとに 1 つの一変量多項式のみを解く表現を使用することをお勧めします。

三角方程式は方程式g = 0であり、gは三角多項式です。このような方程式は、方程式内の正弦と余弦を展開し (和と差の公式を使用)、 sin( x )とcos( x )を2 つの新しい変数sとcに置き換え、新しい方程式s ² + c ² – 1 = 0を追加することで、多項式システムに変換できます。

例えば、アイデンティティのため

${\displaystyle \cos(3x)=4\cos^{3}(x)-3\cos(x),}$

方程式を解く

${\displaystyle \sin^{3}(x)+\cos(3x)=0}$

多項式系を解くことと同等である

${\displaystyle {\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}}$

この系の各解（c ₀、s ₀）に対して、 0 ≤ x < 2 πとなる方程式の唯一の解xが存在します。

この単純な例では、システムが方程式よりも簡単に解けるかどうかは不明瞭かもしれません。より複雑な例では、方程式を直接解く体系的な方法が欠けていますが、対応するシステムを自動的に解くソフトウェアが利用可能です。

q個の元を持つ有限体k上のシステムを解く場合、主にkの解に関心があります。 kの元は方程式x ^q – x = 0の解とまったく同じなので、解をkに制限するには、各変数 x _iに対して方程式x _i ^q – x _i = 0を追加すれば十分です。

代数体の要素は、通常、何らかの一変数多項式方程式を満たす体の生成元の多項式として表されます。係数が数体に属する多項式システムを扱うには、この生成元を新しい変数と見なし、生成元の方程式をシステムの方程式に追加するだけで十分です。したがって、数体上の多項式システムを解くことは、有理数上の別のシステムを解くことに帰着します。

たとえば、系に が含まれる場合、有理数系の系は、方程式r ₂ ² – 2 = 0を追加し、他の方程式で r ₂に置き換えることによって得られます。${\displaystyle {\sqrt {2}}}$${\displaystyle {\sqrt {2}}}$

有限体の場合、同じ変換により、体k が素数位数を持つと常に仮定できます。

解を表す通常の方法は、0次元の正規鎖を介することです。このような鎖は、1 ≤ i ≤ nとなるすべてのiに対して、次のような多項式列_f 1 ( x 1 ) 、f ₂ ( x ₁、 x 2 ₎、...、f _n ( x 1 _、 ... 、_x n )_で構成されます。

• f _{i は}x ₁、...、x _iのみの多項式であり、 x _iの次数はd _i > 0である。
• f _iにおけるx _i ^{d _i}の係数は、 f ₁、...、f _{i − 1}と共通の零点を持たないx _{1 、...、} x _{i −1}の多項式である。

このような規則的な連鎖には三角方程式系が関連している。

${\displaystyle {\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}}$

このシステムの解は、最初の一変量方程式を解き、その解を他の方程式に代入し、次に一変量になった 2 番目の方程式を解く、というように繰り返して得られます。正則連鎖の定義は、f _iから得られる一変量方程式が次数d _iを持ち、したがってこのシステムにはd ₁ ... d _n個の解があることを意味します。ただし、この解決プロセスで多重根が存在しない場合 (代数の基本定理) です。

すべての 0 次元多項式方程式系は、有限個の正規鎖と同等です (つまり、同じ解を持ちます)。 3 つの解を持つ次の系の場合のように、複数の正規鎖が必要になる場合があります。

${\displaystyle {\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}}$

任意の多項式系（必ずしも0次元ではない）^[4]を正則連鎖（または正則半代数系）に三角分解するアルゴリズムはいくつかある。

ゼロ次元の場合に特有のアルゴリズムもあり、この場合は直接アルゴリズムと競合します。これは、まず段階的逆辞書式順序 (grevlex)のグレブナー基底を計算し、次に FGLM アルゴリズム^[5]によって辞書式グレブナー基底を推定し、最後に Lextriangular アルゴリズム^{[6]を適用します。}

この解の表現は有限体の係数に対しては完全に便利です。しかし、有理数係数の場合は、次の 2 つの点に注意する必要があります。

• 出力には非常に大きな整数が含まれる場合があり、計算や結果の使用に問題が生じる可能性があります。
• 出力から解の数値を推測するには、近似係数を持つ一変量多項式を解く必要がありますが、これは非常に不安定な問題です。

最初の問題は、ダハンとショーストによって解決されました。^{[7] [8]}与えられた解の集合を表す正則鎖の集合の中には、入力システムのサイズに関して係数が明示的に制限され、ほぼ最適な制限を持つ集合があります。この集合は等射影分解と呼ばれ、座標の選択のみに依存します。これにより、等射影分解を効率的に計算するためのモジュラー手法を使用できます。^[9]

2 番目の問題は、通常、最初の d i を除くすべてのd _{i が}1に等しい、特殊な形式の正規連鎖(形状補題と呼ばれることもあります) を出力することによって解決されます。このような正規連鎖を取得するには、インデックス0が与えられる分離変数と呼ばれる変数をさらに追加する必要がある場合があります。以下で説明する有理単変量表現を使用すると、正規連鎖またはグレブナー基底のいずれかから開始して、Dahan–Schost 境界を満たすこのような特殊な正規連鎖を計算できます。

有理一変数表現（RUR）は、F.ルイリエによって導入された有理数上の0次元多項式系の解の表現である。^[10]

ゼロ次元システムのRURは、分離変数と呼ばれる変数の線形結合x ₀と方程式のシステムから構成される^[11]

${\displaystyle {\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}}$

ここで、h はx ₀のD次単変数多項式であり、g ₀、...、g _{n は}x _0のD次未満の単変数多項式です。

有理数上のゼロ次元多項式系が与えられた場合、RUR には次の特性があります。

• 変数の線形結合は、有限数を除いてすべて分離変数です。
• 分離変数が選択されると、RUR が存在し、一意になります。特に、hとg _{i は}、それらを計算するためのアルゴリズムとは独立して定義されます。
• システムの解はhの根と 1 対 1 に対応しており、hの各根の重複度は対応する解の重複度に等しくなります。
• システムの解は、hの根を他の方程式に代入することによって得られます。
• h に重根がない場合、 g _0はhの導関数です。

例えば、前のセクションのシステムでは、 x、y、x + yの倍数を除く変数のすべての線形結合は分離変数です。t = ⁠を選択した場合、x – y/2⁠ を分離変数として、RURは

${\displaystyle {\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}}$

RUR は、任意のアルゴリズムとは無関係に、特定の分離変数に対して一意に定義され、根の重複度を保存します。これは、一般的に重複度を保存しない三角分解 (等射影分解も含む) との顕著な違いです。RUR は、等射影分解と同様に、比較的小さいサイズの係数を持つ出力を生成するという特性を持っています。

ゼロ次元システムの場合、RUR では、単一の一変数多項式を解き、それを有理関数に代入することで、解の数値を取得できます。これにより、任意の精度で解の認定近似値を作成できます。

さらに、RUR の単変数多項式h ( x ₀ )は因数分解することができ、これによりすべての既約因数に対して RUR が得られます。これにより、与えられたイデアルの素分解(つまり、イデアルの根基の一次分解) が提供されます。実際には、特に多重度の高いシステムの場合には、これによりはるかに小さい係数の出力が提供されます。

三角分解や等射影分解とは異なり、RUR は正の次元では定義されません。

非線形方程式のあらゆるシステム用に設計された一般的な数値アルゴリズムは、多項式システムにも適用できます。ただし、一般的な方法ではすべての解を見つけることができないため、通常は特定の方法の方が好まれます。特に、一般的な方法で解が見つからない場合、通常は解がないことを示すものではありません。

それでも、ここでは 2 つの方法について言及する価値があります。

• ニュートン法は、方程式の数が変数の数と等しい場合に使用できます。この方法では、すべての解を見つけることも、解が存在しないことを証明することもできません。ただし、解に近い点から開始する場合は非常に高速です。したがって、これは以下で説明するホモトピー接続法の基本的なツールです。
• 最適化は多項式システムを解くためにめったに使用されませんが、1970年頃に、56変数の81の二次方程式のシステムが矛盾しないことを示すことに成功しました。^[12]他の既知の方法では、2022年現在、これは現代の技術の可能性を超えています^{[アップデート]}。この方法は、方程式の二乗の合計を最小化するだけです。ゼロが局所的最小値として見つかった場合は、解でそれが達成されます。この方法は過剰決定システムに対して機能しますが、見つかったすべての局所的最小値が正の場合、空の情報が出力されます。

これは、方程式の数が変数の数に等しいと仮定する半数値法である。この方法は比較的古いが、ここ数十年で劇的に改良された。^[13]

この方法は 3 つのステップに分かれています。まず、解の数の上限が計算されます。この上限はできるだけ厳密にする必要があります。したがって、少なくとも 4 つの異なる方法で計算され、最良の値、たとえば が保持されます。 ${\displaystyle N}$

2 番目のステップでは、計算しやすい解を正確に持つ多項式方程式のシステムが生成されます。この新しいシステムは、解くべきシステムと同じ数の変数、同じ数の方程式、同じ一般的な構造を持ちます。 ${\displaystyle g_{1}=0,\,\ldots ,\,g_{n}=0}$${\displaystyle N}$${\displaystyle n}$${\displaystyle n}$${\displaystyle f_{1}=0,\,\ldots ,\,f_{n}=0}$

次に、 2つのシステム間のホモトピーが考慮される。これは、例えば、2つのシステム間の直線で構成されるが、特にシステム内のいくつかの特異点を回避するために、他の経路が考慮されることもある。

${\displaystyle (1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0}$。

ホモトピー接続は、パラメータを0 から 1 に変形し、この変形中の解をたどることから成ります。これにより、 の望ましい解が得られます。 に従うということは、 の場合、 の解がニュートン法によっての解から演繹されることを意味します。ここでの難しさは、 の値を適切に選択することです。 が大きすぎると、ニュートン収束が遅くなり、解のパスから別のパスにジャンプする可能性もあります。 が小さすぎると、ステップ数によって方法の速度が低下します。 ${\displaystyle t}$${\displaystyle N}$${\displaystyle t=1}$${\displaystyle t_{1}$${\displaystyle t=t_{2}}$${\displaystyle t=t_{1}}$${\displaystyle t_{2}-t_{1}:}$

RUR から解の数値を推測するのは簡単そうに見えます。単変数多項式の根を計算し、それを他の方程式に代入するだけで十分です。しかし、多項式を別の多項式の根で評価することは非常に不安定であるため、これはそれほど簡単ではありません。

したがって、一変数多項式の根は、一度では定義できない高精度で計算する必要があります。この要件を満たすアルゴリズムは 2 つあります。

• MPSolveに実装されているAberth 法は、すべての複素根を任意の精度で計算します。
• コリンズとアクリタスのウスペンスキーのアルゴリズム^[14]は、ルイリエとツィンメルマン^[15]によって改良され、デカルトの符号規則に基づいています。このアルゴリズムは、任意の小さな幅の区間で分離された実根を計算します。これはMapleに実装されています（関数fsolveとRootFinding[Isolate]）。

ゼロ次元システムを自動的に解くことができるソフトウェア パッケージは少なくとも 4 つあります (自動とは、入力と出力の間に人間の介入が不要であり、したがって、ユーザーがその方法を知る必要がないことを意味します)。ゼロ次元システムを解くのに役立つ可能性のある他のソフトウェア パッケージもいくつかあります。そのうちのいくつかは、自動ソルバーの後にリストされています。

Maple関数RootFinding[Isolate] は、有理数上の任意の多項式系を入力として受け取り (係数の一部が浮動小数点数の場合は、有理数に変換されます)、(オプションで) 有理数の区間または任意の精度の浮動小数点近似値として表される実数解を出力します。システムが 0 次元でない場合は、エラーとして通知されます。

内部的には、F. Rouillier によって設計されたこのソルバーは、まずグレブナー基底を計算し、次に有理一変量表現を計算して、そこから必要な解の近似値を導き出します。このソルバーは、最大数百の複雑な解を持つシステムに対して日常的に機能します。

有理一変量表現はMaple関数Groebner[RationalUnivariateRepresentation]で計算できます。

有理一変量表現からすべての複素解を抽出するには、一変量多項式の複素根を任意の精度で計算するMPSolve を使用します。入力変数の方程式の根の代入は非常に不安定になる可能性があるため、解が安定するまで、精度を毎回 2 倍にしてMPSolve を複数回実行することをお勧めします。

2番目のソルバーはPHCpack ^{[13] [16]}で、 J. Verscheldeの指導の下で書かれたものです。PHCpackはホモトピー接続法を実装しています。このソルバーは変数と同じ数の方程式を持つ多項式システムの孤立した複素解を計算します。

3番目のソルバーはDJ Bates、JD Hauenstein、AJ Sommese、CW Wamplerによって書かれたBertini ^{[17] [18]}です。Bertiniは適応精度で数値ホモトピー接続を使用します。ゼロ次元の解集合を計算することに加えて、PHCpackとBertiniはどちらも正次元の解集合を扱うことができます。

4 番目のソルバーは、Marc Moreno-Maza と協力者によって作成されたMapleライブラリRegularChainsです。これには、正規連鎖を使用して多項式システムを解くためのさまざまな関数が含まれています。

• 消去法
• 多項式不等式のシステム
• 三角分解
• ウーの特性集合法