数理解析研究所講究録
第 1648 巻 2009 年 192-206

192

Challenge to solve simultaneous nonlinear algebraic
equations in the history of Japanese mathematics
木村欣司
KINJI KIMIJRA

JST・立教大学
JAPAN SCIENCE AND TECHNOLOGY AGENCY. FACULTY OF SCIENCE, RIKKYO UNIVERSITY

1

はじめに

非線形連立代数方程式を解くことは簡単ではない. そのテクニックは多岐にわたる. こ
こでは, 現在われわれが知っているすべてのテクニックをあますところなく紹介することを試みる. これらの手法の成果として, 日本数学史の問題を解いたのであり問題を解くことが最終目標ではない. 手法の確立のためのテスト問題と位置づけている.

2

基本的な道具21

数式処理

1 Characteristic set Wu 先生の方法)$($

2. Gr\"obner ba.sis (Buchberger 先生の 7) レゴリズム,F4 ア) レゴリズム)

3 終結式 multipolynomial resultant
4. real root finding
5. 倍写像行列
この研究集会では, Wu 先生自らが中国よりいらっしゃったので私の稿の中で Characteristic
set について触れることは, ご容赦願いたい.

22

数値計算

l. Krawczyk 法 (精度保証付き数値計算法)

2. ホモトピー法 精度保証もおこなう)$($

3. B\’ezout の定理, Bernstein の定理

193
4. Gerschgorin の定理
それぞれの詳細は. 後に述べる.

3

数式処理
終結式は, 行列式を用いて計算することもできる. よって, 行列式から始める.

3.1

行列式

3.1.1

Fraction-free Gaussian elimination$\ell\iota_{ii}$を多変数多項式とする.

$]$$[0000000a_{k-\dot{i},k-1}000000$$a_{j}a_{\text{海},j}$$a_{k\cdot.\cdot k}a_{i,.k^{\backslash }}$$.\cdot$$.\cdot$

次の漸化式に従って計算する.
$a_{i_{)}\dot{\supset}}^{karrow 1} arrow\frac{a_{i,j}^{k}a_{k_{Z}k}^{k}-a_{i.k}^{k}a_{k^{\backslash }.j}^{k}}{a_{k-1,k-1}^{k\cdotarrow 1}}$

肩の添字は, 消去法が第何行目まで進んだかをあらわす.
で割り切れる. [5]$(\begin{array}{lll}a b cf g hk l m\end{array})arrow$$(00a$$|\begin{array}{ll}a bf ga bk l\end{array}|$$a_{i,j}^{k\backslash }a_{k,k}^{k}-a_{i,k}^{k}a_{k_{\dot{\theta}}}^{k}$$|_{km}^{1_{fh}^{a^{C}c}}ac|)arrow(()0a$$|\begin{array}{ll}a bf g\end{array}|$$X=’\det|\begin{array}{ll}(\iota cf h\end{array}|)$,$|\begin{array}{ll}a c\underline{fh} \end{array}||\begin{array}{l}b-\end{array}||\begin{array}{ll}a bf g\end{array}||\begin{array}{ll}a ck m\end{array}|$

$X$

は必ず

$fa$

$gb$

$hc$

$k$

$l$

$m$

$=$

$\iota_{k-1,k-1}^{k-1}$

194
つぎのように書き直してみる.

$|\begin{array}{ll}a ck rn\end{array}||\begin{array}{ll}a bf g\end{array}|-|\begin{array}{ll}(l bk l\end{array}||fa$

これを, Jacobi の恒等式という. 行列式は

312$(\iota_{n,n}^{(n)}$$hc$$fkagblmhc$

$=$

$a$

に現れる.

小行列式展開[15] を参照されたい.
313

ラプラス展開の行列まで, この方法では 1 箇所も計算結果の使い回しができないことがわかる.
の行列 $A=(a_{i,j})$ の行列式を例にどの程度計算結果の使い回しができるかをみる.

$4\cross 4$$5\cross 5$$.,$ $L_{3}=a_{4_{1}3}a_{S,4}-a_{4,4}a_{5,3}$ ,$L_{1}$$=a_{4_{)}4}ar_{J},5-a_{4_{2^{L}}^{r_{1}}}a_{5,4},$ $L_{2}=a_{4,3}a_{5.5}-a_{4,5}a_{5,3}$
・$L_{4}$$=$$L_{5}=a_{4,2}a_{5.4}-a_{4.4}a_{S.2}.L_{6}=a_{4,2}a_{5_{2}3}-a_{4.3}a_{5,2}$,$L_{7}$$=a_{4.1}a_{5.2}-a_{4,2}a_{\supset,1}r,$ $L_{8}=a_{4,1}a_{5,5}-a_{4.5}a_{5.1_{!}}.L_{9}=a_{4,1}a_{5,4}-a_{4,4}a_{5.1}$,$L_{10}$$\det(A)$$a_{4,2}a_{5_{1}S}-a_{4,5}a_{5_{1}2},$$=a_{4.1}a_{5,3}-a_{4,3}a_{5.1}$$=$$+(a_{1,1}a_{2,2}-a_{1,2}a_{2,1})(a_{3,3}L_{1}-a_{3.4}L_{2}+a_{3_{1}:i}sL)$$-(a_{1.1}a_{2.3}-a_{1,3}a_{2,1})(-a_{S,4}L_{4}+a_{3,5}L_{5})$$+(\iota_{1,1}a_{2,4}-a_{1,4}a_{2_{:}1})(a_{t}’;,2L_{2}-a_{3,3}L_{4}+a_{3.5}L_{6})$$-(a_{1,1}a_{2,5}-a_{1.5}a_{2.1})(a_{3,2}L_{3}-a_{3,3}L_{5}+a_{3,4}L_{6})$$+(a_{1.2}a_{2,3}-a_{1,3}a_{2_{2}2})(a_{3.1}L_{1}-a_{3.4}L_{8}+a_{3_{\nu}5}L_{9})$$-(a_{1,2}a_{2.4}-a_{1,4}a_{2,2})(a_{3,1}L_{2}-a_{3,3}L_{S}+a_{3,5}L_{10})$$+(\iota_{\backslash }))$

. $+a_{3,4}L_{10})$$+(a_{1,3}a_{2.4}-a_{1.4}a_{2,3})(a_{3,1}L_{4}-a_{3,2}L_{S}+a_{3.5}L_{7})$$-(a_{1.3}a_{2,5}-a_{1.5}a_{2,3})(a_{3,1}L_{5}-a_{3,2}L_{9}+a_{3_{2}4}L_{7})$$+(a_{1,4}a_{2,5}-a_{1,5}a_{2,4})(a_{3_{4}1}L_{6}-a_{3.2}L_{10}+a_{3,3}L_{7})$一般に, $N\cross N(N>4)$ の行列のラプラス展開においては ( $N/2$ の切り上げの数一 ) $\cross(N/2$の切り上げの数 $-1$ ) 以下のサイズの行列式の計算結果の使い回しができる. 計算結果の使い回しをするためには, 大量のメモリが必要である. もちろん, $N$ が大きくなれば組み合わせ爆発もおきる.
$1$

314

補間法

私が最も力を注いでいる算法である. [8] に詳しく述べたので, そちらを参照されたい.

195
3.2

終結式

321

終結式の行列式による表現

終結式を行列式で表現する場合に. 現在知られている 3 つの代表的な方法を紹介する.
れ以外にも, 佐々木らの方法 [14] もある.

こ$\acute$

1. Sylvester の方法
2. 関孝和の方法

3. 擬剰余を用いて構成する方法
はじめの 2 については, あまりにも有名でありここでは特に触れることはしない. [5] 最後の 1 つは, [3] に解説がある.
最後の 1 つについて, ここでは具体例をあげてその特徴をみることとする.

,$f(x)$$=$$b_{0}+bix+b_{2}x^{2}$$g(x)$$=$$(\iota_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}$.

$f(x)$ と $g(x)$ の終結式を計算したかったとする. $g(x)$ を法として, $f(x)$ についての擬剰余を計算して行列式を構成すると$res_{x}(f(x),g(x))=a_{1}^{-1}’;\cross$$b_{0}$$b_{1}$$b_{2}$$-a_{0}b_{2}$$a_{\delta}l)_{0}-a_{1}b_{2}$$a\cdot;^{b_{1}-a_{2}b_{2}}$$a_{2}a_{\zeta\rangle}b_{2}-a_{3}\iota_{0}b_{1}$$(a_{2}a_{1}-a_{3}a_{(\rangle})b_{2}-a_{3}a_{1}b_{1}$$(\iota_{2}^{2}-a_{3}a_{1})b_{2}+a_{3}^{2}b_{0}-a_{3}a_{2}b_{1}$という余剰な因子を取り関孝和の方法をもちいても.
の行列式が構成され, かつ除くための割り算が存在しないのでこの定義を用いる意味はまったくない. $f(x)$ を法として, $g(x)$ についての擬剰余を計算して行列式を構成すると$3\cross 3$$a_{3}^{-1}$$a_{3}b_{0}b_{1}+a_{0}b_{2}^{2}-(\iota_{2}$$res_{x}(f(x),g(x))$$=$$a_{3}^{-1}\cross$bob2$(\iota_{2}b_{2}-a_{3}b_{1})b_{0}b_{1}+((\iota_{3}b_{0}-a_{1}b_{2})b_{0}b_{2}$$a_{3}b_{1}^{2}-a_{2}b_{2}b_{1}+a_{1}b_{2}^{2}-a_{3}b_{0}b_{2}$$(a_{2}b_{2}-a_{3}b_{1})b_{1}^{2}+2(\iota_{3}b_{0}b_{2}b_{1}+(a_{0}b_{2}-a_{2}b_{0}-a_{1}b_{1})b_{2}^{2}$となり, $2\cross 2$ の行列式が構成される. この具体例では顕著ではないが, 500 次の式と 3 次のの式の終結式を計算したいときなど、この定義がきわめて有効に働くときがある.
行列式の計算問題に帰着するからである.
の行列式は, サラスの方法ではなくラプラス展開を用いて計算すればよい.
$3\cross 3$$3\cross 3$

196
322

終結式の計算行列式による定義をもちいて. 行列式として計算をおこなうこともできが, 終結式の特徴を生かして計算する方法に以下のものがある.
Colins の subresultant PRS(polynomial remainder sequence)$\deg(A(x))\geq\deg(B(x))$ の $A(x),$ $B(x)$ という環 $R$ の元を係数とする 1 変数多項式が与えられたとき,

1. $R_{\{}(x)=A(x),$ $R_{1}(x)=B(x)$2. $\alpha_{i}R_{i-1}(x)=Q_{i}(x)R_{i}(x)+,\prime 3_{i}lt+1(x)$3. prem$=$$\mathcal{B}_{i}\in R$$(R_{k-1,}\backslash R_{k})=0$という条件をみたす多項式列$r_{i}$$with\alpha_{i},$$R_{1}(x)_{\}\ldots.,$$R_{k}(x)$を PRS という.

$\alpha_{i},$$\beta_{i}$には不定性がある.

leading coeff. $(R_{i}(x)),$ $\delta_{i}=\deg(R_{-1}(x))-\deg(R(x))$ として$\alpha_{i}=\cdot r_{i:}^{\delta_{i}+1}\beta_{1}=(-1)^{\delta_{1}+1},/\beta_{i}=-r_{i-1}\psi_{i}^{\delta_{i}}$$\psi_{1}=-1,$ $\uparrow/^{l})i=(-r_{i-1})^{\delta_{i-1}}\psi_{i-1}^{1-\tilde{\delta}_{iarrow 1}}$

for

for

$2\leq i\leq k,\cdot$$2\leq i\leq k$と選ぶと終結式が計算できる.[5]
補間法も有効に働く, 補間を用いるための準備としてつぎの結果を紹介する.
有限体 GF(p) を係数とする多項式の終結式の計算法$R_{1}=f,$ $R_{2}=g$ とする. ユークリッドの互除法により$R_{3},$$\ldots R_{k}$を計算する, $ni=\deg(R_{i})$として$res(R_{1}, R_{2})=$lcoe $ff(R_{k})^{n_{k-1}}\prod_{i=1}’(-1)^{n_{i}n.+1}1coeff(R_{i\neq 1})^{n-n_{i+2}}k-2:$ .

を計算すると, 有限体 GF(p) を係数とする多項式の終結式が計算できる. 終結式の補間による計算のためには各変数への数値の代入が必須となるが, そのときに主係数が消えた場
合の取り扱いには十分に注意しなければならない. 具体的には, 上記の計算の後その結果への補正が必要となる. 詳しくは. [5] を参照されたい.
323

re

終結式計算の計算量削減のための公式,$\llcorner s_{x}(A_{1}\cross A_{2\}}B)=res_{x}(A_{1}, B)\cross re_{\text{ノ}}s_{x}(A_{2},B)$$res_{x}(A, B_{1}\cross B_{2})=res_{x}(A, B_{1})\cross res_{x}(A, B_{2})$$res_{x}$

.

(1)

(2)

( $m$ の倍数の次数のみ係数をもつ多項式 $A_{7}n$ の倍数の次数のみ係数をもつ多項式 $B$ )$=(r\infty_{x}(A(x^{m}arrow x), B(a:^{m}arrow x))^{\pi\iota}$

これらの定理を, 上手に使って終結式の計算を高速化する. また, 与えられた終結式の問
題を行列式で表現してみると) 計算を効率化するための指針を得られることもある.

(3)

197
3.3

multipolynomial resultant

multipolynomial resultant は, 新しいアイディアを導入しない限り Sylvester の定義を多変数拡張することとなり行列式のサイズが大きくなる. そこで, 多少サイズを小さくする
ような試みがありその代表が Macaulay によるものである. しかし, それでも十分に大きいためさらなる改良が図られた. それが Gelfand-Kapranov-Zelevinsky によるものである.
[4] これらは, その出発点から明らかなように 次の式と 次の式から 1 変数を消去する
場合, その行列式は Sylvester によるものそのものが構成される. 一方で, 関孝和先生の定
義の多変数への拡張も図られている. まず, はじめに触れておかなければならないことは. 次の式において $m=n$ の場合に関孝和先生により構成される $m\cross m$ の行$m$ 次の式と列式には, Cayley による別の構成法が存在することである.[16, pp 355] $m\neq n$ の場合には, Cayley による構成法では余分な因子が入り込むことになるが. それを気にしなければ$n$$\gamma n$$7l$$\acute$

この Cayley の見方は優れており多変数への拡張という点では非常に都合がよい.

そのことに注日して, Dixon はこの Cayley による構成法の多変数への自然な拡張を提案している. [17] 各変数の次数が高い場合には, Gelfand
apranov-Zelevinsky によるものは Dixon
による行列式よりもサイズが小さい, 逆に. 変数の数が多いものについては, サイズが小さいくなるという傾向があるため Dixon による行列式を利用したほうがよい場合が多い.
$- I\nwarrow’$34

グレブナー基底グレブナー基底の定義, 計算法やその高速化につながる Automatic wight generator[10]についてまで記述するほどの紙面に余裕がない. ここでは, 日本数学史の問題を解く上で最も重要な定理 [12, pp 240] をひとつ紹介するのみとする.
定理
は, 項順序に関する簡略グレブナー基底とし, を $Go\subset Q_{<p>}[X]$ となる素数とす
る. $f\in\subset Q_{<p>}[X]$ に対し, $m_{p}(t)\in$ GF $(p)[t]$ を $o_{p}(f)$ の $<\emptyset_{P}(G_{0})>$ に関する最小多項式とする. このとき, モニックな多項式 $m(t)\in Q_{<p>}[t]$ が存在して,$G_{0}$$\prec_{\dot{(}1}$$p$$\deg(m,(t))=\deg(m_{p}(t))$

かつ$m(f)\in<G_{0}>$ならば, $7n(t)$ は $f$ の $<G_{0}>$ に関する最小多項式となる. 定理は. さらに拡張される.

$G_{0}$$\acute$にパラメータ含まれている場合には, 頭係数が消えないようなパラメータへの数値の代入は許される.

この定理は, 終結式とグレブナー基底とを結ぶものである. すなわち, 終結式を計算することで $m(f)\in<G_{0}>$ なるを作ることは容易である. 一方, グレブナー基底が計算できれば $\deg(rn_{\rho}(t))$ の計算も容易にできる. 一般に, 終結式の計算は必要条件変形であり非線形連立代数方程式の解法に応用すると偽因子 (偽の根) が混入する場合ある. 運
よく偽因子が混入しない場合には, この定理が有効に働きその計算が必要十分条件変形であったことが証明されるわけである. では, 不運にも偽因子が混入した場合すなわち$\deg(rn(t))\neq\deg(m_{p}(t))$ の場合には, どのように対処したらよいであろうか?
$7t\iota(f)$198
具体例を用いて: その対処法を述べる、 日本数学史の問題の中に次のような問題がある.
$a,$$f.g,$は, パラメータ$b,$ $c_{:}d,$
$e,$

$h$

$st+wx+yz+u-b=0,$ $st+ut)+yz+w-c=0$$st+\cdot uv+wx+y-d=0,$ $u+w+y+t-e=0,$ $s+u+y+v-f=0$$s+u+y+x-g=0,$ $s+u+?l\rangle+z-h=0$$?lt:+t\iota|?’+y\approx+s-a=0,$の式から$y_{\backslash }w,$$\approx,\cdot x,$$\cdot n,$$v,$ $t$

を消して

$s$

だけの式にせよ$!$

方程式系から Dixon multipolynomial resultant 行列をつくり, その行列を計算すると$s$についての 15 次の多項式 ( の 12 次の多項式) ができる. しかし, $\deg(m_{p}(s))$ を計算す
ると 12 である. この場合には$s^{3}$$s$$\grave$$u\iota’+u)x+yz+S-a=0,$ $st+WX+y$ ご十 $\uparrow l-b=0_{J}.st+r\iota v+yz+u_{/}-C=0$$st+uv+u|x+y-d=0,$ $u+w+y+t-e=0,$ $s+w+y+\iota-f=0$$s+n+y+x-g=0,$ $s+u+w+z-h=0,\underline{s=0}$についてのグレブナー基底を計算し, {1} を確認すると上記の定理に持ち込むことができる.
また, $7n(f)$ はグレブナー基底の計算後, 連立一次方程式を用いても構成できる. 詳しくは, [12, pp.240-248] を参照されたい.

3.5

real root flnding

上記の定理をもちいると最小多項式が計算できる. 最小多項式の係数が整数の場合の実根の探索法は, [9] を参照されたい.

36

倍写像行列

以下では, 具体例として$f_{1}(x_{1}, x_{2})=x_{1}^{2}+x_{2}^{2}-2$,$f_{2}(x_{1;}x_{2})=3x_{1}x_{2}-2$を考える. 項順序は $x_{2}\prec x_{1}$ として全次数逆辞書式順序を用いてグレブナー基底を計算

する.
$G_{1}=\{3\underline{x_{1^{1}}.r_{2}}-2,\underline{x_{1}^{2}}+x_{2}^{2}-2, -3\underline{a:_{2}^{3}}-2x_{1}+6x_{2}\}$

項順序は$x_{2}\prec x_{1}$として辞書式順序を用いてグレブナー基底を計算する.
$G_{2}=\{9\underline{x_{2}^{4}}-18x_{2}^{2}+4, -2\underline{x_{1}}-3x_{2}^{3}+6x_{2}\}$

辞書式順序では.

のみの式が現れるために数値計算において都合が良いように思われるが 1 変数にしたことにより係数の桁が全次数逆辞書式順序に比べて膨張する傾向がある.
$x_{2}$

199

図 1:

$G_{1}$

または$G_{2}$

書く.

と$G_{1}$$G_{2}$の頭項による割り切れる項と割ることのできない単項の識別図の下線の部分は頭項を現している. その頭項を利用して次のような図を塗りつぶされた円がとのそれぞれの頭項を表している. 中抜きの円は, 頭項では割れない項を表し, は頭項で割ることのできる項を表している. 正規化の対象となる多項式は, その多項式の頭項が のものだけでなくその多項式の頭項がグレブナー基底の頭項に一致するものも含まれる. 例えば, 単項式媛はでは i
では中抜きの円に属しているためこれ以上の正規化は望めない. しかし,においては頭項であり正規化によって$-x_{2}^{2}l+2$ となる.
天下りであるが, グレブナー基底に対してその頭項で割れない項を利$G_{1}$$G_{2}$$\cross$$\cross$$G_{1}$$G_{1}$$G_{2}$$G_{1}$

用して次のベクトル$u$を用意する.
$u$$=$$(1,x_{1}.x:_{2_{i}}x_{2}^{2})^{T}$$x_{1}u$$=$$(x_{1\backslash }x_{1\dagger}^{2}x_{1}x_{2_{\grave{\prime}}}x_{1}x_{2}^{2})^{T}$となるが, グレブナー基底を法とする正規化が実行できるものも存在し$x_{1}u\equiv$$\equiv$$x_{1}=\lambda$$(x_{1}, -x_{2}^{2}+2,2/3,2/3x_{2})^{T}$$(\begin{array}{llll}0 1 0 02 0 0 -12/\backslash .3 0 0 00 0 2/3 0\end{array})u$

$mod$

inod

$G_{1}$$G_{1}$とすると、非線形連立代数方程式はグレブナー基底を通して標準固有値問題に変換される. [12, pp. 131-146]

4

数値計算

ホモトピー法とその精度保証については, $[13, pp.146rightarrow 158]$ を参照されたい. ここでは,Krawczyk 法とそれに関連して Bezout の定理と Bernstein の定理を述べることとする.

200
4. lKrawczyk 法と有界領域の全根探索
Krawczyk ,:ま [13, pp.141-146]

4.1.1

非線形連立方程式 $f(x)=0$ を考える. この方法は, 代数方程式以外にも適用できるこ級とする. $U$ の内部におけるある区間 $T$ としとを注意する. $U\subset R^{n},$ $f$ : $Uarrow R^{n}$ を$c=$ Mid $(T)$ を区間 $T$ の中心として, 区間行列 $M$ を$C^{1}$$M=E-L^{-1}F’(T)\backslash$,を考える.
ここで, $E$ は単位行列であり $F’(T)$ は写像 $f$ のヤコビ行列の各要素を定義域 $T$ として区間包囲したものである.
は.l 構成法としては通常 $c=Mid(T)$ においてヤコビ行列の各要素を近似的に評価しその近似逆行列を計算して得るが条件 (4) (5) を満たせば数学的にはどのような構成法を用いてもよい. 区間写像 $K$ を$L^{-1}$$K(T)=c-L^{-1}f(c)+M(T-c)$$(c=$ Mid $(T))$

で定義する. ただし, $f(c)$ は点に対してその値域を無誤差で計算することは一般にはできないため $x_{j}=[ci,$ ci という区間における $f(x)$ の評価とする. ここで,$]$$||M||_{\infty}<1$

(4)

,

(5)

$K(T)\subset T$がただ一つ存在する. ただし, 重は $K(T)$ が $T$ の境界上に辺を根の場合にはこの存在判定は絶対に成立しない. ここで,持たない $T$ の真部分集合と定義する. $K(T)$ が $T$ の境界上に辺を持つことはここでは認めない.
がみたされるならば,$K(T)$ に方程式 $f(x)=0$ の解$x^{*}$$\subset$412

有界領域の全根探索$f(x)=0$ と有界超直方体領域 $S$ が与えられたとき,

1. $G=\{\},$ $H=\{S\}$ とする

2. $H=$$\{\}$

ならば end

3. $Tarrow$ head $(H)$4.

$f(T)\not\supset O$

5.

$T$

ならば 2 へに根が唯一存在するかを Krawczyk 法で判定. 条件をみたすならば $G$ に $T$ を追加.

2へ

6.

$T$

のもっとも長さの長い辺を 1/2 する. それを加. 2 へ

$T_{1},$ $T_{2}$とすると$T_{1},$ $T_{2}$を $H$ の最後に追

201
$G$

は根を含む超直方体のリストとなる.
もし, $K(T)$ が $T$ の境界上に辺を持つ場合にも根の存在を認めてしまうと分割領域の境界上に根が存在する場合には同じ根を異なった領域で 2 回数えるあるいは根として判定することとなる. そのような判定条件の場合, 上記のアルゴリズムの後再度連結した区間について再計算をしなければならないという問題が起きる. 逆に, 根の存在の際に $K(T)$ が$T$の境界上に辺を持たないとすると偶然にも分割領域の境界上に根が存在した場合アルゴ
リズムはその根について存在判定をすることができずかつその根を含む領域では非存在判定もできない. よって, アルゴリズムは停止しない. そのような場合には, 初期領域 をわずかに大きくすることで回避できる. プログラムの簡便性なども考慮すると $K(T)$ がの境界上に辺を持たないとするのが妥当である.
$S$

$T$

4.1.3

有界領域の全根探索の speed up

有界領域における全実根の探索の改良として, 以下 3 つをあげることができる.
1. 非存在判定の強化$T$$K(T)$

このような場合には, $T$ に根がないことが証明できる.

であるが, $K(T)$ になかに 2 つ以上の根があるその場合には, $T$ ではなく$K(T)$ を二分割する.
$K(T)\subset T$202
この場合には, 斜線の部分のみを調べればよいことになる,

414

無限領域探索問題の有界領域探索問題への帰着

ホモトピー法により Bernstein の定理 [2] から導かれる個数分の複素根を求めた後. 得られた根を Krawczvk 法により実と複素に分離すれば無限領域における実根をすべてもとめ$\acute$ることも可能であるが、ここでは別のアプローチを模索することにする.
上記のような有界領域探索問題の解法が与えられると 次のような方法で. 無限領域探索問題を扱うことができるように誤解を招くのであらかじめ注意をする.
$\grave$$\{\begin{array}{l}x_{1}^{2}+2x_{1}+x_{2}^{2}-2x_{2}-7= 0x_{1}^{2}-6x_{1}+x_{2}^{2}-4x_{2}+9 = 0\end{array}$が与えられたとき, はじめに Krawczyk 法を用いて $-1\leq x_{1}\leq 1,$ $-1\leq x_{2}\leq 1$ のすべての根を調べる. 次に, $x_{1}arrow 1/y_{1}$ とする.
$\{\begin{array}{l}y_{1_{\sim}}^{2_{X_{9}^{2}-2y_{1}^{2}x_{2}-7y_{1}^{2}}}+2y_{1}+1 = 0y_{1}^{2}x_{2}^{2}-4y_{1}^{2}x_{2}+9y_{1}^{2}-6y_{1}+1 = 0\end{array}$$-1\leq y_{1}\leq 1,$ $-1\leq x_{2}\leq 1$のすべての根を調べる. さらに,

$X_{2}^{i}arrow 1/y_{2}$とする.

$\{\begin{array}{l}x_{1}^{2}y_{2}^{2}+2x_{1}y_{2}^{2}-7y_{2}^{2}-2y_{2}+1 = 0X_{1}^{22_{-6x_{1}+9_{J_{2}^{2}}}}y_{2}y_{2}^{2}\not\in-4y_{2}+1 = 0\end{array}$$-1\leq x_{1}\leq 1,$ $-1\leq/l2\leq 1$のすべての根を調べる.

最後に,$\{\begin{array}{ll}-7y_{1}^{2}y_{2}^{2}+2y_{1}y_{2}^{2}+y_{2}^{2}-2y_{1}^{2}y_{2}+y_{1}^{2} = 09y_{1/^{2}-6y_{1}y_{2}^{2}+y_{2}^{2}-4y_{1}^{2}y_{2}+y_{1}^{2}}^{2_{2_{2}}} = 0\end{array}$の $-1\leq y_{1}\leq 1,$ $-1\leq y_{2}\leq 1$ のすべての根を調べる.

(6)以上より, 有界な領域のすべての根を調べることができるように思える. しかし、それは間違いである. 最後の方程式に注目する. 式 (6) は, 原点 $(y_{1}., y_{2})=(0,0)$ に重根をもつ. もちろん, それは偽の解である. 偽の解を得ることがこの手法の問題なのではなく, $(y_{1}, y_{2})=(0,0)$ が重根であることがこの手法の問題なのである. Krawczyk 法は、重根には非対応である. よって, アルゴリズムが停止しないためこのような手法を用いることはできない. 計算手順から明らかなように無限遠方の根がこの手法の邪魔をする. 非線形連立代数方程式には, 複素根まで含めて根の個の定理と Bernstein の定理 [2] である. B\’ezout
数の上界を計算できる定理がある.
の定理では, 無限遠方の解まで含めて根の個数を数える. 一方で, Bernstein の定理は数えない. 少なくとも, 現時点でいえることは B\’ezout の定理と Bernstein の定理が異なった数を出すときこの手法は使えないという否定的な結果のみである. より確実な手法を次に述べる.
$Be\ovalbox{\tt\small REJECT} zout$

203
4.1.5

Gerschgorin の定理 [1]グレブナー基底の計算の後. 倍写像行列を変数の種類分構成し以下の定理を用いること
で根の存在範囲を構成できる与えられた 次正方行列 $A=((\iota_{i,j})$ の圃有値の位置を事前に推定する方法がある. いま,とおく. 1)
の固
$n$

$A$

$r_{i}= \sum_{j=1(j\neq i)}^{n}|a_{i_{2}j}|\dot{!}c_{j}=\sum_{i=1(i\neq j)}^{n}|\iota_{i.j}|$有値は複素平面のを中心とする半径 の円 $R_{i}=\{\sim?:|\approx-a_{i,i}|\leq r_{i}\}$ のユニオンにある. 2) $A$ の固有値は複素平面のを中心とする半径 の円 $C_{j}=\{z:|z-a_{j_{l}j}|\leq c_{j}\}$のユニオンにある. この定理を用いると無限領域探索問題は, 有限領域探索問題に常に帰着できる. これ以外にも方法がある. 終結式を用いて最小多項式を因子として含む式$a_{i_{t}i}$$\cup R_{i}$$7_{i}$$a_{jj}$$c_{i}$$\cup C_{j}$を高速に計算できた場合, 以下の定理を用いれば根の限界が計算できる.
定理 [9] 実係数の方程式 $x^{n}+aix^{n-1}+\cdots+a_{n}=0$ において, 負の係数をすれば $G_{4}=2$ niax$a_{\alpha},$$a_{\beta},a_{\gamma},$$\cdots$とが正根の限界である. $xarrow-x$ により負根の限界を計算できる. 仮に, 最小多項式以外の因子を含んでいても Krawczyk 法が$[(|a_{\alpha}|)_{:}^{1/\alpha}(|a_{/};|)^{1/\beta},$ $(|a_{\gamma}|)^{1/\gamma},$$\cdots]$

その領域を除外してくれるので問題はない.

5

日本数学史の問題

5.1

6 角形の辺の長さの関係の導出$(X_{1}-b)^{2}+y_{1}^{2}=c^{2},$ $(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}=e^{2},$$x_{2}^{2}+y_{2}^{2}=f_{X_{1}+y_{1}^{2}=a^{2},(x_{2}-b)^{2}+?/^{2}=d^{2}}^{22’},2$

これより, グレブナー基底を用いて$a^{2}d^{2}(b^{2}+c^{2}+e^{2}+f^{2})-a^{2}d^{4}-a^{4}d^{2}+l_{1}^{2}e^{2}(a^{2}+c^{2}+d^{2}+f^{2})-b^{2}e^{4}-b^{4}e^{2}-c^{2}f^{4}$$+c^{2}f^{2}(a^{2}+b^{2}+e^{2}+d^{2})^{4}-c^{1}f^{2}-a^{2}b^{2}c^{2}-a^{2}e^{2}f^{2}-b^{2}f^{2}(l^{2}-c^{2}d^{2}e^{2}=0$という 22 項の式を得る. 左辺を $F(\alpha, b, c, d, e, f)$ とする.

(7)

204

6 角形は,て$U_{1}$と$U_{2}$$U_{1}=F(\alpha, b_{6^{\backslash }}, c_{4}, g_{6}, h_{6},0_{()}\backslash ),$$U_{2}=G(a_{6}, \alpha, d_{6}, e_{6}, f_{6}, h_{6}, i_{6},j_{6})$として$\alpha$の終結式 $K(a_{6}, b_{6}, c_{6}, d_{6}, e_{6}, f_{6}, g_{6}, h_{6}, i_{6},j_{6})=res_{\alpha}(U_{1}, b^{r_{2}})$ を計算する.

につい$U_{3}=$とすると, $K((\iota_{6}.b_{6}, c_{6}, d_{6}, e_{6}, f_{6,96}, h_{6}, i_{6},j_{6})=[res_{\alpha}(U_{1}, U_{3})]^{2}$について丁寧にみると $II_{1}=(U_{1}(0))+(U_{1}(2))\alpha^{2}+(U_{1}(4))\alpha^{4},$ $II_{3}=(U_{3}(0))+$$H(a_{6}, \alpha, d_{6}, e_{6}, f_{6}, h_{6}, i_{6},j_{6})$となる.

$U_{1},$ $U_{3}$$(L^{r_{d}}\cdot(2))\alpha^{2}+(U_{3}(4))\alpha^{4}+(U_{3}(6))\alpha^{6}+(U_{3}(8))\alpha^{8}$という構造をしている.

$U_{1}’=(U_{1}(0))+$$(U_{1}(2))\beta+(U_{1}(4))\beta^{2},$ $U_{3}’=(U_{3}(0))+(U_{3}(2))\beta+(U_{3}(4))\beta^{2}+(U_{3}(6)),\mathcal{B}^{3}+(U_{3}(8))’\beta$

4 とすると,終結式計算の計算量削減のための公式 (3) が利用でき, $K(a_{6}, b_{6\prime}.c_{6}, h, e_{6}, f_{6}, g_{6}, h_{6}, i_{6},j_{6})=$となる.
は, 273123 項である. この終結式の計算は, 関孝和先生の定義とラプラス展開を利用して行った.
$[res_{\beta}(U_{1}’, U_{3}’)]^{4}$$res_{\beta}(U_{1}’, U_{3}’)$

205
5.2

1458 次式の問題

521

1458 次式の導出

式 (7) のほかに,$d^{3}-b^{3}=271,$ $b^{3}-c^{3}=217,$ $c^{3’}-a^{l}\backslash =60.8,$ $a^{3}-e^{3}=326.2,\cdot e^{3}-f^{3}t=61$(8)という条件も課す. 終結式を利用して $f$ のみの式を作ると 1458 次式が得られる. この計算には, さまざまな工夫が考えられる. その中で, 他の問題にも使える終結式計算の効率化のための工夫として, 式 (8) の次数が低いことから擬剰余を用いて $3\cross 3$ の行列を構成
し, ラプラス展開を用いてその行列式を展開することで終結式計算する方法をあげる. これ以外にも, この問題に特化したさまざまな工夫が考えられるが, ここでは省略する. [11]一方で, グレブナー基底を計算し, 有限体上で の最小多項式を計算すると 1458 次式になるために, この終結式の計算は必要十分条件であったことがわかる. すなわち, 1458 次式の中には偽因子は混入していない.
$f$

5.2.2

real root flnding

倍写像行列を作り, Gerschgorin の定理をもちいて実根の存在範囲を計算すると$a=[-52589152874765992, 52589152874765992]$$b=[-421460234S27\ulcorner 00655,421460234827_{0}^{r}0655]$$c=[-914711826294707S\} 9147118262947078]$$d=[-30423673761003S74,30423673761003S74]$$e,$$=[-14776817925389682_{\dot{\Gamma}}147768179253S96S2]$294561020909, 15965294561020909とわかる. この範囲において, Krawczyk 法を適用すると実根は 8 つであり, すべてが正の根は唯一であることが証明できる.
$f=[-1596_{0}^{r}$

$]$

参考文献
[1] 有本卓, 数値解析 (I), コロナ社, 東京, 1997.
[2] D. N. Bernshtein, $:rr$} number of roots of a system of equations,” Functional Analysis and Appl., 9(3), 1975, pp. 183-185.
$1e$[3] David Cox,Donal $O$ ’ Shea,John Little: グレブナー基底 1 代数幾何と可換代数におけるグレブナー基底の有効性 (大杉英史, 日比孝之, 北村知徳訳), シュプリンガー.
フェアラーク東京, 東京, 2000.

[4] J. F. Canny, I. Z. Emiris: An Efficient Algorithm for the Sparse Resultant, Applied
Algebra, Algebraic Algorithms and Error-Correcting Codes, Intemational Conference, 1993.

206[5] K. O. Geddes, Stephen R. Czapor. George Labahn, Keith O. Geddes, S. R. Czapor, G.
Labahn. Algorithms for Computer Algebra. Kluwer Academic Pub., United States,
1992.
[6] 平山諦: 関孝和その業績と伝記, 恒星社版, 東京,1974.
$[$

7 広田良吾: 行列式とパフイアン (1), 日本応用数理学会誌 「応用数理」 , $14(1)$ , 2004,
pp.62-66.
$]$[8] 木村欣司, 多項式行列の行列式の補間による計算 II, 京都大学数理解析研究所講究録 1514 「Computer Algebra-Desingn of Algorithms, Implementations and $Applica-$
tions , 2005, pp. $176arrow 182$ .
$\rfloor$[9] 木村欣司, 固有値 / 特異値計算ライブラリの性能評価のための数式処理のアルゴリ
ズム, 京都大学数理解析研究所講究録 1505 「計算科学の基盤技術とその発展 Computational Science–Fundainental and Emerging Technology , 2005, pp. 1-13.
$\rfloor$[10] K. Kimura, M. Noro: Automatic weight generator for the Buchberger algorithm, In

Proceedings of International Conference on Mathematical Aspects of Computer andInformation Sciences (MACIS2006), 2006, pp.33-44.
[11] 野呂正行: private communication.
[12] 野呂正行, 横山和弘: グレブナー基底の計算基礎篇, 東京大学出版会, 東京, 2003.
[13] 大石進一: 非線形解析入門. コロナ社, 東京, 2000.
[14] 佐々木建昭, 金田康正, 渡辺隼郎: 終結式計算アルゴリズムと判別式の計算./ 情報処理学会研究報告 「プログラミング」 , Vol.1981 No.28, 1981.

[15] 佐々木建昭, 村尾裕一: 記号行列に対する効率的なガウス消去法, 情報処理学会研究
報告 「プログラミング」 , Vol.1979 No.50, 1980.

[16] 高木貞治: 代数学講義 (改訂新版), 共立出版, 東京, 1965.
[17] Deepak Kapur. Tushar Saxena, Lu Yang: Algebraic and geometric reasoning using
Dixon resultants, International Conference on Symbolic and Algebraic Computationarchive, Proceedings of tlie intemational symposium on Symbolic and algebraic computation, 1994, pp.99-107.