《一类新预条件Gauss》由会员分享，可在线阅读，更多相关《一类新预条件Gauss（17页珍藏版）》请在金锄头文库上搜索。
1、一类新的预条件 Gauss-Seidel 迭代法摘 要：本文给出了一个新的预条件因子 Pt ,证明了在非奇异 M 矩阵和严 格对角占优 L 矩阵下，该预条件不仅加快了 GaussSeidel 迭代法的收敛速度， 而且说明了在该预条件下 GaussSeidel 迭代法的谱半径是单调下降的 . 最后再 用相关的数值例子说明文中给出的预条件 Pt 要优于文献中所给的预条件 .关键词 ：预条件； GaussSeidel 迭代法；谱半径；收敛性；收敛速度 .A New Class of Preconditioned Gauss-Seidel Interative MethodAbstract: This
2、 paper give a new preconditioner large sparse linear equationsPt .In the pre condition,by using Gauss-Seidel iteration format was linear equations . we first present a preconditions factor and then prove the accelerated convergence of the iteration method by the preconditions under the nonsingular M
3、matrixDiscussed the in the the Strictly Diagonally Dominant the L matrix under the conditions of, the pre-conditions to speed up the the the convergence speed of of the Gauss-Seidel iterative method, but also in the the pre-under the conditions of the the Spectral Radius of the Gauss-Seidel iterativ
4、e method is monotonic decliningFinally ，some numerical examples are given to explain our theoretical result.Key words: pre-conditions factor，GaussSeidel iteration method ， spectral radius， weak regular splitting;，convergence rate.引言在对自然科学与社会科学许多实际问题进行数值模拟时， 人们最后都归结为 求解一个或者一些大型稀疏矩阵方程组 ,因此研究大型稀疏矩阵方程组的
5、解法是 人们关注的焦点，后来人们发现迭代法是求解这种线性方程组的一类主要方法之 一，但是在实际生活中， 迭代矩阵的收敛性和收敛速度的改善不仅取决于迭代方 法和迭代矩阵中参数的选取， 而且和方程组自身的某些变化密切相关 近几年来， 稀疏线性方程组的迭代解法有了很大发展， 特别是预条件矩阵的引入， 大大加快 了迭代的收敛性和收敛速度 .因此，对预条件的研究仍是一个意义深刻的课题 .为了加速迭代法的收敛速度 ,很多学者对线性方程组提出了各种不同的预处 理方法 .1991 年文献 2 中 Guwnawardena等人提出预条件 P I S ，其中1a1，200001a2,30000100P I S00
6、01an 1,n00001文献 5 中提出的预条件100000100000100P I R00010an,1an,2an,3an,n 11以及文献 7 中提到的预条件1a1，2000a2,11a2,300a3,10100PS I Ban 1,n001an 1,nan,10001本文主要考虑一种新的预条件因子1t 2a21a1210 a23 000Pt I S Sttn 1an 1,100an 1,ntnan,1001并且新的预处理矩阵加速了 Gauss-Seidel迭代法的收敛速度此时，预条件 Gauss-Seidel迭代法的迭代矩阵为G (DLt) 1Ut(IDS)(LLSSt)1(UU S
7、S).1. 预备知识1.1 相关定义定义12 设矩阵 A (aij)n n Rn n ，如果对于矩阵主对角线的元素都不小于 0，而主对角线外的元素都不大于 0，则称矩阵 A为 L 矩阵.定义22 设A (aij)n n Rn n，矩阵 M 和N满足 A M N,其中M 为可选 择的非奇异矩阵，且使 Mx d容易求解，称 M 为分裂矩阵， M 1N 为迭代矩阵， 若 M 1 0 和 N 0 ，则称 A M N 是 A 的正则分裂；若 M 1 0 和 M 1N 0 ， 则称分裂 A M N 是若正则的 .定义33 如果 xk 是由迭代公式 xk 1 Bxk f,k 0,1,2 ，产生的序列， 且满
8、足 lim xk x , x0 Rn, 那么称 x k 1 Bx k f 是收敛的 .k定义43 设矩阵 A (aij)n n Rn n，A 可表示为 A sI B,B 0，I 为n阶单 位阵，并且当谱半径 (B) s，那么 A是M 矩阵.当 (B) s时，则称 A是非奇异 M 矩阵 .定义 5 4 设矩阵 A (aij )n n Rn n ，如果 A的元素满足n|aii | j 1,j i |aij |i 1，2 n, ,j 1,j i则称 A 为严格对角占优矩阵 .1.2 相关引理引理 14 设 A 为非奇异 M 矩阵，分裂 A M1 N1和A M 2 N2是若正则 的，若 M2 1 M1
9、 1，N2 0，则有(M1 1N1)(M 2 1N2).引理 23 若系数矩阵 A 为严格对角占优 L 矩阵，那么经过预处理后的矩阵 A 是严格对角占优 M 矩阵 .证明 设经过预处理后所得的矩阵为 A (aij )n n .因为矩阵 A 是严格对角占优 L 矩阵，则有当 i j 时1 aij 0 ，所以从而有0 a1jaj1 1 ，1 a1jaj1 0 ， ( j 2, ,n).因此矩阵 A 的对角元部分是Dt diag(1 a12a21,1 a23a32 t2a21a12, ,1 tnan,1a1,n) 0,对于矩阵 A 的非对角元部分有a1,jj 2, ,n,aijai,1 tiai,1
10、 i 2, ,n,ai,j tia1,j ai,1 其它.因为a1,j0, ai ,1 ti ai ,1 0,ai,j ti a1, j ai,1 ai,j0.矩阵 At的非对角元部分是不大于 0 的,所以矩阵 At 是L矩阵.记a (1,1, ,1)，则有 nnTAa (j 1a1j, , j 1anj) 0.又因为 Pt I St S 0 ，所以At Pt Aa 0.引理34 设矩阵 A (aij)nn Zn n ，则有以下两个等价性质(1)存在向量 x ，使得 Ax 0 ；(2)矩阵 A是非奇异 M 矩阵.引理45 设矩阵A (aij)nn Zn n为非奇异M 矩阵，B Znn，若有B
11、A， 则A1，B 1都存在且 A1 B1 0.引理53 若 A为严格对角占优矩阵且 A为 L矩阵，则 A 1 0并且 A为非奇异M 矩阵证明 由于 A 是严格对角占优矩阵，则有n|aii | j 1,j i |aij | i 1,2, ,n, j 1,j i成立，从而有naii | j 1,j i |aij | 0.记 a (1,1, ,1) ，有又由于 A为L 矩阵，则对 innAa (j 1a1j, ,j 1anj)T.j,aij 0 且 i j,aij 0，从而有j 1aijaiij 1,j iaij |aii | j 1,j i|aij| 0.即 Aa 0 .所以，由引理 2得 A为非
12、奇异 M 矩阵.由定义 4 知 A 若 0 (G ) 1，有 (G ) (G ) ； 0.2. 主要结论2.1 新预条件下 Gauss-Seidel 迭代法的收敛定理定理 1 线性方程组Ax b ， (1) 其中 A 为严格的对角占优 L 矩阵，若,即 i 2,3, ,n,都有 i i，( 1, 2, , n), ( 1, 2, , n),并且 i 0,1, i 0,1 ， i 2,3, ,n, G 表 示用 P I S +S 预处理矩阵后的迭代矩阵， G 表示用 P I S +S 预处理矩阵 A 得到的迭代矩阵，I. 若对于 i 0,1,i 2, ,n, 有(G ) (G ) 1.II. 若
13、 A 为非奇异且是不可约的 M 矩阵，则对于任意的 ti 0,10,1i , 2, 3n,都有, 以,下结论a1 i,ai , 12) 若 (G ) 1，有 (G ) (G ) ；3) 若 (G ) 1,有 (G ) (G ).证明 I 因为矩阵 A是严格的对角占优 L 矩阵，所以 A为非奇异 M 矩阵且 矩阵 A ,A 是严格对角占优非奇异 M 矩阵.若令 A ,A 的分裂如下ADLUI DSL L S SU US S E F ，ADLUI DSL LS SU U SS E F ，其中E I DSLL SS ,F U U S S，E I DSLLSS ,F U U S S，由定理 1的证明可
14、知， A EFEF 是矩阵 A的两个弱正则分裂.因为有 ，EEI D S L L S S(U U S S)I D S L LS SU U S S(D s D s) (S S LsLs ) 0，所以E E ，由引理 4 可得11E 1 E 1 ，又 F 0. 从而由引理 1 知(E 1F )(E 1F ) 1.由于E 1F G ,E 1F G ，所以有(G ) (G ) 1.II 因为系数矩阵 A是非奇异不可约 M 矩阵，从而由引理 3 可得At I S St A 也是非奇异不可约 M 矩阵 .由于1At Dt Lt Ut ,Dt 1 0,Lt Ut 0, 则At Dt Lt Ut是矩阵 At的一个 M 分裂，Gt Dt Lt 1U t,从而由引理 1知，存在一个正向量 x， 使得Gt xGt x,令Gt ，由定理 1 知G x x I DS L LS S 1 U US S x x1 I DS L LS SDS LS U S x因为y I DS L LS S 1 DS LS US x 0, 所以当 0 (G ) 1 时，有0 1,G x x ( 1)y
