数值计算学习报告

《高斯消元法》研究与思考第一章《高斯消元法》描述1、《高斯消元法》的相关概念在自然科学研究和工程技术中有许多问题可归结为求解线性代数方程组的问题,线性方程组求解是科学计算中最常遇到的问题。如在应力分析、电路分析、分子结构、测量学中都会遇到解线性方程组问题。在很多广泛应用的数学问题的数值方法中，如三次样条、最小二乘法、微分方程边值问题的差分法与有限元法也都涉及到求解线性方程组。直接法是在没有舍入误差的情况下，通过有限步四则运算来求的方程组精确解的方法。直接法基本方法是高斯消元法，其改进方法包括高斯列主元消去法，三角分解法，追赶法等的基本思想和原理。高斯消去法（GaussEliminationMethod）是一种规则化的加减消元法。基本思想是通过逐次消元计算把需要求解的线性方程组转化为上三角形方程组，即把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化为等价(同解)的上三角形方程组的求解。1.1Gauss消去法的计算过程通过一系列的加减消元运算，也就是代数中的加减消去法，以使A对角线以下的元素化为零，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。现举例说明如下：）（）（）（322x-2-4x242x22x16x23x321321321xxx1.1.1消元过程第一步：将(1)/3使x1的系数化为1,再将(2)、(3)式中x1的系数都化为零，即由(2)-2×(1)(1)得由(3)-4×(1)(1)得第二步：将(2)(1)除以2/3，使x2系数化为1，得再将(3)(1)式中x2系数化为零，由(3)(1)-(-14/3)*(2)(2)，得第三步：将(3)(2)除以18/3，使x3系数化为1，得经消元后，得到如下三角代数方程组：）（）（）（3-1x242x16x3132x332321xx1.1.2回代过程)1(321)1(......23132xxx)1(32)2(......03432xx)1(32)3(......6310314xx)2(32)2(......02xx)2(3)3(......6318x)3(3)3(......1x由(3)(3)得x3=1,将x3代入(2)(2)得x2=-2,将x2、x3代入(1)(1)得x2=1,所以，本题解为[x]=[1,2,-1]T1.1.3用矩阵演示进行消元过程第一步：先将方程写成增广矩阵的形式nnnnnnnbaaabaaabaa21222221111211aBA第二步：然后对矩阵进行初等行变换第三步：将增广矩阵变换成上三角矩阵，主对角线全为1，左下三角矩阵全为0.即原方程组被等价转化成为上三角方程组，然后，逐步回代得原方程组的解即可。1.1.4高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为第一步，消元（1）令),3,2,1,(b),3,2,1,(a(()1()1(njibnjiaiiijij（2）对k=1到n-1，若akk(k)≠0，进行),,2,1(*1b),,2,l,(*1a),,2,1(/l)(k)1k()(k)1k()()(ik((nkkibbnkkjiaankkiaakkjikijijkkjikijijkkkkik）（）（第二步，回代若)()()()()()(/)*((/x0aiiijiiiiiinnnnnnnnnaxasgmbxab2、高斯消元法的运算量由公式，可得出消去过程的第k步共含有除法运算nk次，乘法和减法运算各()(1)nknk次，所以消去过程共含有乘除法次数为6523)1n)()(2311k11knnnkknknnn（含加减法次数为33)1n)(311knnkknn（而回代过程含乘除法次数为(1)2nn，加减法次数为(1)2nn，所以Gauss消去法总的乘除法次数为33n3323nnn，加减法次数为36523323nnnn二、《高斯消元法》的相关问题1.为什么说高斯消元法是中国古法？2.哪种线性方程组可用平方根法求解？为什么说平方根法计算稳定？3.什么样的线性方程组可用追赶法求解并能保证计算稳定？4.何为向量范数？给出三种常用的向量范数。5.何为矩阵范数?6.高斯消去法与LU分解有什么关系？用它们解线性方程组Axb有何不同？A要满足什么条件？三、《高斯消元法》的相关理论3.1.特征值和特征向量设A是一个nnx，使得Axx成A的特征值(CharacteristicValue)，x为A量(CharacteristicVector)。3.2向量和矩阵用Rnm表示全部nm实矩阵的向量空间,Cnm表示全部nm复矩阵的向量空间.mnmmnnijnmaaaaaaaaaaAAR212222111211)(（称为m行n列矩阵）.TnnxxxxRx21（称为n维列向量）naaaA21,其中ia为A的第i列.同理TmTTbbbA21,其中Tib为A的第i行.矩阵基本运算:(1)矩阵加法)),,.(,nmnmnmijijijRCRBRAbacBAC其中.(2)矩阵与标量的乘法ijijacAC,.(3)矩阵与矩阵的乘法),,(,1pmpnnmnkkjikijRCRBRAbacABC.（4）单位矩阵nnnReeeI21,其中.,,2,1,0,,0,1,0,0nkeTk3.3特殊矩阵设nnijRaA][,则有A为:(1)对角矩阵如果当ji时,0ija;(2)三对角矩阵如果当01ijaji时，;(3)上三角矩阵如果当0ijaji时，;(4)对称矩阵如果TAA;(5)正定矩阵如果设A是n阶实系数对称矩阵,如果对任何非零向量nxxX,,1都有0AXXT,就称A正定.四、《高斯消元法》国外研究进展十几年来直接法在求解具有较大型稀疏矩阵方程组方面取得了较大进展。关于三对角线性方程组的直接求解已经有大量并行算法,其中Wang的分裂法是最早针对实际硬件环境,基于分治策略提出的并行算法。它不仅通信结构简单,容易推广到一般带状线性方程组的并行求解,而且为相继出现的许多其它并行算法提供了可行的局部分解策略。近20年来求解三对角方程组的并行算法都是基于分治策略,即通过将三对角方程组分解成P个小规模问题,求解这P个小规模问题,再将这些解结合起来得到原三对角方程组的解。一般求解三对角方程组的分治方法的计算过程可分为3个阶段:一是消去,每台处理机对子系统消元;二是求解缩减系统(需要通信);三是回代,将缩减系统的解回代到每个子系统,求出最终结果。具体可分为以下几类:（一)递推耦合算法(RecursiveDoubling)由Stone于1975年提出,算法巧妙地把LU分解方法的时序性很强的递推计算转化为递推倍增并行计算。D.J.Evans对此方法做了大量研究。P.Dubois和G.Rodrigue的研究表明Stone算法是不稳定的。（二)循环约化方法(CyclicReduction)循环约化方法由Hockey和G.Golub在1965年提出,其基本思想是每次迭代将偶数编号方程中的奇变量消去,只剩下偶变量,问题转变成求解仅由偶变量组成的规模减半的新三对角方程组。求解该新方程组,得到所有的偶变量后,再回代求解所有的奇变量。即约化和回代过程。由于其基本的算术操作可以向量化,适合于向量机。此方法有大量学者进行研究,提出了许多改进的方法。例如,Heller针对最后几步的短向量操作提出了不完全循环约化方法;R.Reulter结合IBM3090VF向量机的特点提出了局部循环约化法;P.Amodio针对分布式系统的特点改进了循环约化方法;最近针对此方法又提出对三对角方程组进行更大约化步的交替迭代策略。（三)基于矩阵乘分解算法将系数矩阵A分解成AFT,方程Axb化为Fyb和Txy两个方程组的并行求解。这种算法又可以分为两类:1.重叠分解。如Wang的分裂法及其改进算法就属于这一类。P.Amodio在1993年对这类算法进行了很好的总结,用本地LU、本地LUD和本地循环约化法求解,并在1995年提出基于矩阵乘分解的并行QR算法。H.Michielse和A.VanderVorst改变Wang算法的消元次序,提出了通信量减少的算法。李晓梅等将H.Michielse和A.VanderVorst算法中的通信模式从单向串行改为双向并行,提出DPP算法,是目前最好的三对角方程组分布式算法之一。2000年骆志刚等中依据DPP算法,利用计算与通信重叠技术,减少处理机空闲时间取得了更好的并行效果。此类算法要求解P-1阶缩减系统。2.不重叠分解。例如Lawrie&Sameh算法、Johsoon算法、Baron算法、Chawla在1991年提出的WZ分解算法以及Mattor在1995年提出的算法都属于这一类。此类算法要求解2P-2阶缩减系统。(四)基于矩阵和分解算法将系数矩阵分解成AA0A,这类算法的共同特点是利用Sherman&Morrison公式将和的逆化为子矩阵逆的和。按矩阵分解方法,这种算法又可分为两类:1.重叠分解。这类算法首先由Mehrmann在1990年提出,通过选择好的分解在计算过程中保持原方程组系数矩阵的结构特性,具有好的数值稳定性,需要求解P-1阶缩减系统。2.不重叠分解。Sun等在1992年提出的并行划分LU算法PPT算法和并行对角占优算法PDD算法均属于这一类。需要求解2P-2阶缩减系统。其中PDD算法的通讯时间不随处理机的变化而变化,具有很好的可扩展性。X.H.Sun和W.Zhang在2002年提出了两层混合并行方法PTH,其基本思想是在PDD中嵌入一个内层三对角解法以形成一个两层的并行,基本算法是PDD,三对角系统首先基于PDD分解。PTH算法也具有很好的可扩展性。五、《高斯消元法》国内研究现状1、并行求解三对角系统的直接解法李晓梅等将H.Michielse和A.VanderVorst算法中的通信模式从单向串行改为双向并行,提出DPP算法,是目前最好的三对角方程组分布式算法之一。2000年骆志刚等中依据DPP算法,利用计算与通信重叠技术,减少处理机空闲时间取得了更好的并行效果。此类算法要求解P-1阶缩减系统。2、病态线性方程组解法研究病态线性方程组解法的研究是数值计算研究的一个重要课题.通过分析病态线性方程组的特点和成因的基础上,对一些传统的算法进行了改进,给出了加权迭代改善法和PSD-PCG法.其改进效果不仅在理论上得到了证明,且同时由几个典型的数值试验得到了验证.3、解循环三对角线性方程组的追赶法循环三对角、循环Toeplitz三对角线性方程组的求解在科学与工程计算中有着广泛的应用.运用矩阵分解给出此类方程组的直接解法;通过分析其特性,给出了达到机器精度的截断算法,其计算复杂度几乎等同于求解一个三对角线性方程组的计算复杂度.数值实验的结果与理论分析的结果十分吻合.该算法还推广到求解拟三对角线性方程组.4、基于矩阵分解的周期块三对角线性方程组的并行直接解法提出了分布式环境下求解周期块三对角线性方程组的一种并行算法．该算法充分利用系数矩阵结构的特殊性，通过对系数矩阵进行适当分解及近似处理，使算法只在相邻处理机间通信2次，并从理论上给出了算法有效的一个充分条件．最后，在HPrx2600集群上进行了数值试验，结果表明，实算与理论是一致的，并行性也很好．5、病态线性方程组的新解法：误差转移法提出了一种求解病态线性方程组的简便有效的新算法，它的主要思想是将直接求解法中的计算误差转移到一个中间量上，从而使得最终解获得很好的精度，因此可极大地缓解一般算法条件预优的困难以及病态方程组的求解难度。数