next up previous contents
Next: 2.2 連立法, 特に Durand-Kerner Up: 2.1 序 Previous: 2.1.2.3 実根のみを持つ実係数代数方程式の解きにくさ

2.1.3 連立代数方程式

一松 [16] 第3章 6節「連立代数方程式」の写経。


計算機代数の話題はまだ数多くあるが、近年有名になった「グレブナー基底」に ついて略説する。

多変数多項式に関する連立代数方程式を解く問題は良く現れるが、 一般的な解法はほとんどない。理論上ではつぎつぎに消去法によって 変数を消去してゆけば解けるはずだが、それを正直に実行すると、 たちまち大きな係数を持つ高次方程式が現れて、手におえなくなる。

これまでは与えられた方程式を適当に組み合わせて、因数分解できる形に直す方 法が主力だった。しかしこれを下手に実行すると、考察すべき場合の個数が激増 し、解をうまくまとめるのが厄介いになる。

変数に対称性がある場合には、それを生かしてうまく解ける場合もあった。ただ しそれにこだわるのは得策でなく、対称性を無視して消去法を使うほうがよいこ とも多い。

この問題は、一般化すると、多項式イデアルに関する所属判定問題になる。 イデアルとは、歴史的な由来のある述語だが、いくつかの基底要素 $ p_1$, $ \cdots$, $ p_m$ に多項式 $ u_1$, $ \cdots$, $ u_m$ をかけて加えて表わされる

$\displaystyle I = \{u_1p_1+\cdots+u_mp_m\}
$

という形の多項式の族と考えてよい。

一変数の場合には、このようなイデアルが、$ p_1$, $ \cdots$, $ p_m$ の 最大公因子 $ d$ の倍式全体として表される (単項イデアル)。この $ d$ は 「よい基底」である。

多変数の場合には、単項でないイデアルがふつうであり、 「よい基底」を求めることが重要である。

連立代数方程式 $ p_1=0$, $ \cdots$, $ p_m=0$ を解くには、 原理的には $ p_1$, $ \cdots$, $ p_m$ の生成するイデアルの 任意の基底の共通零点を求めればよい。 しかし基底が悪いと、この操作が実行困難である。

イデアルに関する所属判定問題とは、 与えられた多項式 $ f$ が、 そのイデアル $ I$ に含まれるかどうかを判定する算法を問う問題である。 その応用例は後述する。

もし具体的に $ u_1$, $ \cdots$, $ u_m$ を求めて

$\displaystyle f=u_1p_1+\cdots+u_mp_m
$

と書くことができれば $ f$$ I$ に含まれる、他方もし変数 $ x_1$, $ \cdots$, $ x_n$ にたいして適当な値 $ a_1$, $ \cdots$, $ a_n$

$\displaystyle p_1(a_1,\cdots,a_n)=0,\cdots,p_m(a_1,\cdots,a_n)=0,f(a_1,\cdots,a_n)\ne
0
$

である組がみつかれば、$ f$ はイデアル $ I$ には含まれない。

その昔、何日も所属問題がうまく解けずに苦しみ、試しに数値を代入したら、 前期のような組がみつかり、$ f$$ I$ に属さないことがわかった、 そして結果的にそれまでの計算はむだだった、という実例がある。 現在でもこのような予備テストは重要である。しかしこのような $ a_1$, $ \cdots$, $ a_n$ の組がみつからない (いつでも $ f(a_1,\cdots, a_n)=0$ とな る) とき、$ f$$ I$ に含まれそうだと予想されても証明にはならない。

この判定には $ I$ の基底自体が重要である。じっさいに基底のとり方が 悪いと、奇妙な現象が起こる。

例えば変数の個数を $ 3$ とし、$ x_1$, $ x_2$, $ x_3$$ x$, $ y$, $ z$ と書く ことにして、次の基底を考える。

$\displaystyle p_1=x^3yz-xz^2,\quad
p_2=xy^2z-xyz,\quad
p_3=x^2y^2-z^2
$

これにたいして $ f=x^2yz-z^3$ の所属問題を考えてみよう。

原則として最も高い次数の項を合わせて消去する。 しかし $ f$ の主項 $ x^2yz$ は、$ p_1$, $ p_2$, $ p_3$ のどれを 使っても、そのままでは簡約できない。この $ f$ $ ^xp_2+zp_3$ と 表現できるので、イデアルに属する。このことは $ x^2y^2z$ という おなじ項を加減して変形すればわかるが、これを機械的に求めることはできない。

この例は $ f$ が悪いというよりも、イデアルの基底が不足しているのである。 これにさらに新しい基底を補充して、基底 (base) を固める必要がある。

多項式イデアルの基底を補充して、標準的な基底を整備する理論は、 かなり昔から考えられていた。たとえば広中平祐氏が、 フィールズ賞の対象となった 「特異点の還元」の研究中に、 その種の「標準基底」を扱っている。 したがって、これを「広中基底」とよぶべきかもしれない。

しかしその具体的な構成算法を示したのはブーフバーガーであり、 彼は恩師の名をとって、それをグレブナー基底とよんだ。 今日その名で広く使われているので、以下でもそうよんで論じることにする。

それはある意味では、連立一次方程式を解くガウスの消去法の一般化である。 対称式については基本対称式が 「グレブナー基底」に相当する。一般のグレブナー基底は、 これらの概念の一般化に相当する。


next up previous contents
Next: 2.2 連立法, 特に Durand-Kerner Up: 2.1 序 Previous: 2.1.2.3 実根のみを持つ実係数代数方程式の解きにくさ
Masashi Katsurada
平成21年7月9日