判定H-矩阵的一个迭代算法的修正 翻译.doc

1、 判定 H-矩阵的一个迭代算法的修正 * 李耀堂， 张 讯 (云南大学 数学系， 云南 昆明 650091) 摘要 :随着 H 一 矩阵在科学与工程计算中的广泛应用， 如何判定一个给定矩阵是否为 H 一 矩阵引起了 许多研究者的兴趣 .本文对一个现有判定 H 一 矩阵的迭代算法进行了修正， 得到了一个新的迭代算法 .数值算例表明该算法是有效的 . 关键词 :H-矩阵 ;对角占优矩阵 ;迭代算法 令 nnR 表示所有 nn 矩阵 , nnij RaA . A 的比较矩阵 nnij RbAM 定义如下： jia jiaij ijijb , 如果 AM 是 M-矩阵 ,那么矩阵 A 是 H-矩阵 .

2、众所周知 H-矩阵通常称作广义对角占优矩阵 (GDDM).那就是 ,存在一正对角矩阵 D 使得 AD 为严格对角占优矩阵 （ SDDM） . 一类 H-矩阵是在工程和科学计算中具有广泛应用的一类矩阵 .许多迭代算法求解线性方程 bAx 是收敛的如果系数矩阵 A 是 H-矩阵 .因此 ,如何判断一个给定的矩阵是 H-矩阵在以上研究领域起着重要作用 .在文章 2 6,一些研究者给出了一些方法来确定 H-矩阵 .尽管这类方法有很多种，但是 它们都来源于一个事实 :试着去寻找一个正对角矩阵 D 使得 AD 为严格对角占优矩阵 .本文的方法也是基于这一点 .做为改性的方法，我们从两对角占优行和非对角占优

3、行入手 .这在之前的学习研究中被忽略 . 1、 H-矩阵的一些引理 为了不失一般性 ,令 nnij RaA 为一个不可约矩阵 ,在本文中 ,我们使用以下符号 : nNaAR ij iji ,2,1, ; NiARaiANiii ,1; NiARaiANNANiii ,12; ijANj ijiiaaANiiAN2,23 ; ijANj ijiiaaNiiANANAN2,2324 ; 为了不产生歧义 ,我们用 AN1 表示 1N , AN2 表示 2N , AN3 表示 3N , AN4表示 4N .显然 , 21 NNN , 432 NNN , 21 NN , 43 NN . 引理 1 令 n

4、nij RaA 为 H-矩阵 , ni iia1 0. 引理 2 令 nnij RaA 为 H-矩阵 , 0det A . 引理 3 令 nnij RaA 为 H-矩阵 , 01 AN . 引理 4 令 nnij RaA 为 H-矩阵 , D 是一个正对角矩阵 ,当且仅当 AD 为 H-矩阵时 A 为 H-矩阵 . 引理 4 指出了 A 和 AD 具有同一属性的对角优势 .我们的任务是确定一个正对角矩阵 D 使得 AD 为严格对角占优矩阵 . 2、迭代标准矩阵 算法 A (1) 输入矩阵 A ,如果 ni iia1 0，此时 A 不是 H-矩阵 ,停止并且输出“ A 不是 H-矩阵 !” ;

5、(2) 如果 AN1 ,此时 A 不是 H-矩阵 , 停止并且输出 “ A 不是 H-矩 阵 !”； 如果 NAN 1 ,此时 A 是 H-矩阵 , 停止并且输出“ A 是 H-矩阵 !” . (3) 令 ijNjijiiNjijiANiaaa121m a x 显然 , 0i , 10 ,(当 0 时 A 可约 ),现取 10 ,这时 1 ,使 nddddiagD , 21 ,这里 12,1 NiNiid . (4) 计算 ADA ,回到 (2) 算法 A 是从对角占优行开始 ,找到一个正 对角矩阵 D 使得 AD 为严格对角占优矩阵 .显然 ,如果这个算法终止在有限迭代次数 ,这时我们 可以

6、得到一个明确的结论 : NN1 时 A 是一个 H-矩阵 ,或者说 1N 时 A 不是 H-矩阵 . 用 kD 表示 k 重正对角矩阵 , kkk DAA 1 表示 k 重生成矩阵 ,通常的 , AA 0 . 引理 5 在算法 A 中 , ,2,1,111 kANAN kk . 证明 一般情况下 ,当 D 为一重正对角矩阵 时，我们只需证明 ADNAN 11 . 令 ijbADB , ANi 1 . iiiii adaiib , 21 Nj ijij Nj ijij iji aabBR , 21 Njijij Njijiiiii aaaBRb 211 Njijij Njijiiij Njiji

7、i aaaaa 211 Njijij Njijiiij Njijiii aaaaa 01ij Njijii aa. 那就是 ADNBNi 11 ，即 ADNAN 11 . 引理 5指出 ,在算法 A中 , A 的对角占优行数随迭代次数的增加而增加 .所以经过有限次迭代 ,我们可以得到一个正对角矩阵 kDDD 10 ,当 A 为 H-矩阵时 , AD 为严格对角占优矩阵 .但是这里有两个问题需要解答 :首先 ,如果 A 不是 H-矩 阵会怎么样 ;第二 ,算法什么时候终止 ?这些问题会在我们给出我们的改进算法后得到解答 . 算法 B (1) 输入矩阵 A ,如果 ni iia1 0或者 AN1

8、，此时 A 不是 H-矩阵 ,停止并且输出“ A 不是 H-矩阵 !” ; (2) 令 AA0 , ID0 , 0k ; (3) 如果 NAN k 1 ,此时 A 是 H-矩阵 ,停止并且输出“ A 是 H-矩阵 !” ; (4) 令 1m ax11121111111 ijANjkijkiiANjkijkiANikkkk aaa 1m a x111211111111 ijANjkijkiiANjkkijkiANikkkk aaa 选取 10 1 k ,这时 1,1 1111 kkkk , 规定 112111 , knkkk ddddi agD ,这里 121111111,kkkkkkki AN

9、iANid 11111 ,0 kkikiik ANiARa （ 5） 使 11,1 kkk DAAkk ,回到 (3). 注意 :很显然 10 1111 kkkk .这说明对所有 Ni ,输入 111 kkij ANja ,减少速度比其他的要快 .尽管 kiia 的对角元素的非对角占优行在减少 ,但输入的 其他的 在同一行的减少比也同样如此甚至比这更多 . 3、算法的定理证明 定理 1 算法 B 中 (i) ,2,1,0,111 kANAN kk ; (ii) ,2,1,0, 112 kARaARaANi kikiikikiik . 证明 为了完成证明 ,我们列举三个例子 . 1) 令 kAN

10、i 1 ,这时 ijkijkii aa,并且 kiikkkii aa 1 , 211Njkijkkij Njkijkkki aaAR . 所以 2111Njkijkkij Njkijkkkiikkkikii aaaARa = ij Nj NjkijkijkiikNjkijkij Njkijkiik aaaaaa1 221 21 21 Njkijkij Nj Njkijkijkiikij Njkijkiiki aaaaaa 0 ijkijkiik aa 那么 kANi 1 ,那就是说 111 kk ANAN .结论 (i)得证 . 2) 令 kANi 3 ,这 时 kAN3 且 ij ANjki

11、jkiikaa2.那么有 11211kk ANjkijkkij ANjkijkiikkkikii aaaARa . 因为 ij ANjkijkiikaa2且 10 kkkk , 因此 11211kk ANjkijkkij ANjkijkiikkkikii aaaARa 112 kk ANjkijij ANjkijkiikk aaa ij Njkijkiikk aa 因为 kANi 2 且 10 kk ,因此 ij Njkijkii aa,并且 kikiiij Njkijkiikikii ARaaaARa 11. 2) 令 kANi 4 ,此时 10 kk .那么有 11211kk ANjkij

12、kkij ANjkijkiikkkikii aaaARa . 因为 ij ANjkijkiikaa2且 10 kkkk .此时 kikiiij NjkijkiiANjkijij Njkijkiikikii ARaaaaaaARak 1111. 从 2)和 3)中 ,我们得出了 (ii)的结论 综上所述 ,我们可以得到明确的结论 ;算法 A 和 B 都能保持矩阵的对角占优性 .但是 ,作为一个改性方法 ,算法 B 能同时处理对角占优和非对角占优列 ,于是我们可以 我们可以说如果矩阵没有对角占优行 ,那么 算法 B 的收敛速度比算法 A 更快 . 定理 2 算法 B 在有限的迭代终止或产生一种独特的无限 序列 mmijAa对所有 ,i j N 都有 lim mijm a. 证明 通过定理 1 我们知道在算法 B 中 121 1 1 mN A N A N A