（应用数学专业论文）结构矩阵的并行算法.pdf

摘要 在本论文中，我们主要讨论了结构矩阵的并行算法首先，建立中心对称矩 阵和中心h e r m t n a n 矩阵的矩阵乘积的并行算法；其次，对于中心对称肼一矩阵和 中心对称矩阵线性方程组的求解，构造多分裂方法，建立快速并行计算方法 在论文中，我们建立了几个快速并行算法，分别讨论他们的计算量和存储量，并 与传统的算法进行了比较，通过比较说明了利用中心对称矩阵的可约性可以极大 的减少计算量和存储量 本论文共分六章 第一章为绪论主要介绍了本论文研究问题的主要背景，研究内容和创新 第二章主要介绍了一些在本论文中要用到的基本概念、引理及定理 第三章建立了中心对称( h e r m i t i a n ) 矩阵与矩阵乘积的并行算法并对所建 立的算法进行了详细的分析，分析结果说明了新建立的算法在计算量和存储量方 面比传统的算法有很大的改进 第四章介绍了矩阵多分裂的概念和它的并行性；弓i 进了关于多分裂迭代方法 的一些收敛理论；最后还给出了多分裂方法中的比较定理 第五章主要讨论了中心对称m 一阵和中心对称一阵的多分裂算法在此章 中我们给出了中心对称肘一阵和中心对称日一阵的一种多分裂方法，建立了相应 的算法，并讨论此种多分裂的收敛性 第六章简单介绍了多分裂方法的松弛方法建立了具体实现多分裂方法松弛 的算法，并对算法进行了相应的分析 关键词：中心对称矩阵；m 一矩阵；h 一矩阵；多分裂；中心h e r m t t i a n 矩阵； 算术平均多分裂 a b s t r a c t i n t h i sp a p e r , w ec h i e f l yi n v e s t i g a t et h ep a r a l l e la l g o r i t h m sf o r s t r u c t u r a l m a t r i c e s f i r s t l y , s e v e r a la l g o r i t h m sf o rc o m p u t i n gt h ep r o d u c t so fm a t r i x m a t r i x w i t hac e n t r o s y m m e t r i cm a t r i x ( o rc e n t r e h e r m i t i a nm a t r i x ) a g ep r o p o s e d s e c o n d l y ， w ec o n s i d e r e dt h em u l t i s p l i t t i n g sa n dp r o p o s e dt h ep a r a l l e la l g o r i t h m so ft h e c e n t r o s y m m e t r i cm m a t r i c e sa n dt h ec e n t r o s y m m e t r i ch - m a t r i c e sl i n e a rs y s t e m i nt h ej a s t ，w ec o m p a r e dt h e i rc o s to fc o m p u t a t i o na n ds t o r e ，w es h o wt h a tt h ec o s t c a nb er e d u c e dg r e a t l yb yt h er e d u c t i o no ft h ec e c t r o s y m m e t r i cm a t r i c e s t h i sp a p e rc o n s i s t so fs i xc h a p t e r s i nt h ef i r s tp a r tt h ec o n d u c t i o n m a i n l yi n t r o d u c e dt h eb a c k g r o u n d ，t h em a i n c o n t e n t sa n dt h eo r i g i n a l i t i e so ft h et h e s i s i nt h es e c o n dc h a p t e l w eb r i e f l yr e v i e ws o m eb a s i cd e f i n i t i o n s ，n o t a t i o na n d p r e l i m i n a r i e sw h i c hw i l lb eu s e di nt h es e g u e l i nt h et h i r dc h a p t e ro ft h i sp a p e ls e v e r a la l g o r i t h m sf o rc o m p u t i n gt h ep r o d u c t s o fm a t r i x m a t r i xw i t hac e n t r e s y m m e t r i cm a t r i x ( o rc e n t r e h e r m i t i a nm a t r i x ) a r e p r o p o s e d w eg i v es o m ed e t a i la n a l y s i so ft h e s ea l g o r i t h m s ，c o m p a r et h e i rc o s to f c o m p u t a t i o na n ds t o r et ot h et r a d i t i o n a la l g o r i t h m s ，t h ea l g o r i t h m sw ep r o p o s e dc a n s a v eal o to ft h ec o s to fc o m p u t a t i o na n ds t o r e i nt h ef o u r t hc h a p t e r ，w ei n t r o d u c e dt h em u l t i s p l i t t i n gm e t h o d so fm a t r i x ，t h e t h e o r i e so fm u l t i s p l i t t i n gc o n v e r g e n c e ，a n dt h ec o m p a r e dt h e o r i e so fm u l t i s p l i t t i n g i nt h ef i f t h c h a p t e r s ，w ep r o p o s e dt h ep a r a l l e la l g o r i t h mf o rt h ec e n t r o - - s y m m e t r i c m m a t r i c e sa n dt h e c e n t r o s y m m e t r i eh m a t r i c e s ，a n d w e i n v e s t i g a t e dt h ec o n v e r g e n c ea n dt h ec o s to f t h e s ea l g o r i t h m s i nt h el a s tc h a p t e r ，w ei n v e s t i g a t e dt h er e l a x a t i o no ft h em u l t i - s p l i t t i n g k e y w o r d s ： c e n t r o s y m m e t r i c m a t r i c e s ；m - m a t r i c e s ；h - m a t r i c e s ； m u l t i - s p l i t t i n g ； c e n t r o - h e r m i t i a nm a t r i c e s ； a r i t h m e t i c a v e r a g em u i t i - 叩l i t t i ng 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特5 i r j 3 n 以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 储豳彳晕槲 吼矿嶂，月堋 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 魂彩砰 日期：炒年上月7 - 日 导师张橛卞 眺知；年r 肼日 1 1 背景 第一章绪论 目前，在许多的工程问题中会遇到大规模的矩阵计算问题，当然其中肯定会 遇到很多问题需要快速算法在计算信号复原问题时，离散的方程所表现的大多 是一个大规模的线性方程组目前许多的信号复原问题，大多是在对原问题的边 界加以一些特殊的限制后来进行研究这些限制使离散问题表现为具有某种特殊 结构和某些特殊性质的线性方程组( 例如应用反卷积技术到信号复原问题，就会 出现系数矩阵为循环矩阵、t o e p l i t z 矩阵、t o e p h f z + t t a n k e l 矩阵等结构矩阵见参 考文献 3 6 、 3 8 ) 虽然以上几类矩阵已有一些快速算法，但对于其他许多的 已在信号复原问题中出现的结构矩阵( 例如应用小波技术处理信号复原问题时， 就会出现诸如中心对称矩阵、中心h e r m i t i a n 矩阵等结构矩阵见参考文献 1 、 3 8 ) ，至今还没有找到有效的快速算法因此，为了减少计算量和节省内存，设 计快速的算法( 当讨论的结构矩阵为非奇异矩阵时) 或有效的最小二乘解算法( 当 讨论的结构矩阵是奇异或超定矩阵时) ，尤其显得十分重要目前有关这方面的研 究尚属起步阶段，至今只有极少数的论文所以，对结构矩阵的研究以及建立相 关的快速算法是很有研究价值的 对于一些超大规模的工程计算问题，我们就不得不研究并行算法了对于有 些信号复原问题如天气预报、大地石油勘探等问题，所表现的方程组通常是超 大规模的( 上百万阶) ，串行的算法根本就不能解决这些实际问题目前，对于有 些实际问题，已有一些使用的并行算法但是对有些问题( 如图象复原问题等) ， 由于起步阶段较晚，加上计算方面的困难，目前的研究主要集中在中、小规模的 信号复原问题，而对大规模的信号复原问题和相关的超大规模计算问题还很少有 涉及然而，在实际问题中有时常会碰到这些计算问题因此，为了解决这些超大 规模问题的计算问题，很有必要进一步研究他们的并行算法 当然我们在研究结构矩阵线性方程组的求解的时候当然会遇到矩阵的乘积 因此，矩阵乘积也是我们要解决的问题目前，国内外对结构矩阵的乘积问题的 研究也有不少的研究，同时也出现了很多相关的算法，并且都在不同的程度上达 到了我们建立快速算法的最终目的一一减少计算量、节省内存，见参考文献e 2 、 r 3 但是至今还没有找到最优化的快速算法，所以其中还有许多的工作可以值得 去研究 结构线性方程组的求解问题是矩阵计算中的核心部分，许多科学与工程问题 最终会归结到线性方程组的求解，对于一些特殊线性方程组如何进行迭代改进一 直是国内外一个比较活跃的研究领域，研究的主要目的是如何利用矩阵的特殊结 构来减少计算量和存储量，从而可以节省计算的时间和计算需要的费用，主要结 果见参考文献 2 3 、 3 、 3 5 、 4 7 3 另外，结构矩阵有着广泛的应用背景，经常出现在下面一些领域中： ( 1 ) 微分方程的数值求解； ( 2 ) 马尔可夫过程的研究； ( 3 ) 电子与机械的振动和控制； ( 4 ) 调和恢复问题； ( 5 ) 自正交小波基的构造； ( 6 ) 其他各种各样的工程和物理问题 1 2 本文的研究内容和创新 1 2 1 本文研究的内容 为求得一个给定线性方程组的解，我们经常选用合适的迭代方法求其近似解 对于系数矩阵为严格对角占优矩阵，当方程组阶数较低时，人们常常选用d a c o b i 迭代法和g a u s s s e i d e l 迭代法；当方程组的阶数较高时，这两种方法的收敛速度 较慢因此，许多学者便提出了收敛速度更快的j o r 、s o r 、m s o r 、a o r 、 s a o r 、s s o r 、t o r 等方法，见参考文献 3 3 、 9 、 1 5 、 2 0 3 、 2 2 3 、 2 7 、 3 1 、 3 7 3 、 4 3 3 但是，对于一些超大规模线性方程组的求解，这些方法在计 算速度方面还是很慢，有的方法甚至不能采用因此我们必须考虑用并行机进行 计算所以我们在这里讨论矩阵的多分裂并行计算具有很大的实际价值 在本论文中，我主要研究了中心对称矩阵( 中心h e r m i t i a n 矩阵) 的矩阵乘法 的并行计算和此类系数矩阵线性方程组的并行计算方法此类方程组有着广泛的 应用背景，经常出现在下面一些领域中：1 ) 在微分方程的数值求解中；2 ) 在某个 马尔可夫过程的研究中；3 ) 在自正交小波基的构造中；4 ) 在多维的调和恢复问题 中；5 ) 在别的各种各样的物理和工程问题中其中小波分析是数学中的一个迅速 发展的领域，正在成为一个重要和活跃的研究领域，更重要的是它已经在数学家 和电子工程师之间建立了一种牢固的联系，引起了其它学科的科学家和工程师的 注意对于小波分析是用泛函分析的方法研究的，然而在小波的研究中矩阵方法 起着一个重要的作用 我在论文中主要讨论了两个问题第一：关于含有中心对称矩阵( 中心 h e r m i t i a n 矩阵) 的矩阵乘法的并行算法；第二：研究了系数矩阵为中心对称m 一 阵和中心对称日一阵的线性方程组的并行多分裂算法其中第三部分是论文的主” 要部分 1 2 2 本文的主要创新 1 ) 在第三章中，我针对中心对称矩阵和中心h e r m i f i a n 矩阵设计了一种关于 这两种矩阵乘法的快速并行算法建立的算法主要是在计算量和占用计算内存方 面有了很大的创新；并且可以类似得出斜中心对称矩阵和斜中心h e r m i t i a n 矩阵的 2 矩阵乘法的快速算法 2 ) 在第五章中，主要讨论了中心对称m 一阵和中心对称日一阵的种的中 心对称多分裂，并证明了这种多分裂方法的收敛性，并讨论了如何利用中心对称 矩阵的可约性来减少计算量和存储量( 在均衡论、投入产出分析的研究中产生 的m 矩阵；在控制论及神经网络大系统的稳定性、线性时滞系统的稳定性研究 中需要矩阵) 3 ) 在第六章中，简单的介绍和分析了多重分裂的松弛方法，以及怎么优选 松弛因子国 第二章预备知识 弟一早 耿亩划伏 在这一章中，我们主要来介绍一些在论文中要用到的记号，定义和相关 结论，对于在后章节中单独出现的概念再做另外介绍参考文献见 1 、 2 、 3 、 4 、 6 、 1 0 、 2 8 、 3 0 、 3 6 、 3 7 、 3 8 、 4 0 、 4 3 、 5 0 2 1 定义 定义2 1 1 设a 为弹拧的复数矩阵，如果万。4 万。= a 成立，则称a 为中 心对称矩阵，其中万。为反对角线上元素为l 其余元素为0 的置换矩阵 一个中心对称矩阵可以表示为： 4 = ( 万。置：万万。置：万j 定义2 1 1 若矩阵a 中的元素满足下面的关系式：q 。，= a p “十川，a e r ”， 彳= 口袋 ，即一 lb 冗霄s 氕：、 a = l 矿 口 ，万二i ，b , c r - x - , 口，b r ”“，口r ” 、c b 霄覆 定义2 1 3 设a 为拧丹的复数矩阵，如果万。万= 孑成立，则称a 为中心 4 ：f粤4 z1 ( 其中疗：2 所) 忉，彳：万。万。彳。万。j 定义2 1 4 设a 为n x n 拘复数矩阵，如果万a l l 。= 一4 成立，则称a 为斜 4 定义2 1 5 如果d e t ( a ) 0 ，则称矩阵a 为非奇异的；否则称a 为奇异的 定义2 1 6 矩阵a = 瓴) r 称为z 一矩阵，如果f ，时恒有吩0 定义2 1 7 如果彳是一个非奇异的z 一矩阵且a 。0 ，则称矩阵4 为m 一 矩阵 定义2 1 8 如果a 的比较矩阵( a ) = 也) 为m 一矩阵，则称矩阵a 为h 一矩 触i 弦f o r ，i = 定义2 1 9 设彳= m 一为矩阵a 的一个分裂( ”i 0 ) ，如果m 。1 0 ， n 0 ，则称此分裂为正则分裂；若m - 1 0 ，m 。n 0 ，则称此分裂为弱正则分 裂 定义2 1 1 0设4 = m 一为中心对称矩阵a 的一个分裂，若m 和都为中 心对称矩阵，则称此分裂为4 的一个中心对称分裂 定义2 1 1 1若彳= m 一为中心对称分裂且m 12 0 ，0 ，则称此分裂 为中心对称的正则分裂 定义2 1 1 2设4 = m 一为中心对称分裂且m - 1 0 ，m 。1 n 0 ，则称此 分裂为中心对称的弱正则分裂 定义2 1 1 3设4 = m 一为矩阵a 的一个分裂，若p ( m 。1 n ) 0 ，则称a 为正定矩阵若x * a x 0 ，则称a 为半正定矩阵 定义2 1 2 0 如果矩阵p 鸩在它的每一行和每一列正好有一个元等于 1 ，而其余所有的元都是0 ，就称| p 为置换矩阵 2 2 常用的迭代方法 在这一节中，我们先来回顾一下常用的几种迭代格式在这几种迭代格式中 要用到的矩阵分裂为4 = d 一一u ，其中d 是一个对角矩阵，一是a 的严格下三 角矩阵，一( ，是彳的严格上三角矩阵 2 2 j a c o b i 迭代格式： x “= d 一f + u ) x + d 一1 6 迭代矩阵为ig j = d 。1 + u ) 2 2 2g u a s s s e t d e l 迭代格式； ，+ 1 = ( d 一三) - 1 ( 詹+ ( d 一三) 。b 迭代矩阵为：g 。= ( d 一工) 。u 2 2 3s o r 迭代格式： x t + l ：( 1 - _ d 一) 一“一l + 三) d + ( ，) x + ( - - td 一) 一6 甜 面- 0 埘 迭代矩阵为：g s ：( i d 一三) 一- ( ( - l + ! ) d + u ) 埘珊 注；( 1 ) 当廖= l 时，& 璃迭代即为g u a s s s e m e l 迭代 ( 2 ) 当s o r 迭代收敛时。国( o 2 ) ，讲的最优值在区间( 1 ，2 ) 中选取 ( 3 ) 使用暇方法求解线性方程组，首先要选择松弛因子国，所选出的国 不仅要使迭代法收敛。而且应有高的收敛速度，关于如何选取最佳松弛因子的问 题，至今仍没有有效的解决在实际计算工作中，经常采用试算的方法来寻找较 好的松弛因子，特别是同时求解多个具有相同系数矩阵的线性方程组，通过试验 找出恰当的松弛因子能大大提高计算效率 2 3 迭代方法的理论基础 设4 = m n 为矩阵的一个分裂，所谓的求解a x = 6 迭代格式即为任给的 妒，反复计算x 。“= r x 。+ c 直至收敛，这里r = m 一1 ，c = 肘一b 下面介绍几个关于迭代的引理和定理 引理2 3 1 【蚓设删为任意一种算子范数( i i r h - - - m a x 。料) ，如果i i r u o ，存在 一个算子范数i | 1 | ，使得i i r i i p ( 固+ f ，其中i | | 。依赖于r 和占 定理2 3 3 对于任意的起始向量x o ，迭代序列 z ”1 = r x ”+ c 收敛到a x = b 的解p ( j r ) 1 我们在构造一个矩阵分裂a = m n 时，般遵循如下两个原则： ( 1 ) r x = m 1 n x 和c = m - 1 6 是容易计算的 ( 2 ) p ( r ) l 我们需要平衡这两个相互矛盾的原则，例如我们选择m = i 能很好的满足原 则( 1 ) ，但有可能使得p ( r ) l 不成立另一方面，选择m = a 和n = 0 能很好的满 足原则( 2 ) ，但对于原则( 1 ) 可能不满足 2 4 几个关于迭代法收敛的定理 定理2 4 1 矧j a c o b t 迭代法收敛p ( q ) 1 定理2 4 2 如果l i g j 1 ，则肠d 6 ，迭代法收敛 定理2 4 3 【蚓如果线性方程组a x = b 的系数矩阵是主对角线按行( 或按列) 严格占优阵，则j a c o b i 迭代法收敛 定理2 4 4 g u a s s s e l d e l 代法收敛p ( g d ) 1 定理2 4 5 m l 如果0 g 洲 l ，则g u a s s s e i d e l 迭代法收敛 定理2 4 6 m 1 如果线性方程组爿x = 6 的系数矩阵是主对角线按行( 或按列) 严格占优阵，则c , u a s s s e i d e l 迭代法收敛 定理2 4 7 陋】如果线性方程组血= 6 的系数矩阵是正定矩阵，则 。g u a s s s e t d e l 迭代法收敛一* ，一n 一一；一 、”一 定理2 4 8 3 6 1s o r 迭代法收敛p ( g 。) 1 ” 定理2 4 8 如果忪。0 1 ，则双坎迭代法收敛 定理2 4 9 【“1s o r 迭代法收敛的必要条件是0 0 3 k # l ，2 ”，故此算法有很大的使用价值 3 3中心胁删m 册矩阵乘积的并行算法 3 3 1 引言 “在本节中总是假定4 为聆( 拧= 2 m ) 阶的中心h e r m t t i a n 矩阵，。尸为h x h 阶 的任意的矩阵，下面我们来讨论此时w = a p 的算法在这一部分当中a 、p 分别 记为：a = a 。+ f 彳：；p = p 。+ f 尸：其中a 、a ：分别表示4 的实、虚部：p 。、 p ：分别表示p 的实、虚部 首先我们考虑用传统算法计算w = a p ，即 1 2 w = a p = u 。+ 谢：) 【尸l + i p ：) = a 。只一a ：尸：+ f 匕p 2 + 4 ：p 。) 在这个计算过程当中我们总共要计算4 个n x 胛阶矩阵的乘法以及4 个，打阶 矩阵的加减法，需要的总计算量大约为：8 n 3 次计算量若用s t r o s s e 算法计算大 约需要跏吲* 8 n 2 ”次计算量 3 3 2 改进的矩阵乘法算法 利用中心h e r m m a n 矩阵的性质( 定义2 1 3 ) 我们建立下面的算法3 准备步骤：计算矩阵： b = a + 互：万。；b ：a l l 互：万。 从而可以形成如下矩阵； 肚程 步骤1 ：计算矩阵： 嘲。尸= 织纠( ”删 = ( 毫象卜+ ，( 与象 阶吼 步骤2 ：计算矩阵。 z 捌= s 袅兹1 】，) 。曙爱：b 妻p 。+ g 袅：b 晏 l z 乙“z ， l 3 8 2 瞰2j 12 。l 3 8 2 吼2j 1 厶“。6 。 步骤8 1 计算矩阵： = 妇= 眨纠( z 孙 = 臣饥q - 尸 7 + 肠，( 囊瓿i i z ，i 附帆 算法分析：下面讨论算法3 所需要的计算量：备步骤当中，需要巧n 2 次加 减运算；在步骤1 中，需要的计算量为：3 4 m 2 = 3 n 2 次加减运算；在步骤2 中， 相当于进行两个阶数为i 1 的矩阵乘法，然后再求和故在此步骤中共需要的计算 量大约为：4 行3 ( 当肝充分大时) 在步骤3 中，也只需要3 4 m 2 = 3 n 2 次加减运算 综上所述，当r l 哼* 时，用改进的矩阵乘法算法计算w = 爿尸共需要大约锄3 次 计算量，比用传统算法计算减少了一半的计算量；同时我们可以注意到，在此算 法中我们采用了分块的矩阵乘法，并且在算法中把矩阵的乘法转化成矩阵的加减 法计算，从而提高了计算的速度，节省了不少的内存 3 3 3 改进的s t r a s s e n 算法 在这一部分当中我们主要是对算法3 中的步骤2 运用s t r a s s e n 算法进行改进， 其他步骤与算法3 嚆故不鞲玑在计算z 制= 曙盒程1 帆峭y j = 罡金兹1y ( 善囊兹1 卜 的过程中用s t r a s s e n 算( 罢皇兹 l 与储谨1 弦 在这一步骤当中共需要的计算量为：4 n l o l , * 4 行：s t 次运算因此，当刀充分大 时，若用s t r a s s e n 算法进一步改进算法3 ，总共需要的计算量为4 n l w * 4 n ：n ，较上 述算法有进一步的改进 3 4 两点说明 ( 1 ) 在本章节中我主要讨论的是矩阵阶数为 疗( , = 2 m ) 的情形，其实 当矩阵的阶数为疗胛( 刀= 2 m + 1 ) 的时候我们关于矩阵乘法的算法一样可以建立， 只是要用到中心对称矩阵的以下性质 ，性质：碧4 为阶数为( 脚川冲凸对称矩阵，令q ：r 压i l j r 一刀j 贿q 7 a q f 4 1 2 n 。b 崩肌一砌一 则有7 = l 口- 口7 l ，其中，口吼，以6 吼”4 l 。占+ c j 1 4 ( 2 ) 作为本文的个推广，当a 或p 为斜中心对称( h e r m l t i a n ) 矩阵时有 类似于中心对称( h e r m i t i a n ) 矩阵的结论 第四章多分裂方法及迭代收敛定理 4 1 矩阵多重分裂概念与它的并行性 4 1 1 矩阵多分裂的导出 1 引进j a c o b i 分裂( 见参考文献 3 6 ) 对于线性方程组a x = b ，我们利用j a c o b i 分裂的思想有： 其中，彳= q 1 q 2 吼l 口2 2 q 。 呸 a iq 2 k，分块后为彳= 至至兰至 4 ，t = 以+ 矗，i = k 2 ，口( 降阶) j 冉 构造迭代：“”= - a 1 1 4 才耻+ 4 1 龟s j ( k ) = k 同步ls j ( k ) k 异步 j 2 导出多分裂方法 对于线性方程组a x = b 。我们对系数矩阵a 做如下分裂： a = m 一，d e t ( m j ) o ，= l ，2 ，口 那么我们可以构造它的迭代格式如下： 4 善= m x + 6 ，= l ，2 ，口 x - - - - m i 。1 m x + m i b ， ，= l 2 ，口 下面引迸一个加权矩阵来构造并行的多分裂迭代格式： 对于任意给定的x o ，我们可以形成迭代格式： x = 仃1 x + 肼i l b 若有巨o 为对角矩阵且满足局= i i = 1 ，2 ，群 则有： e l x = e 彤_ 1 n l 一+ e l m _ b ，“= z e , e 。 其中互为权矩阵 ， 定义4 1 1 若a l ( r “) ，且a = m m ，d e t ( m 1 ) o ，= 1 , 2 ，a 口s 肝； 若存在巨o 为对角矩阵，且e l = ，则称分裂4 = m 一j 为a 的一个多重分裂， 记为( m ，m ，e ) 1 6 4 1 2 多分裂的计算过程 取定初始值x 0 、e ，z = 1 2 ，瑾 j t 7 = m i l n , x + m i l b x “1 = 局x k j 考虑要达到的精度，终止计算 由上可知该计算过程为一个同步并行的计算过程 由可知p ( 圻1 ) l 。 由：矿“2 e e , 矿。2 e e , m ； nx k + 局m ：6 = 彬+ g 6 可知p ( ) 1 ，为多分裂 收敛的必要条件 例1 若4 = 陌。斗m 一 = 鸩2 其中m = ( 0 1 5 丹m = ( 一o i 2 7 斟嘶吣( 。三，捌 鸠= 巴斟m = 。蛰呲吣( 譬；冀5 则有p 似i 1 i ) = p 似；1 2 ) = 0 7 9 6 9 1 ，从而该分裂不收敛 若取置= ，易= ( 贬w 叫羔，- 0 。2 5 而p ( e l m 7 1 n ，) = 0 2 5 1 从而该分裂收敛 结论：对于我们构造出来的多分裂，若取不同的权矩阵巨，则有不同的收 敛性，因此选取恰当的权矩阵是构造收敛的多分裂中的一个重要的方面 f ，f 4m ，。 _ _ n 、 p 一4 。 4 2 多分裂迭代法的收敛理论 引理4 2 1设al ( r ”) = r ”“，a = b c 为4 的弱正则分裂，则 a 一1 0 p ( 口- 1 c ) 1 证明：必要性：因为a _ 1 0 ，而h = b 。c 0 ，则： ( ，+ 日+ + ”) ( ，一日) = ，一h ”1 1 7 ( ，+ 月+ + 日“) u h ) a 一= u 一日“) 爿。 又因为a = b ( i 一日) ，则b 一= ( ，一日) 4 4 则0 ( ，+ 日+ + 何“) 曰一= ( ，一日肿1 ) 4 - 1 a 一 ( 4 1 ) 故：l i m 日1 = 0 p ( h ) 1 m 充分性：因为p ( 日) o ，则下列事实是等价的： p ( 日) l ； g 的每一列至少有一非零元素； g 。存在 证明；j 显然成立 j 因为g a = ，一h ，g = ( ，一h m 一，又p ( h ) l ，所以g 1 存在 j 因为g 。、a 。存在，所以( ，一日) _ 存在，所以p ( 日) o ，则： 妒k 州。q 州i ) ，彬s q “跟坍无关 故p ( 日) 1 定理4 2 4 若一l ( r ”) 非奇异，且a - 1 0 ( m ， ，骂) ，= l 2 ，口为彳的弱正 则分裂，则对任何满足条件的巨，= 1 , 2 ，口有p ( 日) 1 证明：只要验证定理4 2 3 中的即可 引理4 2 5 矩阵a ，最c l ( n “) ，d = 西鳄( 爿) ，那么： 若彳为肘一矩阵，那么d 0 ，且d - 1 存在； 若为m 一矩阵，且a b d ，那么8 也是m 一矩阵； 1 8 若彳为h 一矩阵，那么1 4 。1 l ( 爿) 一； 若a 为h 一矩阵，且( a ) = p ) 一i c l ，d r a g ( a ) = d i a g ( b ) ，那么b 也是h 一矩阵； 若a 为日一矩阵，并且a 的任意口口块对角矩阵也是日一矩阵 证明：先证第四条：因为( a ) = ( 功- i q ，且似) = ( 曰) 一i d | ，所以有( b ) 为m 一 矩阵，从而b 也是日一矩阵，这是因为日一矩阵的比较矩阵为m 一矩阵 取a z a g ( a ) = d z a g ( b ) ，因为a 。1 0 ，a = d j = d ( i d 。j ) ，所以 i d “j i i d l 4 f 卅，故p ( d 。1 刀p q j d l 。l 卅) l ；印) = ( d ) 一i g i = i d i ( t i d i i j l ) ，( a ) n m 一 矩阵，为( a ) 的正则分裂，故p ( j d i i j i ) 1 q 4 f e 则p ( 爿) p p ) ) 所以由： a _ 1 = ( ，一d - 1 ，) _ d q ；有： i a - i i - z ( i d l l l 9 1 ) i d i 。1 = ( ，一i d l l l 9 1 ) 。i d l 4 = ( 4 ) r 4 -4 ：4 “ 若彳：l4 t 如：”4 n l 。 l 以以：缸_ 如 ，则有：( a ) = ( 以) 一i a 一4j ， 又因为( a ) a o ) - i o f ，所以( 4 ) 为m 一矩阵，故4 为日一矩阵 一 定理4 2 6 ( 丑= 1 ) 若a 。o ，( m i ，m ，e i ) ，= 1 , 2 ，口为a 的弱正则分裂；或 a 为日矩阵，且( 彳) = ) 一m | ，西曙( m ) = 西曙( 4 ) 则均有p ( h 。) l ，此处 证明：a 为日矩阵( 4 ) 为吖一阵，即) 一2 0 ，因为( 4 ) = ( m ，) 一l j l ， 一“= l ，2 ，口所以0 ) ( m ) ( d ) ，即( m ) 为m 一阵 “一”4 6 ”8 a - 1 o ，( ，m ，e ) ，= 1 2 ，瑾，为a 的弱正则分裂，所以 p ( e e , 似) 。m 1 ) 1 所以： 1 9 l 甄i = i 乓m i ，卜巨p 一l l s 岛( m ，) - l t n i i ( a 。i 0 ) 一；h e p ( 4 ) p 忸) p ( h ) s p ( 日) 4 m 1 ) 1 定理4 2 7 若4 。o ，( m ，m ，巨) ，= 1 , 2 ，口为a 的弱正则分裂；或a 为h 矩阵，且( a ) = ( m ) 一i n , i ，d i a g ( m ，) = d r a g ( a ) 则均有p ( h 。) l 此处 风= 卜肘i 1 e 。a 证明： 只需证明p ( h 。) 1 即可 因为( ) = ( 爿。) r o ，( m 7 ) 一= ( m 1 ) 7 0 又a - 1 o ，( ，m ，巨) ，f = l ，2 ，窿 为a 的弱正则分裂所以胛2 0 ，( m d 孵2 0 又a 7 = 聊一f ，为a 7 的正则分裂 所以凰= 局( 聊) 。孵，p ( 玩) 2 o ) 则p ( m i l 1 ) p ( m ；n 2 ) 引理4 3 3 1 ( w o z n i c k i 引理) 若m i l 乞1 ，则p ( 玎1 i ) p ( m 2 ) 引理4 3 4 嗍( e i s n e r ) 若a = m 一l = m s 一2 ，为弱正则分裂，a 4 o 则下 列三个条件之一成立： l 2 ； 圻1 嵋1 ，l2 0 ；( a = m j 一l 是正则分裂) m i l 嵋1 ，2 o ； 都有p ( m i l 1 ) s p ( m ；2 ) 引理4 3 5 1 4 1 ( e ls n e r ) 若a 一1 o ，且a = m t m ，l = t ，2 ，a 为a 的弱正则 分裂，存在局o ，= l ，2 ，口使得z e , = ，记h = 晰1 m 今有麝、厨满足 厨m 厨，l ：l ，2 ，瑾则当4 = 厨一为正则分裂时，就有p ( 日) p ( 砑一1 ) ； 当a ：m 一为正则分裂时p 一1 ) p ( 日) 2 1 第五章中心对称m 一阵、h 一阵的多分裂方法 5 1 中心对称m 一阵的多分裂方法 5 1 1 中心对称m 一阵多分裂方法的构造 设4 ：帆一以为中心对称矩阵_ 的一个收敛足重多分裂，由此分裂导出如下 的迭代序列 x “j ：m ：n t x 7 + 圻b j = o , l ，2 ；i t = l 2 ，k ( 5 1 1 ) 相应的，_ ：肼，一以，也为中心对称矩阵a 的一个收敛k 重多分裂，它所对应 的迭代序列为： 了j “ ；j m ， 1 肛7 + 鹏1 j b ，= o 2 ，；| | = l ，2 ，k ( 5 l 2 ) 考虑迭代序列( 5 1 1 ) 和( 5 1 2 ) ) 的算术平均，得到一个新的迭代序列 x 川，i 。委( m ，+ j m l l n j ) x j + 吾( m ，+ 埘h ，j ) 6 j = o ，l ，2 ；摩= l ，2 ，k ( 5 1 3 ) 有此式我们可以立刻得出a 的一种新的多分裂： a = 哇似+ 脚坩4 一哇似，+ j m ；1 删4 专似以+ 埘以，) ( 5 l 记 u ；戛呼 n i + j m n i d ，v = 毛哪- 、+ j m ：d 又记 衍。= 矿4 = 唼m + 皿f ；1 i ，) 】4 ， 机：v - u ：畦t + 晰1 ，) r 丢似，m + j m ；v ) 则迭代序列( 5 1 3 ) 可以写成 苴，“ ：u x j 十p 西，= 0 , 1 ，2 ；i | = l ，2 ，k ( 5 1 5 ) 因而( 5 1 4 ) 可以记为彳= m i m 然后对( 5 t 5 ) 引进多分裂迭代的加权计算可以得到a x = 6 的迭代解 ，- ：艺皿矿- ：圭q 仉x ，+ 圭仇k 6 ( 5 t 6 ) 记= 见以，g = 眈圪 那么( 5 1 6 ) 可以写成 x j = 日x ，+ gb ( 5 1 7 ) 若g _ 1 存在则迭代序列( 5 1 7 ) 可以看成由多分裂a = g 4 一g 。1 口所产生的迭代序 列 引理5 1 1 如果4 = ( q ，) 吼是非奇异的中心对称矩阵，那么a - i 也是 中心对称矩阵 定理5 1 2 a = 府。一成为一个中心对称的多分裂即：成、矾均为中心 对称矩阵 证明：v = 去( m ；1 + 删刀； j 阿= ：1 ( m ，+ 肼，) = v v 为中心对称矩阵再根据引理5 1 1 ，可以得出矿1 为中心对称矩阵 又因为域：矿一：己+ 以虻t ，) 】- i ，所以成为中心对称矩阵同理我们可以证 明u 为中- c a 对称矩阵。那么我们根据引理5 1 1 可以直接得出 l 乙= y u = 【兰( m f + 皿，f ，) 】- i 弓1 以+ j m ；- ，) 为中心对称矩阵即： a = 啦一机为一个中心对称的多分裂定理得证 - 5 1 2 分裂方法的收敛性 引理5 1 3 m 1 设a l ( r ”) 非奇异且一一1 0 ，a = 帆一m ，j | = 1 , 2 ，k 为彳 的足个弱正则分裂则对于任意满足条件的仇，k l 2 , ，k ，有p ( h ) 1 ，这里 f ，、 = 蹴1 肮，i d k = 计 i = l t = l 定理5 1 4 设4 为一个中心对称的m - 阵，那么由多分裂彳= 帆一虬和 a = j m 。j 一以，所构造的算术平均多分裂4 = 衍。一机是收敛的“m ”“” 。“ 证明：由于a 为一个m - 阵，所以有a 非奇异且4 _ 1 o 所以我们只要证明多 分裂a = 巩一矾是弱正则分裂即可由于a = m 。一 0 和a = m 以，一以j 都是弱 正则分裂，然后根据弱正则分裂的定义很显然有a = 啦一机为a 的一个k 重弱 正则分裂由引理5 1 3 可知，该定理成立 5 1 3 相应的算法以及算法分析 5 1 3 1 中心对称膨一阵的中心对称多分裂算法 算法l ： s t e p l ：给定一个初始值x 。和一个约束值g ，b = d 2 一一眈= 昙，对中 心对称的m 一阵a 做两个弱正则多分裂： a = m t n t 【a = 批j j n j s t e p 2 ：f o r = 0 。1 x j + t - t = i 1 ( m ， k + 3 m f n