 Pure Mathematics 理论数学, 2012, 2, 39-44 http://dx.doi.org/10.12677/pm.2012.21008 Published Online January 2012 (http://www.hanspub.org/journal/pm) Copyright © 2012 Hanspub 39 Preconditioned Diagonally Dominant Properties of H-Matrix Xuezhong Wang, Xiaomei Li School of Mathematics and Statistics, Hexi University, Zhangye Email: xuezhongwang77@126.com Received: Nov. 28th, 2011; revised: Dec. 27th, 2011; accepted: Dec. 30th, 2011 Abstract: It is well-known that most iterative methods converge for linear system whose coefficient matrix A is strictly diagonally dominant. When A is not diagonally dominant, preconditioned techniques can be em- ployed. This paper presents a method to establish appropriate preconditioned matrices P and Q for transfor- ming an H-matrix which is non-diagonally dominant matrix into the diagonally dominant matrix. Numerical examples also show the effectiveness of this method. Keywords: Iterative Method; H-Matrix; Preconditioned Matrix; Diagonally Dominant Properties H-矩阵的预条件对角占优性 王学忠，李晓梅 河西学院，数学与统计学院，张掖 Email: xuezhongwang77@126.com 收稿日期：2011 年11 月28 日；修回日期：2011 年12 月27 日；录用日期：2011 年12 月30 日 摘 要：对于线性方程组 x bA，当 A是严格对角占优矩阵时大部分迭代法都收敛。当 A不是对角占 优矩阵时，预条件技术常被采用。本文给出了一种选取预条件矩阵 P和Q的方法，把一个非对角占优 的H-矩阵转化为严格对角占优矩阵。数值例子也说明了该方法的有效性。 关键词：迭代法；H-矩阵；预条件矩阵；对角占优性 1. 引言 对于给定的线性方程组 x b A (1) 其中 nn R A 和 已知， n bRn x R未知。当用迭代法求解时迭代格式为 1,1,2, kk xxck G 其中 称为迭代矩阵， nn R G 0n x R称为初值[1]。 M NA，M非奇被称为矩阵 A的一个分裂，对 A进行不同的分裂可得到经典的 Jacobi 迭代法， Gauss-Seidel 迭代法，SOR 迭代法，AOR 迭代法以及它们的变形。当系数矩阵 A为严格对角占优矩 阵时，这些迭代法都收敛，而且系数矩阵的对角占优性越强时，迭代法的收敛速度越快。但是，在实际问题中 0 1  王学忠 等 矩阵的预条件对角占优性 H- 我们所遇到的系数矩阵 A不一定是严格对角占优的。H-矩阵作为实际应用中常见的一种矩阵，它不一定对角占 优，因此，对原方程组进行预条件等价变形，把非对角占优矩阵转化为对角占优矩阵便显得十分重要。例如， 我们可以找两个非奇异矩阵P和Q使得 PAQ 严格对角占优，这样便把解 x b A的问题转化为解其同解问题 yPb PAQ (2) 和 x y Q (3) 因此，找到好的 P和Q便成为问题的关键，这里 P和Q被称为预条件矩阵。 本文主要考虑了当系数矩阵 A是H-矩阵时，怎样建立适当的预条件矩阵P和Q，使 得PAQ 严格对角占优。 2. 预备知识 定义 1[2,3]：设，若 A可以表示为 Znn ij a A s IB A，其中 ，则当0B s B 时，称 A为非奇异 的M-矩阵，简称 M-矩阵，这里() 表示矩阵的谱半径， nn Z表示 n阶Z矩阵。 定义 2[4]：矩阵 A是H-矩阵，如果它的比较矩阵nn ij mA是一个 M-矩阵，这里 ii ii ma， j ij ij mai 。 定义 3[3]：设 nn ij A aC ，若 A满足 , 1,2,, ii ij ji aai n 且至少有一个 i使上述不等式严格成立，则称 A为弱严格对角占优矩阵；如果上述n个不等式都严格成立，则 称A为严格对角占优矩阵。 定义 4[3]：设 ，若存在正对角矩阵 Q，使得 nn ij aC A A QQA为行(列)严格对角占优矩阵，则称 A为 行(列)广义对角占优矩阵。 引理 1[4]：A是H-矩阵的充要条件是存在 使0r0rA，其中。 ,T n r12 ,,rrr 引理 2[5]：A是对角元全为 1的H-矩阵，若 1 ij m A，则成立不等式 11, 1,2,, n ij jmi n 3. 主要结论 若A是对角元全为 1的H-矩阵，我们考虑如下预条件矩阵 nn R α P和nn QR， 11 22 1 1 () s t rrm nnr a a IS a a α P 1 ， 12 , ,0 n rdiag ,rr Q 其中 12 ,,, n 是参数， 是使得 12 ,, ,T n rr rr0rA的正向量。 定理 1：若 A是对角元全为 1的H-矩阵，假设存在一个正的向量 使得 ,T n rrr>0A让 12 ,,rr 2 2 im m i im mm rar car r A A 那么 c > 1。 40 Copyright © 2012 Hanspub  王学忠 等 矩阵的预条件对角占优性 H- 证明：由 I A，及知，0rrr A ，因而 22 1 2 2 im mim m ii im m im mm rarrar car ar r . AA A 定理 2：A是对角元全为 1的H-矩阵，假设存在一个正向量 ，使得 12 ,, ,T n rr rrr0A，如果满足条 件0ic ，那么，是 H-矩阵，并且 是严格对角占优矩阵，其中 α PA α PAQ 12 ,,, n t 是常数。 证明：让 , ,1,2,,,, ,, iji im mj ij aaaij nmrs α PA ， 取 ，则 12 ,, ,T n rrr r , ,, 1 1 i im miiimiimmiji im mjj ijim iiimmiiiimmij jiimmj j jim jim raaraaraaar raarararaa α PA r 1) 当1 i 时， ,, ||0 iiimmiiimmi immijji immjj ijim jim iijjiimmmjjiim im ji ji rr aararararaar rarararr ar α PA AA 2) 当1ic 时， ,, 22 220 ii immiiimmi immijji immjj ijim jim iij jimmiimmmj jm ji ji im miimm im rr aararararaar rararararr rarar r α PA AA 因此，是 H-矩阵，并且 是严格对角占优矩阵。 α PA α PAQ 从上面的定理 2，我们可以看出，只要存在一个正向量 ，使得 12 ,, ,T n rr rr 02,1,2 iinAr ,,， 那么结论就是成立的，但在具体的应用过程中，我们很难确定r数值，从而给应用带来不便，因此可考虑 r取 特殊值来避免此不便。现对 r取特殊值为 10, 1,1,,1diag T ree ，AQ r 可得下面的定理。 推论 1：A是对角元全为 1的H-矩阵，让 10,1,1,,1T ree A和，如果 diag rQ 12 ,1,2,,, ,,, 21 im m iim m ar inmrs ar t 那么， 是H-矩阵，并且是严格对角占优矩阵，其中 α PA α PAQ 12 ,,, n 是常数。 定理 3：如果 2 021 im m iim m ar ar ，那么 是比 α PAQ A Q对角占优性更强的矩阵。 Copyright © 2012 Hanspub 41  王学忠 等 矩阵的预条件对角占优性 H- 证明 显然 21 21 im m im m ar ar ，只需表明 1,1, 2,, i i rri α PA An即可， 1) 当1 i 时， ,, 11 iiimmiiimmi immijji immjj ijim jim iijjiimmmjj ji ji iim rr aararararaar rararar a α PA 2) 当 2 121 im m iim m ar ar 时， ,, ||22 12211 iiimmiiimmi immijji immjj ijim jim iijjim miimmmjjm ji ji im miimm rr aararararaar rararararr arar α PA 4. 数值例子 例1：特别地，对 ，我们运用定理 2的结论，对下面的测试矩阵去建立对角占优矩阵。取 H-矩阵 A为 1rsmt 10.10000.2000 0.1000 0.900010.7000 0.8000 0.1000 0.100010.3000 0.30000.5000 0.20001 A 运用预条件矩阵 和，其中 α PQ 0.97000 0 0 0.0270 1 0 0 0.0300 0 1 0 0.0300 0 01 α P diag rQ， 10,1,1,,1 T ree A ，即 16.4275 000 0 66.183200 00 22.3053 0 00043.4809 Q 得到 15.93476.41984.3272 4.2176 15.2283 66.0045 15.734234.9021 1.14996.816922.4391 12.9138 4.435433.2901 4.594943.3505 α PAQ 42 Copyright © 2012 Hanspub  王学忠 等 矩阵的预条件对角占优性 H- 很明显 是严格对角占优矩阵。 α PAQ 例2：对任意给定的,, ,mrs t ，给出定理 2的数值例子。取 H-矩阵A为 10.10000.20000.1000 0.900010.7000 0.8000 0.1000 0.100010.3000 0.30000.5000 0.20001 A 运用预条件矩阵 和Q，其中 α P 10.0070 00 0100.00 0.0300010 00 0.02001 α P80 2 c Q同例 1，得到 16.32406.1550 4.35184.1046 14.824266.447915.5780 34.4369 1.14996.4198 22.171512.9138 4.961133.22404.0150 43.2200 α PAQ 很明显 是严格对角占优矩阵。 α PAQ 例3：考虑如下 H-矩阵 A，下面对它测试了(2) 的Gauss-Seidel 迭代法，为了比较，同时也测试了(1)的 Gauss-Seidel 迭代法。取H-矩阵 A为 123 123 31 21 1 3 32 23 1 123123 1 1 1 ccc ccc cc cc c c cc cc c ccc ccc A 其中， 12 cn ， 21 1 cn ， 31 1 cn ，n表示矩阵 A的阶数。我们选择 b使得(1)的解为 1, 2,,T x n， 让收敛准则为 16 110 kk k xx x ，取初始迭代向量为 ，对 00,0,,0 T x4,10,16,25,49n 分别进行测试。我们在 下面的表格中表明了系数矩阵A和的 Gauss-Seidel 迭代的谱半径和迭代次数。在测试中，我们取预条件 矩阵 Q为推论 1中的矩阵，取 α PAQ 1 1 1 10 01 0 00 c c c 0 1 α P Copyright © 2012 Hanspub 43  王学忠 等 H-矩阵的预条件对角占优性 44 Copyright © 2012 Hanspub 让表示系数矩阵 A的Gauss-Seidel 迭代，()GSA GS α PAQ 表示系数矩阵 的Gauss-Seidel 迭代。如 下表 1： α PAQ Table 1. The spectral radius and iterative number 表1. 谱半径和迭代次数 GS(A) GS(P α AQ) n 谱半径 迭代次数 谱半径 迭代次数 4 0.4293 17 0.0055 4 10 0.5235 20 0.2543 11 16 0.5659 22 0.4012 14 25 0.5990 23 0.4968 17 49 0.6339 24 0.5838 21 从表 1，我们可以看出系数矩阵为 的Gauss-Seidel 迭代要好于系数矩阵为A的Gauss-Seidel 迭代。这 也说明了我们方法的有效性。 α PAQ 5. 总结 选取预条件矩阵P和Q，使 得是严格对角占优矩阵的方式有很多种，本文给出了一种建立预条件矩阵 P和Q的方法，并给出了相应的结论，数值例子也说明结论是正确的。 PAQ 6. 致谢 作者由衷地感谢匿名的审稿人对本文提出的修改意见，这大大提高了原稿的质量。 参考文献 (References) [1] 刑志栋, 曹建荣. 矩阵数值分析[M]. 西安: 陕西科学技术出版社, 2005. [2] 张凯院, 徐仲. 数值代数[M]. 北京: 科学出版社, 2006. [3] 陈公宁. 矩阵理论与应用[M]. 北京: 科学出版社, 2007. [4] 黄廷祝, 杨传胜. 特殊矩阵分析及应用[M]. 北京: 科学出版社, 2007. [5] 王学忠, 黄廷祝, 李良等. H-矩阵方程组的预条件迭代法[J]. 计算数学, 2007, 29(1): 89-96. |