（计算数学专业论文）模糊线性系统的分块预处理技术及其数值求解方法.pdf

摘要 在本文中，我们的主要工作是提出了对于特定块结构的线性系统的降阶处 理方法，结合一些预处理技术来求解大规模的模糊线性系统。通过对特殊结构 的系数矩阵的降阶处理，我们加快了迭代的收敛速度并减小了计算的代价，我 们还特别的讨论 t o e p l i t z 矩阵的情形。最后我们给出一些数值例子来说明我们 的计算结果。 关键词：模糊线性系统，广义极小残量法，降阶，预处理 中图法分类号：0 1 5 1 2 1 ；0 2 4 1 1 一i i a b s t r a c t i nt h i sp a p e r , w ep r e s e n tas p e c i a ld i m e n s i o nr e d u c t i o nm e t h o df o rs o m em a t r i c e s w i t hs p e c i a lb l o c ks t r u c t u r e ，a n ds o m ep r e c o n d i t i o n i n gt e c h n i q u e st os o l v et h el a r g e s c a l ef u z z yl i n e a rs y s t e m t h r o u g hr e d u c et h ed i m e n s i o n so ft h ec o e f f i c i e n tm a t r i x w i t bt h es p e c i a ls t r u c t u r e w ec a r la c c e l e r a t ec o n v e r g e n c eo f t h ei t e r a t i o na n dr e d u c et h e c o s to ft h ec o m p u t a t i o n e s p e c i a l l y , t h ec a s et h a tt h ec o e f f i c i e n tm a t r i xi st o e p l i t zi s d i s c u s s e d l a s t l y , w eg i v es o m en u m e r i c a le x a m p l e sa n df i g u r e st os h o wt h en u m e r i c a l r e s u l t s k e yw o r d s ： f u z z yl i n e a rs y s t e m ，g m r e s ，d i m e n s i o nr e d u c t i o n ，p r e c o n d i t i o n i n g t e c h n i q u e s c h i n e s el i b r a r yc l a s s i f i c a t i o nh u m b e r t i l l 前言 本文的主要工作是提出了由模糊线性系统嵌入产生的系数矩阵结构为 ，ab 、 ibaj 的线性系统的降阶处理方法。通过分析块结构的性质和降阶处理和预处理方法 的引入，我们大大降低了计算的代价。我们最后在数值例子中还考虑了一般情 形和系数矩阵是t o e p l i t z 的情况，并使用相应的预处理方法。本文提出的矩阵降 阶分块处理方法对于具有 ( 口a 三) 的块结构的矩阵都成立，因此凡是对于有这个结构的系数矩阵，无论是否奇 异，求方程的解均可以降阶处理，这样可以较好地改善计算的效率。在本文的 最后我们给出了一些数值例子来说明降阶前后和预处理前后计算收敛过程的比 较。 与前人的工作相比，我们采用分块计算并采用不完全l u 分解和循环矩阵 逼近的预处理方法，很大程度上改善了计算收敛的表现。 本文第一章给出了模糊线性系统的定义，一些性质和嵌入求解的一般过 程；第二章给出了广义极小残量法的算法；第三章给出了矩阵分块降阶计算的 定理和一些预处理的方法；最后我们给出了些数值例子说明了我们的计算改 善是行之有效的。 一 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 ll l2 寻 亏州剪 论文使用授权声明 隗趋逍。厂 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 名；弼聊签澎嘲 j 2 6 1 | ； 1 1 问题背景 第一章模糊线性系统 模糊数的概念和计算规则最早被z a d e h 【3 0 ，3 1 ，m i z i l m o m 和t a n a k a 【3 2 ， 3 3 ，d u b o i s 和p r a d e 【3 4 和n a h m i a s 3 5 等人所引入。在普通线性方程组中， 它的系数矩阵元素或者是右端项全部或者部分的被模糊数取代所生成的就是模 糊线性方程组。在本文中，我们将会考虑以下形式的模糊线性方程组 a z = y 其中系数矩阵a = ( a q ) ，1 i ，j 礼是一个几n 的精确数的矩阵，y 是一 个元素全部为模糊数组成的模糊向量。模糊线性方程组( 1 1 ) 的概念 1 】在数 学；统计学；物理学；工程科学等学科中扮演着重要的角色，寻找求解形如 ( 1 1 ) 的模糊线性方程组的数值解法也具有很重要的现实意义。许多学者已 经在模糊线性方程组的求解中做了大量的工作，例如解的存在性和嵌入等方 法的提出【1 ，1 4 ，1 5 】。对于 n 的非奇异的模糊线性方程组，s a b b a s b a n d y 等人发展了一系列的数值求解方法，包括直接法 1 6 】和一些经典迭代法，例 如r i c h a r d s o n 迭代，j a c o b i 迭代，g a u s s s e d i e l 迭代和s o r 方法【1 7 - 2 2 】。对于 系数矩阵非奇异的情形，求解模糊线性系统的最速下降法 2 3 】和共轭梯度法 ( c g ) 2 4 】也在随后相继被提出。对于mx 佗一般情形的模糊线性方程组，一些 研究成果关于奇异线性系统，广义逆和最小二乘问题也被提出 2 5 - 2 7 】。但是在 前人的工作中，求解形如( 1 1 ) 的模糊线性方程组并没有考虑嵌入后的系数矩阵 的结构问题，而致使问题规模扩大。而在已有研究成果中，数值例子多以小规 模矩阵符号运算为主，很难推广到实际高阶的问题求解中，这样就使问题失去 了实际意义。此外，已有的研究成果并不包括用广义极小残量法( g m r e s ) 等现 代迭代法求解模糊线性方程组的结果。 作为经典的结果，许多经典直接法在求解大规模的线性方程组时会有很多 缺点，经典的迭代法对于方程( 1 1 ) 的迭代矩阵的谱半径接近于1 的时候效果不 是很理想。对于c g 方法，【2 4 】所提出的方案只能适用于系数矩阵对称正定的 模糊线性系统。综上所述，研究模糊线性系统的结构和预处理技术，提出适用 于较大规模的模糊线性系统的解法是非常有必要的。 1 _ 2 模糊线性方程组 1 2 1 模糊数 在这个部分中，我们简要回顾一下模糊数的性质。 我们用一个有序函数对( 笪( r ) ，面( r ) ) ，0 r 1 来表示任意的模糊数，满足 以下性质： 笪( r ) 是一个在 0 ，1 】上的有界左连续非减函数， 面( r ) 是一个在【0 ，1 】上的有界左连续非增函数， 型( r ) 百( r ) ，0 r 1 。 图1 给出了模糊数( 1 + r ，4 2 r ) 的表示。当型( r ) = 面( r ) = d ，0 r 1 ，q 是常数时，我们称该模糊数是精确的( c r i s p ) 。相对于模糊数，如果没有特别说 明，我们在本文的其余地方称这种情形的数为精确数。 r 1 一一 1 2 3 4 图1 1 一个模糊数 1 2 2 模糊线性方程组 定义1 1 ：当n n 的线性系统 ( 1 2 ) 的系数矩阵a = ( a j ) ，1 t ，j n 是一个由精确数组成的n n 的矩 阵，y ，1 i n 是模糊数，我们称这样的系统为模糊线性系统( f l s ) 。 1 2 3 求解模糊线性系统的数学模型 在本小节，我们将给出模糊线性系统的一些性质，定义它的模糊向量解和 求解一般步骤。 我们首先回顾一下模糊数的一些运算性质，考虑模糊数z = ( 互( r ) ，虿( r ) ) ，y = ( r ) ，可( r ) ) 和实数七。 1 。= y 当且仅当星( r ) = y ( r ) 和虿( r ) = 可( r ) 2 z + y = 瞧( r ) + 可p ) ，z ( r ) + 可( r ) ) 3 k x ：j ( 垃，k 0 i ( 船，k x _ ) 岛 0 ，1 jsn ，我们可以简单地得到 ( 1 3 ) a i j x j = 甄 ( 1 4 ) 3 = 1 3 一 玑抛 玑 = | | = n n 饥 磊研 o， ，舻 ， m h 甜 竹 m m 口 + + + + + + 2 2 ： 2毗姚；胞 + + + 城 心 地 m 以 咖 兰呐器 玑一 = n 。m 对于一般情形，任意的丝或者甄的方程的表达式可能为含有曼或巧的线性组 合。为了求解( 1 2 ) 的线性方程组，m f r i e d m a n 等人给出了一个嵌入方法【l 】1 ， 用求解一个2 n 2 n 的精确数的方程组来代替直接求解形如( 1 2 ) 的模糊方程组。 我们重排线性方程组( 1 3 ) 使得未知项是而和写，1 i 礼，方程右端列 向量为 y = ( y l ，y 2 ，广西，一_ ，一砺) r 按照这样的排列，我们就可以得到以下2 n 2 n 的线性系统 8 1 1 x 1 1 + s 1 2 x 呈2 + + 8 1 n x _ 旦n + 8 1 ，n + 1 ( 一百) + 8 1 ，n + 2 ( 一瓦) + + 8 1 ，2 n ( 一面_ ) = 丝 s n l 兰l + s 。2 丝+ - - + 8 n n x _ 旦n 3 f8 n , n + l ( 一_ ) + 8 n , n + 2 ( 一_ ) + + 8 n , 2 n ( 一瓦) = 丝， 8 n + l ，1 兰l + s n + 1 ，2 兰兰+ + 3 1 ，n 曼量+ s n + l ，n + 1 ( 一j 可) + s n + 1 ，n + 2 ( 一j 动+ + s n + 1 2 n ( 一互动= 一丝 ； 8 2 n ，l x _ ! - + - $ 2 n ，2 丝+ + s 2 n ，n x n + 8 2 ”+ 1 ( 一- ) + s 知卅2 ( 一瓦) + + s 2 m 2 n ( 一瓦) = 一丝， 其中按照下式所定义 j o 穹剐巧，s + n j 。a j ，( 1 5 ) 【a l j 0 = 辛s ，j + n = 一a i j ，8 i + n j = 一。巧， 所有未被( 1 5 ) 式所定义的8 玎都是零。于是按照上面所定义的，我们可以得到 s x = ( 1 6 ) 其中s = ( 5 玎) ，1 ，j 2 n ， x = 4 y= 1 ： _ - y l ： 一鲰 ( i 7 ) 一1 一n 鱼；堕呵屯 下面我们举例来说明。 例1 3 ：考虑2 2 的模糊系统 经过嵌入后我们得到4 4 的系统 其中系数矩阵 我们可以很容易看出的值，并且注意到s 具有以下结构 s = ( 考三) ， s ， 其中b 包含了a 的所有非负的元素，e 包含了所有a 的所有非正的元素的绝对 值，并且有4 = b e 。 线性方程组( 1 6 ) 是一个2 n 2 n 的精确数方程组，当且仅当系数矩阵s 是 非奇异的时候，( 1 6 ) 有且仅有唯一的解。于是我们就有了下面两个问题： 1 系数矩阵s 在什么时候是非奇异的? 2 由( 1 6 ) 所得到的2 n 维的解向量x 是否可以得到原模糊线性方程组( 1 2 ) 的解向量? 如果a 是非奇异的，那么上述第二个问题的答案是肯定的当且仅当 ( 鱼( r ) ，酉( r ) ) 对于所有的i 都是模糊数。 下面的例子揭示了这样一个事实：即使原系数矩阵a 是非奇异的，s 也可 三 现知 一 + 1 i z z ，、【 一抛弛，项沪地兰嘲动|l西酞嘲梦司删 + + + 万 研一研一现一卜 0 0 l l o 2 1 o 1 l o o ，。一 = s 能奇异。 例1 4 ：现有如下线性系统 系数矩阵 是非奇异的，但 a = ( ；_ 1 ) s 一 ； 是奇异的。换句话说，原系数矩阵为a 的模糊线性系统可能无解，也可能有无 穷多个解。 下面给出一些已有的定理结论来进一步说明模糊线性系统和嵌入后精确数 线性系统的关系和性质。 定理1 5 ：【1 】矩阵s 是非奇异的当且仅当矩阵a = b c 和矩阵b + c 都是非 奇异的。 推论1 6 ： 1 如果精确数线性系统没有唯一解，那么相对应的模糊线性系统也 没有唯一解。 定理1 7 ：【1 如果矩阵s - 1 存在，那它一定具有和s 相同的块结构 = ( ；丢) ， 事实上，由( 1 8 ) 如果s 可逆，我们可以很容易的计算出 。e 三；f ；言：昌：二：b b 二昌：；j c - - 。， 【= ( 口+ c ) 一( 一g ) 一1 】 、。 这样在理论上( 1 6 ) 的解就可以写成 x ：s 一、y ? 一6 一 玑沈 = = 2 2 z z 一 + l 1 o z ，、l 这样的解向量虽然是唯一的，但仍然可能不对应一个模糊向量。下面我们给出 一个定理来说明这种情况。 定理1 8 ：【1 】线性方程组( 1 6 ) 对于任意y 的唯一解( 1 11 ) 都对应一个模糊向量 当且仅当s - 1 是非负矩阵 ( s 一1 ) 玎0 ，1si ，j 2 n ( 1 1 2 ) 我们限定在本文中我们所讨论的模糊数都是三角模糊数，即是丝( r ) ，嚣( r ) 和垒( r ) ，瓦( r ) 都是关于r 的线性函数。在计算得到了( 1 6 ) 的精确数解后，我们 接下来将定义原模糊线性方程组( 1 2 ) 的“模糊解”。 定义1 9 ：【1 】令 x = ( 亟( r ) ，一再( r ) ) ，1 s i n ) 表示( 1 6 ) 的唯一解，模糊向量 u = ( 坐p ) ，面p ) ) ，1 i 几) 称为s x = y 的模糊解当它按照下式定义 丝( 7 ) = m 饥 堕( r ) ，瓦( r ) ，旦( 1 ) ) ，( 1 1 3 ) 【面( r ) = m a x 乜( r ) ，写( r ) ，丑( 1 ) 、 下面我们给出一个例子来说明上面的定义。 例1 1 0 ：考虑以下2 2 的模糊系统 z x 。l + - 。= $ 2 。= ：( r 。, 2 + - ，r ，7 ) , 一。， 方程组系数矩阵为a ，经过嵌入后得到的线性系统为s x = y ，其中 s = 、 l 0 0 3 o 0 1 l o 3 1 o 卜 这个线性系统的解为 x = 丑( r ) x 2 ( r ) 一石( r ) 一瓦( r ) = s o y 并且 ，1 1 2 5- 0 1 2 50 3 7 5 y ：i - 0 3 7 5 0 。3 7 5 _ 0 1 2 5 1 0 3 7 5- 0 3 7 51 1 2 5 、- 0 1 2 50 1 2 5 - 0 3 7 5 、 这样我们就得到如下模糊解 r 4 + r r 一2 2 r 一7 z l ( r ) = 1 3 7 5 + 0 6 2 5 r ，嚣( r ) = 2 8 7 5 0 8 7 5 r 兰2 ( r ) = 0 8 7 5 + o 1 2 5 r ，瓦p ) = 1 3 7 5 0 3 7 5 r 这里堕s 石，x 2 2s 瓦；一x l ，一x 2 都是单调下降函数。 一8 一 、 5 5 朋幻弛两 o 1 o 3 一 o o 第二章k r y l o v 子空间与广义极小残量法( g m r e s ) k r y l o v 子空间迭代法在解决由实际问题衍生而来的大规模稀疏线性方程 组方面非常著名。在本章节中，我们将介绍用于求解( 1 6 ) 的k r y l o v 子空间方 法。k r y l o v 子空间方法是一个子空间修正方法，它的步骤框架将会在本章的几 节介绍。 2 1 子空间修正法 考虑精确数线性系统c x = y ，我们将会构造一个逼近方程真解的迭代序 列x ( ”，x ( 2 1 ，他们有如下关系 x ( m ) = x ( o ) + d ( m ) 其中d ( ”) 是从m 维修正空间e 。中取出的修正量。我们可以运用构造方法来确 定d ( ”) 。构造方法主要有两种：极小化残量法( m i n i m a lr e s i d u a l ) 和正交化残量 法( o r t h o g o n a lr e s i d u a l ) 。 令 r ( m ) = y c x ( m ) = ( 篆；) = ( ；) 一( 戛蓦) ( 耋：) 我们可以对残量r ( r a ) 运用构造方法。令d 燃由极小化残量法( m r ) 所决定的修 正，d 鼎是由正交化残量法( o r ) 所决定的修正。我们有以下关系 r 一c 塌1 1 = 蝙m i n 胪一c d “i i = m i n i ir ” 和 r ( o ) 一c d g 皇= r ( ”上、，( 2 2 ) 其中为m 维空间。我们定义w 。= g c 。为修正空间的像空间，我们可以重 新把( 2 1 ) 和( 2 2 ) 写为 和 r 。一t j 蹴1 1 = 。m 。w m i n | i r ( 0 一叫f | ， ( 2 3 ) r ( ”) 一凛j _ 9 ( 2 4 ) 于是，( 2 3 ) 和( 2 4 ) 的解就可以由r ( o ) 在w 。上正交投影 叫蹴= ，饥( r ( o ) 和r ( o ) 沿着l k 在w 。上斜投影 加罐= 磁( r ( o ) 来得到。于是从( 2 3 ) 和( 2 4 ) ，极小化残量过程( m r ) 和正交化残量过程( o r ) 就可以分别构造出r ( o ) h 的在空间w t 。中的正交投影和斜投影形成的序列。 2 2 k r y o v 子空间方法 在k r y l o v 子空间方法中，我们从i n y l o v 子空间中得到x ( ”) = x ( o ) + d ( ”) 的迭代改进，其中 d ( m 足k r ( o ) ：= s p a n ( r ( 0 1 ，c r ( 0 1 ，c m 一1 r ( o ) 在这种情况f c m = ( gr ( o ) ，w 。= c ( ar ( o ) 对于正交化残量过程，我们有 1 = s p a n r ( o ) + c c m 一1 = s p a n ( r ( o ) + c e m 一1 ( gr ( o ) = j 岛( e ，r ( o ) = ( k 于是我们很容易知道 w m s p a n ( r ( o + w m = ， 我们可以用的一组基 1 ，y 2 ，v k + t ) 来得到w 。的每一个基向量 k + l w k = 仍，* j = l 我们也可以用矩阵的符号来表示上面的关系式 w m = v m + 1 e k = i 厶日。+ 【o ，- ，0 ，7 h ；+ 1 ，。y m + 1 】， ( 2 5 ) 一1 0 其中 w m = w l ，w 2 ，w 。】， = v l ，v 2 ， ， = b ，k 】c ( r e + 1 ) 。“是一个上h e s s e n b e r g 矩阵，= 厶，o 】瓦是把瓦最 后一行删除后所得到的方阵。我们注意到 和 于是( 2 5 ) 可以被写为 = k = c c m g = + 1 瓯= + 【0 ，0 ，“。+ 1 】( 2 6 ) 如果r ( o ) 岳w 。，并且w m 岳，我们就会有 ，7 m + 1 ，。0 因此我们得到 r a n k ( ) = m 如果r ( o ) w ，。对一些指标m 成立，我们有 屹+ 1 = v l = s p a n v a ，毗) ， ( 2 7 ) 其中l 是使得r 【o ) 毗成立的最小的指标。相似地，我们也可以重新表示 ( 2 7 ) w l = v l 巩， 于是 c v l = v l h l 特别地，对于嵌套的子空间序列，我们可以递归地构造一组正交 基。g r a m s c h m i d t 正交化过程可以被用于构造这组基 r o ，w 1 ，w 。一1 ) 。考虑 到 + 1 = + 印n n ) 构造过程如下所示： 驴罢，口；r k u | i ”1 2 万，2 | | | i 和 y m + l = 1 ；端，m = ，z ，三一- 因此，矩阵豆。的元素如下所示 协，。= ( 。，) ，j = 1 ，m + 1 ，m 1 和 ， 。+ 1 。= ( w 。，w 。+ 1 ) = j | ( j 一f 1 ) 埘。l i 0 ( 2 8 ) 等式( 2 8 ) 成立当且仅当w m 1 ，仇，或者等价地，r ( o ) w 。，即是m = l ， 如果我们取子空间1 ，k 的不同的基，我们可以得到不同的算法。如果我们 取l ，m 的一组标准正交基，对于极小残向量方法，我们有 其中 m i n 护= r a i n 胪一e 璐i i 2 d m i n i | r ( 0 lw , m ，。r 2 d m 剐i n r 。一c y m y 2 凡 我们只需要求解 = m i n | | r ( 0 一+ z 群r l | 2 d m 。c m i n 1 1 卢+ 1 e m + 1 一+ 厩蟛r = 畦m c i n 。i i 肌f m + 1 1 一直m y r a m 凡i i ， e p + 1 = 【1 ，0 ，0 】丁r ”+ 1 对于正交化残量过程，由于 鹾r = 卢詹赢e p l r ( ”) = r ( o ) 一c d g 皇= r o ) 一w ，m 铲= r ( o ) 一c y 。y 8 只上 一1 2 一 我们有 r ( ”) =v m ( r ( o ) 一c y r u s o r 、 ( p + 1 e p l l 一+ 1 矗k y o r ) 瑶p + 。e p 一k + ，嘏r 肛p + 1 一h m y o r = 0 因此，对于正交化残量过程我们只需要解e 。鳃丑= 风p + 1 1 ： 嘏r ：= 卢蚝1 e p l 在实际计算中，我们使用a r n o l d i 过程来产生 = s p a n r ( ，c r ( 叭，c ”一1 r ( o ) 的正交基。在这种情况下，上h e s s e n b e r g 矩阵矗- m 的元素由下式给出 琅j = ( e 仇，) ，i = 1 ，m + 1 ，j = 1 ，m 在这种情况下，极小化残量的过程就是广义极小残量法i ( g m r e s ) ，正交化残量 的过程就是f o m 方法。 2 3 广义极小残量法及算法 在本节中我们将详细给出广义极小残量法( g m r e s ) 的算法过程。首先我们 考虑在i c j y i o v 子空间上的a m o l d i 过程， 于是 ( er ( o ) = s p a n ( r ( m ，c r ( m ，c m r ( o ) r ( o ) ：y c x ( o )似1 一卜岛、if ，1 可，qc 1 l 哥 y c l z t o ) 一g 哥o ) 、 2 ；一q 扩) 一喇。) j 因此我们可以如下的表示a r n o l d i 过程 1 计算r ( o ) = 型一c a _ z ( o ) 一q 虿rl i ( o 1 1 2 和f ( o ) = 歹一q 互( o ) 一a - ( o ) ， f 哥o 她 2 计算p 2 = i l ( o 1 1 2 + l i 再o 1 1 2 和 1 = 也1 ，- 1 】丁，其中型l = ( o 伊，- 1 = 一o ) 邝。 3 定义汩+ 1 ) m 上h e s s e n b e r g 矩阵瓯= b ) 1 s 。! 。+ 1 ，1 9 m ，令如= 0 。 4 对于j ：1 ，2 ，m ，计算 5 计算_ w j = c l v j + 岛弓和码= 岛码+ c 2 _ v j 。 6 对于i = 1 ，2 ，j ，计算 7 h , s =( ( 耄) ，( 艺) ) 8 计算马= 马一危巧马和吗= 砀一h , j v j 。 9 结束 1 0 计算砖+ 1 ，= i l 哟i i 。如果h s + 1 j = 0 ，中止。 - 计算哟+ = ( 耄+ 1 ) ，其中马+ ，= 骂，b 扎，和弓+ - = 码，+ t 。 1 2 结束 令矩阵= ( 1 ，) ，我们可以用矩阵的形式来表示a m o l d i 过程 ( 爰兽) t 矾 一1 4 其中 = h l lh 1 2 危2 1h 2 2 0 h a 2 ： 00 oo h i , m 一1 h 2 m 一1 h 3 , m - - 1 h m l 一1 0 h 1 。m h 2 m h 3 m 凡m m m + 1 m 因此，要得到广义极小残量法( g m r e s ) 的表示，我们只需要解出下面的最 小二乘问题： m i ni f 风p 1 1 一厩y 由于丘。是列满秩的，我们可以用q r 分解到矩阵丘。来解出上述最小二乘问 题。由作用在反。上的q r 分解我们可以得到 于是我们有 厩：qf ，r1 、0 r a i nl ip e p + 一亩o y | | = r a i nl i 矿( 卢e ( m + 一可) i l = m i n i l 卢q r e p + 一q t 后r r yj = m t n l i p q t e p + 1 1 一( 孑) ，创， 毛2 残量即为，m + 1 。作用在矩阵豆。的q r 分解可以用g i v e n s 旋转来完成。 一1 5 当m 变得很大的时候，由于内存和数据存储的需求的快速增加，原始的广 义极小残量法( g m r e s ) 变得难以运用到实际问题中。为了克服这个困难，我们 通常采取重开始的方法。给出一个重开始的参数m ，当广义极小残量法进行到 第m 步时，我们可以把第m 步得到的逼近向量x ( m ) 作为下一次循环迭代的初 始向量，即是x c o ) = x ( m ) 。关于k r y l o v 予空间和广义极小残量法( g m r e s ) 的 更多信息可以参见 2 】。 一1 6 第三章分块矩阵预处理策略 本章我们主要考虑对形如s x = y 的精确数线性系统作预处理的方法，其 由 s ： 1 ( 3 1 ) 岛岛 、。 通过对模糊系统嵌入后形成的系统系数矩阵的结构的分析，我们得到了定 理3 1 。通过定理3 1 的结论，我们容易看出这种矩阵结构的特性；并且我们还容 易看出，第一章的一些经典结论实际上是本定理的直接推论。在本章中我们首 先提出了对于形如( 3 1 ) 的分块矩阵的块对角化处理方法，这样就可以把2 n 2 n 的线性系统转化为两个nx 礼的线性系统来处理，这样两个系统就可以并行的 处理从而降低原方程的求解时间。在具体求解1 7 , n 阶的线性系统时，根据矩 阵结构的不同我们采用一些预处理方法如不完全l u 分解，或者是用循环矩阵 逼近的办法来对系统进行预处理从而降低求解时间。 3 1 分块矩阵降阶 在本节中我们主要考虑对于系数矩阵形如( 3 1 ) 的块结构的线性系统的降阶 方法。为此我们给出下述定理。 定理3 1 ：令a = ( ) ，b = ( b i j ) 为扎几的实方阵。给定形如 s = ( 三三) 2 2 块的矩阵，s 必正交相似于块对角阵 ( ；+ b 三一b ) 证明：在这里我们为了叙述方便，只对n 是偶数的情况证明，奇数的情况类 似。 首先s 可以通过初等变换的置换变为 ，7 1 ，1 五，2 冗，。、 t = f 誓引 死，2 一兀，。 一1 7 t = q 丁尸t s p q 其中 p = p 1 忍r “ 只为交换第i + 1 列和n + t 列的初等置换阵。q 丁为置换阵把如下形式的向量 钉= ( n ，砚， u 3 ，地，t k 一1 ， o n 一1 ，副2 ，u 2 ，u 4 ，勘4 ，) t 化为 o = ( 口1 ，铆，u 2 ，u 2 ， 0 3 ，) 3 ，- ，) r ， 即是 q 丁u = 0 又因为对于每个2 2 的小块矩阵，我们有 巧= ( 等笔) = f 丁( 0 + 0 一吻) e 其中 f = ( 妻乏) 为2x2 的f o u r i e r 矩阵。于是我们可以得到 ，a a ，2 r ：户rl a 2 a 2 。 i ! ； i a n ，1a n ，1 2 1 8 一 腻 ， 下mi成 i | 写 乃 默次这把“我阵 矩的 中 2 其 为 _ f 、i_lf_l_i_-， 功 抑 a a ；a 户= 厶。f = ( 手 ； f 至 为对角阵。令 令 矿为置换阵把形如 的向量化为 即是 舻( + 0 、 o b b b ) ，a ，a 。，2 a ：f a 2 ， l = ： a a 啦引 w = ( i n ，叫l n ，伽f ，叫乒，删i 制，础) r 西= ( 加i ”，叫p ，伽 ，训， 乎，伽) r 于是综上所述，我们有等式 m t w = 面 0 。叼一，) = ( + b 三一b e = m r a m = m 丁鼢户r m = m r p q t p t s p q 铲m 从上述等式和推导中我们容易知道矩阵m ，户，p q 都是j 下交阵，于是定理证 毕。口 1 9 一 、， 卜 u o ，一， i l c i | ma r 有 m 就样这 推论3 2 ：矩阵s 非奇异的当且仅当月+ b 和a b 都是非奇异的；并且只要上 述两个矩阵有一个是奇异的，则s 就是奇异的。 推论成立显然。由上述推论可以很好的解释例l ，4 ：虽然系数矩阵a 非奇 异，但绝对值矩阵i a f 奇异，因此s 奇异。 a = 匿封 s = 1 1o1 31 40 1 20 0 o2 2 2 302 1002 4 3 l3 2oo003 3 3 4 4 1 4 2 4 3o o 004 4 0 1 20 0 1 101 31 4 2 1002 40 2 2 2 30 003 3 3 43 13 200 0004 44 14 2 4 30 经过第一步初等置换的变换后我们可以得到 ，正，。乃，。乃3 tl t 2 1t 2 ，2t 2 ，3 12 l 乃，死，。疋，3 t 4 ，t 噩，：t 4 ，a 1 1001 21 301 40 01 11 2001 301 4 o 2 1 2 20 2 30 02 4 2 10 02 2o 2 32 40 3 10 3 20 03 30 3 4 o3 103 2 3 30 3 40 4 104 204 300 4 4 04 104 204 3 “0 2 0 = 、l， 4 4 4 4矸死乃乃 经过第二步变换，就有 a ； a 1 。a 1 f 。a 1 t 、 a 2 ，2a 2 ，3a 2 4 i a 3 ，2a 3 ，3a 3 ，4l a 。，。a 4 ，。a 4 ，4 1 2o 0- 1 2 2 2o o2 2 3 20 03 2 4 20 o4 2 再经过最后一步置换就可以得到如下形式的分块矩阵： s = 1 11 2 2 1 2 2 3 1 3 2 4 1 4 2 oo 0o o0 0o 1 31 40 2 3 2 4o 3 3 3 4o 4 34 4o oo1 1 o0- 2 1 o03 1 oo4 1 1 3o 01 3 2 30 02 3 3 30 0 - 3 3 4 30 04 3 1 40 o 1 4 2 40 0 - 2 4 3 40 0 - 3 4 4 40 04 4 在上述定理的构造性证明中可以看出，使得块对角矩阵( 3 1 ) 正交相似于块 对角矩阵的正交阵在实际计算中非常容易构造，它的元素与s 的元素值无关， 正交阵的构造只与s 的规模n 有关。 由定理3 1 可知，要解n n 规模的模糊线性系统a x = y ，我们不必求解规 模为2 n 2 n 的精确数线性方程组s x = y ，其中s 如( 3 1 ) 所示；只需要分别 求解7 1 , 7 1 , 的方程组( 岛+ 岛) x i = k 和( 研一s 2 ) x 2 = m 即可，而这两个方程 可以并行地求解，这样就大大降低了原模糊线性系统的求解时间。事实上由模 糊线性系统嵌入方法【l 】的定义可知a = 岛一岛，而岛+ 岛为把a 的相应元 素取绝对值所得到的矩阵，记为i a i ，这样为了得到原模糊线性系统的解，我 们只需要并行地求解下述两个方程组 ( 3 2 ) o n oo甜。缸 n o殂0乩o n o o o o o m 以4 3 o o o o 嬲船 2 o o o o o 毖弛舵 3 2 预处理策略 在上节中我们给出了一个把形如( 3 1 ) 的矩阵块对角化的方法，本节中我们 主要讨论对于模糊线性系统( 1 1 ) 的系数矩阵a 的结构来利用预处理的办法来加 速求解方程组( 3 2 ) 。 对于方程组a z = b ，令尸为系数矩阵a 的逼近矩阵，我们需要求解如下方程 组： p 一1 a x ：p 一1 b 来代替求解原方程组 a z = b 这个矩阵p 即是预处理矩阵，它的选择应该遵循以下原则： p 应该很容易的被构造，计算量较小。 p v = 可应该求解容易。 尸- 1 a 的谱分布应该尽量聚集，谱半径尽可能小。 3 2 1a 无特殊结构时的一般情形 当a 本身无特殊结构时，a 的绝对值矩阵j a i 也无特殊结构。这种情况 下，我们采取不完全l u 分解( i n c o m p l e t el ud e c o m p o s i t i o n ) 作为预处理方法。 不完全l u 分解即是找出下三角矩阵l 和上三角矩阵使得它们满足下式 m l ua e 其中矩阵雪是矩阵a 丢掉的部分。我们的目的即是尽可能找出符合下式的三角 阵l 和矿 嘧l il u a 即使a 是一个一般意义下的稀疏矩阵，三角阵l 和u 也有可能是稠密的。我们 在进行分解时可以加一些结构的限制在l u 上使其保持结构。对于a 是稠密 矩阵的情况，在进行分解之前我们可以对a 的元素进行调整来使其计算效率增 加。 一个简单的想法就是使工和u 的非零元的位置与a 的非零元的位置保持一 致，保持a 和l + u 的稀疏模式相同。这就是所谓的没有填充的i l u ( o ) 方法。 一2 2 定义s ( a ) 为a 的非零的坐标集。例如，所有( i ，j ) s ( a ) 。 算法3 3 ：m u ( 0 ) 预处理方法 为了找出a 的不完全分解因子l 和u ，定义新矩阵b ，令初始b = a 玎。 f o r i = 2 一几 f o r k = 1 ，一，i 一1 和( i ，k ) s ( a ) 计算b 琅= b , f o r j = k + 1 ，n 和( i ，j ) s ( a ) = b i j b 娩峙 e n d j e n d k e n d i 我们同时给出更加一般的不完全l u 分解的算法，令p 为指定的非零元数 量的固定值，7 为初始计算精度( 舍弃值小的元素) 。 算法3 4 ：i l u ( p ，7 - ) 预处理方法 为了找出a 的不完全分解因子l 和u ，定义新矩阵b ，令初始吆= a i j 。 计算月的所有行的2 范数，并把结果保存在向量 中。 f o r i = l ，扎 取出a 的第i 行，并把它储存在向量w = s ( i ，：) 中。 f o r k = 1 ，i 一1 和w 女0 计算w k = w k k 初始：如果1 w k l v i 7 _ ，对这个k 令w = 0 。 这样做下去更新k 行；如果w k 0 ，令w = w w k b ( k ，：) 对所有的非零元。 e n dk u 初始：如果i 叼l v , j r ，对所有j 令w j = 0 。 在每个l 的范围j = 1 ，( i 一1 ) 和u 的范围j = i ，n 中，更新b 玎= 哟直 到p 个加f 的最大的非零元数。 e n d i 如果一些对角元过于接近于零，这就有必要在算法中引入部分选主元的技 巧a 具体参见 3 7 】。 3 2 24 为t o e p l i t z 矩阵 在本节丁f 始，我们先介绍些矩阵的定义。 2 3 定义3 5 ：一个礼n 的矩阵厶如果被称为t o e p l i t z 矩阵当它的元素如下式 ，口。n 。一。 l n 1回 n 一1 ， 如：l ： 。， 印 i 1 a n 一2 ： n 。一，n 。一。 也就是说，a 的元素在沿对角线方向是相同的。 定义3 6 ：一个nxt , 的矩阵g 如果被称为是循环 c 0 c 一- c 2 一。 f c 1c d c 一1 1 。| ： c 1c 0 l c a 一2 ： i lc a 一1 岛一2 c 1 其中c 一= 岛一b 1 sk 7 1 一1 。 循环矩阵可以被傅立叶矩阵r 所对角化 其中矩阵r 的元素由下式给出 g = 只a 。r 斟 对 1 吼矿去班加，= 佤。鲰七n 一1 ( 3 3 ) a 。是包含了所有c k 的特征值的对角阵，具体细节和例子可参见【1 2 】。我们注 意到a 。可以通过快速傅立时交换( f f d 计算得到，计算复杂度为d l o gt , ) ，具 体算法和细节可以参见 1 3 。事实上，对角阵a 。对角线上的元素儿由下式给 出 n - 1 丸= c j e 2 7 r i j 枷，k = 0 ，凡一1 ( 3 4 ) 一旦a n 得到，对于任意向量y ，矩阵向量积g 和g 1 y 可以以复杂性 o ( n l o g n ) 用快速傅立叶变换( f f t ) 计算得到。 2 4 法。 在本文中，我们主要是使用以下两种用循环矩阵来作为预处理矩阵的方 3 2 2 1t c h a n 的最优预条件方法 当线性方程组的系数矩阵是t o e p l i t z 矩阵时，tc h a n 在1 9 8 8 年提出了用循 环矩阵逼近的最优预处理方法 4 】。预处理矩阵e 可以被看作是矩阵a 的逼 近，并且它是容易求逆阵的。预处理矩阵可以被用于下列迭代法以求得线性系 统a x = b 的解： c o + 1 = ( c a ) x i + b 这个迭代法的收敛性或者收敛速度主要依赖于矩阵c _ 1 一a ) 的谱：c 。( c a ) 的谱半径越小，收敛速度越快。这点可以很容易扶下式中体现出来，如果 于是有 b 三c a p ( c - 1 b ) - i i b i i = i i ( i + a - i b ) - 1 a - 1 b i i 当耥 给定矩阵范数使得 l la - 1 bi l 1 由于上界是9a - 1 b i 的严格递增的函数，这样很自然的想法就是选择合适的矩 阵e 使得a - 1 b 极小化。因为 a - 1 b i i l i a i i i i b i i ， 我们可以遵循下式来构造所求矩阵g ： c 罂墨。i l c a 在f r o b e n i u s 范数下，t c h a r t 给出了下面结论。 一2 5 定理3 7 ：f 4 】令 和 a = c= 矩阵c 的元素由下式给出 c i ：i a - ( n - o + ：( n - 一i ) a i ，i ：一( 凡一1 ) ，0 ，一，n - 1 ) n 并且c 极小化| | c a 忙，最小