附录 非线性代数方程组求解方法

附录非线性代数方程组的求解方法

由n个变量n个方程（n>1）组成的非线性代数方程组（简称为非线性方程组）可表示为：(1)

式中，为n个待定的变元组成的列阵，

为定义在维子空间

上的维向量值函数，即

若中至少有一个为非线性函数，则称(1)为非线性方程组。n求非线性方程组数值解的一般迭代法的迭代格式为:上海海运大学专用（2）

式中，G为迭代矩阵。上述迭代格式必须满足：1)适定性。即由迭代格式（2）得到的序列是适定的，也就是，对均成立；2)收敛性。若是方程组（1）的解，则

3)在给定精度内求得解的近似解的工作量较少。在上述三个要求中，前两个要求是必须满足的。第三个要求是计算复杂性问题，是衡量一个算法好坏的标志。迭代格式（2）的含意是明确的。即求解时，必须取定一个初始点（或初值），通过逐次迭代，最终求得方程组（1）的满足精度要求的数值近似解。上海海运大学专用如果一个数值迭代法对初值没有本质上的限制，则称这种方法为大范围收敛的方法，如同伦法和区间分析法等；否则，称为一般迭代法。除必须满足适定性和收敛性条件外，还应考虑迭代格式的收敛速度。迭代格式收敛的快慢，是衡量算法好坏的标准之一。对于迭代格式的收敛速度，我们建立如下的衡量标准。对收敛于解的迭代序列，若存在正实数和一个与迭代步数k无关的正常数q，由某开始，若成立（3）

则称迭代序列具有阶敛速。上海海运大学专用特别，当时，称迭代序列具线性敛速；当时,称迭代序列具超线性敛速；而当时，称迭代序列具二阶敛速。向量值函数的雅可比矩阵的表达形式为:（4）

上海海运大学专用从上述表达式可知，一个向量值函数值的雅可比矩阵的第i行就是的第个函数的梯度向量的转置，即（5）

上海海运大学专用§1求解非线性代数方程组的一般迭代法本节将介绍简单代法、牛顿一拉夫逊(Newton-Raphson)法和詹重禧法。一、简单迭代法对于非线性方程组（1），若令，则该非线性方程组可等价地表示为（6）

式中，为x的n维向量值函数。此时，方程组（6）的解成为向量值函数的不动点上海海运大学专用对于具有式（6）形式的非线性方程组，可构作如下的简单迭代格式：（7）

式中，称为初始向量或初始点。非线性方程组（6）的简单迭代格式（7）具有计算方便、编程容易、每迭代一步只需计算一个向量值函数等优点。但对任取的初始点迭代格式（7）并不一定收敛；而且，即使收敛，其敛速也很不理想，其依据为下列定理：上海海运大学专用定理1设为非线性方程组（6）的解，若存在球域和常数,对一切成立（8）

则对任意由迭代格式（7）产生的迭代序列且收敛于解，并具有线性敛速。证明：由于,利用迭代格式（7）和条件式（8）可得上海海运大学专用因此若已知，则由可知，.这表明对一切，有，又因，，由上式可知，序列的收敛性得证。另外，由不等式可知，迭代序列具线性敛速。证毕

上海海运大学专用定理1中的条件(8)称为的压缩条件。这个条件对讨论迭代法的收敛性以及解的存在性等理论间题都是极为重要的。至于合适初始点的选取，由于对于任意向量值函数，事先无法知道满足定理1条件的球域，我们只能根据试算情况或所求问题的物理意义经验地确定之。简单迭代法只具线性敛速，这一缺点影响了该法的实用价值。文献[18]介绍了一个较实用的简单迭代法的改进方案，需要时，可参考之。上海海运大学专用

二、牛顿一拉夫逊法

将一元方程的牛顿迭代法推广应用于解非线性方程组(1)，即得牛顿一拉夫逊法(以下简称牛顿法)。牛顿法由非线性函数线性化得到。设已有迭代点，将向量值函数近似地取为点处的一阶展式,从中解出x，作为下一个新的迭代点，即得如下牛顿法的迭代格式：（9）

式中，为向量值函数在点处的雅可比矩阵。上海海运大学专用若非奇异，则可通过解线性方程组求得增量，进而求得下一个迭代点。若范数(为精度)，则可取为方程组(1)的近似解。牛顿法是求解非线性方程组(1)的一个极为基本而又十分重要的算法。该法的最大优点是收敛快，具有二阶敛速。但牛顿法的一个致命缺点是对初始点的要求非常苛刻。若初始点取得不合适，往往导致计算失败。上海海运大学专用牛顿法的另一个问题是迭代过程中需计算雅可比矩阵。当函数复杂，求导不易时，可用数值求导法计算一阶偏导数。当然，这要以牺牲一定的敛速为代价的。围绕着放宽对初始点的要求，改善雅可比矩阵可能出现的病态性以及提高敛速等三个方面，不少文献介绍了牛顿法的一些改进方案，有兴趣的读者请参阅之。作者用FORTRAN语言编制的牛顿法子程序取名为NRM.上海海运大学专用

三、詹重禧法在机构分析与综合等工程问题中，更一般的情况是需要求解下列相容非线性方程组：(10)

显然，只要方程组(10)有解，求解非线性方程组(10)等价于求解如下最小二乘问题的最小值点：（11）

上述问题属无约束优化间题，当然可用无约束优化方法求出其极小值点，但考虑到该问题的目标函数为平方和形式，故可用更有效的优化方法求解。上海海运大学专用1、法式方程如式（11）所示的目标函数的梯度（12）

式中，为向量值函数的的雅可比矩阵，（13）

设为已知的迭代点，取在点的一阶展开式：（14）

于是（15）

上海海运大学专用将近似式（14）和（15）代入梯度表达式（12），可得的近似表达式：（16）

在极小值点处，应成立：或（17）

方程（17）称为法式方程。从法式方程（17）中解出，并将作为新的迭代点，即得下列迭代格式：上海海运大学专用（18）

式中的称为初始点。上述迭代格式就是最小二乘法的迭代格式。在最小二乘法的计算过程中，需求矩阵的逆。虽然总是对称半正定，在一般情况下逆矩阵似乎总存在，但其行列式det()很小，病态情况相当严重。因而解的稳定性很差。针对最小二乘法这一致命的不足，不少学者提出了各种改进方案。其中，最有名的算法是阻尼最小二乘法(又称为L－M法)。但中国学者詹重禧提出的方法(本书作者称之为詹重禧法)的计算效果比L－M法更好，收敛速度比L－M法更快，是目前为止求解最小二乘问题的最好方法。上海海运大学专用2、基本公式令，并设为对称正定矩阵，则可分解成（19）

式中，为下三角矩阵，为对角线矩阵，即和的非常数元素可按下式确定：上海海运大学专用（20）

于是迭代格式（18）可改写为（21）

式中，由于易呈病态，上述迭代格式的数值稳定性较差，故对加阻尼，得詹重禧法的迭代公式为（22）

上海海运大学专用式中，I为n阶单位矩阵，>0称为阻尼因子。迭代格式(22)中的线性方程组有简单的公式解。令记,则线性方程组的解为（23）

进而由线性方程组解得（24）

于是下一个迭代点为上海海运大学专用3、有关问题的讨论1）阻尼因子的选取在詹重禧法中，阻尼因子的选择至关重要。选取的值既要保证在迭代过程中是逐渐减小的，且最终，只有这样才可能收敛到最小二乘问题(11)的极小值点；又要保证由式（11）计算得到的，使得迭代过程能收敛；还要考虑能改善迭代式(22)的病态，尽可能减少计算工作量和具有一定的敛速。所以，阻尼因子的选择是一个十分重要但又比较困难的问题。至今，数学家们已提出了选择阻尼因子的多种方法。下面介绍其中一种较有效的确定的算法。上海海运大学专用步0假设已得到和，计算步1取（可取v=2，5或10），求解方程组得和步2计算并作如下比较：上海海运大学专用（1）若，则取（2）若，且，则取并解方程组得，进而可得（3）若，且，则令上海海运大学专用逐次对求解方程组得，直到求得一个使成立的i整数为止。此时，可取2）收敛准则因为非线性方程组(10)的解是最小二乘问题(11)的最小值点，所以若用詹重禧法解方程组（10）。应采用下列残量均方根收敛准则：上海海运大学专用（25）

式中，为精度。若用詹重禧法求解最小二乘间题的极小值点，则可采用下列2个条件同时满足的混合相对收敛准则：（26）

在用詹重禧法求解非线性方程组(10)时，可用迭代次数和残量的均方根值判断求解是否成功。上海海运大学专用若经多次迭代，前后两点和几乎不变，但始终不满足收敛条件(25)，则这种情况表明计算只收敛到最小二乘问题(11)的一个局部极小值点。此时，可用迭代次数加以判断是否出现这种情况。在迭代计算过程中还可能出现残量的均方根值不断增大的情况，这表明计算过程发散。当出现上述两种情况之一时，表明原方程组(10)可能无解；也可能有解，但初始点取得不合适。3）初始点的选取理论和实际都表明，詹重禧法有较大的收敛域，但该法毕竟不是大范围收敛的算法，因而合适初始点的选择是一个困难而又必须解决的问题。本书建议用经验定点法或区域寻找法确定合适初始点。上海海运大学专用(1)经验定点法在解决实际工程问题时，非线性方程组(10)中的每个未知量一般都有确定的物理意义。因此，可根据求解者的经验和每个未知量的可能值，尝试性地确定一个初始点，并在试算过程中加以调整。(2)区域寻找法根据求解者的经验和每个未知量可能的取值范围确定一个求解区域其中这里称为区间,称为区间向量(关于他们的定义，祥见文献[Z27])。给出的求解区域要保证非线性方程组(10)的解，即。上海海运大学专用根据所求问题的性质，给出这样的求解区域要比直接给出一个合适的初始点容易得多，而且也可根据试算情况调整。当n较小时，可用随机试验法在求解区域中选定一个计算点,的各分量可由下式随机产生：(27)

式中，为区间[0，1]上均匀分布的伪随机数。可由计算机语言中的内部函数产生。上海海运大学专用当n较大时，可用正交计算设计法在求解区域中选定一个计算点。然后，以点为初始点，用詹重禧法求解非线性方程组(10)。若求解成功，则为一个合适的初始点，计算结束，否则，在中再取不同的计算点，重新求解方程组(10)；直到求解成功为止。根据随机试验法和正交计算设计法所选计算点在中均匀分布，以及詹重禧法有较大收敛域的特性，较易落人收敛域内，因而区域寻找法往往成功。上海海运大学专用4、计算步骤用詹重禧法求解非线性方程组（10）的步骤如下：步0输入未知量个数n，方程个数m，初始点，初始阻尼因子（可取=0.01等），倍率v（v=2，5或10）和精度，令k=0。步1由已知的和阻尼因子，用本节介绍的方法确定合适的阻尼因子和下一个迭代点.步2收敛判断：若，则输出，计算结束；否则，令k=k+1，转步1。上海海运大学专用作者用FORTRAN语言编制的詹重禧法子程序取命为ZZX。在程序ZZX中，还考虑了计算过程中可能出现半正定的情况。当为半正定时，在中将出现对角阵的某个对角线元素。为使计算继续进行下去，可采用小扰动法，即令理论分析和实际计算都表明，詹重禧法具有与阻尼最小二乘法相似的性质，但比阻尼最小二乘法有更快的收敛速度和更小的计算工作量。这是因为詹重禧法采用对角阵加阻尼的办法，即用替代。上海海运大学专用这种加阻尼的办法，不仅调整了矩阵的主对角线元素，而且对整个矩阵进行了调整，从而提高了敛速。从上述介绍中可看到，迭代计算过程中要大量地求解线性方程组(22),由于詹重禧法对正定矩阵采用了分解，这样线性方程组(22)就有式(23)和式(24)所示的公式解。而且，当阻尼因子变化，但，不变时，由式(23)求得的不受的影响。当变化时，只需用式(24)重新计算即可。不需像阻尼最小二乘法等其他方法那样，要用消元法或迭代法整个地求解线性方程组。因此，詹重禧法的计算工作量要小得多。可以说，詹重禧法是目前求解最小二乘法问题的最好方法。上海海运大学专用值得指出的是詹重禧法还可用于求解下列3种问题：1）的方程组的数值解。2）的矛盾方程组的残量最小解，即可求得，，但成立（28）

3）求病态线性方程组的数值解。本节介绍的简单迭代法、牛顿-拉夫逊法和詹重禧法都不是大范围收敛的算法，其迭代计算过程收敛与否，都与初始点的选取有关。经验定点法和区域寻找法是确定合适初始点的2个实用有效的方法。上海海运大学专用§2求解多元多项式方程组的消元方法一、基本概念设多项式方程组为:（29）

式中，为实系数，，幂指数为非负整数；表示n个变元。我们约定：多项式中的同类项已合并。即若，则。上海海运大学专用为叙述方便，将n个多项式的集合记为，即：

（30）以后不加区分地把方程组（30）的解或零点称为多项式组（PS）的解或零点。

定义1

在一个多项式中，实际出现的变元的最大下标m称为该多项式的类，记作；对于非零常数多项式，定义。例1设,则上海海运大学专用

定义2

在一个多项式中，变元的最高幂指数称为该多项式关于变元的度，记作对于非零常数多项式和不含的多项式，定义。特别地，设，，则简称为多项式的度，记作，即例2设，则设一个多项式的类为，则该多项式可简表为：

（31）

上海海运大学专用式中，为实系数，，幂指数均为非负整数

定义3

设和是两个非零多项式，称比有较低的秩或比有较高的秩。记作或；如果以下两种情形之一成立：1）

2）

在与不能比较秩的高低时，则称与同秩。记作上海海运大学专用例3设，因，故

定义4

设和是两个非零多项式，若，则称为的约化多项式。显然，若，则必为的约化多项式；反之，不然。例4 设因，故是的约化多项式，但上海海运大学专用定义5设为一非零多项式，，则可表示成：（32）

式中，。而称为多项式的初式。显然，是的约化多项式。上海海运大学专用定义6

设为一多项式组，,若则称为一半特征组；不仅如此，若对任意的是的约化多项式，则称为一特征组。例5设；其中因故是一半特征组；但不是一特征组，因为不是的约化多项式。上海海运大学专用若改为，则成为一特征组。因为都是的约化多项式，而且还是的约化多项式。定义7设一多项式组中的n个多项式具有如下的形式：（33）

上海海运大学专用且真正地出现在中，即则称该多项式组为一三角形组，记,而称为三角形方程组。显然，若多项式组是一半特征组或特征组，则该多项式组必为一个三角形组。上海海运大学专用二、吴方法1、伪除法 设和为两个非零多项式，的初式为，而是的未约化的多项式，即，则可表示为：（34）

式中，且。不妨认为是关于的初式。若上海海运大学专用若可用表示为：（35）

式中，为非负整数，均是的多项式，且；则称为除的商，为除的余式。显然是的约化多项式，故称求除余式的过程为对的约化。对约化或求除余式的方法之一是伪除法。伪除法的计算过程可表述如下：上海海运大学专用（36）

式中，,是关于的初式，从上可知，每做一次伪除，余式中关于的度数至少降低１次。因此，最多做次伪除，就可求得上海海运大学专用除余式的。另外，若将和表示成：，则式（36）中的可表示成：（37）

式（37）在节省计算工作量方面是十分有用的。因为吴方法的基本运算之一是伪除法，在下述的整序过程中，需要进行大量的伪除法。例6设,求除的余式。上海海运大学专用解：

上海海运大学专用2、整序

定义8设给定的多项式组为若有某种方法，能求出与相对应的三角形组，使的零点也是的零点。那么，我们称从出发，到求得的过程为整序，而称为原多项式方程组的类解析解或多项式解。显然，通过分别求解中的n个一元多项式方程，可求得原方程组的所有零点。1)基组的选取根据秩的大小，按照下列步骤从一多项式组中选取到的多项式组上海海运大学专用称为的一个基组。步1：令，在的n个多项式中，选取一个秩为最低的多项式，设为，则。除以外，在的其余个多项式中，找出所有与约化的多项式，记这些多项式的集合为若（空集），即则为所求基组，结束选取；否则，转步2；步2：在的个多项式中，选取一个秩为最低的多项式，设为，则。除以外，在上海海运大学专用的其余个多项式中，找出所有与约化的多项式，记这些多项式的集合为若，即，则为所求基组，结束选取；否则，在中再进行选取，直到某个为止。显然，经有限步选取，必可选出的一个基组例7设，其中求的基组。上海海运大学专用解：令在中，，故，且。因此，2)多项式对基组的余式设是一非零多项式，为一基组。若设为用伪除法求得的除的余式，为除的余式，为除的余式，则称为多项式上海海运大学专用对基组（BS）的余式。在上述求余式的过程中，若遇到这样的情况：为多项式对基组（BS）的余式。在上述求余式的过程中，若遇到这样的情况：，即中不含变元，则除的余式定义为，即，也就是不做此步伪除法。例8设基组，其中求对基组（BS）的余式。上海海运大学专用解：除的余式：除的余式：3)整序算法（BR格式）按下列步骤，可将一多项式组化成一三角形组（TS）。步1：输入（PS），令，置；步2：在中选取基组；若中的多项式个数等于n，则为所求，整序结束；否则，求出中除以外的每一个多项式对基组的余式。上海海运大学专用若这些余式中有一个为零（表示有无穷多个解）或有一个为非零常数（表示无解），则停机；否则，记这些非常数余式的集合为，转步３；步3令，置，转步２。上述整序算法需交替地选基组和求余式集，故称此整序格式为BR格式。每进行一次选基组和求一次余式集，称为进行一次BR步。需要指出的是：按上述步骤求得的三角形组实际上就是的一个特征组。然而从节省计算工作量的角度讲，只需求出的一个半特征组就可结束整序。上海海运大学专用例如，当计算到某一步时，在的n个多项式中，只有一个类为n的多项式，或只有一个类为n的多项式和一个类为n-1的多项式，则可将这个或这两个多项式选进基组中。例9 设，其中试对整序。解：

上海海运大学专用上海海运大学专用3、多项式方程组的零点集结构式吴文俊在文献[11~14]中给出了如下多项式组的零点集结构式：（38）

式中，是的特征组或半特征组。是将非常数不重复的多项式添入后的多项式组，而是历次基组中所有多项式的初式的集合。是将非常数不重复的多项式添入后的多项式组，而是在整序过程中被约去的所有最大公约式的集合。“＋”号和求和号SUM表示集合的并。是这些和的乘积。表示中使的部分。上海海运大学专用例10求例9中的零点集解：由例9知，该的特征组为：令，可得如下5个孤立零点，其中上海海运大学专用在历次基组中，只出现一个非常数初式，也没有约去最大公约式，故。显然，上述5个零点都使，故.可判断,无解，因而根据结构式（38），首先要对（PS）进行整序，以求得三个多项式组：（CS）、（IS）与（FS）。若（CS）含有一个非零常数多项式，且则（PS）无解；若（CS）中多项式的个数少于变元的个数n，且，则在不可约的情况下，（PS）有无穷多个解；若（CS）中含有n个多项式，则可求出，剔除使的解，得上海海运大学专用然后将（IS）和（FS）中每一个非常数不重复的初式和最大公约式分别添入（PS），构造出新的多项式组和,再重新整序，求得结构式（38）的后两个和集，最后才能求得大量的计算可能花在求结构式（38）中的后两个和集上。因为非常数不重复的初式和最大公约式往往不止一个，有时多达几十个、上百个；而且在对和的整序过程中，又会出现新的非常数不重复的初式和最大公约式，又需分别添入中进行检验。这种反复应用整序几十次、甚至上百次的计算工作量，在实际应用中是难以被接受的，必须对（BR）格式进行改进。上海海运大学专用三、的基组结式消元法基组结式消元法的主要思想是：根据秩的大小选取基组，利用贝左结式消元，将一个多项式组化成一个三角形组，再由改进的零点集结构式确定的所有解。1、贝左结式用辗转相除法可从两个多项式中消去一个变元而得到仅含他们系数的一个有理式，然后根据这个有理式是否为零，来判断这两个多项式是否有公共根。这样的有理式称为这两个多项式的结式。有多种形式的结式。例如西尔维斯特（Sylvester）结式，等等。这里采用低阶行列式表示的贝左结式。上海海运大学专用设和是两个非零多项式，它们的表达式为：（39）

式中，各和均为的多项式，文献[15]分别给出了和两种情况下的贝左结式。经归纳整理，我们得到如下贝左结式的统一表达式上海海运大学专用（40）

式中，上海海运大学专用当时，当时，。贝左结式为一阶行列式，其阶数比西尔维斯特结式的阶数低阶。根据结式的性质知，和的公共零点，必然是结式的零点。例11求和的贝左结式其中解：

上海海运大学专用上海海运大学专用2、零点集结构式

定理2在按（BR）格式对多项式组进行整序并求得三角形组的过程中，若不约去诸中的各多项式的最大公约式，则；但不一定成立。证明：不失一般性，设第一个基组中包含了多项式组中的２个多项式和，即：。进行整序并用伪除法消元时，可得中除外的个多项式对的第一个余集，其中上海海运大学专用（41）

式中，和分别为和的初式，指数为非负整数，为多项式。记，设上海海运大学专用由于的各多项式均是的线性组合，易知即；反之，设虽然，但从中，无法肯定，同样也无法肯定。只有当２个初式和不为零时，才能肯定同时由于从求与从求的做法相同，易知；直到求得时，成立：上海海运大学专用反之不一定成立。证毕。若在整序过程中约去诸中的各多项式的常数公约式，则定理2仍成立。推论1在按（BR）格式对多项式组进行整序并求得三角形组的过程中，若约去诸中的各多项式的最大公约式，则（42）

这里的含义同结构式（38）中的含义。证明：若先不约去最大公约式，当进行第一次（BR）步后，可得。由定理2可知，设有最大公约式，则中任一多项式上海海运大学专用均可表示为和另一多项式的乘积，即。若，则,故有，因而和两者中，至少有一个为零。由此推断下去，易知推论成立。证毕。根据推论1，可将多项式组的零点集结构式（38）改变为如下形式：（43）式中的和第三项的含义同式（38）中的含义；而且至少有一上海海运大学专用使,为历次基组中的非常数不重复的初式的集合。根据定理2可构造如下的零点集结构式：（44）

结构式（44）的含义是明确的：在求的过程中，若不约去诸中的各多项式的非常数最大公约式，则可保证对而言不失根。因此，只需求出的全部零点，然后代入方程组中检验，根据检验结果，在中剔除使的零点，剩下的零点就是的全部零点。上海海运大学专用根据结构式（44），在求解方程组时，只需对进行一次整序，也不需要记忆初式集，就可求得的全部零点，从而极大地减少了计算工作量，使吴方法向更实用的程度迈进了一大步。例12 设。试用结构式（44）求。解：经过两次（BR）步可得的三角形组。其中，上海海运大学专用求解，可得３个不同零点（记）：经代入原方程组检验知，他们是原方程组的全部不同零点，无需将整序过程中出现的初式添入中重新整序求解。3、基组结式消元法的主要计算步骤基组结式消元法仍按秩的大小选取基组，但不用伪除法而用贝左结式进行消元，且由结构式（44）求待解多项式组(PS)的零点集。因在求解过程中用到了基组和结式的概念，故取名为基组结式消元法[Z19]。上海海运大学专用(1)多项式对基组的结式1)两个不同类多项式的贝左结式设g和f为两个非零多项式，cls(f)=l＞0,deg(f)=k＞0,cls(g)=n≥l，deg(g,xl)=m≥k,则g和f可表示为：（45）

式中，上海海运大学专用称按式（40）生成的结式为多项式g对f的结式。显然，利用结式可从g和f中消去变元。当时，可按同样的思想生成g和f的结式。当g中不含变元时(即时），定义g对f的结式为。2)多项式对基组的结式设g(x)是一非零多项式，cls(g)＞0,为一基组。若设为g对的结式，为对的结式，…，为对的结式，则称为多项式g(x)对基组(BS)的结式。上海海运大学专用在上述求结式的过程中，若遇到中不含的类变元，则取，也即不计算对的结式。3)基组结式消元法的主要计算步骤用基组结式消元法求多项式组的多项式解的主要计算步骤如下。步1输入维数n，多项式组(PS)及其它所需信息；令(PS1)=(PS)，置k=1；步2在(PSk)中按本节二中选取基组的方法选出基组(BSk)。若(BSk)中的多项式个数等于n，则(TS)=(BSk)为所求，整序结束，转步4；否则，求出(PSk)中除(BSk)以外的每一个多项对基组(BSk)的结式。上海海运大学专用若这些结式中有一个为零(表示(PS)有无穷多个解)或有一个为非零常数(表示(PS)无解)，则停机；否则，记这些非常数结式的集合为(RSk)，转步3；

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

步4求出(TS)=0的全部零点，并根据改进型结构式（44）确定(PS)的所有零点，输出所需信息，计算结束。仿照吴方法中的提法，用基组结式消元法对多项式(PS)进行整序的算法仍称为(BR)格式。其中，每进行一次选基组(BSk)和求一次结式集(RSk)称为进行了一次(BR)步。作者用FORTRAN语言编制的基组结式消元法的程序取名为CHS。上海海运大学专用4、基组结式消元法的优点基组结式消元法具有下列3个明显的优点：1）基组结式消元法至多进行次（BR）步，就可求得的一个三角形组，其零点包含了的所有零点。而吴方法在一次整序中至少要进行次（BR）步，才有可能求得这样的。这是因为进行１次伪除并不总能消去１个变元；但展开１个结式总能消去１个变元。至于聚筛法[15]，要分别进行伪除求商和不带分式的高斯消元，才能求得，其消元工作量是非常大的。2）相对吴方法和聚筛法而言，在用基组结式消元法求得的中，各多项式具有较低的度数。这是因为吴上海海运大学专用方法和聚筛法都用伪除法或不带分式的高斯消元法进行消元。两种方法都有可能增大消元结果的度数。这可从除的伪除公式去理解。当的初式为一非常数多项式，的度数时，余式就有可能比贝左结式的多出因式，为非负整数。3）根据改进型结构式（44），基组结式消元法只需进行一次整序就可求得的所有零点，也不需要记忆初式集和最大公约式集，极大地减少了计算工作量，使吴方法向更实用的程度迈进了一大步。上海海运大学专用应当指出：基组结式消元法还存在有待改进的地方。如当贝左结式的阶数较高时，行列式的展开需要较大的计算工作量和计算机内存；求得的组，其各多项式的度数有时还较大；建议用WR分解法对进行后处理，以剔除多余的增根，得到度数较低的组，但进行后处理的计算工作量也相当大。例13 设,其中，均为的函数，且；试分别用基组结式消元法和吴方法求的三角形组。上海海运大学专用解：基组结式消元法：其中，吴方法：上海海运大学专用由比较可知，用吴方法所得中的第１个多项式比用基组结式消元法所得的多出一个因式。上海海运大学专用四、的结式消元法1、一元多项式组的最大公约式的结式消元法需用到一元多项式组最大公约式的概念。为此，先证：定理3设为一元多项式组，其中,为r个参变元，则：（1）有公共零点的充要条件是有非常数的最大公约式（2）若有非常数的最大公约式，则和具有相同的零点集；即上海海运大学专用证明设为的一个公共零点，则是的一个公约式。根据文献[10]知，一定是最大公约式的一个因式。因此，可令的非常数最大公约式为，其中为非零多项式。反之，设有最大公约式则对任一，可表示为；设为公约式的零点，则故是的一个公共零点。结论(1)成立。上海海运大学专用由结论(1)知，可设是的任一个公共零点，则

，所以。反之，设是最大公约式的任一个零点，则，故，结论(2)成立。根据结式的性质，易知成立：定理4设在多项式组中,选出所有类为k的多项式，并把它们的集合记为上海海运大学专用而把中挑剩的个多项式组成集合。利用个结式，从中消去变元，并把这些结式的集合记为，令，则但反之，不一定成立。从定理4可知，原方程组的解一定满足每一个结式。上海海运大学专用2、的结式消元法的消元步骤步0输入多项式组步1从中挑选出所有类为n的多项式，并把它们的集合记为：(46)

将中挑剩的所有多项式组成集合，并从