（计算数学专业论文）大型稀疏矩阵线性方程组的并行算法.pdf

西北工业大学顿 论文 摘要 许多大型科学与工程计算问题最后常需要解一个或一些系数矩阵为大型稀 疏矩阵的线性方程组.木文研究了 针对此类线性方程组 ax =b 的并行迭代解法.主要讨论了如下几个问 题: ( 1 ) 对块三对角线性方程组的系数矩阵a做适当的分裂并利用 b s o r方法 的迭代格式构造出一种适于 mi md分布式存储并行机的并行迭代算法.从理论 上证明了此算法与b s o r方法有同样的收敛速度， 而且与b 3 方法有相同的并行 性. 在h p r x 2 6 0 0 集群上进行数值计算， 验证了 此算法的计算结果与理论相一致. ( 2 ) 在第一种算法的基础上导出 一种更为灵活的求解块三对角线性方程组 的适合于 m i m d分布式存储并行机的二级并行迭代算法，理论证明了在系数矩 阵为h e r m i t e 正定矩阵和m- 矩阵时算法的收敛性. 在h p r x 2 6 0 0 集群上做了数值 计 算并与多分裂方法进行比 较， 结果表明此算法有良 好的并行性. 此外， 还应用 此迭代格式于系数矩阵为块循环三对角矩阵的线性方程组， 也得到良好的收敛性 理论及计算结果. ( 3 )扩展( 2 ) 的方法到系数矩阵为块五对角矩阵的线性方程组.讨论了 此算 法的收敛性并给出了系数矩阵为 m一 矩阵时的收敛速度的比较定理，初步讨论了 子块分裂对收敛速度的影响. 最后在h p r x 2 6 0 0 集群上进行了数值计算， 结果验 证了算法的有效性. 关键词 并行算法，线性方程组， h e r m i te 正定矩阵， m- 矩阵，h p r x 2 6 0 0 集群 西北t业大学硕 t : 论文 ab s t r a c t l i n e a r e q u a t i o n s w i t h l a r g e s p a r s e c o e f f i c i e n t m a t r i c e s a r i s e i n m a n y p r a c t i c a l s c i e n t i f i c a n d e n g in e e r in g p r o b l e m s . t h e w o r k p r e s e n t e d i n t h i s p a p e r f o c u s e s o n p a r a l l e l i t e r a t i v e a l g o r i t h m s f o r s o l v i n g s u c h l a r g e l i n e a r s y s t e m s . h e r e , i t i s t o b e d i s c u s s e d a s f o l l o ws : ( 1 ) wi t h s u i t a b l e d e c o m p o s i t i o n o f b l o c k - t r i d i a g o n a l c o e f f i c i e n t m a t r i x a n d u s i n g t h e f o r m o f t h e i t e r a t i v e f o r m u l a o f t h e b s o r m e t h o d , a p a r a l l e l a l g o r i t h m o n d i s t r i b u t e d - m e m o r y m u l t i - c o m p u t e r i s e s t a b l i s h e d i n c h a p t e r t w o . a c c o r d i n g t o t h e o r e t i c a l a n a l y s i s , i t h a s t h e s a m e c o n v e r g e n c e a s b s o r me t h o d , a n d t h e s a m e p a r a l l e l i s m a s b j m e t h o d . m o r e o v e r , f o u r e x a m p l e s h a v e b e e n i m p l e m e n t e d o n h p r x 2 6 0 0 c l u s t e r , a n d t h e wi t h i t s t h e o r e t i c s . v e r i f y t h a t t h e n u m e r i c a l r e s u l t s o f t h i s a l g o r i t h m c o i n c i d e ( 2 ) t h e m o r e fl e x i b l e t w o - s t a g e i t e r a t i v e p a r a l l e l a l g o r i t h m i n c h a p t e r t h r e e d e r i v e s f r o m t h e f i r s t o n e . c o n v e r g e n c e i s p r o v e d w h e n t h e c o e ff i c i e n t m a t r i x i s h e r m i t e p o s i t i v e d e fi n i t e m a t r i x o r m- m a t r i x . u s i n g h p r x 2 6 0 0 c l u s t e r , t h e e x p e r i m e n t r e s u l t s s h o w t h a t t h e a l g o r i t h m i s q u i t e c o m p e t i t i v e w i t h m u l t i - s p l i t t i n g m e t h o d . f u r t h e r m o r e , w e e m p l o y t h e i t e r a t i v e s c h e m e i n c h a p t e r t h r e e t o c i r c u l a n t b l o c k - t r id i a g o n a l s y s t e m , a n d g e t t h e s i m i l a r r e s u l t s ( 3 ) t h e m e t h o d i n c h a p t e r t h r e e e x t e n d e d t o b l o c k - f i v e - d i a g o n a l l i n e a r s y s t e m s , w e g e t s o m e c o n v e r g e n c e t h e o r e m s a n d a c o m p a r i s o n t h e o r e m , w h i c h d i s c u s s e s h o w t h e d e c o m p o s i t i o n o f s u b - b l o c k s i n fl u e n c e s t h e w h o l e v e l o c i t y . i n t h e e n d , t h e r e s u l t s o f n u m e r i c a l e x p e r i m e n t s i m p l e m e n t e d o n h p r x 2 6 0 0 c lu s t e r i n d i c a t e t h a t t h e a l g o r it h m i s e ff e c t i v e . k e y w o r d s : p a r a l l e l a l g o r i t h m , l i n e a r s y s t e m s , h e r m i t e p o s i t i v e d e f i n i t e m a t r i x , m- ma t r i x , h p r x 2 6 0 0 c l u s t e r 西北工业人学硕 1 : 论文 第一章 预备知识 1 . 1引 言 数值线性代数是计算数学的重要组成部分， 它是研究代数问题的数值计算方 法及有关理论的一门学科， 既涉及数学理论方面的研究， 又涉及工程设计方面的 研究. 其理论与方法在微分方程数值解、 有限元及其他数学技术中都有) b 泛的应 用，其地位日趋显赫 虽然线性代数方程组的求解方法和数值计算软件包均很成熟，但随着并行 计算机的发展， 及现今科学研究与大型工程项目中各种复杂的计算课题对计算速 度的更高要求， 使得数值计算方法和相应的数学软件包都产生了 变化， 从而相应 地线性方程组的有效并行计算的求解也引起了人们的普遍关注. 大量的研究工作 在于开发传统算法的并行性， 使之适应并行计算机计算: 如g a u s s 消去 法、 共骊 梯度法、 j a c o b i 方法等; 另一方面则致力于研制新的有效的并行解法: 如三对角 方程组的分裂法、循环约化法、多分裂并行迭代法、异步迭代并行算法等川. 本文所要研究的就是针对系数矩阵为大型稀疏矩阵的线性方程组的并行迭 代解法. 关于此种类型的线性方程组的并行解法有: 并行j a c o b i 型方法、 红黑或 多色排序实现s o r并行处理、 a d i 方法( 交替方向隐式方法) 、 多分裂等算法. 文 献 2 给出 了 一种直接法求 解块三对角线 性方程 组的并行 算法: t 1 中的二 级多 分 裂 求 解块三对角线性方程组的并行性较高， 但收 敛性分析比 较困 难; 3 给出了 一种并行迭代解法， 但要达到各处理 机负 载平衡要求 条件较高 本文在 3 的基 础上引入二级迭代的思想从而得到本文的并行算法. 本篇论文中首先针对系数矩阵为块三对角线性方程组给出一种简单易行的 并 行迭代算法， 从理论上证明了 此算法与b s o r有同 样的收敛速度， 而且与b j 方法有相同的并行性. 在h p r x 2 6 0 0 集群上进行数值试验， 结果也证明了 此算法 的有效性和可行性， 在此基础上引入二级迭代， 对系数矩阵为块三对角矩阵、 块 循环三对角矩阵、 块五对角矩阵的线性方程组给出一种并行二级迭代算法， 并证 明了 在系数矩阵为h e r m i t e 正定 矩阵和m - 矩阵时 算法的收敛性. 在h p r x 2 6 0 0 集群上进行数值试验， 结果表明此算法有良 好的并行性. 最后还给出一个比较定 西北工业人学硕 1 : 论文 第一章 预备知识 1 . 1引 言 数值线性代数是计算数学的重要组成部分， 它是研究代数问题的数值计算方 法及有关理论的一门学科， 既涉及数学理论方面的研究， 又涉及工程设计方面的 研究. 其理论与方法在微分方程数值解、 有限元及其他数学技术中都有) b 泛的应 用，其地位日趋显赫 虽然线性代数方程组的求解方法和数值计算软件包均很成熟，但随着并行 计算机的发展， 及现今科学研究与大型工程项目中各种复杂的计算课题对计算速 度的更高要求， 使得数值计算方法和相应的数学软件包都产生了 变化， 从而相应 地线性方程组的有效并行计算的求解也引起了人们的普遍关注. 大量的研究工作 在于开发传统算法的并行性， 使之适应并行计算机计算: 如g a u s s 消去 法、 共骊 梯度法、 j a c o b i 方法等; 另一方面则致力于研制新的有效的并行解法: 如三对角 方程组的分裂法、循环约化法、多分裂并行迭代法、异步迭代并行算法等川. 本文所要研究的就是针对系数矩阵为大型稀疏矩阵的线性方程组的并行迭 代解法. 关于此种类型的线性方程组的并行解法有: 并行j a c o b i 型方法、 红黑或 多色排序实现s o r并行处理、 a d i 方法( 交替方向隐式方法) 、 多分裂等算法. 文 献 2 给出 了 一种直接法求 解块三对角线 性方程 组的并行 算法: t 1 中的二 级多 分 裂 求 解块三对角线性方程组的并行性较高， 但收 敛性分析比 较困 难; 3 给出了 一种并行迭代解法， 但要达到各处理 机负 载平衡要求 条件较高 本文在 3 的基 础上引入二级迭代的思想从而得到本文的并行算法. 本篇论文中首先针对系数矩阵为块三对角线性方程组给出一种简单易行的 并 行迭代算法， 从理论上证明了 此算法与b s o r有同 样的收敛速度， 而且与b j 方法有相同的并行性. 在h p r x 2 6 0 0 集群上进行数值试验， 结果也证明了 此算法 的有效性和可行性， 在此基础上引入二级迭代， 对系数矩阵为块三对角矩阵、 块 循环三对角矩阵、 块五对角矩阵的线性方程组给出一种并行二级迭代算法， 并证 明了 在系数矩阵为h e r m i t e 正定 矩阵和m - 矩阵时 算法的收敛性. 在h p r x 2 6 0 0 集群上进行数值试验， 结果表明此算法有良 好的并行性. 最后还给出一个比较定 西北t业人学倾 卜 论文 理，初步分析了子块的分裂对收敛速度的影响. l 2基本概念及理论准备 1符号说明 p处理机台数; t时间( 单位:秒) ; l迭代次数; 5相对加速比 ( 一 台处理机用此算法的时间 p 台处理机用此算法的时间 e相对并行效率 3绝对加速比 ( p 本文中一台处理机所用的最少时间 p 台处理机用此算法的时间 一5一 亘绝对并行效率 i 5 ( ila x 一 b lh ) 2 h e r m i t e 矩阵及有关结论 定义1 . 1 设a为n 阶h e r m i t e 矩阵，若对任意n 维非零向量x e c ，都有 x a x _ 0 成立， 都有 成立， 则称a为h e r m i t e 半正定( 非负定) 矩阵: 又若对任意n 维非零向量x e x 注z 0 则称a为h e r m it e 正定矩阵. 定义1 . 2 ， 设a , b 都是。 阶h e r m i t e 矩阵， 若a - b 为正定 矩阵 ( 或非负 定 矩 则称a大于b，记为a b ( 或称a不小于b，记为a s - b) . 定义1 . 3 p - it则分裂:设矩阵a是。 阶方阵，若矩阵m和n满足: m一 n且m + n为h e r m i t e 正 定矩阵， 则称a= m一 n为a的p - 正则分裂， 定义1 . 4 强p - 正则分裂:设矩阵a是。 阶方阵，若矩阵m和n满足: 、卜公二 阵月 西北t业人学l o ! 卜 论文 理，初步分析了子块的分裂对收敛速度的影响. 肛.2基本概念及理论准备 1符号说明 p处理机台数; t时间( 单位:秒) ; l迭代次数; 5相对加速比 ( 一 台处理机用此算法的时间 p 台处理机用此算法的时间 与p e相对并行效率 3绝对加速比 ( 本文中一台处理机所用的最少时间 p 台处理机用此算法的时h 1 一5一 豆绝对并行效率 误 差( iia x 一 b ih ) 2 h e r m i t e 矩阵及有关结论 定义1 . 1 设a为n 阶h e r m i te 矩阵，若对任意。 维非零向量x e c ，都有 x a x _ 0 成立， 都有 成立， 则称a为h e r m i te 半正定( 非负定) 矩阵: 又若对任意n 维非零向量x e c ， x a x 0 则称a为h e r m i t e 正定矩阵， 定义1 . 2 设a , b都是n 阶h e r m i t e 矩阵， 若a - b为正定 矩阵 或非负定矩 阵 ) ， 则 称a 大 于b， 记 为a b( 或 称a 不小 于b， 记 为a - b) . 定义1 .3 p - t则分裂:设矩阵a是。 阶方阵， 若矩阵m和n满足: a二 m一 n且m + n为h e r m it e 正定矩阵， 则称a= m一 n为a的p 一 正则 分裂. 定义1 . 4 ，强p - it则分裂:设矩阵a是。 阶方阵，若矩阵m和n满足: 西北工业大学硕 】 : 论文 a二 m一 n且n r o，则称a= m一 n为a的强p - 正则分裂， 定义1 . 5椭圆范数:设a是任意一个n 阶h e r m i t 正定矩阵，列向量x e c 则 函 数 ilx tl， 一 ( x a x ) ， 是 一 种 向 量 范 数 ， 称 为 加 权 范 数 或 椭 圆 范 数 ， 引理1 俨 设a , b都是n 阶h e rm i t e 矩阵，且ay b，则有b - - a - 引理1 . 2 0 设a , b都是。 阶h e r m i t e 矩阵，且a-b, p为n x m矩阵，则 p a p - p b p. 引理1 .3 ，设t e c ，则p ( t ) - o. 引理1 . 4 a 设矩阵a为h e r m i t e 正定矩阵，分裂a= m一 n为p - 正则分裂， 则 对 v s 1,s e z * ， 存 在 唯 一 的 分 裂 a = p 一 q ， 使 得 p -q = ( m -n ) 且 此 分 裂 为 p 一 正则分裂. 引理1 . 5 6 ，设矩阵a为h e r m i t e 正定矩阵， 分裂a= m一 n为强p 一 正则分裂， 则 对 v s - i, s c- z , 存 在 唯 一 的 分 裂 a = p - q ， 使 得 p - q 一 ( m - n ) 且 此 分 裂 为 强p 一 正则分裂 引理1 . 6 若a为实对称正定矩阵，则a= m一 n是p 一 正则分裂充要条件是 iim - n ii _ o且a ”一 o ( 3 ) 第一类弱非负分裂:当,l 1 - _ 。且m- n _ o. ( 1 ) 第二类弱非负分裂:当m- o且n m- ? o . 引 理1 . 8 ( p e n -o n - f r o b e n i u s 定理) 若a为n 阶非负不可约方阵，则 ( 1 ) a有一正的 特征值等于 其谱半 径p ( a ) ; ( 2 )属 于 特征 值p ( a ) 有 一 正 特 征向 量; ( 3 ) a的 任意元素 ( 一个或多 个) 增加时，p ( a ) 不减少; 仔 ) p “) 为a的简单特征值 引理1 .9 设a e r -，a= m一 n为矩阵a的弱正规分裂 ( 第一类弱非负 分 裂) 或正规分 裂， 则p ( m- n ) _ o, a = m- n为矩阵a的第二 类弱非负分 裂， 则p ( m- n ) o, a 二 私- n i 二 从一 从为 不同 类 弱非负 分 裂， 且拼， 七 m z ， 时 ， 不 等 式p ( 研 n ， ) p ( m 2- 从) - 1 , ， 二 z * ， 存 在 唯 一 的 分 裂 a = p - q ， 使 得 p - q 一 ( m 一 ，n ) ， 且 此 分 裂 西北工业人学硕十论文 为第二类弱非负分裂. 4 m- 矩阵 m - 矩阵( 全称非奇异 m 一 矩阵 ) 经常出现在诸如偏 微分方程的有限差分和有限 元素法、 经济学的投入产出 法、 运筹学中的线性余问题等不同的科技领域中. 这 里介绍一些概念和有关结论. 定 义1 .9 如 果 矩 阵 a 一 ( 马 从 。 的 主 对 角 线 外 的 元 素 非 正 ， 且a - ， 为 非 负 矩 阵 ， 即 a , _ o 则称a为m- 矩阵. 弓 i 理1 . 1 4 设a为m - 矩阵， 当a的 任意元素 ( 一个或多 个) 增大， 但保持主 对角线外的元素仍然为非正 值时， 则所得的矩阵n也是m - 矩阵， 且有n - _ 2 , m e z ) ， 则系数矩阵a可分裂为 a= d一 l一 u ( 2 .2 ) 其中d = d i a g ( aa 2 , - - - , a) ( 2 . 3 ) 西北工业大学硕士论文 、，一一!111夕 - c o 口口 - b . 0 - 氏. , 一 叹。 _ .o o - cm o - b _ ( 2 . 4 ) 0 口 0 00二 口o - c y - n m , z - c_ 1 - c o 2了一.十一一一、 - 、!一1.weeeesesl是，j - b ? o o一 凡 口d - c m 0 气o 00 嵘0 一 - c r - u m : o - $ 1 r : ，二 十 . o o一 找 r了111夕weeseseseslee、 -一 一u 利用b s o r方法的迭代格式， 将l , u分别代替l , u 乙u分别表示矩阵a的严格 块下三角和上三角矩阵) ，则有迭代格式 x (k . l， 二 ( i 一 。 d - l ) 一 ， ( 1 一 0) ) i + 0) d - 功 x (k ) + co ( i 一 c o d - l ) 一 ， d - b ( 2 .6 ) 显 然， ( 2 .6 ) 成 立的 必 要条 件 是a 为 非 奇 异 方 阵 2 . 2迭代实现过程 1 存贮方法 在 第 台 处 理 机 月 中 存 入 人 卜 1).+j 凡 - 1)m + ， q - 1)m + j , 对 践 ， 十 ， ， 气 一 ，).rv ; ( 1 一 1, 2 . . , m)， 其中c= 0,凡= 0. 循环过程 ( 1 ) 月 进 行 一 次 并 行 通 讯 得 到 x (k )x (, - 1)m 7 在君 中 计算: 西北工业大学硕士论文 、，一一!111夕 - c o 口口 - b . 0 - 氏. , 一 叹。 _ .o o - cm o - b _ ( 2 . 4 ) 0 口 0 00二 口o - c y - n m , z - c_ 1 - c o 2了一.十一一一、 - 、!一1.weeeesesl是，j - b ? o o一 凡 口d - c m 0 气o 00 嵘0 一 - c r - u m : o - $ 1 r : ，二 十 . o o一 找 r了111夕weeseseseslee、 -一 一u 利用b s o r方法的迭代格式， 将l , u分别代替l , u 乙u分别表示矩阵a的严格 块下三角和上三角矩阵) ，则有迭代格式 x (k . l， 二 ( i 一 。 d - l ) 一 ， ( 1 一 0) ) i + 0) d - 功 x (k ) + co ( i 一 c o d - l ) 一 ， d - b ( 2 .6 ) 显 然， ( 2 .6 ) 成 立的 必 要条 件 是a 为 非 奇 异 方 阵 2 . 2迭代实现过程 1 存贮方法 在 第 台 处 理 机 月 中 存 入 人 卜 1).+j 凡 - 1)m + ， q - 1)m + j , 对 践 ， 十 ， ， 气 一 ，).rv ; ( 1 一 1, 2 . . , m)， 其中c= 0,凡= 0. 循环过程 ( 1 ) 月 进 行 一 次 并 行 通 讯 得 到 x (k )x (, - 1)m 7 在君 中 计算: 两北t业大学硕上 论文 x (k i fjx (.- p ., 、 二 ( 1 一 。 ) (k j )。 十 ， + 。 式 i) x (,- ijn. ( + w a ,- im t l( 一 几 一，。 ，衬 忿 、。 一 斌 - 1)m .1邓， ， 十 气 7-11-h ) 1 = 2 t o m一 1 ， ， 一 ( 1 一 动 川 岛 。十 “志 、 ， ， ( 一 几 一 。 ,* ) 才+ 1jiim + j - i 一 b ( 一，、 ， ， (k j)m . , x (r-elm . , 十。 + b (r- n . + j ) r戒仰d 0尹羊n 日xe 即 在 每台 处 理 机中， 对前m 一 1 行 块 进行b s o r 迭 代 一 次. ( 注: c= 0 , 凡= 0 ) ( 2 ) p ; 进 行 一 次 并 行 通 讯 得 到x llm , j ， 在月 中 计 算 x 续 ， = ( 一 ” ,) x ;m j + w a m ( - c m x m .i， 一 b ,m x ,(m ;i) + b ,. ) ” ， 在 p ,. 中 判 叫尺 以 缸 ， 一 月 忿 ， ，卜 : ( 。 为 容 差 ， l 二 1 ,2 , .m ) 是 否 都 成 立.若所有处理机都满足此不等式，停机.否则，返回 ( 1 )继续循环，直到满 足所有不等式为止. 由上可知，该算法每迭代一次需要两次并行通讯，因而具有良 好的并行性和 可扩放性. 注 若n 不 能 被p 整除， 则 一 些 处 理 机按 顺 序 存【 o f 川+ 1 个 行 块， 另一 些 存 【 。 / 川个 行块， 同 时 将b ; , 对 o f 中 相 应的 向 量 存入 对 应的 处 理 机中 . 要尽 量 使 每台 处理机的负载大体均衡，以减少等待时间 2 .3收敛性分析 定常迭代法收敛的充要条件是迭代矩阵的谱半径小于1 ，并且谱半径越小收 敛速度越快.这里我们给出此算法的收敛性理论分析. 定 理2 . 1设 ( 2 .6 ) 迭 代 矩 阵兀= ( i 一 。 d - 马一 ， ( ( 1 一 w ) i + w d - u ) ， 则 对 所 有 的 t u ， 又 p ( t ) jw - 1 1 , 且 当 。 e r 时 ， (2 . 6 ) 收 敛 的 必 要 条 件 是0 co jw - 1 1 , 且 当 。 e r 时 ， (2 . 6 ) 收 敛 的 必 要 条 件 是0 co 2 . 证明 因为 d e t 兀= d e t ( 1 - co d - l ) - d e t ( ( 1 - cj ) l + w d - 喻) = d e t ( ( 1 一 m ) 1 + ro d - u ) 艺 d , = ( 1 一 心 ) ， ( d e t ( ( 1 一 o) d l ) 一 ， ) = 1 ) p ( t ) ? id e t t iv y = i。 一 i 西北工业人学硕_ t : 论文 若co - 1 卜 p ( 兀 ) 1 有0 co 2 证 毕 定理2 .2 若a是块三对角实对称正定矩阵，则当。 c) 2 时， ( 2 句收 敛 证明 设a 是兀的 任意 一 个 特 征 值，x 是其 相 应的 特征向 量， 则兀 x = .1 x . 即( ( i 一 co 丫+ co d - 啄 ) x = a ( ， 一 rw d - l ) x 因 为a 二 d 一 2 一 云 且a t = a , 所以l1 二 u 以 一 f 同s o r 方法的证明，最后可得p ( t ,) 1 ， 引理2 . 1 对于块三对角矩阵a d,2 、u分别如 ( 2 . 3 ) 、( 2 . 4 ) 、 证 毕 则 d e t a 一 d e t ( d 一 。 l 一 兰 扔， 其 中 。 # 0 ( 2 . 5 ) . 证明 ( 1 ) 当p 能整除n 时，设n = m p q = d ia g ( a i , a l l ,， 一 。 . i , a 一i ,a i ，一 a ” 一 1 ， 一 a ”一” 一 r +3 ,。 一， 二 i ,. ，。 一 一 ，l ) q - 1 = d i a g ( a - i , “ 一 ， i , ， a - m i ， a - c m - n l , c r m i ， 二 ， a - ,- x . x i ) q a q - = q ( d 一 l 一 u ) q - ， 二 d一 a l 一 a - u d e t( q a q - ) = d e t( d 一 “ l 一 a - u ) ， d e t( a ) = d e t( d 一 。 l 一 1 u ) . 当p 不能 整除。 时， 构造q的 方 式 类似 ( 1 ) . 、.产 ， 孚为以以| 宇因所所 证 毕 定 理2 .3 设 ( 2 .6 ) 迭 代 矩阵不 。 = ( i 一 r) d - 忆 ) 一 ( ( 1 一 。 ) i + w d - 呀) 的 特征 值为 a ， d - ( l + 打 ) 的 特征 值为 k ， 则a 与p 的 关 系 必 有a + 。 一 1 一 0) ,u , 证明 因为d e t 林 i 一 “一 。 d - 忆 ) 一 ， ( ( 1 - 0 ) ”+ c j d - 喻) 两北1 _ 业大学硕 卜 论文 = d e t ( ( i 一 。 d - l ) 一 ， ) d e t a ( ， 一 。 d - l ) 一 ( ( 1 一 。 ) i + r) d - u ) = d e t d - d e t ( a + m 一 1 ) d 一 a oo l 一 x 二 0( d e t ( ( ， 一 ,)d-l) 一 ) = 1 ) 又因为 d e t ( a + 一 1 ) d一 a co l 一 。 云 一 (cj y /i ) a + 0)一 1 。 u e - 下 万 万 一刀一 仪 习 几i -v a 一 去 云 ， 一 0 由引理 2 . 1 得: d e t( a + a) - 1 d 一 if a 、 一 兴。 ) 一 d e t( a + 0 - 1 dr 一 : 一 。 ) = 。 c o - va习凡to v凡 。 。 。 、 .元 十 0)一 1口 n.。 交 r n以，一一 了 犷- = 产，g p 儿 十 。一 t = w p b , . 刃 习 儿 证 毕ii 由 于l + u 二 l + u， 所以d - ( l + 1 1 ) 二 d - ( l + u ) ， 从 而d - ( l 十 u ) 的 特 征 值与d - ( l 十 u ) 的 特征值相同. 由 此可 知， 此算 法与串 行的b s o r 有 相同 的 收 敛性，且其最佳因子的 选取也与b s o r完全相同. 还可以 把此算法推广到b a o r 方法. 同样利用b a o r 方法的 迭代格式， 将厄、 打分别代替l、u，可得到新的迭代算法.采取上面的存贮方式及运算步骤， 也同样可以证明与b a o r方法有相同的收敛速度，且最佳松弛因子和加速因子 的选取方法也是相同的 2 . 4数值算例 对于形如( 2 . 1 ) 式中的系数矩阵 为实对称正定矩阵且m一 矩阵， 其中 1一.lesesjz 典 尽人二 c_ , a- , b n _ , c a 例协阵| 肚 两北1 _ 业大学硕 卜 论文 = d e t ( ( i 一 。 d - l ) 一 ， ) d e t a ( ， 一 。 d - l ) 一 ( ( 1 一 。 ) i + r) d - u ) = d e t d - d e t ( a + m 一 1 ) d 一 a oo l 一 x 二 0( d e t ( ( ， 一 ,)d-l) 一 ) = 1 ) 又因为 d e t ( a + 一 1 ) d一 a co l 一 。 云 一 (cj y /i ) a + 0)一 1 。 u e - 下 万 万 一刀一 仪 习 几i -v a 一 去 云 ， 一 0 由引理 2 . 1 得: d e t( a + a) - 1 d 一 if a 、 一 兴。 ) 一 d e t( a + 0 - 1 dr 一 : 一 。 ) = 。 c o - va习凡to v凡 。 。 。 、 .元 十 0)一 1口 n.。 交 r n以，一一 了 犷- = 产，g p 儿 十 。一 t = w p b , . 刃 习 儿 证 毕ii 由 于l + u 二 l + u， 所以d - ( l + 1 1 ) 二 d - ( l + u ) ， 从 而d - ( l 十 u ) 的 特 征 值与d - ( l 十 u ) 的 特征值相同. 由 此可 知， 此算 法与串 行的b s o r 有 相同 的 收 敛性，且其最佳因子的 选取也与b s o r完全相同. 还可以 把此算法推广到b a o r 方法. 同样利用b a o r 方法的 迭代格式， 将厄、 打分别代替l、u，可得到新的迭代算法.采取上面的存贮方式及运算步骤， 也同样可以证明与b a o r方法有相同的收敛速度，且最佳松弛因子和加速因子 的选取方法也是相同的 2 . 4数值算例 对于形如( 2 . 1 ) 式中的系数矩阵 为实对称正定矩阵且m一 矩阵， 其中 1一.lesesjz 典 尽人二 c_ , a- , b n _ , c a 例协阵| 肚 西北丁业大学硕士论交 取初 始向 量x ,0 ) - 、川川川川j以 b,“c;-一 苦十llleseseeesjj 刁4 司4 4- zrleses.1.，1.t、 l a ( 0。一0 又 、 ， 在。 5 0 , n = 1 0 0 0 , 。 二 1 .8 8 ( 最 优 松 弛 因 子 ) ， 终 止 条 件 为 。 = 1 x 1 0 - 1 ” 时的计算结果如下表 l : 例 2对于形如例 1 的m一 矩阵a，取 一- n 、十了r n曰00 2一、 一一 x 在 . 、!了 ，.人，.1，. 2一、 一 互 一奋/ 拼 2 - 内j 一 2一、 - c 一- 双 、一/ 1 5 . 1 - 3 . 5 - 6 . 9 - 2 . 7 2 0 . 1 - 4 . 8 一1 5 . 7 - 5 . 3 2 5 . 1 /rlesleeesesesl、 l一 a 8 0 0 0 0 , c o = 1 .8 8( 最优松弛因子) 及终止条件为 二 1 x 1 0 - 10 时， 利用本章算法计 算结果