グレブナ基底と多変数連立代数方程式系の解法

多変数の連立方程式系

$$f_1(X) = \cdots = f_m(X) = 0$$ (15.1)

( $X = (x_1,\ldots,x_n)$, $f_i(X) \in {\bf Q}[X]$) を解く場合にも, イデアル

$$I=\langle f_1,\ldots,f_m\rangle = \{g_1(X)f_1(X)+\cdots+g_m(X)f_m(X) \;\vert\; g_i(X) \in {\bf Q}[X]\}$$

を考えることが有効である. 1 変数の場合とちがい, $I$ は 一般には単項イデアルではないが, グレブナ基底を計算することにより, 解を求めやすい形に変形することができる.

${\bf Q}[X]/I$ の ${\bf Q}$ 上のベクトル空間としての次元 $m$ が 有限である場合, $I$ を 0 次元イデアル とよぶ. 根の多重度を適切に定義してやると $m$ は連立方程式系 (16.1) の複素解の個数に一致することが知られている ([2, 5章2節 命題3, 3節 命題8]に多重度のない場合の証明がある).

次の定理は 0 次元イデアルの定義とメンバシップアルゴリズム アルゴリズムを与えている定理 16.1 より容易に証明できる ([2, 5章3節 定理6]も参照).

定理 15.3   次は同値である.

1. $I$ は 0 次元イデアルである.
2. $I$ の, ある項順序に関する $I$ の グレブナ基底が, 各変数 $x_i$ に対して, initial term が $x_i$ のべきであるような元を含む.
3. $I$ の, 任意の項順序に関する $I$ の グレブナ基底が, 各変数 $x_i$ に対して, initial term が $x_i$ のべきであるような元を含む.

この定理より, 解が有限個かどうかの判定が(任意の項順序の)グレブナ基底 により判定できる.

例 15.2   $I=\langle x-yz,y-zx, z-xy \rangle$ の $x > y > z$ なる辞書式順序 に関するグレブナ基底は $\{\underline{z^3}-z,\underline{-z^2y}+y,\underline{-y^2}+z^2, \underline{x}-zy\}$ である(冗長な要素は省いてある). よって 定理より $I$ は 0 次元イデアルである.

問題 15.2   与えられたイデアルの 0 次元性を判定する関数を書け.

また, この定理を, 辞書式順序の場合に適用すると, 次を得る.

定理 15.4   $I$ を 0 次元イデアルとし, $G$ を $x_1>x_2>\cdots > x_n$ なる 辞書式順序に関する $I$ のグレブナ基底とすると, $G$ は

$$\begin{eqnarray*} g_1(x_1,x_2,\ldots,x_n) &=& x_1^{d_1}+g_{1,d_1-1}(x_2,\ldots,x... ...\\ g_n(x_n) &=& x_n^{d_n}+g_{n,d_n-1}x_n^{d_n-1}+\cdots+g_{n,0} \end{eqnarray*}$$

という形の元を含む.

この定理により, まず 1 変数多項式 $g_n(x_n)$ の根を求め, それを $g_n(x_{n-1},x_n)$ に代入すれば, $x_{n-1}$ に関する 1 変数多項式 を得る. その根を求め $g_{n-2}(x_{n-2},x_{n-1},x_n)$ に代入して, と, 次々に 1 変数多項式 の根を求めることで, もとの方程式系の解の候補を求めることができる. (本当の解かどうかは, 他のすべて多項式の零点になっているかどうか をチェックしなければならない. 根を近似で求めてあると, この チェックは容易ではない. )

例 15.3   例 16.2 のイデアル $I$ の零点を求めよう. まず, $z^3-z=0$ より $z=-1,0,1$.

1. $z=-1$

   $-y^2+z^2=0$ より $y=-1,1$. このとき $(x,y,z) = (-1,1,-1), (1,-1,-1).$

2. $z=0$

   $-y^2+z^2=0$ より $y=0$. このとき $(x,y,z) = (0,0,0).$

3. $z=1$

   $-y^2+z^2=0$ より $y=-1,1$. このとき $(x,y,z) = (1,1,1), (-1,-1,1).$

例題 15.2   $n$ 変数の多項式を $n$ 本ランダム生成し, それらで生成される イデアルの辞書式順序グレブナ基底を求めて, どういう形をしている か観察せよ.

この例題の実験を行なう場合, $n$ をあまり大きくすると計算できない. せい ぜい 4, 5程度にする. また, 次数も 2, 3 次程度にしておくこと. 辞書式順 序グレブナ基底は, いきなり gr などで計算しても大抵ムリなので, Asir マニュアルをよく読んで, 上手な計算方法を学ぶこと. 実際にやってみればわかるように, 辞書式順序グレブナ基底は大変特徴 的な形をしている場合が多い:

$$\begin{eqnarray*} g_1(x_1,x_n) &=& x_1-h_1(x_n)\\ g_2(x_2,x_n) &=& x_2-h_2(x_n)... ...}(x_{n-1},x_n) &=& x_{n-1}-h_{n-1}(x_n)\\ g_n(x_n) &=& h_n(x_n) \end{eqnarray*}$$

これを shape base と呼ぶ. この形の場合には, $g_n(x_n)=0$ の根を 求めれば, 他の変数の値は代入により求まる.

例題 15.3   与えられたイデアルが shape base を持つかどうか判定し, shape base を持つ場合に零点の近似値を計算する関数を書け.

1 変数多項式の根は, pari(roots,Poly) で計算できる. たとえば, pari(roots,x^3-1) で $x^3-1=0$ の(複素)近似根を計算できる. ただし,

 ***   the PARI stack overflows !
  current stack size: 65536 (0.062 Mbytes)
  [hint] you can increase GP stack with allocatemem()

というようなエラーが出た場合には,

[295] pari(allocatemem,10^6)$

などを実行して, pari の使用できるメモリを増やすこと.

[826] load("katsura");
1
[831] katsura(7);    
[u0+2*u7+2*u6+2*u5+2*u4+2*u3+2*u2+2*u1-1,
2*u6*u0+2*u1*u7-u6+2*u1*u5+2*u2*u4+u3^2,
2*u5*u0+2*u2*u7+2*u1*u6-u5+2*u1*u4+2*u2*u3,
2*u4*u0+2*u3*u7+2*u2*u6+2*u1*u5-u4+2*u1*u3+u2^2,
2*u3*u0+2*u4*u7+2*u3*u6+2*u2*u5+2*u1*u4-u3+2*u1*u2,
2*u2*u0+2*u5*u7+2*u4*u6+2*u3*u5+2*u2*u4+2*u1*u3-u2+u1^2,
2*u1*u0+2*u6*u7+2*u5*u6+2*u4*u5+2*u3*u4+2*u2*u3+2*u1*u2-u1,
u0^2-u0+2*u7^2+2*u6^2+2*u5^2+2*u4^2+2*u3^2+2*u2^2+2*u1^2]

Risa/Asir ドリル ギャラリー : $n=7$ での katsura の方程式系. u0 から u7 が未知変数.

Risa/Asir ドリル ギャラリー : $n=7$ での katsura の方程式系の解の第一成分 u0