数值计算学习报告..

1、高斯消元法研究与思考第一章高斯消元法描述1、高斯消元法的相关概念在自然科学研究和工程技术中有许多问题可归结为求解线性代数方程组的问题,线性方程组求解是科学计算中最常遇到的问题。如在应力分析、电路分析、分子结构、测量学中都会遇到解线性方程组问题。在很多广泛应用的数学问题的数值方法中，如三次样条、最小二乘法、微分方程边值问题的差分法与有限元法也都涉及到求解线性方程组。直接法是在没有舍入误差的情况下，通过有限步四则运算来求的方程组精确解的方法。直接法基本方法是高斯消元法，其改进方法包括高斯列主元消去法，三角分解法，追赶法等的基本思想和原理。高斯消去法（Gauss Elimination Method

2、）是一种规则化的加减消元法。基本思想是通过逐次消元计算把需要求解的线性方程组转化为上三角形方程组，即把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化为等价(同解)的上三角形方程组的求解。1.1 Gauss消去法的计算过程通过一系列的加减消元运算，也就是代数中的加减消去法，以使A对角线以下的元素化为零，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。现举例说明如下： 1.1.1消元过程第一步：将(1)/3使x1的系数化为1,再将(2)、(3)式中x1的系数都化为零，即由(2)-2(1)(1)得 由(3)-4(1)(1)得 第二步：将(2)(1)除以2/3，使x2系数化

3、为1，得再将(3)(1)式中x2系数化为零，由(3)(1)-(-14/3)*(2)(2) ，得第三步：将(3)(2)除以18/3，使x3系数化为1，得经消元后，得到如下三角代数方程组：1.1.2回代过程 由(3)(3)得 x3=1,将x3代入(2)(2)得x2=-2,将x2 、x3代入(1)(1)得x2=1,所以，本题解为x=1,2,-1T 1.1.3 用矩阵演示进行消元过程第一步： 先将方程写成增广矩阵的形式第二步：然后对矩阵进行初等行变换第三步：将增广矩阵变换成上三角矩阵，主对角线全为1，左下三角矩阵全为0.即原方程组被等价转化成为上三角方程组，然后，逐步回代得原方程组的解即可。1.1.4

4、高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为第一步，消元（1） 令 （2） 对k=1到n-1，若akk(k)0，进行 第二步，回代 若 2、高斯消元法的运算量由公式，可得出消去过程的第步共含有除法运算次，乘法和减法运算各次，所以消去过程共含有乘除法次数为含加减法次数为 而回代过程含乘除法次数为，加减法次数为，所以Gauss消去法总的乘除法次数为，加减法次数为2、 高斯消元法的相关问题1. 为什么说高斯消元法是中国古法？2. 哪种线性方程组可用平方根法求解？为什么说平方根法计算稳定？3. 什么样的线性方程组可用追赶法求解并能保证计算稳定？4. 何为向量范数？给出三种常用的向量

5、范数。5. 何为矩阵范数?6.高斯消去法与LU分解有什么关系？用它们解线性方程组Ax=b有何不同？A要满足什么条件？3、 高斯消元法的相关理论3.1.特征值和特征向量设A是一个nn阶实矩阵，若对于数l，存在非零向量x，使得Ax=lx成立。则称l是A的特征值(Characteristic Value)，x为A的对应于l的特征向量(Characteristic Vector)。3.2 向量和矩阵 用表示全部实矩阵的向量空间,表示全部复矩阵的向量空间.（称为m行n列矩阵）.（称为n维列向量） ,其中 为A的第列.同理 ,其中 为A的第行. 矩阵基本运算: (1)矩阵加法 . (2)矩阵与标量的乘法

6、. (3)矩阵与矩阵的乘法 . （4）单位矩阵 ,其中3.3 特殊矩阵设,则有A为:(1)对角矩阵 如果当时,;(2)三对角矩阵 如果当;(3)上三角矩阵 如果当;(4)对称矩阵 如果;(5)正定矩阵 如果设A是n阶实系数对称矩阵, 如果对任何非零向量 都有,就称A正定.四、高斯消元法国外研究进展十几年来直接法在求解具有较大型稀疏矩阵方程组方面取得了较大进展。关于三对角线性方程组的直接求解已经有大量并行算法, 其中Wang 的分裂法是最早针对实际硬件环境, 基于分治策略提出的并行算法。它不仅通信结构简单, 容易推广到一般带状线性方程组的并行求解, 而且为相继出现的许多其它并行算法提供了可行的局

7、部分解策略。近20 年来求解三对角方程组的并行算法都是基于分治策略, 即通过将三对角方程组分解成P 个小规模问题, 求解这P个小规模问题, 再将这些解结合起来得到原三对角方程组的解。一般求解三对角方程组的分治方法的计算过程可分为3个阶段: 一是消去, 每台处理机对子系统消元; 二是求解缩减系统( 需要通信) ; 三是回代, 将缩减系统的解回代到每个子系统, 求出最终结果。具体可分为以下几类:（一) 递推耦合算法(Recurs ive Doubling)由Stone 于1975 年提出, 算法巧妙地把LU 分解方法的时序性很强的递推计算转化为递推倍增并行计算。D.J.Evans对此方法做了大量研

8、究。P.Dubois 和G.Rodrigue 的研究表明Stone 算法是不稳定的。（二) 循环约化方法(Cyclic Reduction)循环约化方法由Hockey 和G.Golub 在1965 年提出, 其基本思想是每次迭代将偶数编号方程中的奇变量消去, 只剩下偶变量, 问题转变成求解仅由偶变量组成的规模减半的新三对角方程组。求解该新方程组, 得到所有的偶变量后, 再回代求解所有的奇变量。即约化和回代过程。由于其基本的算术操作可以向量化, 适合于向量机。此方法有大量学者进行研究,提出了许多改进的方法。例如, Heller 针对最后几步的短向量操作提出了不完全循环约化方法; R.Reulte

9、r 结合IBM3090VF向量机的特点提出了局部循环约化法; P.Amodio 针对分布式系统的特点改进了循环约化方法; 最近针对此方法又提出对三对角方程组进行更大约化步的交替迭代策略。（三) 基于矩阵乘分解算法将系数矩阵A 分解成A=FT, 方程Ax=b 化为Fy=b 和Tx=y两个方程组的并行求解。这种算法又可以分为两类:1.重叠分解。如Wang 的分裂法及其改进算法就属于这一类。P.Amodio 在1993 年对这类算法进行了很好的总结, 用本地LU、本地LUD 和本地循环约化法求解, 并在1995 年提出基于矩阵乘分解的并行QR 算法。H.Michielse 和A.Van derVor

10、st改变Wang 算法的消元次序, 提出了通信量减少的算法。李晓梅等将H.Michielse 和A.Van der Vorst 算法中的通信模式从单向串行改为双向并行, 提出DPP 算法, 是目前最好的三对角方程组分布式算法之一。2000 年骆志刚等中依据DPP 算法, 利用计算与通信重叠技术, 减少处理机空闲时间取得了更好的并行效果。此类算法要求解P- 1 阶缩减系统。2.不重叠分解。例如Lawrie & Sameh 算法、Johsoon 算法、Baron 算法、Chawla 在1991 年提出的WZ 分解算法以及Mattor在1995 年提出的算法都属于这一类。此类算法要求解2P-

11、2 阶缩减系统。( 四) 基于矩阵和分解算法将系数矩阵分解成A=A0+DA, 这类算法的共同特点是利用Sherman & Morrison 公式将和的逆化为子矩阵逆的和。按矩阵分解方法, 这种算法又可分为两类:1.重叠分解。这类算法首先由Mehrmann 在1990 年提出,通过选择好的分解在计算过程中保持原方程组系数矩阵的结构特性, 具有好的数值稳定性, 需要求解P- 1 阶缩减系统。2.不重叠分解。Sun 等在1992 年提出的并行划分LU 算法PPT 算法和并行对角占优算法PDD 算法均属于这一类。需要求解2P- 2 阶缩减系统。其中PDD 算法的通讯时间不随处理机的变化而变化,

12、 具有很好的可扩展性。X.H.Sun 和W.Zhang在2002 年提出了两层混合并行方法PTH , 其基本思想是在PDD 中嵌入一个内层三对角解法以形成一个两层的并行, 基本算法是PDD, 三对角系统首先基于PDD 分解。PTH 算法也具有很好的可扩展性。5、 高斯消元法国内研究现状1、 并行求解三对角系统的直接解法李晓梅等将H.Michielse 和A.Van der Vorst 算法中的通信模式从单向串行改为双向并行, 提出DPP 算法, 是目前最好的三对角方程组分布式算法之一。2000 年骆志刚等中依据DPP 算法, 利用计算与通信重叠技术, 减少处理机空闲时间取得了更好的并行效果。此

13、类算法要求解P-1 阶缩减系统。2、病态线性方程组解法研究病态线性方程组解法的研究是数值计算研究的一个重要课题.通过分析病态线性方程组的特点和成因的基础上,对一些传统的算法进行了改进,给出了加权迭代改善法和PSD-PCG法.其改进效果不仅在理论上得到了证明,且同时由几个典型的数值试验得到了验证.3、解循环三对角线性方程组的追赶法循环三对角、循环Toeplitz三对角线性方程组的求解在科学与工程计算中有着广泛的应用. 运用矩阵分解给出此类方程组的直接解法; 通过分析其特性, 给出了达到机器精度的截断算法, 其计算复杂度几乎等同于求解一个三对角线性方程组的计算复杂度. 数值实验的结果与理论分析的结

14、果十分吻合. 该算法还推广到求解拟三对角线性方程组.4、基于矩阵分解的周期块三对角线性方程组的并行直接解法提出了分布式环境下求解周期块三对角线性方程组的一种并行算法该算法充分利用系 数矩阵结构的特殊性，通过对系数矩阵进行适当分解及近似处理，使算法只在相邻处理机间通信2次，并从理论上给出了算法有效的一个充分条件最后，在HP rx2600集群上进行了数值试验，结果表明，实算与理论是一致的，并行性也很好5、病态线性方程组的新解法：误差转移法提出了一种求解病态线性方程组的简便有效的新算法，它的主要思想是将直接求解法中的计算误差转移到一个中间量上，从而使得最终解获得很好的精度，因此可极大地缓解一般算法条

15、件预优的困难以及病态方程组的求解难度。数值计算的结果表明，算法对极其病态的线性方程组也可获得较好的精度和稳定性。6、块三对角线性方程组的并行直接解法提出了分布式环境下求解块三对角线性方程组的一种并行算法,该算法充分利用系数矩阵结构的特殊性,通过对系数矩阵进行适当分解及近似处理,使算法只在相邻处理机间通信两次.并从理论上给出了算法有效的一个充分条件.最后,在HPrx2600集群上进行了数值实验,结果表明,实算与理论是一致的,并行性也很好.第二章 算法研究一、高斯消元法方法有多少1. 高斯消元法及其改进法1、高斯消元法 高斯消元法，又称高斯消去法。是线性方程组直接解法的基本法。2、列主元Gauss

16、消去法列主元素消去法是为控制舍入误差而提出来的一种算法,在高斯消去法的消元过程中,若出现a=0,则消元无法进行,即使其不为0,但很小,把它作为除数,就会导致其他元素量级的巨大增长和舍入误差的扩散,最后使计算结果不可靠.使用列主元素消去法计算,基本上能控制舍入误差的影响,并且选主元素比较方便。3、 直接三角分解法 回顾高斯消元法的实质,是经过一系列的初等变换,将方阵A分解为下三角矩阵L与上三角矩阵U的乘积 A=LU,这里 , , .对系数矩阵一旦实现了这种三角分解(称为LU分解),那么此方程组就可写为等价形式于是,容易先解出y,再求出x.4、三对角方程组的追赶法应用有限元法解结构力学问题时，最后

17、归结为求解线性方程组，系数矩阵大多具有正定性质。所谓平方根法，就是利用对称正定矩阵的三角分解而得到的求解对称正定方程组的一种有效方法，目前在计算机上广泛应用平方根法解此类方程组。5、 改进的平方根法 在许多应用中，欲求解的线性方程组的系数矩阵是对称正定的.所谓平方根法，就是利用对称正定矩阵的三角分解而得到的求解具有对称正定矩阵的线性方程组的一中有效方法。2. 经典的高斯消元法经典的线性方程组的直接解法是高斯消去法，这是国际上的通用称呼，以数学家高斯命名，大约在1800年，高斯（Gauss）提出了高斯消元法并用它解决了天体计算问题。但高斯消去法实是中国古法，早在公元一世纪时我国东汉初年成书的九章

18、算术中已具雏形，至迟在公元263年我国三国时代的数学家刘徽在注解九章算术时已经完成，并经我国历朝历代的数学家们沿用至今。目前，高斯消元法以及有它改进、变形得到的选主元素消去法、三角分解法仍然是常用的有效方法。二、高斯消元法及其改进法方法比较1. 高斯消元法的优缺点分析1. 线性方程组的直接解法及其应用的优缺点分析(1) 高斯消去法优点：可以预先估计工作量。数据空间为系数矩阵、解向量、与常数向量所占的存储空间，而所需要的额外空间与数据无关。缺点：利用高斯消去法进行消元时，消元过程能进行到底的充分必要条件是系数矩阵A的各阶顺序主子式不为零。对于良态问题，高斯消去法也可能给出很坏的结果，这说明高斯消

19、去法的算法很不稳定。事实上，一般的矩阵都是病态矩阵，采用高斯消去法一般也不能得到满意的结果。(2) 列主元消去法优点：优点在于没有增加求解过程的运算量，但大大减小误差.缺点：经过列选主元后，其计算过程还是不稳定的，不适于求解大规模的线性方程组。(3) 直接三角分解法优点：直接三角分解法的优点在于它的精度比高斯消元法高。缺点：矩阵A可以进行三角分解是有条件的，它要求A为方阵且A的所有顺序主子式均不等于零。(4) 平方根法 优点：计算量为a3次乘除法，约为一般高斯消去法的一半。 数值稳定。 存贮量少，可只存贮对角线以下元素。缺点：平方根法的缺点是需要n个开方运算。(5) 追赶法优点：追赶法的计算量

20、是比较小的，追赶法计算公式中不会出现中间结果数量级的巨大增长和舍入误差的严重累积。缺点： 不足之处是当某个时，就不能进行2. 最好的方法是最好的方法是直接三角分解法。（1）由于在求出和后，和就无须保留了，故上机计算时，可把和错误！未找到引用源。,y存在所占的单元，回代时取代错误！未找到引用源。整个计算过程中不需要增加新的存储单元。而且系数矩阵的三角分解与右端常数项无关，故在计算系数矩阵相同而右端项不同的一系列方程组时，用三角分解法更为简便。（2）如果已经实现了A=LU的分解计算，且L,U保存在A的相应位置，则用直接三角分解 法解具有相同系数的方程组是相当方便的，每解一个方程组仅需要增加n2次运

21、算。第三章 算法应用1、 高斯消元法方法怎么用1. 一般程序设计高斯消去法的matlab程序方法高斯消去法求解方程组.根据高斯消去法,编制matlab程序如下首先建立一个M-file文件,保存在work中,文件名为magauss.mfunction x=magauss(A,b,flag)%用途:Gauss消去法解线性方程组Ax=b%格式:x=guass(A,b,flag),A为系数矩阵,b为右端项,若flag=0,则不显示中间过程,%否则显示中间过程,默认为0,x为解向量if nargin A=1 1 1 1;1 2 2 2;1 2 3 3;1 2 3 4;b=4 3 2 1; x=magau

22、ss(A,b);x得计算结果x = 5 0 0 -1二、高斯消元法方法用哪好？1. 高斯消元法方法在你所学专业的应用 工程中求解结构受力后的变形 空气动力学中计算机翼周围的流场 利用滑动最小二乘插值函数加权残值法求解结构动力学方程 2. 高斯消元法方法在你了解的其他领域的应用 气象预报中计算大气的流动 在结构动力学的动力反应数值分析方法中有常加速度法，此方法通过迭代法逐步逼近解析解。利用高斯消元法及其改进法解线性方程组解决一些如道路的交通流量，电网的电流流量，解析几何等的实际问题。第四章 算法展望我们所学的计算方法有：1. 插值法2. 拟合法3. LU法4. 迭代法5. 幂法和反幂法6. 欧拉

23、法7. 龙贝格法在机械专业的应用举例：1.插值法插值法空间插值从广义上讲应分为空间点插值和空间面插值。两者之间有许多不同之处:定义不同。点插值是指已知某些点的值来估计未知点的值;面插值是指已知统计变量在某一分区系统的值求在同一研究区内另一分区系统下的统计变量的值。作用的数据对象不同。点插值主要用于自然地理数据,是某些点的值;而面插值主要用于社会经济统计数据,是统计单元上的集合数据,是某些面的值。插值方法不同。如前所述,点插值和面插值的方法有极大的不同。插值方法的理论基础不同。其在机械中的应用有：基于减小修正量和提高工作效率的考虑，应用插值法中的牛顿插值，提出了一种简单、实用的凸轮工作廓线的修正

24、设计方法，这种方法不必再去考虑原有解析方程的形式，只需通过对要进行修正的曲线附近的一些离散点的数据进行处理，就能对现有凸轮工作廓线进行修正，特别适合凸轮曲线在实际使用中的局部修正设计2。2. 拟合法 曲线拟合法在工程机械发动机故障诊断中的应用3.LU法高斯消元的过程实际是把系数矩阵A分解成单位下三角矩阵和上三角矩阵的乘积的过程。只要A为非奇异，经过一定的行交换后，它一定可以分解为两个三角形矩阵的乘积。设A=LU，其中L为单位下三角矩阵，U为上三角矩阵。这种分解就是杜立特尔分解，即LU分解。经典的高斯消元法是1810年提出的，它稍作修改产生矩阵的LU分解，则是二十世纪四十年代提出的，当A非奇异时

25、只要对A做行置换，总可使PA=LU,其中P为行置换矩阵，利用它求解线性方程组相当于列主元消去法，它的好处是具有相同系数矩阵A的不同向量b的线性方程组AX=b可节省工作量，当矩阵A对称正定时可用LL分解的平方根法或改进平方根法，它是计算稳定的。4. 迭代法对于给定的线性方程组x=Bx+f，用公式x(k+1)=Bx*+f逐步带入求近似解的方法称为迭代法。线性方程组的基本迭代法包括雅克比迭代法、高斯-赛德尔迭代法、SOR迭代法、分块迭代法和共轭梯度法，迭代法有存储空间小，程序简单等特点，是解大型稀疏线性方程组的有效解法，经常出现在边值问题和偏微分方程数值中。这些系统方程未知数n可达上万个。而系统矩阵

26、A非零元素很少。迭代法中收敛性与收敛速度十分重要，实用中以收敛速度较快的SOR法应用最广，但选出最优参数是很困难的。其在机械中应用有迭代学习法在机械压力机滑块位置控制中的应用5. 幂法和反幂法幂法是计算矩阵主特征值（矩阵按模最大的特征值）及应对特征向量的迭代法，计算简单，特别是用于大型稀疏矩阵情形，但收敛速度往往不能令人满意，使用时可以结合反幂法及位移技巧等手段加速收敛。反幂法是计算海森伯格阵或三对角阵的对应一个给定近似特征值的特征向量的有效方法之一。6. 欧拉法欧拉方法是最简单、最古老的一种数值方法。基本思路是用差商近似导数。其在机械中的应用有基于牛顿欧拉法的4-UPS-RPS机械刚体动力学分析。 7. 龙贝格法龙贝格方法是目前计算机上求积的重要方法，针对积函数变化不均匀的自适应方法也是以此为基础给出的.第五章 学习思考 时间总是过得很快，转眼间已经接近学期末了，学习数值计算也已经一个学期了。刚开始感觉还可以，知识接受起来比较容易，后来慢慢的感觉越来越难，上课时越听越朦胧。虽然听不懂，但是每节课依旧坚持上着，总觉得哪怕一节课只收获一点点那也是值得的。虽然懵懵懂懂，但经过