对病态方程组的处理方法研究.doc

对病态方程组的处理方法研究蓝醒龙（广西民族大学数学与计算机科学学院03数本2班，530006）摘 要： 对病态线性方程组解法研究是数值计算方法的一个重要研究课题。本文分析了病态方程组的特点，介绍了几种有效的解法。关键词： 病态线性方程组；条件数；预处理；迭代Studying The Algorithm For Solving Ill-conditionedSystem Of EquationsAbstract： Studying the algorithm for solving ill-conditioned system of equations is an important issue. This paper analyses the equations characteristic, and introduces several effective algorithms.Key words：ill-conditioned system of equations; condition number; pretreatment; iteration1 问题的提出 一个线性方程组，若右端向量或系数矩阵的微小变化就会引起方程组的解发生很大的变化，则称为病态方程组。方程组的系数矩阵的条件数刻画了方程组的性态，若，则称为“病态”方程组；若相对较小，则称为“良态”方程组。良态方程组用GAUSS消去法和JACOBI等简单的迭代法就可以得到比较好的计算解，而对于病态方程组，一般的直接法和迭代法会有较大的误差，甚至严重失真。所以，在解方程组时，有必要先对方程组的性态进行研究，采用相应的算法，才能得到比较精确的计算解。利用方程组的条件数来判断就是一个很好的办法。下面的一些直观的现象可作为判别病态矩阵的参考：（1）在主元消去法的过程中出现小主元，则有可能是病态矩阵，但病态矩阵未必一定有这种小主元；（2）若解方程组时出现很大的解，则有可能是病态矩阵，但病态矩阵也可能有一个小解；（3）从矩阵本身来看，若元素间数量级相差很大且无一定规律；或矩阵的某些行（列）近似线性相关，即矩阵的行列式接近于0，这样的矩阵就有可能是病态的。 当然，这些现象只能帮助我们做初步的判断，并且很多病态矩阵也不一定会出现这些现象。所以，最可靠的判别方法是求出矩阵的条件数。在文1中，引用了Forsythe和Moler的一种估计的简便方法：若残向量，表示用Gauss消去法求解的计算解，表示用Gauss消去法求解的计算解，则 其中，是计算时采用的有效数位。在文1中，作者还举例说明了此法的有效性。有关条件数及其估计，在文5中也有详细的讨论。本文讨论其它的处理方法。2 对病态方程组的处理方法2.1 方程组的预处理 设阶线性方程组 （1.21）解方程组（1.21）的收敛速度通常与矩阵A的条件数有关。当矩阵A的条件数比较大时，收敛速度往往很慢，所得的解的误差也会相当的大，甚至是难以接受的，为此，在求解方程组前，先改善系数矩阵的条件数，即进行预处理。将方程组（1.21）化为易于求解的等价方程组 （1.22）其中，仍然保持原来的特性，c为预处理矩阵，且容易从方程组中解出X。若的条件数小于的条件数，则用相应的算法解方程组（1.22）的收敛速度将会比解方程组（1.21）的快，这就是病态方程组进行预处理的目的。这里用到的预处理方法是不完全的Cholesky分解法，这个方法是1977年J.A.Meijerink 和A.Van der Vorst提出的。将系数矩阵A分解成 其中，L是下三角阵，使尽可能接近A，且L保持跟A一样的稀疏性或具有其它形状的稀疏性。 完全分解是对系数矩阵A进行三角分解，不完全分解是对矩阵进行三角分解。由于有矩阵R可以变化，因此L的稀疏性结构可以预先适当控制，即L中哪些元素为0，可以预先规定，但也不能任意规定，还要考虑到接近A。在实际计算中，常常考虑R有较多的零元素。比如，有矩阵，它是对称正定的。我们将A分解成 要求L和A有相同的稀疏性，即 而。我们比较两端对应的元素。由 取，得。相似的可以得到，。于是，我们可以计算得 在做出A的不完全的Cholesky分解 后。方程组 可化为 其中，。 不难验证，当R尽量的小，时，有，可估计，即改变了A的条件数。可见不完全的Cholesky分解法是一种比较有效的预处理法。具体的M的选择有不同的方法。最简单的就是J迭代（或块Jcobi迭代）中的分解，即 另一种方法是利用对称超松弛（SSOR）或块对称超松弛方法中的分裂。 在很多实际计算中，利用矩阵A的不完全分解的条件预优处理，得到了相当成功的数值结果。2.2 残量迭代法 残量迭代法是在用Gauss消去法求出方程组的近似解后，进行以下的计算： .然后，重复迭代： 其中，X，Y和Z用t位有效数字计算，用2t位有效数字生成。残量迭代法的计算量比较少，在机器上非常容易执行，而且计算精度也比较高，但是它不是对所有的病态方程组都适用，当时，其计算结果就不够准确。2.3 加权迭代改善法 加权迭代改善法是对方程组（2.21）构造一个迭代过程： （2.3.1）其中为一常数，I为与A同阶的单位方阵,为迭代次数，为解的初始值，是第k次迭代后求得的近似解。只要取得合适，的逆矩阵便存在。 文5中，作者具体地证明了下面的结果： 对初始值，当时，由迭代求解过程（2.3.1）产生的序列：收敛到方程组（2.3.1）的真解。 （2.3.1）的具体的迭代过程是： 对，用表示第一次算出的解，将代入迭代过程得 为找出和的迭代关系，令 则有 即 显然，若要使 为精确解，则须确定， 若记 （2.3.2）则有 （2.3.3）解上式，即可得到。由于实际计算中有误差的存在，不一定是准确解。因此，再将代入（2.3.1）中算出，再代入（2.3.3）解出，得出进一步的近似解重复以上过程，直到满足精度为止。 由于值的选取将对计算的收敛速度具有比较大的影响，文5中，作者给出了经验估计式 其中是矩阵A中最小非零元素值的下界.加权迭代改善法不必选主元且保持原系数矩阵的稀疏性，通过加权因子的选取来改善矩阵的条件数，得到了比较好的计算结果，但是由于加权因子的选取也使得加权迭代改善法的应用受到了限制。2.4 误差转移法误差转移法是基于即使方程组的计算解的精度不高，也可获得相对较小的余量这一特点而设计的。设方程组 （2.4.1）的计算解为，既然 （2.4.2）对误差很大的解也能比较准确的成立，因而，如果求解 （2.4.3）其中，c为阶非奇异矩阵，则即使计算解的误差比较大，也能通过（2.4.3）式得到比较准确的。由于未知，（2.4.3）式并不能直接求解，但从（2.4.1）式有 （2.4.4）（2.4.3）式可转化为求解 （2.4.5）于是可求出，再由（2.4.3）式得到原问题的解。 在这种解法中，问题的病态性固然会导致解的巨大误差，但这种误差直接反映在上，对的影响则小得多，因为主要的误差已经从原来的转移到中间量上了。此解法中，矩阵c的选取将直接影响到算法的有效性，经过讨论，作者认为取实际效果比较好。而此时方程组（2.4.5）的系数为，可能由于矩阵元素较大而出现溢出，故在计算前先对方程组（2.4.1）分别进行一次行列均衡处理，因此，整个算法过程为： （1）对方程组（2.4.1）进行一次行均衡处理： （2.4.6）其中，（2）再对方程组（2.36）进行一次列均衡处理： （2.4.7）其中， （3）形成方程组 （2.4.8） （4）采用对称分解法解方程（2.4.8） （5）计算 误差转移法的原理及实现都十分简捷，仅运用了常规的行列均衡处理和对称三角分解，而且巧妙地把误差转移到另一个中间量上，对病态问题具有高度的有效性。2.5 迭代修改法 解系数比较大的线性方程组时，通常采用迭代法。迭代法可以克服误差积累的问题，且具有达到所要求的精度和对计算内存要求不大，计算时间比较少的优点。 迭代修改法是在简单迭代法的基础上，根据线性代数对角占优简单迭代必收敛的性质修改而成的。设线性方程组 （2.5.1）其中系数矩阵A是阶非奇异，病态的。首先分解A：，得其中，在方程组的两端同时加上DX，得 其中D为对角阵，且，符号的含义是与b同号，数值取a。整理后得即得迭代格式 （2.5.2）记，那么有 由此可见（2.5.2）式收敛，因为矩阵D的加入使得满足对角严格占优简单迭代收敛的条件。实际计算中，有时可以放宽处理，可取或 故修改的Jacobi迭代为 （2.5.3）类似的，修改的Seidel迭代为 （2.5.4）下面的例子可以看出此法的有效性：例1 求解，其中 , 其精确解为, 取, 用（2.5.3）迭代20步得，. 由以上数值结果可看出此迭代法对求解病态方程组是有效的。它适宜于解多维的实际问题。不仅可以达到预定的精度（受计算机字长限制），也便于在SIMD或MIMD并行计算机上实现。但是他虽然能保证收敛，但收敛速度较慢，而且解的精度到底有多好，还得将解代入原方程检验。2.6 预处理迭代修改法预处理可以降低方程组系数矩阵的条件数，使得计算解的收敛速度和精确度得到提高；而迭代法可以克服积累误差的问题，提高解的精确度，而且用比较少的时间就可以得出方程的解。综合两者的优点把它们结合起来，形成了预处理迭代修改法。从略。3 数值例子例2 迭代求解，其中，.其精确解为. 过程略.例3 迭代求解，其中 , .其精确解为. 过程略.例4 求解，其中 其精确解为. 过程略.参考文献:1 刘美娟. 关于求解病态方程组的残量迭代算法J. 九江师专学报.1994, 13(6): 7-11. 2 胡圣荣,罗锡文. 解病态方程组的新解法J.华南农业大学学报. 2001,22(4): 91-94.3 王永宝. 关于求解病态方程组的迭代解法J. 航空计算技术. 1995,(3):20-25.4 林胜良. 病态线性方程组解法研究D.