徐 嘉

(西南民族大學(xué)數(shù)學(xué)學(xué)院，四川 成都 610041)

非線性代數(shù)系統(tǒng)求解是計(jì)算代數(shù)中的基本問(wèn)題.這個(gè)問(wèn)題出現(xiàn)在了需要處理多項(xiàng)式方程的符號(hào)和數(shù)值技術(shù)當(dāng)中.作為表示或約束，在計(jì)算機(jī)代數(shù)，魯棒分析，幾何造型的應(yīng)用中使用了大量的多項(xiàng)式方程[1-2].然而眾所周知，一般情況下非線性代數(shù)系統(tǒng)是無(wú)法求出所謂"精確解"的.退而求其次，零點(diǎn)的隔離被當(dāng)作是代數(shù)系統(tǒng)的精確解的替代(代數(shù)系統(tǒng)的解常常也稱(chēng)為零點(diǎn)).在代數(shù)系統(tǒng)的自身結(jié)構(gòu)研究以及應(yīng)用方面，零點(diǎn)的隔離起到了基本的作用.本文中我們主要研究實(shí)系數(shù)方形代數(shù)系統(tǒng)實(shí)零點(diǎn)的隔離.

方形代數(shù)系統(tǒng)是指變?cè)獋€(gè)數(shù)與方程個(gè)數(shù)相同的代數(shù)系統(tǒng).隔離代數(shù)系統(tǒng)的實(shí)零點(diǎn)就是尋找一系列互不相交的Box(區(qū)間的直積)，每個(gè)Box內(nèi)精確地包含一個(gè)零點(diǎn).系統(tǒng)

在空間?n中的一個(gè)零點(diǎn)x*，如果滿(mǎn)足Jacobian矩陣Jf(x*)是非奇異的，則稱(chēng)x*是實(shí)正則零點(diǎn).我們還需要進(jìn)一步的假設(shè)給定的系統(tǒng)僅僅只有有限個(gè)實(shí)正則零點(diǎn).對(duì)非正則零點(diǎn)的處理可參考文獻(xiàn)[3]，本文不多涉及.

有許多的方法可以被應(yīng)用到代數(shù)系統(tǒng)實(shí)零點(diǎn)的隔離.一種較常用的思想是將原始系統(tǒng)轉(zhuǎn)化為三角列形式，再對(duì)三角列進(jìn)行零點(diǎn)隔離.被使用的消去工具有Groebner基方法[4]，吳方法[5]，正則列方法[6]等等.但是消去過(guò)程往往需要大量的符號(hào)計(jì)算，導(dǎo)致效率不高.這些方法都各有自身特點(diǎn)和優(yōu)點(diǎn).

本文的方法主要使用Dixon結(jié)式[7-8]和伴隨多項(xiàng)式方法[9].在第1節(jié)，簡(jiǎn)單地介紹了Dixon結(jié)式，以及怎樣去獲得初始的Box，使得給定系統(tǒng)的所有實(shí)正則零點(diǎn)都位于這些Box中.第2節(jié)，首先介紹了伴隨多項(xiàng)式的概念，總結(jié)了伴隨多項(xiàng)式的4個(gè)基本性質(zhì).接著給出了如何檢測(cè)初始的Box中是否存在給定系統(tǒng)的零點(diǎn)的方法.第3節(jié)，建立了一個(gè)隔離代數(shù)系統(tǒng)實(shí)正則零點(diǎn)的算法SAS-Zeros.

1 Dixon結(jié)式

1779年，Bezout研究了計(jì)算兩個(gè)單變?cè)囗?xiàng)式的結(jié)式.它是用較低階(相對(duì)于Sylvester行列式)的行列式來(lái)表示結(jié)式.下面的構(gòu)造方法是由Cayley給出的.

給定兩個(gè)d次多項(xiàng)式f(x)，g(x)，行列式

是關(guān)于x和α的多項(xiàng)式.注意到當(dāng)x=α?xí)rD(x，α)=0.

因此，

是關(guān)于α的d-1次多項(xiàng)式.即

這里ci(x)是關(guān)于x的≤d-1次多項(xiàng)式.如果x0是f(x)和g(x)的公共零點(diǎn)，則D(x0，α)=0對(duì)任意α，這蘊(yùn)含了

很明顯(1)是關(guān)于d個(gè)變?cè)獂0，…，xd-1的線性方程組.這個(gè)方程組有非平凡解，因?yàn)閤0=1.所以其系數(shù)矩陣的行列式為0.這個(gè)行列式就是著名的Bezout結(jié)式.

1908年，Dixon推廣了這個(gè)思想.構(gòu)造了一般的Bezout結(jié)式.Dixon[7]的工作之后，人們逐漸發(fā)現(xiàn)Dixon結(jié)式在較大范圍的情況是奇異的，也就是res(f1，…，fn)恒等于0，因此得不到關(guān)于原方程組的有用信息.

一個(gè)重要的進(jìn)展發(fā)生在1994年，D.Kapur，T.Sexena，Lu Yang(楊路)在文獻(xiàn)[8]中建立著名的KSY條件，并給出計(jì)算Dixon結(jié)式的高效率算法.

Dixon結(jié)式的基本用法是消元，即從k+1個(gè)方程中消去k個(gè)變?cè)?對(duì)給定的方形系統(tǒng)，Dixon結(jié)式在本文中的主要作用是獲得單個(gè)變?cè)亩囗?xiàng)式.

下面看個(gè)例子.

例1[12]給定代數(shù)系統(tǒng)

第一步:將系統(tǒng)看作變?cè)獂2，x3，x4的系統(tǒng)，計(jì)算其Dixon結(jié)式，我們得到關(guān)于x1的多項(xiàng)式(相當(dāng)于消去了變?cè)獂2，x3，x4).

完全類(lèi)似的，可以得到另外三個(gè)單變?cè)囗?xiàng)式

系統(tǒng)(2)的一個(gè)解需要滿(mǎn)足上面的四個(gè)單變?cè)囗?xiàng)式.

第二步:分別對(duì)上面的四個(gè)單變?cè)囗?xiàng)式做實(shí)根隔離[1]，獲得隔離區(qū)間集(區(qū)間長(zhǎng)度可選擇).

第三步:依次從集合S1，…，S4中各取一個(gè)區(qū)間作直積，我們就獲得了由54個(gè)Box組成的集合SB.如果用1，2，3，4，5的一個(gè)可重復(fù)排列作下標(biāo)來(lái)表示這些Box，例B1111表示依次從S1，…，S4取第一個(gè)區(qū)間所獲得的Box，就是

于是SB={Bi1，i2，i3，i4}.系統(tǒng)(2)的所有實(shí)正則零點(diǎn)都位于這些Box中，并且每個(gè)Box中至多有一個(gè)零點(diǎn).剩下的工作就是判斷SB中哪些Box有系統(tǒng)的零點(diǎn)，哪些沒(méi)有.這個(gè)問(wèn)題的回答構(gòu)成了下一節(jié)的主要內(nèi)容.

2 伴隨多項(xiàng)式與實(shí)正則零點(diǎn)的檢測(cè)

2.1 伴隨多項(xiàng)式與無(wú)實(shí)零點(diǎn)的檢測(cè)

給定BoxB=[a1，b1]×…×[an，bn]和實(shí)系數(shù)方形代數(shù)系統(tǒng)

一個(gè)基本的問(wèn)題是:f(x)=0在BoxB上是否存在零點(diǎn)?本文的方法主要依賴(lài)于下面的伴隨多項(xiàng)式概念.

定義[9]多項(xiàng)式f∈?[x1，…，xn].f相對(duì)于變?cè)獂i次數(shù)記為di(i=1，…，n)對(duì)BoxI=[a1，b1]×…×[an，bn]， 我們定義

fI稱(chēng)為f相對(duì)于BoxI的伴隨多項(xiàng)式.

注意到映射是一一映射.這里Int(I)是指BoxI的內(nèi)部.

下面總結(jié)了部分伴隨多項(xiàng)式的基本性質(zhì)，證明都非常簡(jiǎn)單.

伴隨多項(xiàng)式的基本性質(zhì)

①如果fI的所有非零系數(shù)都是正(負(fù))數(shù)，則

②多項(xiàng)式f在BoxI內(nèi)部Int(I)存在零點(diǎn)，當(dāng)且僅當(dāng)fI在(0，+∞)n上存在零點(diǎn).

③如果fI的所有非零系數(shù)都是正(負(fù))數(shù)，則多項(xiàng)式f在BoxI內(nèi)部Int(I)沒(méi)有零點(diǎn).

④如果fI的所有非零系數(shù)都是正(負(fù))數(shù)且f在BoxI的所有頂點(diǎn)上的值都不是0，則多項(xiàng)式f在整個(gè)BoxI(包括內(nèi)部和邊界)上沒(méi)有零點(diǎn).

這些性質(zhì)雖然簡(jiǎn)單，但應(yīng)用卻非常廣泛.比如根據(jù)性質(zhì)④可以容易地證明代數(shù)系統(tǒng)在給定的Box上沒(méi)有實(shí)解.

在文獻(xiàn)[9]中證明了如下結(jié)果，它顯示了用伴隨多項(xiàng)式方法檢測(cè)代數(shù)系統(tǒng)(不一定是方形的)無(wú)實(shí)零點(diǎn)是完全的方法.

定理1設(shè)多項(xiàng)式f1，…，fm∈?[x1，…，xn]，BoxΛ??n.方程組f1=0，…，fm=0在BoxΛ上沒(méi)有零點(diǎn)，當(dāng)且僅當(dāng)存在正常數(shù)δ(與BoxΛ有關(guān))，使得對(duì)于任意BoxI?Λ，當(dāng)BoxI的長(zhǎng)度小于δ時(shí)，伴隨多項(xiàng)式f1I，…，fmI中至少一個(gè)fiI的非零系數(shù)全是正(或負(fù))數(shù)且fi在BoxI的所有頂點(diǎn)上的值不為0.

2.2 存在實(shí)零點(diǎn)的檢測(cè)

1940年，Miranda[10]證明了關(guān)于連續(xù)函數(shù)零點(diǎn)存在的一個(gè)定理.它的一般形式如下.

定理2(Miranda) 設(shè)BoxI=[a1，b1]×…×[an，bn]，ai＜bi.記

I-i={x∈I:xi=ai}，I+i={x∈I:xi=bi}映射f=(f1，…，fn):I→Rn是連續(xù)的.如果滿(mǎn)足

fi(x)fi(y)＜0，?x∈I-i，?y∈I+i，i=1，…，n則方程f=(0，…，0)在I上有一個(gè)解.

Miranda定理在應(yīng)用上有一個(gè)障礙，即條件

如何檢測(cè)?

1978年Kioustelidis在文獻(xiàn)[11]中，以及Moor和Kioustelidis在文獻(xiàn)[12]中對(duì)連續(xù)函數(shù)使用數(shù)值方法來(lái)檢測(cè)上述條件(3).但是該方法對(duì)符號(hào)計(jì)算并不合適.另外，文獻(xiàn)[11-12]中已經(jīng)指出，Miranda定理對(duì)初始的方程組可能并沒(méi)有效果.需要考慮方程組

這里A是n×n的可逆矩陣.方程組g(x)=0與方程組f x()=0具有相同的零點(diǎn).一個(gè)恰當(dāng)?shù)倪x擇是令

其中Jf(x)是f的Jacobian矩陣，m是BoxI的中點(diǎn).

定義2非零多項(xiàng)式f，g∈?[x1，…，xn].稱(chēng)多項(xiàng)式對(duì)(f，g)具有相對(duì)符號(hào)性質(zhì)，如果其中一個(gè)多項(xiàng)式的非零系數(shù)都是正數(shù)同時(shí)另一個(gè)的非零系數(shù)都是負(fù)數(shù).

對(duì)代數(shù)系統(tǒng)，結(jié)合伴隨多項(xiàng)式的基本性質(zhì)，我們有如下推論2.

推論2給定BoxI=[a1，b1]×…×[an，bn]和實(shí)系數(shù)方形代數(shù)系統(tǒng)f(x)=0.Jf(x)是f的Jacobian矩陣，m是BoxI的中點(diǎn).假設(shè)行列式|Jf(m)|≠0.令

如果伴隨多項(xiàng)式對(duì)

具有相對(duì)符號(hào)性質(zhì)，則代數(shù)系統(tǒng)f(x)=0在BoxI上至少有一個(gè)零點(diǎn).

證明由伴隨多項(xiàng)式的基本性質(zhì)1，如果伴隨多項(xiàng)式對(duì)

具有相對(duì)符號(hào)性質(zhì)，則顯然有

由Miranda定理，代數(shù)系統(tǒng)g(x)在BoxI上至少有一個(gè)零點(diǎn).即代數(shù)系統(tǒng)f(x)=0在BoxI上至少有一個(gè)零點(diǎn).

推論2比原始的Miranda定理應(yīng)用方便許多，它僅僅只需要檢查多項(xiàng)式的系數(shù)的符號(hào)就可以了.

3 算法

根據(jù)第2節(jié)的主要結(jié)果，我們能夠建立如下算法

算法SAS-Zeros

輸入:整系數(shù)的方形代數(shù)系統(tǒng)f(x)∈Z[x1，…，xn]n.

輸出:正則零點(diǎn)的隔離Box集合.

①依次計(jì)算系統(tǒng)f (x)=0關(guān)于變?cè)獂1，…，，…，xn(i=1，…，n)的Dixon結(jié)式(記號(hào)x1，…，，…，xn表示去掉變?cè)獂i).獲得僅含單個(gè)變?cè)亩囗?xiàng)式D1，…，Dn.

②令t:=2，區(qū)間長(zhǎng)度設(shè)定為10-2，隔離D1，…，Dn的實(shí)根.獲得區(qū)間集Si，i=1，…，n，并記Si中元素個(gè)數(shù)為.計(jì)算Si的直積，獲得Box的集合SB

③使用伴隨多項(xiàng)的基本性質(zhì)4排除SB中不含有系統(tǒng)f(x)=0實(shí)零點(diǎn)的Box.剩余Box的集合記為SR.

④使用推論2判斷SR中的Box是否含有f(x)=0的實(shí)零點(diǎn).將返回"是"的Box的集合記為SY.

⑤如果SY=SB，則程序停止.如果SY≠SB，則令t:=t+1，重復(fù)以上的步驟2至5.

⑥輸出:集合SY.

程序結(jié)束.

討論算法SAS-Zeros的正確性是明顯的.步驟1的計(jì)算可能失敗.因?yàn)镈ixon結(jié)式并不是一個(gè)完全的方法，作為替代的方法可以使用Macaulay結(jié)式，Wu方法或Groebner基方法.算法SAS-Zeros可能不終止，主要原因是重零點(diǎn)沒(méi)有考慮.前文已指出對(duì)重零點(diǎn)的處理可參考文獻(xiàn)[3].使用Maple平臺(tái)，我們實(shí)現(xiàn)了上述算法.

4 結(jié)論

針對(duì)方形的代數(shù)系統(tǒng)，本文提出了一種隔離實(shí)正則零點(diǎn)的方法.方法主要分兩大步，首先使用符號(hào)計(jì)算工具(結(jié)式或Groebner基方法均可)去獲得單個(gè)變?cè)枰獫M(mǎn)足的方程，并對(duì)單變?cè)囗?xiàng)式實(shí)施實(shí)根隔離，從而得到一系列的Box.這些Box包含了原代數(shù)系統(tǒng)所有的實(shí)正則零點(diǎn).然后利用伴隨多項(xiàng)式方法，區(qū)分出不含零點(diǎn)的Box和僅僅含有一個(gè)零點(diǎn)Box.計(jì)算實(shí)例顯示出了該方法是簡(jiǎn)潔有效的.其中的關(guān)鍵技術(shù)是伴隨多項(xiàng)式方法.類(lèi)似的代換方法已被應(yīng)用于許多其它問(wèn)題[13-14].