附錄 非線性代數(shù)方程組求解方法

附錄非線性代數(shù)方程組的求解方法

由n個變量n個方程（n>1）組成的非線性代數(shù)方程組（簡稱為非線性方程組）可表示為：(1)

式中，為n個待定的變元組成的列陣，

為定義在維子空間

上的維向量值函數(shù)，即

若中至少有一個為非線性函數(shù)，則稱(1)為非線性方程組。n求非線性方程組數(shù)值解的一般迭代法的迭代格式為:上海海運大學(xué)專用（2）

式中，G為迭代矩陣。上述迭代格式必須滿足：1)適定性。即由迭代格式（2）得到的序列是適定的，也就是，對均成立；2)收斂性。若是方程組（1）的解，則

3)在給定精度內(nèi)求得解的近似解的工作量較少。在上述三個要求中，前兩個要求是必須滿足的。第三個要求是計算復(fù)雜性問題，是衡量一個算法好壞的標(biāo)志。迭代格式（2）的含意是明確的。即求解時，必須取定一個初始點（或初值），通過逐次迭代，最終求得方程組（1）的滿足精度要求的數(shù)值近似解。上海海運大學(xué)專用如果一個數(shù)值迭代法對初值沒有本質(zhì)上的限制，則稱這種方法為大范圍收斂的方法，如同倫法和區(qū)間分析法等；否則，稱為一般迭代法。除必須滿足適定性和收斂性條件外，還應(yīng)考慮迭代格式的收斂速度。迭代格式收斂的快慢，是衡量算法好壞的標(biāo)準(zhǔn)之一。對于迭代格式的收斂速度，我們建立如下的衡量標(biāo)準(zhǔn)。對收斂于解的迭代序列，若存在正實數(shù)和一個與迭代步數(shù)k無關(guān)的正常數(shù)q，由某開始，若成立（3）

則稱迭代序列具有階斂速。上海海運大學(xué)專用特別，當(dāng)時，稱迭代序列具線性斂速；當(dāng)時,稱迭代序列具超線性斂速；而當(dāng)時，稱迭代序列具二階斂速。向量值函數(shù)的雅可比矩陣的表達(dá)形式為:（4）

上海海運大學(xué)專用從上述表達(dá)式可知，一個向量值函數(shù)值的雅可比矩陣的第i行就是的第個函數(shù)的梯度向量的轉(zhuǎn)置，即（5）

上海海運大學(xué)專用§1求解非線性代數(shù)方程組的一般迭代法本節(jié)將介紹簡單代法、牛頓一拉夫遜(Newton-Raphson)法和詹重禧法。一、簡單迭代法對于非線性方程組（1），若令，則該非線性方程組可等價地表示為（6）

式中，為x的n維向量值函數(shù)。此時，方程組（6）的解成為向量值函數(shù)的不動點上海海運大學(xué)專用對于具有式（6）形式的非線性方程組，可構(gòu)作如下的簡單迭代格式：（7）

式中，稱為初始向量或初始點。非線性方程組（6）的簡單迭代格式（7）具有計算方便、編程容易、每迭代一步只需計算一個向量值函數(shù)等優(yōu)點。但對任取的初始點迭代格式（7）并不一定收斂；而且，即使收斂，其斂速也很不理想，其依據(jù)為下列定理：上海海運大學(xué)專用定理1設(shè)為非線性方程組（6）的解，若存在球域和常數(shù),對一切成立（8）

則對任意由迭代格式（7）產(chǎn)生的迭代序列且收斂于解，并具有線性斂速。證明：由于,利用迭代格式（7）和條件式（8）可得上海海運大學(xué)專用因此若已知，則由可知，.這表明對一切，有，又因，，由上式可知，序列的收斂性得證。另外，由不等式可知，迭代序列具線性斂速。證畢

上海海運大學(xué)專用定理1中的條件(8)稱為的壓縮條件。這個條件對討論迭代法的收斂性以及解的存在性等理論間題都是極為重要的。至于合適初始點的選取，由于對于任意向量值函數(shù)，事先無法知道滿足定理1條件的球域，我們只能根據(jù)試算情況或所求問題的物理意義經(jīng)驗地確定之。簡單迭代法只具線性斂速，這一缺點影響了該法的實用價值。文獻(xiàn)[18]介紹了一個較實用的簡單迭代法的改進(jìn)方案，需要時，可參考之。上海海運大學(xué)專用

二、牛頓一拉夫遜法

將一元方程的牛頓迭代法推廣應(yīng)用于解非線性方程組(1)，即得牛頓一拉夫遜法(以下簡稱牛頓法)。牛頓法由非線性函數(shù)線性化得到。設(shè)已有迭代點，將向量值函數(shù)近似地取為點處的一階展式,從中解出x，作為下一個新的迭代點，即得如下牛頓法的迭代格式：（9）

式中，為向量值函數(shù)在點處的雅可比矩陣。上海海運大學(xué)專用若非奇異，則可通過解線性方程組求得增量，進(jìn)而求得下一個迭代點。若范數(shù)(為精度)，則可取為方程組(1)的近似解。牛頓法是求解非線性方程組(1)的一個極為基本而又十分重要的算法。該法的最大優(yōu)點是收斂快，具有二階斂速。但牛頓法的一個致命缺點是對初始點的要求非?？量獭Ｈ舫跏键c取得不合適，往往導(dǎo)致計算失敗。上海海運大學(xué)專用牛頓法的另一個問題是迭代過程中需計算雅可比矩陣。當(dāng)函數(shù)復(fù)雜，求導(dǎo)不易時，可用數(shù)值求導(dǎo)法計算一階偏導(dǎo)數(shù)。當(dāng)然，這要以犧牲一定的斂速為代價的。圍繞著放寬對初始點的要求，改善雅可比矩陣可能出現(xiàn)的病態(tài)性以及提高斂速等三個方面，不少文獻(xiàn)介紹了牛頓法的一些改進(jìn)方案，有興趣的讀者請參閱之。作者用FORTRAN語言編制的牛頓法子程序取名為NRM.上海海運大學(xué)專用

三、詹重禧法在機(jī)構(gòu)分析與綜合等工程問題中，更一般的情況是需要求解下列相容非線性方程組：(10)

顯然，只要方程組(10)有解，求解非線性方程組(10)等價于求解如下最小二乘問題的最小值點：（11）

上述問題屬無約束優(yōu)化間題，當(dāng)然可用無約束優(yōu)化方法求出其極小值點，但考慮到該問題的目標(biāo)函數(shù)為平方和形式，故可用更有效的優(yōu)化方法求解。上海海運大學(xué)專用1、法式方程如式（11）所示的目標(biāo)函數(shù)的梯度（12）

式中，為向量值函數(shù)的的雅可比矩陣，（13）

設(shè)為已知的迭代點，取在點的一階展開式：（14）

于是（15）

上海海運大學(xué)專用將近似式（14）和（15）代入梯度表達(dá)式（12），可得的近似表達(dá)式：（16）

在極小值點處，應(yīng)成立：或（17）

方程（17）稱為法式方程。從法式方程（17）中解出，并將作為新的迭代點，即得下列迭代格式：上海海運大學(xué)專用（18）

式中的稱為初始點。上述迭代格式就是最小二乘法的迭代格式。在最小二乘法的計算過程中，需求矩陣的逆。雖然總是對稱半正定，在一般情況下逆矩陣似乎總存在，但其行列式det()很小，病態(tài)情況相當(dāng)嚴(yán)重。因而解的穩(wěn)定性很差。針對最小二乘法這一致命的不足，不少學(xué)者提出了各種改進(jìn)方案。其中，最有名的算法是阻尼最小二乘法(又稱為L－M法)。但中國學(xué)者詹重禧提出的方法(本書作者稱之為詹重禧法)的計算效果比L－M法更好，收斂速度比L－M法更快，是目前為止求解最小二乘問題的最好方法。上海海運大學(xué)專用2、基本公式令，并設(shè)為對稱正定矩陣，則可分解成（19）

式中，為下三角矩陣，為對角線矩陣，即和的非常數(shù)元素可按下式確定：上海海運大學(xué)專用（20）

于是迭代格式（18）可改寫為（21）

式中，由于易呈病態(tài)，上述迭代格式的數(shù)值穩(wěn)定性較差，故對加阻尼，得詹重禧法的迭代公式為（22）

上海海運大學(xué)專用式中，I為n階單位矩陣，>0稱為阻尼因子。迭代格式(22)中的線性方程組有簡單的公式解。令記,則線性方程組的解為（23）

進(jìn)而由線性方程組解得（24）

于是下一個迭代點為上海海運大學(xué)專用3、有關(guān)問題的討論1）阻尼因子的選取在詹重禧法中，阻尼因子的選擇至關(guān)重要。選取的值既要保證在迭代過程中是逐漸減小的，且最終，只有這樣才可能收斂到最小二乘問題(11)的極小值點；又要保證由式（11）計算得到的，使得迭代過程能收斂；還要考慮能改善迭代式(22)的病態(tài)，盡可能減少計算工作量和具有一定的斂速。所以，阻尼因子的選擇是一個十分重要但又比較困難的問題。至今，數(shù)學(xué)家們已提出了選擇阻尼因子的多種方法。下面介紹其中一種較有效的確定的算法。上海海運大學(xué)專用步0假設(shè)已得到和，計算步1?。扇=2，5或10），求解方程組得和步2計算并作如下比較：上海海運大學(xué)專用（1）若，則?。?）若，且，則取并解方程組得，進(jìn)而可得（3）若，且，則令上海海運大學(xué)專用逐次對求解方程組得，直到求得一個使成立的i整數(shù)為止。此時，可取2）收斂準(zhǔn)則因為非線性方程組(10)的解是最小二乘問題(11)的最小值點，所以若用詹重禧法解方程組（10）。應(yīng)采用下列殘量均方根收斂準(zhǔn)則：上海海運大學(xué)專用（25）

式中，為精度。若用詹重禧法求解最小二乘間題的極小值點，則可采用下列2個條件同時滿足的混合相對收斂準(zhǔn)則：（26）

在用詹重禧法求解非線性方程組(10)時，可用迭代次數(shù)和殘量的均方根值判斷求解是否成功。上海海運大學(xué)專用若經(jīng)多次迭代，前后兩點和幾乎不變，但始終不滿足收斂條件(25)，則這種情況表明計算只收斂到最小二乘問題(11)的一個局部極小值點。此時，可用迭代次數(shù)加以判斷是否出現(xiàn)這種情況。在迭代計算過程中還可能出現(xiàn)殘量的均方根值不斷增大的情況，這表明計算過程發(fā)散。當(dāng)出現(xiàn)上述兩種情況之一時，表明原方程組(10)可能無解；也可能有解，但初始點取得不合適。3）初始點的選取理論和實際都表明，詹重禧法有較大的收斂域，但該法畢竟不是大范圍收斂的算法，因而合適初始點的選擇是一個困難而又必須解決的問題。本書建議用經(jīng)驗定點法或區(qū)域?qū)ふ曳ù_定合適初始點。上海海運大學(xué)專用(1)經(jīng)驗定點法在解決實際工程問題時，非線性方程組(10)中的每個未知量一般都有確定的物理意義。因此，可根據(jù)求解者的經(jīng)驗和每個未知量的可能值，嘗試性地確定一個初始點，并在試算過程中加以調(diào)整。(2)區(qū)域?qū)ふ曳ǜ鶕?jù)求解者的經(jīng)驗和每個未知量可能的取值范圍確定一個求解區(qū)域其中這里稱為區(qū)間,稱為區(qū)間向量(關(guān)于他們的定義，祥見文獻(xiàn)[Z27])。給出的求解區(qū)域要保證非線性方程組(10)的解，即。上海海運大學(xué)專用根據(jù)所求問題的性質(zhì)，給出這樣的求解區(qū)域要比直接給出一個合適的初始點容易得多，而且也可根據(jù)試算情況調(diào)整。當(dāng)n較小時，可用隨機(jī)試驗法在求解區(qū)域中選定一個計算點,的各分量可由下式隨機(jī)產(chǎn)生：(27)

式中，為區(qū)間[0，1]上均勻分布的偽隨機(jī)數(shù)。可由計算機(jī)語言中的內(nèi)部函數(shù)產(chǎn)生。上海海運大學(xué)專用當(dāng)n較大時，可用正交計算設(shè)計法在求解區(qū)域中選定一個計算點。然后，以點為初始點，用詹重禧法求解非線性方程組(10)。若求解成功，則為一個合適的初始點，計算結(jié)束，否則，在中再取不同的計算點，重新求解方程組(10)；直到求解成功為止。根據(jù)隨機(jī)試驗法和正交計算設(shè)計法所選計算點在中均勻分布，以及詹重禧法有較大收斂域的特性，較易落人收斂域內(nèi)，因而區(qū)域?qū)ふ曳ㄍ晒?。上海海運大學(xué)專用4、計算步驟用詹重禧法求解非線性方程組（10）的步驟如下：步0輸入未知量個數(shù)n，方程個數(shù)m，初始點，初始阻尼因子（可取=0.01等），倍率v（v=2，5或10）和精度，令k=0。步1由已知的和阻尼因子，用本節(jié)介紹的方法確定合適的阻尼因子和下一個迭代點.步2收斂判斷：若，則輸出，計算結(jié)束；否則，令k=k+1，轉(zhuǎn)步1。上海海運大學(xué)專用作者用FORTRAN語言編制的詹重禧法子程序取命為ZZX。在程序ZZX中，還考慮了計算過程中可能出現(xiàn)半正定的情況。當(dāng)為半正定時，在中將出現(xiàn)對角陣的某個對角線元素。為使計算繼續(xù)進(jìn)行下去，可采用小擾動法，即令理論分析和實際計算都表明，詹重禧法具有與阻尼最小二乘法相似的性質(zhì)，但比阻尼最小二乘法有更快的收斂速度和更小的計算工作量。這是因為詹重禧法采用對角陣加阻尼的辦法，即用替代。上海海運大學(xué)專用這種加阻尼的辦法，不僅調(diào)整了矩陣的主對角線元素，而且對整個矩陣進(jìn)行了調(diào)整，從而提高了斂速。從上述介紹中可看到，迭代計算過程中要大量地求解線性方程組(22),由于詹重禧法對正定矩陣采用了分解，這樣線性方程組(22)就有式(23)和式(24)所示的公式解。而且，當(dāng)阻尼因子變化，但，不變時，由式(23)求得的不受的影響。當(dāng)變化時，只需用式(24)重新計算即可。不需像阻尼最小二乘法等其他方法那樣，要用消元法或迭代法整個地求解線性方程組。因此，詹重禧法的計算工作量要小得多。可以說，詹重禧法是目前求解最小二乘法問題的最好方法。上海海運大學(xué)專用值得指出的是詹重禧法還可用于求解下列3種問題：1）的方程組的數(shù)值解。2）的矛盾方程組的殘量最小解，即可求得，，但成立（28）

3）求病態(tài)線性方程組的數(shù)值解。本節(jié)介紹的簡單迭代法、牛頓-拉夫遜法和詹重禧法都不是大范圍收斂的算法，其迭代計算過程收斂與否，都與初始點的選取有關(guān)。經(jīng)驗定點法和區(qū)域?qū)ふ曳ㄊ谴_定合適初始點的2個實用有效的方法。上海海運大學(xué)專用§2求解多元多項式方程組的消元方法一、基本概念設(shè)多項式方程組為:（29）

式中，為實系數(shù)，，冪指數(shù)為非負(fù)整數(shù)；表示n個變元。我們約定：多項式中的同類項已合并。即若，則。上海海運大學(xué)專用為敘述方便，將n個多項式的集合記為，即：

（30）以后不加區(qū)分地把方程組（30）的解或零點稱為多項式組（PS）的解或零點。

定義1

在一個多項式中，實際出現(xiàn)的變元的最大下標(biāo)m稱為該多項式的類，記作；對于非零常數(shù)多項式，定義。例1設(shè),則上海海運大學(xué)專用

定義2

在一個多項式中，變元的最高冪指數(shù)稱為該多項式關(guān)于變元的度，記作對于非零常數(shù)多項式和不含的多項式，定義。特別地，設(shè)，，則簡稱為多項式的度，記作，即例2設(shè)，則設(shè)一個多項式的類為，則該多項式可簡表為：

（31）

上海海運大學(xué)專用式中，為實系數(shù)，，冪指數(shù)均為非負(fù)整數(shù)

定義3

設(shè)和是兩個非零多項式，稱比有較低的秩或比有較高的秩。記作或；如果以下兩種情形之一成立：1）

2）

在與不能比較秩的高低時，則稱與同秩。記作上海海運大學(xué)專用例3設(shè)，因，故

定義4

設(shè)和是兩個非零多項式，若，則稱為的約化多項式。顯然，若，則必為的約化多項式；反之，不然。例4 設(shè)因，故是的約化多項式，但上海海運大學(xué)專用定義5設(shè)為一非零多項式，，則可表示成：（32）

式中，。而稱為多項式的初式。顯然，是的約化多項式。上海海運大學(xué)專用定義6

設(shè)為一多項式組，,若則稱為一半特征組；不僅如此，若對任意的是的約化多項式，則稱為一特征組。例5設(shè)；其中因故是一半特征組；但不是一特征組，因為不是的約化多項式。上海海運大學(xué)專用若改為，則成為一特征組。因為都是的約化多項式，而且還是的約化多項式。定義7設(shè)一多項式組中的n個多項式具有如下的形式：（33）

上海海運大學(xué)專用且真正地出現(xiàn)在中，即則稱該多項式組為一三角形組，記,而稱為三角形方程組。顯然，若多項式組是一半特征組或特征組，則該多項式組必為一個三角形組。上海海運大學(xué)專用二、吳方法1、偽除法 設(shè)和為兩個非零多項式，的初式為，而是的未約化的多項式，即，則可表示為：（34）

式中，且。不妨認(rèn)為是關(guān)于的初式。若上海海運大學(xué)專用若可用表示為：（35）

式中，為非負(fù)整數(shù)，均是的多項式，且；則稱為除的商，為除的余式。顯然是的約化多項式，故稱求除余式的過程為對的約化。對約化或求除余式的方法之一是偽除法。偽除法的計算過程可表述如下：上海海運大學(xué)專用（36）

式中，,是關(guān)于的初式，從上可知，每做一次偽除，余式中關(guān)于的度數(shù)至少降低１次。因此，最多做次偽除，就可求得上海海運大學(xué)專用除余式的。另外，若將和表示成：，則式（36）中的可表示成：（37）

式（37）在節(jié)省計算工作量方面是十分有用的。因為吳方法的基本運算之一是偽除法，在下述的整序過程中，需要進(jìn)行大量的偽除法。例6設(shè),求除的余式。上海海運大學(xué)專用解：

上海海運大學(xué)專用2、整序

定義8設(shè)給定的多項式組為若有某種方法，能求出與相對應(yīng)的三角形組，使的零點也是的零點。那么，我們稱從出發(fā)，到求得的過程為整序，而稱為原多項式方程組的類解析解或多項式解。顯然，通過分別求解中的n個一元多項式方程，可求得原方程組的所有零點。1)基組的選取根據(jù)秩的大小，按照下列步驟從一多項式組中選取到的多項式組上海海運大學(xué)專用稱為的一個基組。步1：令，在的n個多項式中，選取一個秩為最低的多項式，設(shè)為，則。除以外，在的其余個多項式中，找出所有與約化的多項式，記這些多項式的集合為若（空集），即則為所求基組，結(jié)束選??；否則，轉(zhuǎn)步2；步2：在的個多項式中，選取一個秩為最低的多項式，設(shè)為，則。除以外，在上海海運大學(xué)專用的其余個多項式中，找出所有與約化的多項式，記這些多項式的集合為若，即，則為所求基組，結(jié)束選??；否則，在中再進(jìn)行選取，直到某個為止。顯然，經(jīng)有限步選取，必可選出的一個基組例7設(shè)，其中求的基組。上海海運大學(xué)專用解：令在中，，故，且。因此，2)多項式對基組的余式設(shè)是一非零多項式，為一基組。若設(shè)為用偽除法求得的除的余式，為除的余式，為除的余式，則稱為多項式上海海運大學(xué)專用對基組（BS）的余式。在上述求余式的過程中，若遇到這樣的情況：為多項式對基組（BS）的余式。在上述求余式的過程中，若遇到這樣的情況：，即中不含變元，則除的余式定義為，即，也就是不做此步偽除法。例8設(shè)基組，其中求對基組（BS）的余式。上海海運大學(xué)專用解：除的余式：除的余式：3)整序算法（BR格式）按下列步驟，可將一多項式組化成一三角形組（TS）。步1：輸入（PS），令，置；步2：在中選取基組；若中的多項式個數(shù)等于n，則為所求，整序結(jié)束；否則，求出中除以外的每一個多項式對基組的余式。上海海運大學(xué)專用若這些余式中有一個為零（表示有無窮多個解）或有一個為非零常數(shù)（表示無解），則停機(jī)；否則，記這些非常數(shù)余式的集合為，轉(zhuǎn)步３；步3令，置，轉(zhuǎn)步２。上述整序算法需交替地選基組和求余式集，故稱此整序格式為BR格式。每進(jìn)行一次選基組和求一次余式集，稱為進(jìn)行一次BR步。需要指出的是：按上述步驟求得的三角形組實際上就是的一個特征組。然而從節(jié)省計算工作量的角度講，只需求出的一個半特征組就可結(jié)束整序。上海海運大學(xué)專用例如，當(dāng)計算到某一步時，在的n個多項式中，只有一個類為n的多項式，或只有一個類為n的多項式和一個類為n-1的多項式，則可將這個或這兩個多項式選進(jìn)基組中。例9 設(shè)，其中試對整序。解：

上海海運大學(xué)專用上海海運大學(xué)專用3、多項式方程組的零點集結(jié)構(gòu)式吳文俊在文獻(xiàn)[11~14]中給出了如下多項式組的零點集結(jié)構(gòu)式：（38）

式中，是的特征組或半特征組。是將非常數(shù)不重復(fù)的多項式添入后的多項式組，而是歷次基組中所有多項式的初式的集合。是將非常數(shù)不重復(fù)的多項式添入后的多項式組，而是在整序過程中被約去的所有最大公約式的集合?！埃碧柡颓蠛吞朣UM表示集合的并。是這些和的乘積。表示中使的部分。上海海運大學(xué)專用例10求例9中的零點集解：由例9知，該的特征組為：令，可得如下5個孤立零點，其中上海海運大學(xué)專用在歷次基組中，只出現(xiàn)一個非常數(shù)初式，也沒有約去最大公約式，故。顯然，上述5個零點都使，故.可判斷,無解，因而根據(jù)結(jié)構(gòu)式（38），首先要對（PS）進(jìn)行整序，以求得三個多項式組：（CS）、（IS）與（FS）。若（CS）含有一個非零常數(shù)多項式，且則（PS）無解；若（CS）中多項式的個數(shù)少于變元的個數(shù)n，且，則在不可約的情況下，（PS）有無窮多個解；若（CS）中含有n個多項式，則可求出，剔除使的解，得上海海運大學(xué)專用然后將（IS）和（FS）中每一個非常數(shù)不重復(fù)的初式和最大公約式分別添入（PS），構(gòu)造出新的多項式組和,再重新整序，求得結(jié)構(gòu)式（38）的后兩個和集，最后才能求得大量的計算可能花在求結(jié)構(gòu)式（38）中的后兩個和集上。因為非常數(shù)不重復(fù)的初式和最大公約式往往不止一個，有時多達(dá)幾十個、上百個；而且在對和的整序過程中，又會出現(xiàn)新的非常數(shù)不重復(fù)的初式和最大公約式，又需分別添入中進(jìn)行檢驗。這種反復(fù)應(yīng)用整序幾十次、甚至上百次的計算工作量，在實際應(yīng)用中是難以被接受的，必須對（BR）格式進(jìn)行改進(jìn)。上海海運大學(xué)專用三、的基組結(jié)式消元法基組結(jié)式消元法的主要思想是：根據(jù)秩的大小選取基組，利用貝左結(jié)式消元，將一個多項式組化成一個三角形組，再由改進(jìn)的零點集結(jié)構(gòu)式確定的所有解。1、貝左結(jié)式用輾轉(zhuǎn)相除法可從兩個多項式中消去一個變元而得到僅含他們系數(shù)的一個有理式，然后根據(jù)這個有理式是否為零，來判斷這兩個多項式是否有公共根。這樣的有理式稱為這兩個多項式的結(jié)式。有多種形式的結(jié)式。例如西爾維斯特（Sylvester）結(jié)式，等等。這里采用低階行列式表示的貝左結(jié)式。上海海運大學(xué)專用設(shè)和是兩個非零多項式，它們的表達(dá)式為：（39）

式中，各和均為的多項式，文獻(xiàn)[15]分別給出了和兩種情況下的貝左結(jié)式。經(jīng)歸納整理，我們得到如下貝左結(jié)式的統(tǒng)一表達(dá)式上海海運大學(xué)專用（40）

式中，上海海運大學(xué)專用當(dāng)時，當(dāng)時，。貝左結(jié)式為一階行列式，其階數(shù)比西爾維斯特結(jié)式的階數(shù)低階。根據(jù)結(jié)式的性質(zhì)知，和的公共零點，必然是結(jié)式的零點。例11求和的貝左結(jié)式其中解：

上海海運大學(xué)專用上海海運大學(xué)專用2、零點集結(jié)構(gòu)式

定理2在按（BR）格式對多項式組進(jìn)行整序并求得三角形組的過程中，若不約去諸中的各多項式的最大公約式，則；但不一定成立。證明：不失一般性，設(shè)第一個基組中包含了多項式組中的２個多項式和，即：。進(jìn)行整序并用偽除法消元時，可得中除外的個多項式對的第一個余集，其中上海海運大學(xué)專用（41）

式中，和分別為和的初式，指數(shù)為非負(fù)整數(shù)，為多項式。記，設(shè)上海海運大學(xué)專用由于的各多項式均是的線性組合，易知即；反之，設(shè)雖然，但從中，無法肯定，同樣也無法肯定。只有當(dāng)２個初式和不為零時，才能肯定同時由于從求與從求的做法相同，易知；直到求得時，成立：上海海運大學(xué)專用反之不一定成立。證畢。若在整序過程中約去諸中的各多項式的常數(shù)公約式，則定理2仍成立。推論1在按（BR）格式對多項式組進(jìn)行整序并求得三角形組的過程中，若約去諸中的各多項式的最大公約式，則（42）

這里的含義同結(jié)構(gòu)式（38）中的含義。證明：若先不約去最大公約式，當(dāng)進(jìn)行第一次（BR）步后，可得。由定理2可知，設(shè)有最大公約式，則中任一多項式上海海運大學(xué)專用均可表示為和另一多項式的乘積，即。若，則,故有，因而和兩者中，至少有一個為零。由此推斷下去，易知推論成立。證畢。根據(jù)推論1，可將多項式組的零點集結(jié)構(gòu)式（38）改變?yōu)槿缦滦问剑海?3）式中的和第三項的含義同式（38）中的含義；而且至少有一上海海運大學(xué)專用使,為歷次基組中的非常數(shù)不重復(fù)的初式的集合。根據(jù)定理2可構(gòu)造如下的零點集結(jié)構(gòu)式：（44）

結(jié)構(gòu)式（44）的含義是明確的：在求的過程中，若不約去諸中的各多項式的非常數(shù)最大公約式，則可保證對而言不失根。因此，只需求出的全部零點，然后代入方程組中檢驗，根據(jù)檢驗結(jié)果，在中剔除使的零點，剩下的零點就是的全部零點。上海海運大學(xué)專用根據(jù)結(jié)構(gòu)式（44），在求解方程組時，只需對進(jìn)行一次整序，也不需要記憶初式集，就可求得的全部零點，從而極大地減少了計算工作量，使吳方法向更實用的程度邁進(jìn)了一大步。例12 設(shè)。試用結(jié)構(gòu)式（44）求。解：經(jīng)過兩次（BR）步可得的三角形組。其中，上海海運大學(xué)專用求解，可得３個不同零點（記）：經(jīng)代入原方程組檢驗知，他們是原方程組的全部不同零點，無需將整序過程中出現(xiàn)的初式添入中重新整序求解。3、基組結(jié)式消元法的主要計算步驟基組結(jié)式消元法仍按秩的大小選取基組，但不用偽除法而用貝左結(jié)式進(jìn)行消元，且由結(jié)構(gòu)式（44）求待解多項式組(PS)的零點集。因在求解過程中用到了基組和結(jié)式的概念，故取名為基組結(jié)式消元法[Z19]。上海海運大學(xué)專用(1)多項式對基組的結(jié)式1)兩個不同類多項式的貝左結(jié)式設(shè)g和f為兩個非零多項式，cls(f)=l＞0,deg(f)=k＞0,cls(g)=n≥l，deg(g,xl)=m≥k,則g和f可表示為：（45）

式中，上海海運大學(xué)專用稱按式（40）生成的結(jié)式為多項式g對f的結(jié)式。顯然，利用結(jié)式可從g和f中消去變元。當(dāng)時，可按同樣的思想生成g和f的結(jié)式。當(dāng)g中不含變元時(即時），定義g對f的結(jié)式為。2)多項式對基組的結(jié)式設(shè)g(x)是一非零多項式，cls(g)＞0,為一基組。若設(shè)為g對的結(jié)式，為對的結(jié)式，…，為對的結(jié)式，則稱為多項式g(x)對基組(BS)的結(jié)式。上海海運大學(xué)專用在上述求結(jié)式的過程中，若遇到中不含的類變元，則取，也即不計算對的結(jié)式。3)基組結(jié)式消元法的主要計算步驟用基組結(jié)式消元法求多項式組的多項式解的主要計算步驟如下。步1輸入維數(shù)n，多項式組(PS)及其它所需信息；令(PS1)=(PS)，置k=1；步2在(PSk)中按本節(jié)二中選取基組的方法選出基組(BSk)。若(BSk)中的多項式個數(shù)等于n，則(TS)=(BSk)為所求，整序結(jié)束，轉(zhuǎn)步4；否則，求出(PSk)中除(BSk)以外的每一個多項對基組(BSk)的結(jié)式。上海海運大學(xué)專用若這些結(jié)式中有一個為零(表示(PS)有無窮多個解)或有一個為非零常數(shù)(表示(PS)無解)，則停機(jī)；否則，記這些非常數(shù)結(jié)式的集合為(RSk)，轉(zhuǎn)步3；

步3令(PSk＋１)=(BSk)＋（RSk），置k=k+1,轉(zhuǎn)步2；

步4求出(TS)=0的全部零點，并根據(jù)改進(jìn)型結(jié)構(gòu)式（44）確定(PS)的所有零點，輸出所需信息，計算結(jié)束。仿照吳方法中的提法，用基組結(jié)式消元法對多項式(PS)進(jìn)行整序的算法仍稱為(BR)格式。其中，每進(jìn)行一次選基組(BSk)和求一次結(jié)式集(RSk)稱為進(jìn)行了一次(BR)步。作者用FORTRAN語言編制的基組結(jié)式消元法的程序取名為CHS。上海海運大學(xué)專用4、基組結(jié)式消元法的優(yōu)點基組結(jié)式消元法具有下列3個明顯的優(yōu)點：1）基組結(jié)式消元法至多進(jìn)行次（BR）步，就可求得的一個三角形組，其零點包含了的所有零點。而吳方法在一次整序中至少要進(jìn)行次（BR）步，才有可能求得這樣的。這是因為進(jìn)行１次偽除并不總能消去１個變元；但展開１個結(jié)式總能消去１個變元。至于聚篩法[15]，要分別進(jìn)行偽除求商和不帶分式的高斯消元，才能求得，其消元工作量是非常大的。2）相對吳方法和聚篩法而言，在用基組結(jié)式消元法求得的中，各多項式具有較低的度數(shù)。這是因為吳上海海運大學(xué)專用方法和聚篩法都用偽除法或不帶分式的高斯消元法進(jìn)行消元。兩種方法都有可能增大消元結(jié)果的度數(shù)。這可從除的偽除公式去理解。當(dāng)?shù)某跏綖橐环浅?shù)多項式，的度數(shù)時，余式就有可能比貝左結(jié)式的多出因式，為非負(fù)整數(shù)。3）根據(jù)改進(jìn)型結(jié)構(gòu)式（44），基組結(jié)式消元法只需進(jìn)行一次整序就可求得的所有零點，也不需要記憶初式集和最大公約式集，極大地減少了計算工作量，使吳方法向更實用的程度邁進(jìn)了一大步。上海海運大學(xué)專用應(yīng)當(dāng)指出：基組結(jié)式消元法還存在有待改進(jìn)的地方。如當(dāng)貝左結(jié)式的階數(shù)較高時，行列式的展開需要較大的計算工作量和計算機(jī)內(nèi)存；求得的組，其各多項式的度數(shù)有時還較大；建議用WR分解法對進(jìn)行后處理，以剔除多余的增根，得到度數(shù)較低的組，但進(jìn)行后處理的計算工作量也相當(dāng)大。例13 設(shè),其中，均為的函數(shù)，且；試分別用基組結(jié)式消元法和吳方法求的三角形組。上海海運大學(xué)專用解：基組結(jié)式消元法：其中，吳方法：上海海運大學(xué)專用由比較可知，用吳方法所得中的第１個多項式比用基組結(jié)式消元法所得的多出一個因式。上海海運大學(xué)專用四、的結(jié)式消元法1、一元多項式組的最大公約式的結(jié)式消元法需用到一元多項式組最大公約式的概念。為此，先證：定理3設(shè)為一元多項式組，其中,為r個參變元，則：（1）有公共零點的充要條件是有非常數(shù)的最大公約式（2）若有非常數(shù)的最大公約式，則和具有相同的零點集；即上海海運大學(xué)專用證明設(shè)為的一個公共零點，則是的一個公約式。根據(jù)文獻(xiàn)[10]知，一定是最大公約式的一個因式。因此，可令的非常數(shù)最大公約式為，其中為非零多項式。反之，設(shè)有最大公約式則對任一，可表示為；設(shè)為公約式的零點，則故是的一個公共零點。結(jié)論(1)成立。上海海運大學(xué)專用由結(jié)論(1)知，可設(shè)是的任一個公共零點，則

，所以。反之，設(shè)是最大公約式的任一個零點，則，故，結(jié)論(2)成立。根據(jù)結(jié)式的性質(zhì)，易知成立：定理4設(shè)在多項式組中,選出所有類為k的多項式，并把它們的集合記為上海海運大學(xué)專用而把中挑剩的個多項式組成集合。利用個結(jié)式，從中消去變元，并把這些結(jié)式的集合記為，令，則但反之，不一定成立。從定理4可知，原方程組的解一定滿足每一個結(jié)式。上海海運大學(xué)專用2、的結(jié)式消元法的消元步驟步0輸入多項式組步1從中挑選出所有類為n的多項式，并把它們的集合記為：(46)

將中挑剩的所有多項式組成集合，并從