本シリーズでは多項式の因数分解を取り上げてきたが，計算機代数の話題はまだ数多くあり，今回取り上げるテーマは「連立代数方程式を解く」ことである．

　連立１次方程式を解くことの幾何学的な意味は，超平面の交わりを求めることである．それに対して連立代数方程式

　　ｆ1（ｘ1，ｘ2，・・・，ｘn）＝０

　　ｆ2（ｘ1，ｘ2，・・・，ｘn）＝０

　　・・・・・・・・・・・・・・・・

　　ｆm（ｘ1，ｘ2，・・・，ｘn）＝０

の解を求めることは超曲面（多様体）の共通零点を求めることにほかならない．超平面は平行でない限り必ず交わるが，超曲面は交わるとは限らない．そのため，連立代数方程式の解は存在するとは限らないし，逆に無限個存在することもある．

　多変数多項式に関する連立代数方程式を解く場合，原理的には変数を順次消去することによって計算できるはずだが，それを馬鹿正直に実行するとたちまち大きな係数をもつ高次方程式が現れて手に負えなくなることが知られている．連立１次方程式の場合と比較して，飛躍的に計算が複雑になるからである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】解ける連立代数方程式

　まず，連立代数方程式が解ける場合についてみてみよう．

　　ｆ1＝ｘ＋ｙ^2＋３ｚ^2−４＝０

　　ｆ2＝４ｙ^2−５＝０

　　ｆ3＝ｙ^4−５ｚ−１０＝０

この例では１つの変数のみの関数ｆ2＝０を解いてｙを求め，それからｆ3＝０によってｚ，ｆ1＝０によってｘというようにして芋づる式に連立代数方程式を解くことができる．

　　（ｘ，ｙ，ｚ）＝（１２５／１６，±√５／２，−２７／１６）

この手順は連立１次方程式を解くガウスの消去法の後退代入計算と類似している．

　一般の連立代数方程式を解くためにはガウスの消去法が使える形（三角化）に直すかあるいは１変数のみの関数に直すことがカギになる．そのための有効な手段として注目されているのが「グレブナー基底」を構成するブーフバーガーのアルゴリズムである．

　グレブナー基底はよい基底であり，対称式については基本対称式がグレブナー基底に相当するものであるから，グレブナー基底は基本対称式の概念の一般化と考えることもできるであろう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】辞書式順序

　多項式は単項式の１次結合であるが，グレブナー基底を構成する際，単項式に順序を入れる必要がある．便宜上，変数にａ＞ｂ＞ｃ（＞１）と順序をつけ，単項式ａ^pｂ^qｃ^rについては指数の列(p,q,r)に辞書式順序をつける（単純辞書式順序）．さらに，全次数（p+q+r）が大きいほうから順序をつけるが，全次数が同一の項どうしは辞書式順序をつける（全次数辞書式順序）．

　たとえば，３変数の場合の単純辞書式順序では

　　ａ^2＞ａｂ＞ａｃ＞ａ＞ｂ^2＞ｂｃ＞ｂ＞ｃ^2＞ｃ

となる．一方，全次数辞書式順序は

　　ａ^2＞ａｂ＞ａｃ＞ｂ^2＞ｂｃ＞ｃ^2＞ａ＞ｂ＞ｃ

になるのである．

　この順序は消去すべき優先順位を表す順序となるものであるから，全次数辞書式順序は次数の高いものから順に消去され，単純辞書式順序ではまずａが消去され，ついでｂという具合になっている．変数の優先順位をｂ＞ａ＞ｃの順に変更するなど，変数の優先順位の適否によって計算所要時間が何千倍，何万倍も違うことがあるという実際的な課題はあるものの，実用上は全次数辞書式順序を使うのが標準的である．

　なお，すべての指数が１か０であるものが基本対称式である．３変数の基本対称式を

　　ａｂ＋ｂｃ＋ｃａ

といった順に整理する習慣があるが，いずれの辞書式順序でも

　　ａｂ＋ａｃ＋ｂｃ

に整理される．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】ブーフバーガーのアルゴリズム

　よい基底の具体的な構成算法を示したのはブーフバーガーであり，彼は恩師の名をとってそれをグレブナー基底と命名した．グレブナー基底はある順序に従って項を消去してゆく演算で作られるのだが，その際，先頭にくる項を主項とよぶ．

(1)基底（ｆ1，ｆ2，・・・，ｆm）の要素対ｆi，ｆjに対して最も高い次数の主項ｓi，ｓjを合わせて消去する．

そのためには主項の最小公倍多項式をＬＣＭ（ｓi，ｓj）として

　　Ｓ（ｆi，ｆj）＝ＬＣＭ（ｓi，ｓj）（ｆi／ｓi−ｆj／ｓj）

とすればよい．

(2)ｆ0＝Ｓ（ｆi，ｆj）の主項ｓ0が（ｆ1，ｆ2，・・・，ｆm）の主項（ｓ1，ｓ2，・・・，ｓm）の倍式であるとき，ｆkに適当な単項式を乗じてｆ0から引くことによりその項を消去する．この操作を簡約という．

　　λ＝ｓ0／ｓk

　　ｆ0~＝ｆ0−λｆk

　　ｆ0←ｆ0~

(3)ｆ0が０に簡約できないとき（イデアルの基底が不足していると考えて）新しい基底として追加補充する．

　　ｆm+1←ｆ0，ｍ←ｍ＋１

　この一連の操作は有限回で完了し，最後にグレブナー基底（ｆ1，ｆ2，・・・，ｆm）を得ることができる．ただし，構成する順序（式の組合せ）によって最終的に得られるグレブナー基底は１通りとは限らない．ｆ0をどのｆkによって簡約するかによってその結果は変わるが，どのように簡約しても最終結果が１通りに定まるのがグレブナー基底である．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　ブーフバーガーのアルゴリズムをコンピュータにインプリメントするには，計算のスピードも重視しなければならない．コンピュータ向きの効率化には本来個々のアルゴリズムの特性によって決められるべきであるが，反復計算をどこで打ち切るか（停止則）はプログラムを設計するうえで重要な問題である．

　その際，各要素対ｆi，ｆjに対し

(a)Ｓ（ｆi,ｆj）がすべて０に簡約される

(b)ｆi,ｆjと異なるｆkがあり，主項ｓkがｓi，ｓjの最小公倍式の因子であって，Ｓ（ｆi,ｆk），Ｓ（ｆj,ｆk）がともに０に簡約される

のいずれかの条件が成立するとき，反復計算を打ち切ることにする（停止則）．

　このようにすれば(a)のようにｍ（ｍ−１）／２個の組合せすべてを調べなくとも，特定のｆkに対して(b)の条件を調べれば済むことが多く，検証すべき場合をを大幅に減らすことができるというわけである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【４】連立代数方程式を解く

　多くの場合，グレブナー基底には変数の一部を含まない多項式が現れる．そして，簡約グレブナー基底が得られればガウスの消去法のように芋づる式に解を求めることができるから計算が簡易化されることになる．

　よい基底を計算する算法がブーフバーガーのアルゴリズムであるが，本質的にガウスの消去法の変法である．グレブナー基底を構成する簡単な演習問題を掲げよう．

［１］

　　ｆ1＝ｘ＋ｙ^2＋３ｚ^2−４＝０

　　ｆ2＝４ｙ^2−５＝０

　　ｆ3＝ｙ^4−５ｚ−１０＝０

　まず，変数の優先順位をｘ＞ｙ＞ｚとして，全次数辞書式順序をいれる．

　　ｆ1＝ｙ^2＋３ｚ^2＋ｘ−４＝０　　　（主項：ｙ^2）

　　ｆ2＝４ｙ^2−５＝０　　　　　　　　（主項：４ｙ^2）

　　ｆ3＝ｙ^4−５ｚ−１０＝０　　　　　（主項：ｙ^4）

　　ｆ0＝Ｓ（ｆ1，ｆ2）＝４ｆ1−ｆ2＝１２ｚ^2＋４ｘ−１１

　　ｆ4＝１２ｚ^2＋４ｘ−１１　　　（主項：１２ｚ^2）

　　ｆ0＝Ｓ（ｆ2，ｆ3）＝ｙ^2ｆ2−４ｆ3＝−５ｙ^2＋２０ｚ＋４０

　　ｆ0＝ｙ^2−４ｚ−８　　　（主項：ｙ^2）

　　４ｆ0−ｆ2＝−１６ｚ−２７　　　（ｆ2で簡約）

　　ｆ5＝１６ｚ＋２７　　　（主項：１６ｚ）

　　Ｓ（ｆ4，ｆ5）＝４ｆ2−３ｚｆ5＝１６ｘ−１２５

　　ｆ6＝１６ｘ−１２５　　　（主項：１６ｘ）

　　ｆ2＝４ｙ^2−５＝０

　　ｆ5＝１６ｚ＋２７＝０

　　ｆ6＝１６ｘ−１２５＝０

と

　　ｆ1＝ｆ2＝ｆ3＝０

の解は同じ解

　　（ｘ，ｙ，ｚ）＝（１２５／１６，±√５／２，−２７／１６）

をもつことは明らかである．

　　ｆ2＝ｆ5＝ｆ6＝０

のほうが方程式の形が簡単になってグレブナー基底は連立代数方程式の解を求めるのに有効であることがおわかり頂けるであろう．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［２］

　　ｆ1＝ａ＋ｂ＋ｃ−３＝０

　　ｆ2＝ａ^2＋ｂ^2＋ｃ^2−５＝０

　　ｆ3＝ａ^3＋ｂ^3＋ｃ^3−７＝０

　いくつかの変数からなるいくつかの多項式の共通零点のつくる集合を代数多様体というが，平面ｆ1＝０と楕円面ｆ2＝０の共通零点である楕円と非コンパクトな３次曲面ｆ3＝０との共通零点を求める問題である．この場合には変数に対称性という特殊性があるので，与えられた方程式を組み合わせて基本対称式に直せば手計算でもうまく進めることができる．

　　ａ^2＋ｂ^2＋ｃ^2＝（ａ＋ｂ＋ｃ）^2−２（ａｂ＋ｂｃ＋ｃａ）＝５　→　ａｂ＋ｂｃ＋ｃａ＝２

　　ａ^3＋ｂ^3＋ｃ^3＝（ａ＋ｂ＋ｃ）（ａ^2＋ｂ^2＋ｃ^2−ａｂ−ｂｃ−ｃａ）＋３ａｂｃ＝７　→　ａｂｃ＝−２／３

このことから，ａ，ｂ，ｃは３次方程式：

　　ｘ^3−３ｘ^2＋２ｘ＋２／３＝０

の３根であり，（ａ，ｂ，ｃ）はそれを巡回置換したものになるから，総計６組の解が出る．

　しかし，コンピュータはこのような計算ができるほど融通はきかないので，ブーフバーガーの消去法アルゴリズムを適用してみることにする．ここでは単純辞書式順序に関して計算する．

　　ｆ1＝ａ＋ｂ＋ｃ−３　　　　　　（主項：ａ）

　　ｆ2＝ａ^2＋ｂ^2＋ｃ^2−５　　　（主項：ａ^2）

　　ｆ3＝ａ^3＋ｂ^3＋ｃ^3−７　　　（主項：ａ^3）

　　ｆ0＝Ｓ（ｆ1，ｆ2）＝ａｆ1−ｆ2＝ａｂ＋ａｃ−３ａ−ｂ^2−ｃ^2＋５　　　（主項：ａｂ）

　　ｆ0−ｂｆ1−ｃｆ1＋３ｆ1＝−２ｂ^2−２ｂｃ＋６ｂ−２ｃ^2＋６ｃ−４　　　（ｆ1で簡約）

　　ｆ4＝−２ｂ^2−２ｂｃ＋６ｂ−２ｃ^2＋６ｃ−４　　　（主項：−２ｂ^2）

　　ｆ0＝Ｓ（ｆ1，ｆ3）＝ａ^2ｆ1−ｆ3＝ａ^2ｂ＋ａ^2ｃ−３ａ^2−ｂ^3−ｃ^3＋７　　　（主項：ａ^2ｂ）

　　ｆ0−ｂｆ2−ｃｆ2＋３ｆ2＝−２ｂ^3−ｂ^2ｃ＋３ｂ^2−ｂｃ^2＋５ｂ−２ｃ^3＋３ｃ^2＋５ｃ−８　　　（ｆ2で簡約）

　　ｆ0＝−２ｂ^3−ｂ^2ｃ＋３ｂ^2−ｂｃ^2＋５ｂ−２ｃ^3＋３ｃ^2＋５ｃ−８　　　（主項：ｂ^3）

　　ｆ0−ｂｆ4＋ｃ／２ｆ4−３／２ｆ4＝−３ｃ^3＋９ｃ^2／６ｃ−２　　　（ｆ4で簡約）

　　ｆ5＝−３ｃ^3＋９ｃ^2／６ｃ−２　　　（主項：−３ｃ^3）

　こうしてｆ5＝０では変数ａ，ｂを含まず変数ｃのみの３次関数が現れた．ｆ5＝０を解くと，ｃは１つの実数解と１組の共約な虚数解をもつことがわかった．その各々からｆ4＝０でｂを求めると平方根の符号を変えた２組の解が出る．最後にｆ1＝０からａを求めるとａは一意に決まるから，解は総計６組になる．このようにして連立代数方程式ｆ1＝ｆ2＝ｆ3＝０を解くことができる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【５】ロボティクス（ロボット工学）への応用

　少し計算が必要であるが，連立代数方程式ｆ1＝ｆ2＝・・・＝ｆm＝０を解くにはイデアルの任意の基底の共通零点を求めればよいことがおわかり頂けたかと思う．グレブナー基底の応用として，ロボットアームのような機械リンク装置がとりうる配置のなす空間を記述できることを述べておきたい．

　小生は以前このＨＰにおいて佐々木誠先生（現・佐賀大学）と，複数の関節をもつロボットアームの配位空間の話を展開したことがある．３次元空間の運動は並進運動と回転運動を考えると少なくとも６次元での解析が必要になるが，さらに複数の関節をもつことによる冗長性が加わって，配位空間は一般にｎ（≧６）次元の多面体になる．

　この多面体はロボットアームが物理的に到達可能な配位を表すものと考えることができるのだが，逆問題を解こうとすると冗長性のために到達できない場所に対応することが起こりうる．

　ｎ次元多面体はｎ次元楕円である程度近似することはできるのだが，配意空間すべてを表しているわけではないのでどうしても楕円では代替することができないのである．

　佐々木誠先生に教えてもらったことだが，岐阜大学の川崎晴久先生が

　　川崎晴久「ロボット数式処理」，昭晃堂

の中でグレブナー基底とブーフバーガー・アルゴリズムを用いて運動方程式の解を導出されておられるそうだ．私はまだ読んだことはないが，興味のある方のために著書を紹介しておく．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝