（计算数学专业论文）结构线性方程组axb和sylvester矩阵方程的迭代解法.pdf

2 0 0 8 上海大学博士学位论文 摘要 本论文主要分为两部分t 一部分是考虑了系数矩阵为中心对称矩阵的线性方 程组a x = b 的迭代求解；另一部分是研究了控制理论中的l y a p u n o v 矩阵方程和 s y l v c s t e r 矩阵方程的数值求解 在线性方程组a x = b 的迭代求解中，我们主要考虑来求解一类具有特殊结构 的线性方程组，即系数矩阵a 是一个中心对称矩阵的情况在本论文中我们主要 针对中心对称矩阵的结构特点构造了几种中心对称分裂格式与j a c o b i 迭代方法和 g a u s s - s e i d e l 迭代方法相比，由这些中心对称分裂格式得到的迭代方法不但收敛速 度快而且还有计算和存储上的优势我们在这里重点考虑中心对称m 阵和中心对 称h - 阵方程组的迭代求解，对于其它的中心对称矩阵线性方程组的迭代求解还在 进一步地研究中 在控制系统的分析和设计中，矩阵方程和线性矩阵不等式的求解占有十分重要 的地位，受到控制学界和数学界的极大关注在这里我们主要给出了求解矩阵方程 的两种迭代解法， 1 ) 利用k r o n e c k e r 积迭代方法来求解离散的l y a p u n o v 矩阵a x a t - x + o = 0 和 连续的l y a p u n o v 矩阵方程a x + x a 2 1 + q = 0 2 ) 利用基于矩阵分裂的梯度迭代法来求解s y l v e s t e r 矩阵方程a x + x b = c 和a x b + x = c 关键词， 中- 5 - 对称m - 阵，中心对称h - 阵，l y a p u n o v 矩阵方程，s y l v e s t e r 矩阵 方程，k r o n e c k e r 积，矩阵分裂，梯度迭代方法 i i a x = b 和s y l v e s t e r 方程的迭代解法 a b s t r a c t t h ec o n t e n to ft h i sp a p e rc o n s i s t so ft w op a r t s ：p a r to n ei sh o wt os o l v et h et i n - e a rs y s t e m sa x = bi t e r a t i v e l y , w h i c hc o e f f i c i e n tm a t r i c e sa r ec e n t r o s y m m e t r i cm a t r i c e s ； p a r tt w op a y sa t t e n t i o nt os o l v i n gt h el y a p u n o vm a t r i xe q u a t i o n sa n ds y l v e s t e rm a t r i x e q u a t i o n si nc o n t r o lt h c o r yb yn u m e r i c a lm e t h o d s f o rt h ei t c r a t i v es o l u t i o n so ft h el i n e a rs y s t e m sa x = b w ec o n s i d e rt os o l v ea s p e c i a ll i n e a rs y s t e mw h i c hc o e f f i c i e n tm a t r i xi sac e n t r o s y m m e t r i cm a t r i x i nt h i sp a p e r w ec o n s t r u c ts e v e r a lc e n t r o s y m m e t r i cs p h t t i n g sa c c o r d i n gt ot h es p c c i a lc o n s t r u c t i o no f t h ec e n t r o s y m m e t r i cm a t r i c e s c o m p a r e dt ot h ej a c o b ia n dg a u s s - s e i d e lm e t h o d s ，t h e i t e r a t i v em e t h o d sb a s e do nt h e s ec e n t r o s y m m e t r i cs p l i t t i n g sh a v ef a s t e rc o n v e r g e n c ea n d l e s sc o s to fc o m p u t a t i o na n ds t o r e h e r ew em a i n l yi n v e s t i g a t et h ei t e r a t i v em e t h o d sf o r t h el i n e a rs y s t e m sw i t hac c n t r o s y m m e t r i cm - m a t r i xa n dac e n t r o s y m m e t r i ch - m a t r i x ， t h eo t h e re a s e sa r ea l s ob e e ns t u d i e d i nt h ea n a l y s ea n d d e s i g no fc o n t r o ls y s t e m s ，t h es o l u t i o n so fm a t r i xe q u a t i o n sa n d m a t r i xi n e q u a t i o n sp l a ya ni m p o r t a n tr o l e ，a n dh a v ec a u s e dm a n ya t t e n t i o n si nc o n t r o l a n dm a t h e m a t i c a lf i e l d s i nt h i sp a p e rw cg i v et w oi t e r a t i v em e t h o d sf o rs o l v i n gt h em a t r i x e q u a t i o n s ： 1 ) s o l v i n gt h ed i s c r e t el y a p u n o ve q u a t i o nm a t r i xa x a t x + q = 0a n dc o n t i n u o u s l y a p u n o vm a t r i xe q u a t i o na x + x a t + q = 0b yu s i n gk r o n e c k e rp r o d u c t si t e r a t i v e m e t h o d ； 2 ) s o l v i n gt h es y l v e s t e rm a t r i xe q u a t i o n sa x + x b = c a n da x b + x = cb y u s i n gt h eg r a d i e n ti t e r a t i v em e t h o d sb a s c do nt h em a t r i xs p l i t t i n g s k e yw o r d s ：c e n t r o s y m m e t r i cm - m a t r i c e s ，c e n t r o s y m m c t r i ch - m a t r i c e s ，l y a p u n o v m a t r i xe q u a t i o n ，s y l v e s t e rm a t r i xe q u a t i o n ，k r o n e c k e rp r o d u c t s ，m a t r i xs p l i t t i n g ，g r a d i - e n ti t e r a t i v em e t h o d 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特别 加以标注和致谢的地方外，论文中不包含其他人已发表和撰写过的研究成果参与 同一工作的其他同志对本研究所做的任何贡献均已在论文中作了说明并表示了谢 意 签名；固a 竖暹日期；盈咝! q ：垡三 本论文使用授权说明 。 本人完全了解上海大学有关保留、使用学位论文的规定，即。学校有权保留论 文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容 ( 保密的论文在解密后应遵守此规定) 签名，燃导师签名：勉丝红期：2 【度趾o f o5 第一章绪论 1 1求解线性方程组a x = b 的方法简介 线性方程组 a x = b ( 1 1 ) 的求解问题是矩阵计算的核心问题，许多科学与工程问题最终会归结到此方程组的 求解，其中a p 黼，b f n 是已知的量，z p 是未知量，这里f 是一个实数 域或复数域 关于线性方程组( 1 1 ) 的求解方法有很多，传统的方法足高斯消去法和它的一 些变形在这些方法中，我们可以通过有限步计算来求得线性方程组( 1 1 ) 的准确 解但对于大型系数矩阵a ，在利用高斯消去法求解时就会破坏a 的稀疏性，从而 增加计算难度和存储空间，因此需要探究a 的一些结构性质，减少或避免同零元 素的乘积，从而节省计算机的存储空问关于高斯消去法的相关算法和具体应用， 可参阅【2 7 】 随着科技的发展，线性方程组的规模越来越大，以至于用直接法很难来求解， 因此，人们越来越重视迭代方法的应用迭代方法主要有两大类；一类为古典迭代 法，常见的方法有j a c o b i 迭代法、g a u s s - s e i d c l 迭代法和s o r 迭代方法 z t ；另一 类为投影方法，即k r y l o v 子空间方法 投影方法主要用来求解大型稀疏线性方程组，有很多著名的方法由h e s t e n e s 和s t i e f e l 提出的c g 方法阳1 主要用于系数矩阵为对称正定矩阵的线性方程组此 后，很多学者从不同角度对c g 方法进行了各种各样的研究，得到了很多有影响的 结果【3 2 ，3 3 ，3 5 ，4 3 ，4 5 】对于求解非对称问题和对称不定问题，y s a a d 和m h s c h u l t z 提出了一种著名的方法g m r e s 方法【6 0 】g m r e s 方法相对于别的很多投影方法具 有数值更加稳定、所需存储更少的特点通过几十年的发展，出现了许多与g m r e s 方法相关的方法 2 8 ，2 9 ，3 4 ，3 6 ，4 l ，叫，这大大丰富了求解线性方程组的方法和手段 本文研究了一种特殊线性方程组的迭代求解，即( 1 1 ) 的系数矩阵a 为中心对 称矩阵，此类方程组有着广泛的应用背景，经常出现在下面的一些领域中： ( 1 ) 微分方程的数值求解； ( 2 ) 一些马尔可夫过程的研究； ( 3 ) 自正交小波基的构造； ( 4 ) 多维的调和恢复问题 1 2 a x = b 和s y l v e s t e r 方程的迭代解法 当然在别的一些物理和工程问题也会遇到这类线性方程组，其中小波分析是数 学中一个迅速发展的领域，正在成为一个重要和活跃的研究领域，它已在数学家和 电子工程师之间建立了一种牢固的联系，引起了广泛注意 关于中心对称矩阵的性质研究及相关问题求解，已经取得了很多成果刘仲云 教授在这方面也做了很多工作，但对于中心对称线性方程组的迭代求解，还是一个 没有涉及的领域中心对称矩阵具有一个很重要的性质，即可约性，利用这个性质 我们就可以通过一个简单的正交变换把一个中心对称矩阵化为一个块对角矩阵，从 而大大的减少计算量和存储量，这是中心对称矩阵的核心性质 a m e l m a n 首先考虑了对称中心对称的矩阵向量乘积【2 4 】，在这篇文章中作者并 没有提到中心对称矩阵的可约性质，只是利用了对称中心对称矩阵的特殊结构来设 计算法，我们知道一般的矩阵向量乘积的计算量为2 n 2 ，而对称中心对称的矩阵向 量乘积则为；n 2 + o ( n ) f a s s b c n d e r 和i k r a m o v 在 2 6 】首先考虑了如何利用中心对称矩阵的可约性来进 行中心对称矩阵的矩阵向量乘积，在 2 6 】中作者不仅考虑了中心对称矩阵，还考虑 了反中心对称矩阵和中心对称的埃米尔特矩阵，并给出了相应的算法这些算法所 需的计算量约为鲁礼2 + d ( 佗) ，看上去比( 2 4 1 中的结果要差一些，但这里考虑地足一 般的中心对称矩阵，而不像【2 4 】中考虑的是对称的中心对称矩阵假如用【2 6 1 中 的算法来计算对称的中心对称矩阵的矩阵向量乘积，计算量大约为鲁n 2 + d ( n ) ，同 m e l m a n s 算法的计算量一样，但 2 6 】中的算法要比m c l m a n s 算法简单且易于实现 刘仲云教授则系统地研究了中心对称矩阵的一系列性质，得到了一些很有价值 的成果在【2 5 】中刘仲云教授利用引理的形式阐述了中心对称矩阵的可约性质，并 利用此引理证明了中心对称日一阵的约化矩阵依然是个日一矩阵，最后得到了一 个系数矩阵是中心对称矩阵的线性方程组的直接解法；他又相继研究了广义的中心 对称矩阵的矩阵向量乘积【3 0 】、中心对称的埃米尔特矩阵的最小二乘解f 3 l 】、中心 对称矩阵的平方根【3 7 ，4 2 】以及广义的k 一中心对称埃米尔特矩阵性质和相应的反 问题的求解 3 8 ，3 9 】 1 2 关于矩阵方程的数值求解方法综述 在线性系统的分析和综合中，检验系统的稳定性、可控性和可观测性是非常重 要的然而，这些检验常常间接地进行，这时l y a p u n o v 理论就非常有用l y a p u n o v 矩阵方程表达式为 a x + x a t + b b t = 0 ( 1 2 ) 2 0 0 8 上海大学博士学位论文3 和 a x a t x + b b r = 0 ，( 1 3 ) 这里a 足一个礼礼的实数矩阵，b r n s 是一个列满秩矩阵且s n ，x 舻x n 是要求的未知矩阵，其中( 1 2 ) 和( 1 3 ) 分别被称为连续的l y a p u n o v 矩阵方程和离 散的l y a p u n o v 矩阵方程矩阵方程( 1 2 ) 和( 1 3 ) 在控制、通讯系统理论和动力系统 中的许多问题研究中有着至关重要的作用，例如日o o 最优控制理论【4 6 】、动力系统 的稳定性分析【2 3 】以及线性时不变的模型降阶【4 7 ，5 9 1 在控制系统中更加频繁遇到 的方程是s y l v e s t e r 矩阵方程 a x + x b + c = 0 ( 1 4 ) 和 a x b - t - x + c = 0 ，( 1 5 ) 其中x 舻黼是一个未知矩阵，a 、b 和c 是具有适当维数的常数矩阵当 b = a t ，s y l v e s t e r 矩阵方程就变为l y a p u n o v 矩阵方程在控制论中还有一类比较 特殊的矩阵方程，即所谓的代数r i c c a t i 方程 a t x + x a + x r x + q = 0 ( 1 6 ) 事实上，( 1 6 ) 为一个非线性矩阵方程，简写为a r e 粗略地说，l y a p u n o v 矩阵方 程在系统分析上非常有用，而a r e 则在控制系统综合方面极为有用；特别地，它 们均在日2 和玩。最优控制中扮演中心角色 在系统的稳定性分析中，对于大部分矩阵方程来说精确解是重要的，但在很多 应用中是没有必要求得精确值的，只需要求得近似值就足够了，如控制系统的稳定 性分析特别地，如果一个系统的参数包含不确定性时，对于鲁棒稳定性分析是不 可能得到精确解的 4 9 ，5 7 】对于矩阵方程的求解方法有很多，通常的方法是利用 k r o n e c k e r 积把要求解的矩阵方程转化成一个线性方程组的形式，然后再利用求解 线性方程组的相关方法如果矩阵方程的规模很大的话，则得到的线性方程组的系 数矩阵会很大，从而由于存储问题而加大了求解难度 还有一些方法是利用了矩阵变换来进行地，即对矩阵进行q r 分解和h e s s e n b e r g 分解，然后对得到的简化矩阵方程来进行求解著名的方法有b a r t e l s - s t e w a r t 算法 5 8 】和h e s s e n b c r g - s c h u r 算法【2 2 1 在b a r t e l s - s t e w a r t 算法中就足对方程( 1 4 ) 中的矩 阵a 和b 进行q r 分解，然后利用一个递推关系式来求得所需要的解；g h g o l u b 等人提出的方法是对b a r t e l s - s t c w a r t 算法的改进，在这个方法中他们对矩阵a 进行 h e s s e n b c r g 分解，而对矩阵b 进行q r 分解，由此得到的递推关系式数值上是稳定 的且相比b a r t e l s - s t e w a r t 算法而言减少了很多计算量 4 a x = b 和s y l v e s t e r 方程的迭代解法 随着科技的发展，迭代方法在矩阵代数和系统识别领域逐渐盛行起来例如， s t a r k c 和n i c t h a m m e r 在【4 8 】中提出了利用s o r 技术来求解c ts y l v e s t c r 方程的 解； m u k a i d a n i 、x u 和m i z u k a m i 【5 7 】讨论了一种求解广义代数l y a p u n o v 方程的 迭代方法；张凯院提出了一种求解l y a p u n o v 矩阵方程的迭代一校正解法【8 】 1 3 本文所做的主要工作 在第三章作者主要讨论了中心对称矩阵方程组的迭代求解，这里的系数矩 阵为一个中心对称m 一阵或一个中心对称日一阵，具有创新性的工作有： ( 1 ) 给出了系数矩阵a 的三个中心对称分裂，它们分别为算术甲均分裂、对三 角分裂i 和对三角分裂，并与j a c o b i 分裂及g a u s s - s c i d e l 分裂做了比较由比较 可以看到，我们给出的三种分裂在收敛速度、计算和存储上具有一定优势 ( 2 ) 对j a c o b i 迭代方法和j o r 迭代方法的收敛速度进行了比较，得到了一些有 意义的结果 ( 3 ) 考虑了如何用h s s 迭代方法来求解系数矩阵为非h e r m i t c 正定t o e p l i t z 矩 阵的线性方程组，它是h s s 迭代方法f 1 3 】的一种特殊形式，其中 h = 去( a + a t ) 是一个中心对称矩阵，而 s = 妄一a r ) 是一个反中心对称矩阵，我们就可以利用中心对称矩阵 2 5 】和反中心对称矩阵 2 6 】 的约化性质来减少存储和运算量在这里我们把本论文中的h s s 迭代方法和h s s 迭代方法【1 3 】作了比较，由数值结果我们可以看到，在一定情况下h s s 迭代方法更 有效率 在第四章中，作者重点考虑了控制论中的l y a p u n o v 矩阵方程和s y l v c s t e r 矩 阵方程的迭代求解，具有创新性的工作有 ( 1 ) 给出了一种求解l y a p u n o v 矩阵方程的迭代方法一k r o n e c k e r 积迭代方法， 即利用k r o n e c k e r 积得到一个收敛的迭代序列，然后分析了这种方法的收敛性并给 出了相应的数值算法 ( 2 ) 讨论了如何用基于矩阵分裂的梯度迭代方法来对s y l v e s t c r 矩阵方程进行迭 代求解，给出了两种梯度迭代方法一j g i 方法和q j g i 方法与【6 叫中的g i 方法 相比，我们给出的方法具有收敛速度快且计算量少的优点 第二章迭代方法综述及一些相关的理论结果 在这一章中我们主要讨论一些求解线性方程组( 1 1 ) 常用的迭代方法，在实际 应用中，矩阵a 的阶数礼一般较高，由于计算机存储的限制，往往很难用直接方法 来求解，在这种情况下一般用迭代方法 在线性代数中，迭代算法的重要性源于一个简单的事实：对于一般矩阵，非迭 代的或直接算法所需的工作量达到o ( m 3 ) 在绝对意义下，当m 很大时m 3 非常巨 大；在相对意义下，大多数矩阵问题输入仅包含o ( m 2 ) 次数，而求解它们时所需的 工作量为m 3 ，这看起来似乎不合理，由此在这两个意义下均太大了下面的图表 给出了这些年来矩阵计算的发展史，从其可以看到在表中相应的年代，对于稠密矩 阵的计算究竟什么维数可以认为是大的，表中的数据给出了一个大致的近似 矩阵计算的发展简史表 1 9 5 0 ：m = 2 0w i l k i n s o n 1 9 6 5 ：仃l = 2 0 0 f o r s y t h e 和m o l e r 1 9 8 0 ：m = 2 0 0 0l i n p a c k 1 9 9 5 ：m = 2 0 0 0 0l a p a c k 由表中我们可以看到在2 0 世纪6 0 年代中期的”f o r s y t h e 和m o l e r 年代”( 因其 于1 9 6 7 年出版了一本有影响的教科书而得名) ，数百阶的矩阵就算大的了，这是因 为在合理的时间内，在当时的机器上数百阶的矩阵计算已达到极限了显然，在这 4 5 年的过程中，可求解的矩阵问题的维数以1 0 3 因子增加，这个进展是巨大的，但 在同一时期内，计算机硬件达到1 0 3 因子，即从浮点运算( 每秒) 到千兆浮点运算 ( 每秒) 的高速发展，从这个数据看来，历史上已经克服了直接矩阵算法然而如果 矩阵问题能以o ( m 2 ) 次运算来求解而不用o ( m 2 ) 次运算，则今天可以处理的某些矩 阵阶可以扩大1 0 到1 0 0 倍，对这些矩阵使用矩阵迭代方法可以达到这个目标 在这一章中我们简单介绍三类迭代方法及其相应的一些迭代收敛理论，这三类 方法分别为古典迭代方法、基于变分原理的迭代方法和基于g a l e r k i n 原理的迭代方 法f 1 , 2 ，3 ，4 ，5 ，6 ，7 ，2 7 ，5 0 1 2 1 古典迭代方法 2 1 1 常用的迭代方法 古典迭代方法是相对基于g a l e r k i n 原理的迭代方法而言，就是基于矩阵分裂的 5 6 a x = b 和s y l v e s t e r 方程的迭代解法 迭代方法，常用的古典迭代方法有简单迭代方法、j a c o b i 迭代方法、g a u s s s c i d e l d 迭代方法和s o r 迭代方法 令 a = m k ( 2 1 ) 是系数矩阵a 的一个分裂且m 是非奇异的，则由分裂( 2 1 ) 可以得到 a x = m x k x = b 即 z = m 一1 k x + m 一1 b = r x + ， 则我们可以得到下面的迭代序列。 x m + l = 鼢m + ， ( 2 2 ) 其中r = m _ 1 k 称为( 2 2 ) 的迭代矩阵，z o 是任意给定的n 维列向量，称为初始 向量如果向量序列 z 知 收敛，即l i m 七一o 。i l k = i l + ，则矿就是线性方程组( 1 1 ) 的 唯一解 由于迭代序列( 2 2 ) 中的z 抖1 线性依赖于z 七( 就其分量而言) ，而不明显依赖 于$ 七一l ，x k 一2 ，i l o ，且迭代矩阵兄保持不变，所以称迭代格式( 2 2 ) 为一阶线性定 常迭代格式对系数矩阵a 给出不同的分裂就可以得到不同的迭代格式，下面就来 介绍几种基本的迭代格式 在下面的迭代格式中要用到矩阵a 的一个分裂，假设a 的对角线上的元素都 不为零，则 a = d l u = d ( i l u ) ， ( 2 3 ) 其中d 是a 的对角矩阵，一是a 的严格下三角矩阵部分，一痧是a 的严格上三 角部分 ( 1 ) 简单迭代格式t 给出下面的矩阵分裂a = i 一( i a ) ，则线性方程组( 1 1 ) 等价于 茁= ( i a ) i l + b ，( 2 4 ) 令r = i a ，= b ，即其相应的格式( 2 2 ) 称为简单迭代格式 ( 2 ) j a c o b i 迭代格式。 利用( 2 3 ) 的表达式，关于j a u c o b i 迭代方法的分裂为a = d 一( 三+ 5 3 ，则线性 方程组( 1 1 ) 等价于 z = ( l + u ) x + d b ，( 2 5 ) 2 0 0 8 上海大学博士学位论文 7 若取r j = 三+ u ，力= d b ，则其相应的格式( 2 2 ) 称为j a c o b i 迭代格式 ( 3 ) g s ( g a u s s - s e i d e l ) 迭代格式： 由( 2 3 ) 我们可以给出关于g s 迭代格式的矩阵分裂ta = ( d 一三) 一痧，则线性 方程组( 1 1 ) 可以写为 z = ( i l ) 一1 u x + ( i l ) 一1 d 一1 b ，( 2 6 ) 令r v s = ( i l ) u ，南s = ( j 一三) - 1 d b ，则其相应的格式( 2 。2 ) 称为g s 迭代格 式g s 迭代格式可以改写为 z 膏+ 1 = l x k + l + u z 知+ d 一1 b( 2 7 ) ( 4 ) s o r 迭代格式 为了改善g s 迭代格式的效率，我们对z 知+ 1 和孤进行算术平均； z 詹+ 1 = ( 1 一w ) x k + w x k + i ， 把g s 迭代格式代入我们可以得到 x k + 1 = ( 1 一w ) x k + w ( l x k + 1 + u x k + d 一1 b ) 珏( i w l ) z k + 1 = ( ( 1 一u ) ，+ u u ) x k + w d 一1 b ( 2 8 ) 镩x k + l = ( i w l ) 一1 ( ( 1 一u ) j + u u ) + ( j u l ) 一1 w d 一1 b ( 5 ) 对称s o r 迭代格式( s s o r ) 在我们上面给出的几种迭代方法中，j a c o b i 迭代方法和g a u s s - s e i d e l 迭代方法 在不需要相关矩阵的信息就可以执行( 尽管在证明它们收敛时需要一些信息) ，s o r 迭代方法中的参数u 的选择依赖于迭代矩阵的谱半径c h e b y s h e v 加速技术在我们 知道迭代矩阵的谱半径的更多信息时是很有用的 现在我们简单介绍一下c h e b y s h e v 多项式及其在迭代方法中的应用 2 7 1 假设我们把线性方程组( 1 1 ) 转化成相应的迭代格式( 2 2 ) ，利用一些常见的迭 代方法，如j a c o b i 迭代方法、g a u s s - s e i d c l 迭代方法或s o r 迭代方法，我们就可以得 到一个序列 翰) ，如果p ( r ) 0 利用c h e b y s h e v 多项式我们可以得到关于加速迭代格式x k + 1 = r x k + f 的算法 【2 7 】： 算法2 1 u 0 = 1 ；u l = p ；y o = x o ；y l = r x o + ， f o rm = 2 ，3 ， u r n = 1 ( p 。2 _ _ 1 - 一磊b ) y m = 看警等r 跏一1 一蠢一2 + 爰黧j ， e n d 但在一般情况下我们不能直接对迭代格式x k + l = r x 七十，进行c h e b ，r s h e v 加 速，因为c h c b y s h e v 加速需要迭代矩阵r 在区间【一p ，p 】中要有实特征值，但在对 称s o r ( s s o r ) 中我们可以用c h e b y s h e v 加速，这需要线性方程组( 1 1 ) 中的系数矩 阵a 是一个对称矩阵，详细的算法及对称s o r ( s s o r ) 迭代格式中的迭代矩阵具有 实特征值的证明详见【2 | 7 】 2 1 2 一些相应的迭代收敛结果 下面我们就给出一些关于上述给出的迭代方法的收敛结果，这些结果是一些常 见结果，关于它们的证明我们可以参考 4 ，5 ，2 7 2 0 0 8 上海大学博士学位论文 9 引理2 3 令l 为一个任意的算子范数( 1 l r l l 三m o 料) 如果旧l i 0 ，存在一个算 子范数”队使得 i r l l + p ( r ) + 范数扎依赖于r 和e 定理2 5 对于所有的初始向量x 0 ，迭代序列( 2 2 ) 收敛到线性方程组( 1 1 ) 的解 的充要条件是p ( n ) 0 ( i = 1 ，2 ，n ) ，则j a c o b i 迭代 格式收敛的充要条件是a 和2 d a 都是正定矩阵 定理2 7 设a 满足下列条件之一 ( 1 ) a 按行( 列) 严格对角占优， ( 2 ) a 按行( 列) 弱对角占优且不可约， 则j a c o b i 迭代格式是收敛的 定理2 8 设a 按行( 列) 严格对角占优，则j a c o b i 迭代格式和g a u s s - s e i d e l 迭 代格式都收敛 定理2 9 设a 是h e r m i t e 正定矩阵且实参数满足0 0 ，故o l k 是，( a ) 的极小值点直接计算可得 妒( x k + a k z k ) 一妒( z 奄) = 一互1i r 五k 夏, z _ k 两 2 ( 2 1 1 ) 当h ，魂】0 ，即钝和仇不正交时，我们有妒( z 知+ 1 ) ，j ：1 川2 ，m ( 3 ) 计算y m = 碥1 ( 肛1 ) 和z m = x 0 + 蜘 性质2 2 2 由f o m 方法得到的近似解z 仇的残量为 b a $ m = 一，h - i - 1 m e 刍毫m 仇n + l ， m 因此 i 陋一a z m i l 2 = + l ，m i e 景1 由算法2 6 可知，由于g r a m - s c h m i d t 正交化过程，我们发现随着m 增加计算 量至少以o ( m 2 ) n 的数量级增加，存储量以o ( m n ) 的数量级增加当n 很大时此算 法的优势不明显，因此我们采用重起的f o m 方法 2 0 0 8 上海大学博士学位论文 1 7 算法2 7 ( f o m ( m ) 算法) ( 1 ) 计算r 0 = b a x 0 ，p = | i t 0 1 1 2 和v l = 署 ( 2 ) 利用a r n o l d i 算法来得到a r n o l d i 基和矩阵丑- m = h i j i ，歹：l 洲2 ，m ( 3 ) 计算y m = 塌：1 ( p e l ) 和z m = x 0 + 如果满足我们的计算要求，则算 法停止 ( 4 ) 令x 0 = z m 并返回到1 2 3 4g m r e s 方法 由于a r n o l d i 算法的中断问题难以解决，并且在理论上很难分析其收敛性，这 促使人们探索另外的g a l e r k i n 型算法令l m = 4 。，则得到g m r e s 方法，即广 义的最小残量方法 我们有两种方式来得到g m r e s 算法第一种方式是利用最优化的性质，即最 小二乘的方法；第二种方式是直接利用g a l e r k i n 原理来得到 ( 1 ) 利用最小二乘来得到g m r e s 算法一 任何在z o + 中的向量z 可以写为 z = x 0 + v m y ， 其中y 是一个仇维的向量定义 j ( y ) = l | 6 一a x 2 = 1 1 6 一a ( x o + v m y ) 0 2 ， 利用a r n o l d i 基的性质，我们可得 b a x = b a ( x o + v m y ) = r 0 a v m y = p 口1 一+ 1 h m y = v m + 1 ( p e l 一直m y ) 因此 j ( y ) = i i b a ( x o + w m y ) 1 1 2 = l | 伽l 一詹_ m 耖1 1 2 ( 2 1 7 ) g m r e s 方法的近似解就是z m = x 0 + ，这里是( 2 1 7 ) 的解 ( 2 ) 利用g a l e r k i n 原理来得到g m r e s 算法： 利用( 2 1 6 ) 且令职秸= a v m ，我们就可以得到 略a = v t a t , o ( 2 1 8 ) 由a r n o l d i 基的性质a 1 ，= 1 ，+ l 宣n ，则( 2 1 8 ) 可以写成 藤矾= 矾阢 ( 2 1 9 ) 1 8 a x = b 和s y l v e s t e r 方程的迭代解法 则( 2 1 9 ) 就等价于( 2 1 7 ) 定理2 2 3 对于m 0 ，名m j 满足( r 0 一a 确) 上l m 的充要条件足 l i t 0 一a z l l = 。m k i n 。i 卜。一a z i | ， 这里z m = y m 算法2 8 ( g m r e s 方法) ( 1 ) 计算r 0 = b a x o ，p = i i r 0 1 1 2 和v l = 弩 ( 2 ) 利用a r n o l d i 算法来得到a r n o l d i 基和矩阵盘。= h i j l i n i + 1 ) ，则称a 为严格左上三角矩阵，对于( 严格) 右下三角矩阵也有类似定义 引理3 8 设a = m n 是一个( 弱) 正则分裂，则 p ( m 一1 n ) 0 引理3 9 设a 是一个日一矩阵，a = m n 为其一个分裂，若 ( a ) = ( m ) 一l i ， 则p ( m 一1 n ) 1 引理3 1 0 设a 和c 是m 一阵，如果a b c ，则b 也是一个m 一阵 3 2 中心对称矩阵的算数平均分裂 如果个中心对称矩阵的分裂是中心对称分裂的话，则就可以利用中心对称矩 阵的可约性质来减少计算量和存储量在下面的几节中我们主要来考虑如何构造中 心对称矩阵的中心对称分裂在这一节中我们首先给出一种中心对称分裂算数平 均分裂 算术平均分裂其实是一种多分裂，通过中心对称矩阵a 的两个收敛分裂的算 术平均，就可以得到它的一个中心对称分裂 设a = m n 为中心对称矩阵a 的个收敛分裂，则由此分裂得到下面的迭 代序列： x k + l = m 一1 n x k + m 一1 b ，歹= 0 ，l ，2 ( 3 3 ) 2 0 0 8 上海大学博士学位论文 由中心对称矩阵的定义可知，m j = a = j m j t ，也是a 的一个收敛分 裂，其对应的迭代序列为 z 七+ l = j m 一1 n j x k + j m 一1 j b ，j = 0 ，1 ，2 ( 3 4 ) 我们考虑迭代序列( 3 3 ) 和( 3 4 ) 的算术甲均，得到一个新的迭代序列， 1 = 丢( m _ l n - kj m _ 1 n j ) x k + 丢( m _ 1 + j m j ) b ，歹= 0 1 2 一 ( 3 5 ) 若记 g = 丢( m _ 1 + j m 。1 n h = i ( m - 1 n + j m n j ) ， 则( 3 5 ) 可以写为 z 知+ l = h x k + g b ，( 3 6 ) 若g - 1 存在，则( 3 6 ) 可以看成是由分裂 a ：g 一1 一g 一1 h 得到的迭代序列，此分裂就是所谓的算术平均分裂 根据中，5 - 对称矩阵的性质3 4 ，我们可知h 、g 。g 一1 和g - 1 h 都是中心对 称矩阵，即算术平均分裂是一个中心对称分裂 3 2 1中心对称m 一阵的算术平均分裂 下面我们来讨论一下中心对称m 一阵的算术平均分裂我们先给出中心对称m 一阵 的算术平均分裂的收敛定理，然后再与j a c o b i 迭代方法和g a u s s - s c i d c l 迭代方法作 一下收敛速度和存储量的比较 引理3 1 1 2 0 设a 是非奇异矩阵且a 一1 0 ， a = 蚴一她( 1 = l ，2 ，k ) 是a 的个弱正则分裂，则对任何满足条件的e l ，l = l ，2 ，七，p ( w ) 1 ，这里 w = 冬1 e t m v l l ，冬1 e z = j 定理3 1 2 设a 是一个中心对称的m 一阵，令a = m n 是a 的一个弱正则 分裂，则由算术甲均分裂得到的迭代序列 撕1 = 丢( m - 1 n + j m 。n j ) x k + 丢( m _ 1 + j m - l j ) b 是收敛的 a x = b 和s y l v e s t e r 方程的迭代解法 证明；由引理3 1 1 直接可证 定理3 1 3 1 9 1 设a 一1 0 ，令( m k ，n k ，鼠) 罂1 是a 的一个多分裂，其中每 个( m k ，n h ) 是a 的一个弱正则分裂更进一步地，令觑，觑满足 ， 舰sm ksm 2 ，k = 1 ，2 ，m 令 m h = 玩坛1 9 k 七= 1 如果a = 晒一觑是一个正则分裂，则 p ( 所1 觑) p ( 日) 如果a = 必一觑是一个正则分裂，则 p ( 日) p ( 砑1 觑) 引理3 1 4 如果a = m n 是中心对称矩阵a 的一个弱正则分裂，则 a = j a j = j m j j n3 。 也是一个弱正则分裂 证明：因为a = m n 是一个弱正则分裂，则有m _ 1 0 和m _ 1 n 0 因 为j 只是一个置换矩阵且j 以= j ，则我们有 ( j m j ) 一1 = j m 一1 j 0 ，( j m j ) 一1 ( j n j ) = j m 一1 ，之0 定理3 1 5 设a = m 一是a 的任意一个收敛的分裂。其中a 是一个中心对 称的m 一阵，令( 尥，n k ，玩) 2 ：l 是a 的一个多分裂，且每个( 尥，肌) 是a 的一个 弱正则分裂，这里 尬= m ，l = n ，e 1 = ， m 2 = j m zn 2 = j n j , f _ a = 荟1 更进一步地，令慨，啦满足 慨m k 盹，k = l ，2 令 日= 丢以n + j m n j ) ， 2 0 0 8 上海大学博士学位论文 如果a = 磁一觑是一个正则分裂，则 p ( 田1 对1 ) p ( 日) 如果a = 艺一觑是一个正则分裂，则 p ( h ) p ( h ? 1 2 1 如) 证明：利用定理3 1 3 和引理3 1 4 即可证明 例子3 1 考虑下面的中心对称m 一阵 a = 21 12 0 一l o一0 5 0 50 一l0 2一l 一12 令a = d 一( l + u ) 为j a c o b i 分裂，a = ( d l ) 一u 为g a u s s - s e i d e l 分裂，则我们有 ( d l ) d ，j ( d l ) j d 令 h = 去( ( d l ) 一1 u + j ( d 一工) 一1 u ，) 是由从g a u s s - s e i d e l 分裂得到的算术平均分裂的迭代矩阵，g ，= d 。陋+ u