多項式方程式系

三角方程式は、 gが三角多項式である方程式g = 0です。このような方程式は、その中の正弦と余弦を展開し（和と差の公式を使用）、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を追加すれば十分です。 

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

例えば、システムに$\displaystyle {\sqrt {2}}}$有理数上のシステムは、方程式r ₂ ² – 2 = 0を追加し、置き換えることによって得られます。$\displaystyle {\sqrt {2}}}$他の方程式ではr ₂を使用します。

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

解を表す一般的な方法は、零次元の正則鎖を用いることである。このような鎖は、 1 ≤ i ≤ nを満たすすべてのiに対して、次の式が成り立つような多項式の列f ₁ ( x ₁ )、f ₂ ( x ₁ , x ₂ )、 ...、f _n ( x ₁ , ...、x _n )から構成される。

• f _iはx ₁、 ...、x _iのみに関する多項式であり、 x _iに関して次数d _i > 0を持つ。
• f _iにおけるx _i ^{d _i}の係数は、x ₁、 ...、x _{i −1}に関する多項式であり、 f ₁、 ...、f _{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個の解を持ちます（代数学の基本定理）。

零次元多項式方程式系はすべて、有限個の正則連鎖と等価（つまり、同じ解を持つ）である。次の系のように3つの解を持つ場合、複数の正則連鎖が必要になることもある。

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

任意の多項式システム（必ずしもゼロ次元ではない）^{[ 4 ]}を正則な鎖（または正則な半代数システム）に三角分解するアルゴリズムがいくつか存在する。

また、ゼロ次元の場合に特有のアルゴリズムもあり、この場合、直接アルゴリズムと同等の性能を発揮します。このアルゴリズムは、まず次数付き逆辞書式順序 (grevlex)のGröbner 基底を計算し、次に FGLM アルゴリズム^{[ 5 ]}によって辞書式 Gröbner 基底を導出し、最後に Lextriangular アルゴリズム^{[ 6 ]を適用するというものです。}

この解の表現は、有限体における係数に対しては完全に都合が良い。しかし、有理係数の場合、次の2つの点に注意する必要がある。

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

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

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

有理単変数表現（RUR）は、F. Rouillierによって導入された、有理数上のゼロ次元多項式系の解の表現である。^{[ 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は次数Dのx ₀に関する単変数多項式であり、g ₀、...、g _{n は次数が}D未満のx ₀に関する単変数多項式である。

有理数上の零次元多項式系が与えられた場合、RURは次の性質を持つ。

• 変数の線形結合のうち、有限個のものを除いてすべてが分離変数である。
• 分離変数が選択されると、RURは存在し、一意となる。特に、hとg _iは、それらを計算するアルゴリズムとは独立して定義される。
• この連立方程式の解は、 hの根と一対一に対応しており、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}$は保持されます。

第２段階では、システムが${\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}$。

ホモトピー連続は、パラメータを変形することから成ります。${\displaystyle t}$0から1へ、そして${\displaystyle N}$この変形中の解。これにより、以下の望ましい解が得られます。${\displaystyle t=1}$.以下は、もし${\displaystyle t_{1}<t_{2}}$解決策${\displaystyle t=t_{2}}$の解から導き出される${\displaystyle t=t_{1}}$ニュートン法による。ここでの難しさは、の値を適切に選択することである。${\displaystyle t_{2}-t_{1}:}$数が大きすぎると、ニュートン法の収束が遅くなり、解の経路から別の経路に飛び移ってしまう可能性があります。逆に数が小さすぎると、ステップ数が増えすぎて処理速度が低下します。

RURから解の数値を導き出すのは簡単そうに見える。単変数多項式の根を計算し、それを他の式に代入すればよいだけだからだ。しかし、これはそう簡単ではない。なぜなら、ある多項式の根における別の多項式の評価は非常に不安定だからだ。

したがって、一変数多項式の根は、一度定義すれば必ず得られるとは限らない高精度で計算する必要がある。この要件を満たすアルゴリズムは2つ存在する。

• MPSolveに実装されているアバース法は、任意の精度で全ての複素根を計算します。
• CollinsとAkritasによるUspenskyアルゴリズム^{[ 14 ]}は、 RouillierとZimmermann ^{[ 15 ]}によって改良され、 Descartesの符号法則に基づいています。このアルゴリズムは、任意の小さな幅の区間に分離された実根を計算します。Maple （関数fsolveとRootFinding[Isolate] ）に実装されています。