實正則方形代數系統

徐 嘉

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

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

方形代數系統是指變元個數與方程個數相同的代數系統.隔離代數系統的實零點就是尋找一系列互不相交的Box(區(qū)間的直積)，每個Box內精確地包含一個零點.系統

在空間?n中的一個零點x*，如果滿足Jacobian矩陣Jf(x*)是非奇異的，則稱x*是實正則零點.我們還需要進一步的假設給定的系統僅僅只有有限個實正則零點.對非正則零點的處理可參考文獻[3]，本文不多涉及.

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

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

1 Dixon結式

1779年，Bezout研究了計算兩個單變元多項式的結式.它是用較低階(相對于Sylvester行列式)的行列式來表示結式.下面的構造方法是由Cayley給出的.

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

是關于x和α的多項式.注意到當x=α時D(x，α)=0.

因此，

是關于α的d-1次多項式.即

這里ci(x)是關于x的≤d-1次多項式.如果x0是f(x)和g(x)的公共零點，則D(x0，α)=0對任意α，這蘊含了

很明顯(1)是關于d個變元x0，…，xd-1的線性方程組.這個方程組有非平凡解，因為x0=1.所以其系數矩陣的行列式為0.這個行列式就是著名的Bezout結式.

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

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

Dixon結式的基本用法是消元，即從k+1個方程中消去k個變元.對給定的方形系統，Dixon結式在本文中的主要作用是獲得單個變元的多項式.

下面看個例子.

例1[12]給定代數系統

第一步:將系統看作變元x2，x3，x4的系統，計算其Dixon結式，我們得到關于x1的多項式(相當于消去了變元x2，x3，x4).

完全類似的，可以得到另外三個單變元多項式

系統(2)的一個解需要滿足上面的四個單變元多項式.

第二步:分別對上面的四個單變元多項式做實根隔離[1]，獲得隔離區(qū)間集(區(qū)間長度可選擇).

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

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

2 伴隨多項式與實正則零點的檢測

2.1 伴隨多項式與無實零點的檢測

給定BoxB=[a1，b1]×…×[an，bn]和實系數方形代數系統

一個基本的問題是:f(x)=0在BoxB上是否存在零點?本文的方法主要依賴于下面的伴隨多項式概念.

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

fI稱為f相對于BoxI的伴隨多項式.

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

下面總結了部分伴隨多項式的基本性質，證明都非常簡單.

伴隨多項式的基本性質

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

②多項式f在BoxI內部Int(I)存在零點，當且僅當fI在(0，+∞)n上存在零點.

③如果fI的所有非零系數都是正(負)數，則多項式f在BoxI內部Int(I)沒有零點.

④如果fI的所有非零系數都是正(負)數且f在BoxI的所有頂點上的值都不是0，則多項式f在整個BoxI(包括內部和邊界)上沒有零點.

這些性質雖然簡單，但應用卻非常廣泛.比如根據性質④可以容易地證明代數系統在給定的Box上沒有實解.

在文獻[9]中證明了如下結果，它顯示了用伴隨多項式方法檢測代數系統(不一定是方形的)無實零點是完全的方法.

定理1設多項式f1，…，fm∈?[x1，…，xn]，BoxΛ??n.方程組f1=0，…，fm=0在BoxΛ上沒有零點，當且僅當存在正常數δ(與BoxΛ有關)，使得對于任意BoxI?Λ，當BoxI的長度小于δ時，伴隨多項式f1I，…，fmI中至少一個fiI的非零系數全是正(或負)數且fi在BoxI的所有頂點上的值不為0.

2.2 存在實零點的檢測

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

定理2(Miranda) 設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ù)的.如果滿足

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

Miranda定理在應用上有一個障礙，即條件

如何檢測?

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

這里A是n×n的可逆矩陣.方程組g(x)=0與方程組f x()=0具有相同的零點.一個恰當的選擇是令

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

定義2非零多項式f，g∈?[x1，…，xn].稱多項式對(f，g)具有相對符號性質，如果其中一個多項式的非零系數都是正數同時另一個的非零系數都是負數.

對代數系統，結合伴隨多項式的基本性質，我們有如下推論2.

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

如果伴隨多項式對

具有相對符號性質，則代數系統f(x)=0在BoxI上至少有一個零點.

證明由伴隨多項式的基本性質1，如果伴隨多項式對

具有相對符號性質，則顯然有

由Miranda定理，代數系統g(x)在BoxI上至少有一個零點.即代數系統f(x)=0在BoxI上至少有一個零點.

推論2比原始的Miranda定理應用方便許多，它僅僅只需要檢查多項式的系數的符號就可以了.

3 算法

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

算法SAS-Zeros

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

輸出:正則零點的隔離Box集合.

①依次計算系統f (x)=0關于變元x1，…，，…，xn(i=1，…，n)的Dixon結式(記號x1，…，，…，xn表示去掉變元xi).獲得僅含單個變元的多項式D1，…，Dn.

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

③使用伴隨多項的基本性質4排除SB中不含有系統f(x)=0實零點的Box.剩余Box的集合記為SR.

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

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

⑥輸出:集合SY.

程序結束.

討論算法SAS-Zeros的正確性是明顯的.步驟1的計算可能失敗.因為Dixon結式并不是一個完全的方法，作為替代的方法可以使用Macaulay結式，Wu方法或Groebner基方法.算法SAS-Zeros可能不終止，主要原因是重零點沒有考慮.前文已指出對重零點的處理可參考文獻[3].使用Maple平臺，我們實現了上述算法.

4 結論

針對方形的代數系統，本文提出了一種隔離實正則零點的方法.方法主要分兩大步，首先使用符號計算工具(結式或Groebner基方法均可)去獲得單個變元需要滿足的方程，并對單變元多項式實施實根隔離，從而得到一系列的Box.這些Box包含了原代數系統所有的實正則零點.然后利用伴隨多項式方法，區(qū)分出不含零點的Box和僅僅含有一個零點Box.計算實例顯示出了該方法是簡潔有效的.其中的關鍵技術是伴隨多項式方法.類似的代換方法已被應用于許多其它問題[13-14].