数值计算学习报告

《数值计算学习报告》由会员分享，可在线阅读，更多相关《数值计算学习报告（20页珍藏版）》请在金锄头文库上搜索。

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

2、d）是一种规则化的加减消元法。基本思想是通过逐次消元计算把需要求解的线性方程组转化为上三角形方程组，即把线性方程组的系数矩阵转化为上三角矩阵，从而使一般线性方程组的求解转化为等价(同解)的上三角形方程组的求解。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.Reult

9、er 结合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 derVo

10、rst改变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消去法列主元素消去法是为控制舍入误差而提出来的一种算法,在高斯消去法的消元过程中,若出现a=0,则消元无法进行,即使其不为0,但很小,把它作为除数,就会导致其他元素量级的巨大增长和舍入误差的扩散,最后使计算结果不可靠.使用