《数学毕业论文线性方程组的欲条件解法.doc》由会员分享，可在线阅读，更多相关《数学毕业论文线性方程组的欲条件解法.doc（26页珍藏版）》请在三一文库上搜索。
1、学校代码：10206学生学号：051074210 白城师范学院 毕业论文线性方程组的预条件解法Pre-conditions for Solution of System of Linear Equations 学生姓名：孙雷指导教师：牟欣 讲师学科专业：数学与应用数学 所在单位：数学系 2011年 6 月摘 要随着计算机的发展，在许多实际应用和数学研究中，经常遇到求解线性方程组的问题，而数值代数己经成为处理这些问题的强大工具。在本文中，主要研究了对线性方程组的几种预条件迭代解法。使用预条件矩阵来加速迭代方法的收敛性是通常所采用的方法，预条件迭代法对于解决系数矩阵是大型稀疏矩阵的情况有较好的效果
2、。证明了当线性方程组的系数矩阵A为不可约L-矩阵时的预条件AOR方法，并且证明了其收敛性，最后用数值试验验证所提出的理论结果。当选取最优参数时，通过数值试验可看出我们的方法所得迭代矩阵的谱半径比小。提出以SSOR多分裂作为内分裂的松弛不定常二级多分裂法，然后研究了所提出的方法在求解当系数矩阵为H-矩阵的线性系统的收敛性，最后具体给出此方法收敛性的论证及其应用。关键词： L-矩阵，H-矩阵，M-矩阵，预条件AOR法，SSOR多分裂AbstractWith the development of the computers, numerical analysis concerned with the
3、 solution of linear systems of equations is always used in the practical and mathematic problems.For a linear system, we study the several preconditioning method in this paper.It is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme which is very useful to
4、solve the large sparse coefficient matrix.We improve the preconditioned AOR iterative scheme for irreducible L-matrices considered and then we prove the convergence of our method.Lastly, numerical experiments to illustrate the theoretical results are provided.When choosing the approximately optimal
5、parameters, our scheme has small spectral radii of the iterative matrices than the spectral radii of AOR iterative scheme, which is shown through numerical examples.We present the relaxed nonstationary two-stage multisplitting method using an outer splitting and the SSOR multisplitting as inner spli
6、tting.Then, we study the convergence of the proposed method for solving the linear system whose coefficient matrix is an H-matrix.At last, we give the specific convergence of this method of argumentation and its application. KeyWords： L-matrix, H-matrix, M-matrix, preconditioned AOR method, SSOR mul
7、tisplitting目 录1 绪论11.1引言11.2常见的预条件方法22 预条件AOR迭代法42.1概论42.2预备知识52.2.1本章中用到的定义72.2.2本章中用到的定理72.3主要结果72.4小结133 预条件多分裂迭代法143.1概论143.2预备知识143.2.1本章中用到的定义143.2.2几种常见的分裂方式153.2.3本文中用到的定理163.3主要结果173.4小结19结论20参考文献21致谢221 绪论1.1引言很多科学问题的解决都需要解这样一个线性方程组，求解线性方程组是数值线性代数的一个基本问题，即给定，寻找解向量使得。解线性方程组的传统方法是用Gaussian消元
8、法，假设系数矩阵A是一个的非退化阵，这样用Gaussian消元法直接解的运算量是。并且许多微分方程经过适当差分或有限元离散所产生的线性代数方程组的系数矩阵，不仅具有大型稀疏的特性，而且常常呈现出规则的分块结果。当n很大且A稀疏时，用直接法就很不划算，而且需要很大的存储空间，人们开始考虑和研究用迭代法求方程组的近似解，即用某种极限过程去逐渐逼近精确解，并发展了许多非常有效的迭代方法，常见的如Jacobi方法、Gauss-Seidel方法、SOR方法、SSOR方法，这几种迭代方法是最常用的一阶线性定常迭代法。即若系数矩阵A的一个分裂：A=M-N，M为可逆矩阵，线性方程组Ax=b(M-N) x=b
9、Mx=Nx+bx =+得到迭代方法的一般公式： 其中：，H称为迭代矩阵，它的收敛性直接关系到方程组的求解，收敛性迭代矩阵的谱半径有关，谱半径小于1时就收敛，否则就发散，而且谱半径越小，迭代矩阵收敛速度就越快。若假设A是阶矩阵，且，和分别是的严格下三角和严格上三角部分，则经典的Gauss-Seidel迭代法的迭代矩阵为。迭代法解线性方程组时都假设矩阵A是非奇异矩阵，当矩阵A是奇异矩阵时，可以通过变换把变为一个和它同解的新的系数矩阵为非奇异的线性方程组。为改善迭代法的收敛性和收敛速度，Hadjidioms于1978年提出一种快速超松弛迭代法(简称AOR迭代法)，它含有两个参数，当时=，这种方法就变
10、为逐次超松弛迭代法(简称SOR迭代法)；随着并行计算机的发展，1983年Misirlis提出一种解线性方程组的方法，称为并行Jacobi型方法，它的突出优点是适合大型并行机的计算。胡家赣在1992年提出了两参并行的Jacobi型方法(简称2PPJ型方法)，使Misirlis提出的方法成为2PPJ型方法的特例。另外，结合实际的需要，还产生了一些如SSOR型迭代法、SAOR型迭代法、PSD型迭代法等一系列迭代方法，目的都在于改善迭代矩阵的收敛性和收敛的速度。1.2常见的预条件方法在实际的计算过程中，收敛性的改善不仅取决于迭代方法以及迭代矩阵中参数的选取，而且同方程组自身的某些变化也密切相关，例如可
11、以对方程组两边左乘一个非奇异矩阵P(预处理)。通过这种技巧，线性方程组Ax=b等价变为PAx=Pb (1-1)如果PA还有分裂，那么(1-1)对应的迭代格式为 (1-2)式(1-1)称为预条件方法。1991年，Gunawardena等提出了修改的Gauess-Seidel方法（简称MGS方法）如下：令(1-2)式中的P=I+S，其中 文献3证明了该预条件用于Gauess-Seidel迭代法的收敛性。为了进一步研究MGS方法并改善其收敛速度，1997年Kohno等利用带有n-1个参数的预条件矩阵，其中 并采用与文献3相同的迭代格式（只把S改成），将文献3的结果进行了推广。随后文献5将文献4中的预
12、条件方法应用到H-矩阵类。国内外很多学者对于这类方法都进行了进一步的研究，如GAOR迭代法，并且给出了当A为H-矩阵时的一些收敛性结论。本文的第二章将考虑用如下两种预条件矩阵形式： 和 这里，其中 并讨论了该预条件用于AOR迭代法的收敛性。当选取不同的参数值时，通过实例可以看出，我们所提出的预条件迭代矩阵的谱半径要比文献中所提到的预条件迭代矩阵谱半径小的多，在一定程度上改进了迭代法的收敛速度。 若A=是A的一个分裂，则三角阵称为A的一个多分裂，是非负矩阵，并且 。由此多分裂，我们得到了求解线性系统Ax=b的多分裂法，Bai，Sun和Wang在统一的算法框架下建立了矩阵多分裂迭代算法的收敛理论。
13、多分裂法首先由OLeary和White所提出，后来又被许多学者进行了进一步的研究。多分裂法被广泛的应用于二级分裂迭代法中，其中ILU多分裂法在文献里对于系数矩阵为H-矩阵或M-矩阵等的收敛性以及由此做出的预条件矩阵已做了深入研究和讨论，并得到了较好的收敛效果，但还有许多分裂法仍可用于二级迭代法中，及其他一些特殊类型的矩阵的多分裂法还可做进一步讨论。本文第三章将考虑当系数矩阵为H-矩阵时用SSOR多分裂作为内分裂的二级多分裂法的预条件法，并讨论了该预条件迭代法的收敛性，并与SSOR多分裂法进行了比较，数值表明我们的算法要优于SSOR多分裂法。2 预条件AOR迭代法2.1概论 在第一章中已经提到，
14、当线性方程组的系数矩阵A是大型稀疏矩阵或具有某些特殊性质时，对方程组的系数矩阵A进行预条件处理是一种不但常用而且较为有效的方法。其基本思想就是寻找一个特殊的可逆矩阵P，左乘方程组后，使得矩阵PA相应分裂的迭代矩阵的谱半径较小。近年有好多学者对系数矩阵为特殊情形进行了深入的研究。 在本章中，我们考虑当线性方程组的系数矩阵A为不可约L-矩阵时，预条件迭代法的构造及其具体应用。主要构造了二种预条件矩阵，把这二种预条件矩阵应用到AOR迭代法中，比较在此迭代法中的作用，还讨论了预条件AOR迭代法收敛性同预条件矩阵的参数之间关系。 考虑线性方程组 (2-1)其中x,b，在实际应用中，Gauss消去法及Ch
15、olesky分解法是常见的直接解法，但当系数矩阵A具有某些特殊性质时，这时迭代法具有了相当的优势，相比之下，直接解法往往很不实用，效果不佳。上面我们已就相关内容的展开作了铺垫性的说明，对于应具备的理论背景作了扼要的介绍，下面我们就系数矩阵为不可约L-矩阵的线性方程组预条件矩阵的选取作详细的论证。 为了更好的求解线性方程组Ax=b，这里是非奇异矩阵，常用某些非奇异矩阵P对(1-1)式进行预处理，即考虑方程组 PAx=Pb这里P称为预条件矩阵。1991年，Gunawardena提出了修改的Gauess-Seidel方法（简称MGS方法）如下：令上式中的P=I+S，其中文献3证明了该预条件用于Gau
16、ess-Seidel迭代法的收敛性。为了进一步研究MGS方法并改善其收敛速度，1997年Kohno利用带有n-1个参数的预条件矩阵，其中 并采用与文献3相同的迭代格式（只把S改成），将文献3的结果进行了推广。随后文献5将文献4中的预条件方法应用到H-矩阵类。本文则考虑用如下两种预条件矩阵形式： 和 这里，其中并讨论了该预条件用于AOR迭代法的收敛性。2.2预备知识 考虑线性方程组Ax=b，这里是非奇异矩阵，我们考虑用迭代法求解此方程组。对于矩阵A的一个分裂，其中，则有求解线性方程组(2-1)的基本迭代法为： 不失一般性，设矩阵A的一个分裂形式为，这里D，L和分别是A的对角、严格下三角和严格上三
17、角矩阵。不妨设D=I，则定义A的AOR迭代矩阵为： (2-2)则有AOR迭代法的迭代矩阵为： (2-3)这里参数和r都为正的。现在我们将原来的线性方程组(2-1)转换为预条件系统PAx=Pb (2-4)这里矩阵P称为预条件矩阵。则求解线性方程组(2-4)的基本迭代法为： (2-5)其中为初始向量，是矩阵PA的一个分裂。是实参数并且对所有的i=2,3,n都有 0。特别的，若令，则所对应的预条件矩阵就为6中所讨论的形式。令 这里，和分别是A的对角、严格下三角和严格上三角矩阵。由于=0，我们可得 (2-6)其中。令和，其中是对角矩阵，是严格下三角矩阵，则我们可得到： (2-7)其中 =I D*， L
18、*，。若我们将AOR迭代法用在预条件线性系统（2-4），则我们得到预处理AOR迭代法，其迭代矩阵为： 若 (2-8)或 若 (2-9)当=r时，则（预条件）AOR迭代法就是（预条件）SOR迭代法。对=r及迭代矩阵，由(2-3)，(2-8)，(2-9)可得到相应的迭代矩阵，即： (2-10) (2-11) (2-12)2.2.1本章中用到的定义定义2.2.1.1设为nn的矩阵，若则我们称之为Z-矩阵。定义2.2.1.2记所有nn实矩阵所组成的集合为,的子集为。当，且成立时，称矩阵A为L-矩阵。定义2.2.1.3设是同阶矩阵，若，则称则称。2.2.2本章中用到的定理定理2.2.2.1设A为n阶非负
19、不可约方阵，则 (a)(A)为A的一个正特征值；(b)A对于(A)，相应地存在一个正的特征向量x0；(c)(A)为A的一个简单特征值。定理2.2.2.2设A为n阶非负方阵，则有如下结论成立： (a)若存在一非负向量x，x0，使得Axx，则有(A)；(b)存在一正向量x，使得Axx，则有(A)；进一地的，如果A是不可约的且0xAxx对某一非负向量成立，则(A)成立，并且是一正向量。2.3主要结果 定理2.3.1设是一个L-矩阵，是A的不可约子阵。假设存在一个非空集和实参数，i=2,3,n，使得 若 设(2-3)和(2-8)定义的矩阵分别为和若0r1(0,r1)，则有： (a)若，则；(b)若，则
20、；(c)若，则。 证明 由(2-3)，可表示为 = (2-13)这里H是一个非负矩阵。由于A是一个L-矩阵，故L和U也是非负的。由(2-13)可得。由于是不可约矩阵，对所有的i，都有，所以可得矩阵A也是不可约的。由于0,r1，A是不可约矩阵，得是不可约矩阵。故由(2-13)得是不可约矩阵。由定理2.2.2.1，则存在一个正向量x，使得，我们很容易的可得： (2-14)由(2-8)和(2-14)有： (2-15)由于，得和是非负的。由于也是L-矩阵，则和都为非负矩阵。经简单计算，可表示为： (2-16)这里是一非负矩阵，是阶矩阵，是阶矩阵。由于对所有的i，故是一非零矩阵是不可约的，我们很容易得到
21、也是不可约的。由于0,r1,由(2-16)得是不可约的。令 及 (2-17)对所有的i，当及x0时是一非负向量且y向量的第一个元素都为0。由于是非负的下三角矩阵，故z0是一非负向量且z向量的第一个元素都为0。所以，我们可令 及 (2-18)这里是一非负向量。由(2-15)-(2-18)，得，故 (2-19) (2-20)当1时，由(2-20)，我们可得： 及 (2-21)由式(2-20)及定理2.2.2.2，有。由于，有： 当1时，由(2-20)，我们可得： 及 (2-22)是不可约的且，由(2-22)式及定理2.2.2.2得 (2-23)由于是非负的且，有。由(2-19)，及 (2-24)
22、由于由(2-23)及(2-24)得。当=1时，由式（2-15）。因此，由定理2.2.2.2可得： 推论2.3.2设是一个L-矩阵，A(2:n,2:n)是A的不可约子阵。假设存在一个非空集和实参数使得 若 设(2-10)和(2-11)所定义的矩阵分别为和。若00，使得，这里。由，我们很容易得到： (2-26)由(2-9)和(2-26)得： (2-27)由于，得，和是非负的。令 及 (2-28)对所有的i，当r1及x0时有是一非负向量且对所有的i，都不为零。由于是非负的下三角矩阵，故z0是一非负向量且对所有的i，都不为零。由(2-27)和(2-28)，我们可得： (2-29)当=1和1时，由定理2
23、.3.1和定理2.3.3，我们可直接相应的得到及。当1时，由(2-29)得和。由引理2.3.3可知是不可约的，故由定理2.2.2.2可得。故由定理2.2.2.2，结论成立。推论2.3.5设是一个L-矩阵，假设存在一个非空集使得对所有的i满足条件，以及实参数，使得对所有的，都有。设(2-10)和(2-12)所定义的矩阵分别为和。如果0B。定义3.2.1.3 若，且A可表示为A=sI-B，I为n阶单位矩阵，B0，那么当时，称A为M-矩阵，特别的当时，称A为非奇异M-矩阵，如果有，则称A为奇异M-矩阵。定义3.2.1.4 若，A可逆且，则称A为非奇异M-矩阵。定义3.2.1.5 若A为L阵，且有分解
24、那么A为非奇异M-矩阵的等价条件为。由定义可看出，定义3.2.1.3，定义3.2.1.4，定义3.2.1.5是等价的，L-矩阵在线性迭代理论中很大程度上指M-矩阵，M-矩阵在迭代法中主要指非奇异M-矩阵，很少涉及奇异M-矩阵。定义3.2.1.6 称为A的比较矩阵，若满足条件(a) 当i=j时，；(b) 当i=j，。 定义3.2.1.7 若A的比较阵是M-矩阵，则称A为H-矩阵。3.2.2几种常见的分裂方式 定义3.2.2.1如果A是方阵，且M为非奇异M-矩阵，N0，那么A=M-N称为矩阵A的M-分裂。 定义3.2.2.2如果A是方阵，A有分裂A=M-N，则 (1)如果，那么这种分裂叫正规分裂。
25、(2)如果，那么这种分裂叫弱正规分裂。(3)如果，且M为非奇异M-矩阵，那么这种分裂叫M-分裂。显然，M-分裂正规分裂弱正规分裂。定义3.2.2.3 称是矩阵A的一个多分裂，若： (1) 是A的一个分裂；(2) ，是一个非负对角矩阵，称为权矩阵；(3) ，这里I是一个单位矩阵。 对于矩阵A的一个多分裂，松弛参数为一个正数，对于求解线性系统Ax=b的松弛多分裂算法如下： 算法3.2.2.4松弛多分裂法： 给定一个初始向量 For i=1,2,直到收敛 for k =1 to , 注3.2.2.5 若是矩阵A的一个多分裂的一个多分裂，对每一个k，是的一个分裂，松弛参数为一个正数，则对于求解线性系统
26、Ax=b的松弛非定常二级多分裂算法如下： 算法3.2.2.6松弛非定常二级多分裂法： 给定一个初始向量 For i=1,2,直到收敛 for k=1 for j =1 to 注3.2.2.7在算法3.2.2.6中，分裂称为外分裂，分裂称为内分裂。当A是一个单调矩阵（即, ）或A是一个H-矩阵，在算法3.2.2.6中当内迭代数用一个常量s代替，即s与变量k和i无关时，则我们得到了松弛二级多分裂法(即算法3.2.2.8)。3.2.3本文中用到的定理 引理3.2.3.1 设是H-矩阵，这里D=diag(A)，则有以下结论成立： (a) A和是非奇异矩阵，且；(b) 。 定义3.2.3.2 设02，这
27、里D=diag(A)，是严格下三角矩阵，是一般矩阵。若是A的一个多分裂，则称是A的SSOR多分裂。其中 3.3主要结果 定理3.3.1 设A是一个nn阶的H-矩阵，且，这里D=diag(A)，是严格下三角矩阵，是一般矩阵，若是A的一个多分裂，。则当00时，是H-矩阵。设，则是矩阵C的一个正规分裂。当2/(1+)，1/，由引理3.2.3.1，得1, 从而我们可得并且。即当02/(1+)时是H-矩阵。由于和是H-矩阵，由引理3.2.3.1，我们可以得到 (3-1)由(3-1)，。(a)证毕。下面我们证明(b)和(c)。情况1：令01，则 (3-2)因此情况2：令12/(1+)，则 (3-3)因此，
28、则至此，(b)和(c)证毕。3.4小结 在本章中，我们讨论了在求解线性系统Ax=b（这里是一个H-矩阵）时，用SSOR多分裂作为内分裂的松弛非定常二级多分裂法的收敛性。为了有效的加快我们所提出方法的收敛性，如何选取一组参数将是我们今后所要探讨的问题，有待于进一步的研究。结论我们首先提出了对于不可约L-矩阵的AOR迭代法的预条件矩阵，并且证明了其收敛性。特别的，我们还可以讨论如何选取一组参数值，使得我们所提出方法的收敛速度有进一步的提高。如何选取一组最优参数将是我们今后继续研究的课题。我们在本文中还讨论了在求解线性系统 (这里是一个矩阵)时，用SSOR多分裂作为内分裂的松弛非定常二级多分裂法的收
29、敛性，当选取近似最优参数时，我们所提出的算法其收敛速度更快。为了更有效的加快我们所提出方法的收敛性，如何选取一组参数将是我们今后所要探讨的问题，还有许多多分裂法仍可用于二级迭代法中，及其他一些特殊类型的矩阵的多分裂法还有待进一步讨论。参考文献1A.D.Hadjidimos.Accelerated over relaxation method J. Mathematics of computation, 1978,32:149-1572胡家赣.双参并行Jacobi型方法及其收敛性J.计算数学,1992,14(1):70-783Gunawardena A.D., Jain S.K., Snyder
30、 L.Modified iterative methods for consistent linearSystemsJ. Linear Algebra Appl, 1991, 12:123-1434Kohno T.Improving modified iterative methods for Z-matrices J.Linear Algebra Appl, 1997,267:113-1235孙丽英.解线性方程组的预条件迭代方法J.高等学校计算数学学报,2002,24(2):155-1626胡家赣.线性代数方程组的迭代解法M.北京:科学教育出版社,19917Niki H, Harada K,
31、 Morimoto M, Sakakibara M.The survey of preconditioners used foraccelerating the rate of convergence in the Gauss-Seidel method J.Comput Appl.Math, 2004,13:587-6008张谋成,黎稳.非负矩阵论M.广州:广东高等教育出版社,19959Usni M, Niki H, KohnoT.Adaptive Gauss-Seidel method for linear systemsJ.Int J of Comput and Math, 1994,51:119-12510曹志浩.数值线性代数M.上海:复旦大学出版社，1996致谢在论文撰写过程中，得到了系里各位老师的支持与鼓励，尤其是指导教师牟欣老师，从确定题目到定稿打印，一直不顾劳累，抽出时间对论文的写作目的和方向予以指导和改正。对论文中出现的疑难问题，牟欣老师又帮忙查阅资料、文献，使论文能够顺利完成。在此对牟欣老师及系里的各位老师表示深深的感谢。