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

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

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

式中，為n個(gè)待定的變?cè)M成的列陣，

為定義在維子空間

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

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

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

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

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

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

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

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

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

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

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

二、牛頓一拉夫遜法

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

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

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

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

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

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

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

于是（15）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義1

在一個(gè)多項(xiàng)式中，實(shí)際出現(xiàn)的變?cè)淖畲笙聵?biāo)m稱為該多項(xiàng)式的類，記作；對(duì)于非零常數(shù)多項(xiàng)式，定義。例1設(shè),則上海海運(yùn)大學(xué)專用

定義2

在一個(gè)多項(xiàng)式中，變?cè)淖罡邇缰笖?shù)稱為該多項(xiàng)式關(guān)于變?cè)亩?，記作?duì)于非零常數(shù)多項(xiàng)式和不含的多項(xiàng)式，定義。特別地，設(shè)，，則簡(jiǎn)稱為多項(xiàng)式的度，記作，即例2設(shè)，則設(shè)一個(gè)多項(xiàng)式的類為，則該多項(xiàng)式可簡(jiǎn)表為：

（31）

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

定義3

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

2）

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

定義4

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

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

設(shè)為一多項(xiàng)式組，,若則稱為一半特征組；不僅如此，若對(duì)任意的是的約化多項(xiàng)式，則稱為一特征組。例5設(shè)；其中因故是一半特征組；但不是一特征組，因?yàn)椴皇堑募s化多項(xiàng)式。上海海運(yùn)大學(xué)專用若改為，則成為一特征組。因?yàn)槎际堑募s化多項(xiàng)式，而且還是的約化多項(xiàng)式。定義7設(shè)一多項(xiàng)式組中的n個(gè)多項(xiàng)式具有如下的形式：（33）

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

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

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

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

式（37）在節(jié)省計(jì)算工作量方面是十分有用的。因?yàn)閰欠椒ǖ幕具\(yùn)算之一是偽除法，在下述的整序過程中，需要進(jìn)行大量的偽除法。例6設(shè),求除的余式。上海海運(yùn)大學(xué)專用解：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將中挑剩的所有多項(xiàng)式組成集合，并從