（计算数学专业论文）toeplitz系统求解方法的研究.pdf

摘要 摘要 科学与工程的很多领域如常微分方程和偏微分方程求解、信号处理、数字图 像处理、排队网络、积分方程求解等都需要求解t o e p l i t z 线性代数系统大规模 t o e p l i t z 线性代数系统求解方法的研究具有重要的理论意义和实际应用价值本文 主要对基于符号代数系统( 如m a p l e 、m a t l a b 等) 的五对角矩阵求逆算法和基于离散 余弦变换离散正弦变换的求解t o e p l i t z 系统的新分裂方法进行了系统的研究具 体包括以下四个方面的内容： 1 介绍t o e p l i t z 矩阵的一些背景知识，然后介绍t o e p l i t z 系统求解方法的发展 历史以及最新进展 2 提出了基于符号代数系统( 如m a p l e 、m a t l a b 等) 的一般五对角矩阵求逆算 法，并将其应用到五对角t o e p l i t z 矩阵的求逆并给出了数值例子 3 介绍了研究具有特殊结构矩阵的重要概念位移秩( d i s p l a c e m e n tr a n k ) 进一 步介绍最近提出的利用位移秩概念求解t o e p l i t z 系统的位移秩方法 4 基于位移秩概念以及离散余弦变换与离散正弦变换，k a i l a t h 和o l s h e v s k y s i a mj m a t r i xa n a l a p p l ，2 0 0 5 给出了t o e p l i t z 矩阵的两种新的分裂基于上 述分裂，提出了求解t o e p l i t z 系统的新分裂方法并讨论了新分裂方法的收敛性进 一步研究了最佳参数的选取以及s o r 加速等迭代加速技术并给出了数值例子 关键词：t o e p l i t z 系统，符号代数系统，五对角矩阵，位移秩，离散余弦变换离散正 弦变换，分裂，迭代法 a b s t r a c t a b s t r a c t t o e p l i t zm a t r i c e sa r i s ef r o mav a r i e t yo fs c i e n t i f i ca n de n g i n e e r i n ga p p l i c a t i o n s ， s u c ha ss i g n a lp r o c e s s i n g ，i m a g ep r o c e s s i n g ，q u e u i n gn e t w o r k s ，n u m e r i c a ls o l u t i o no f o r d i n a r y p a r t i a ld i f f e r e n t i a le q u a t i o n s ( o d e s p d e s ) a n dn u m e r i c a ls o l u t i o no fi n t e g r a l e q u a t i o n s s ot o e p l i t zs o l v e rp l a y sa ni m p o r t a n tr o l ei np r a c t i c ea n dt h e o r y t h i s d i s s e r t a t i o nm a i n l ys t u d i e st h ea l g o r i t h mt of i n dt h ei n v e r s eo fag e n e r a lp e n t a d i a g o n a l m a t r i xa n dn e ws p l i t t i n gi t e r a t i o nm e t h o d sf o rt o e p l i t zs y s t e m s t h et h e s i sm a i n l y i n c l u d e st h ef o l l o w i n gf o u rp a r t s ： 1 b r i e fi n t r o d u c t i o n so fb a c k g r o u n d 、b a s i cc o n c e p t sa n dh i s t o r yo ft o e p l i t zs o l v e r a r eg i v e n 2 e m p l o y i n gt h eg e n e r a ld o o l i t t l ef a c t o r i z a t i o n ，a ne f f i c i e n ta l g o r i t h mi sd e v e l o p e d t of i n dt h ei n v e r s eo fag e n e r a lp e n t a d i a g o n a lm a t r i xw h i c hi s s u i t a b l ef o r i m p l e m e n t a t i o nu s i n gc o m p u t e ra l g e b r as y s t e m ss o f t w a r es u c ha sm a t l a ba n dm a p l e p a r t i c u l a r l y ，i nc a s eo fp e n t a d i a g o n a lt o e p l i t zm a t r i x ，t h ea l g o r i t h ms u c c e s s f u l l ya v o i d s b r e a k d o w no c c u r r i n gi nt r e n c h sa l g o r i t h m e x a m p l e sa r eg i v e nt o i l l u s t r a t et h e e f f i c i e n c yo f t h ea l g o r i t h m 3 b r i e fi n t r o d u c t i o n so ft h ec o n c e p to fd i s p l a c e m e n tr a n ka n di t sp r o p e r t i e sa r e g i v e n t h e nn e w l yd e v e l o p e dd i s p l a c e m e n ta p p r o a c h ( n e w t o n si t e r a t i o nm e t h o d ) i s i l l u s t r a t e d 4 n e ws p l i t t i n gi t e r a t i o nm e t h o d sf o rt o e p l i t zs y s t e m sa lep r o p o s e db ym e a n so f m a t r i xs p l i t t i n gb a s e do nd i s c r e t ec o s i n e s i n et r a n s f o r m t h e o r e t i c a la n a l y s i ss h o w st h a t t h en e ws p l i a i n gi t e r a t i o nm e t h o d sa l w a y sc o n v e r g et ot h eu n i q u es o l u t i o no fc o m p l e x s y m m e t r i ct o e p l i t zs y s t e m s m o r e o v e r , a c c e l e r a t i n gt e c h n i q u e ss u c ha sf i n d i n gt h e o p t i m a lp a r a m e t e ra n ds o ra c c e l e r a t i n ga r es t u d i e d n u m e r i c a le x a m p l e sa r eg i v e nt o i l l u s t r a t et h ee f f i c i e n c yo ft h es p l i t t i n gi t e r a t i o nm e t h o d s k e y w o r d s ：t o e p l i t zs o l v e r ，c o m p u t e ra l g e b r as y s t e m s ，s p l i r i n g ，d i s p l a c e m e n tr a n k ， p e n t a d i a g o n a lm a t r i x ，d i s c r e t ec o s i n e s i n et r a n s f o r m ，i t e r a t i o nm e t h o d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特另, i d i i 以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：趔! 日期： 2 净岁月2 7 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 盘殴。红导师签名： 日期： 2 刃罗年5 月2 了日 第。章绪论 第一章绪论 1 1 研究背景和意义 随着科学技术的快速发展，数学在科学研究中的发挥着越来越大的作用特别 是随着计算机技术的飞跃，计算数学的作用显得格外突出当今在计算数学中十分 重要的研究课题之一就是大规模线性代数系统的高效求解方法因为在科学与工程 的许多重要领域，如数字信号处理、数字图像处理、计算流体力学、电磁场计算、 石油勘探数据处理、地震数据处理、数值天气预报及核爆数值模拟等都离不开微 分方程或积分方程的数值求解，而解决这些问题的常用方法是先通过有限差分方法 或有限元方法将其进行离散，最终问题转化为大规模稀疏线性代数系统或大规模具 有特殊结构线性代数系统的求解 实际经验表明，尽管计算机技术发展迅猛，上述问题的数值计算和模拟的过 程中，求解线性代数系统所花费的时问在整个问题的计算时间中往往占很大比 重，有时甚至达百分之八十，成为整个计算的瓶颈，因此研究大规模线性代数系统 的高效求解方法显得十分重要求解线性代数系统的方法可分为两类：直接法和 迭代法在不计舍入误差的情况下直接法能得到准确解，但当系数矩阵的条件数 很大时，舍入误差的影响常引起所求出的解与准确解相差甚远，且对于规模很大 的情况下，直接法一般需要花费的时间和内存都很大因此，迭代法作为求解大型 线性代数系统的有效方法受到广泛关注目前大规模稀疏线性代数系统的求解， c g 和g m r e s 等k r y l o v 子空间迭代法已经被应用广泛但由于往往不具有稀疏性， 上述k r y l o v 子空间迭代法不适用大规模具有特殊结构线性代数系统的求解因此针 对大规模具有特殊结构线性代数系统，研究高效的求解方法成为当前数值代数领域 的一个热点问题目前国外己出现多个研究群体，主要有以r c h a n 、m n g 和q j i n 等 为代表的研究群体( 求解t o e p l i t z 线性系统的预处理技术及其应用) ，以t k a i l a t h 、g h e i n i g 、v p a n 和v o l s h e v s k y 等为代表的研究群体( 具有特殊机构矩阵的位移秩及其 位移秩方法) 大陆许多学者也在相关课题做了大量的研究工作西安交通大学的游 兆永、李磊、路浩等研究- j t o e p l i t z 矩阵、循环矩阵求逆的快速算法与复杂性分析， 西北工业大学的徐仲、张凯院、陆全等研究了v a n d e r m o n d e 、类t o e p l i t z 矩阵的快 速算法，厦门大学卢琳璋等研究了p a s c a l 矩阵的快速算法，汕头大学的林富荣研究 t t o e p l i t z 系统的预处理技术以及中国科学院数学机械化研究中心的支丽红研究了 具有特殊结构矩阵的符号与数值混合计算 电子科技大学硕士学位论文 1 2 研究的现状 1 2 1 t o e p l i t z 矩阵的定义及基本性质 德国数学家0 t o e p l i t z 在二十世纪初首次提出t o e p l i t z 矩阵的定义【1 】以来， t o e p l i t z 矢 e 阵广泛应用在科学与工程的许多重要领域【“】，如数字信号处理、数 字图像处理、排队网络、常、偏微分方程数值解和积分方程数值解等本节将简单 介绍t o e p l i t z 矩阵的概念及性质 定义1 2 1 1 2 1 形如 丁：o岛一，乙：。：兰：。三2乏 u 。， 的甩阶方阵称为t o e p l i t z 矩阵如果矩阵( 1 1 ) 的元素满足对称关系，即t j = t j ，其 中j = 1 ，2 ，n 一1 ) ，则称矩阵( 1 1 ) 为对称t o e p l i t z 矩阵，如果矩阵( 1 1 ) 的元素满 足亡一j = 石其中歹= 1 ，2 ，扎一1 ) ，则称矩阵( 1 1 ) 为h e r m i t e t o e p l i t z 矩阵 定义1 2 2 【2 1 ，l 2 【- 7 r ，7 r 】，令 如。去上丌朋) e - i k o d 9 ，后= 0 ，4 - 1 ，- - 2 ， 即，的f o u r i e r 系数则称函数，为t o e p l i t z 矩阵的生成函数但实际应用中往往给出 的不是t o e p l i t z 矩阵而是其生成函数，如数字图像还原中点扩散函数( p o i n t s p r e a d f u n c t i o n s ) 、积分方程中的积分核以及静态随机过程中的谱密度函数等由定义易 知当生成函数，为实值函数时，对应的t o e p l i t z 矩阵为h e r m i t i a n 矩阵；当，为偶函数 时，对应的t o e p l i t z 矩阵为对称矩阵 记为定义在f - 7 r ，7 r 】上周期为2 7 r 实值连续函数集合 定理1 2 1 【2 1 若t o e p l i t z 矩阵的生成函数，q 霄，则，仇t n 入m 饥( t ) a m ( t ) 厶眦：其中入m 饥( t ) 和入m a x ( t ) 分别为生成函数，对应t o e p l i t z 矩阵的最小和最大特征 值，厶t n 和厶分别为生成函数的最小值和最大值特别当， 0 时，t o e p l i t z 矩阵正 定 性质1 2 1 t s l 两个n 阶t o e p l i t z 矩阵相加减或数乘t o e p l i t z 矩阵，仍然是t o e p l i t z 矩 2 第一章绪论 性质1 2 2 t s lt o e p l i t z 矩阵是次对称矩阵，即满足j t j = t ，其中 j=cen，e2，et，=(111 ) t o e p l i t z 矩阵的逆矩阵仍然是次对称矩阵【卯但t o e p l i t z 矩阵的逆矩阵一般不再 是t o e p l i t z 矩阵 定义1 2 3 t s 形如 c = ( c i ) 易：1 c n l c 2 c oc n - 1 e lc o c n - 2 c 1 ( 1 - 2 ) 的n 阶方阵c 称为循环矩阵 定义1 2 4 【3 1 记= e i o o ，其中6 l d 【- - 7 1 ，丌】，l 阶矩阵w 称作 u ) - 循环矩阵当且仅 当满足： w = q + f a f q 其中q = d i a g 1 ，叫一1 加，甜一( n - 1 ) 竹】特别的， 1 ) 循环矩阵即循环矩阵； 一l - 循环 矩阵即反循环矩阵 定义1 2 5 【5 1 形如 f = 11 uu 2 u n 一1u 2 ( n 1 ) ( 1 3 ) 的n 阶方阵f 称为f o u r i e r 矩阵，其中u = e - j 2 7 r n 定理1 2 2 【3 5 】g 为挖阶循环矩阵的充要条件是存在数入o ，又l ，入托一l 使 f 一1 c f = d i a g ( a o ，a l ，、n - 1 ) ( 1 - 4 ) 3 q q ； 驴印 2 1 印 q ； 铲 俨 c c ，jj-。一 、lilllj， 1一 l 扎 1 舻 ；州 u 肛 u 电子科技大学硕士学位论文 1 2 2t o e p l i t z 线性系统求解方法的发展历史与最新进展 由于具有重大的科学意义和应用价值，吸引了大量的数学家和工程 师研究求解t o e p l i t z 系统的快速算法，这些算法被称作t o e p l i t z 求解器( t o e p l i t z s o l v e r s ) 早期t o e p l i t z 求解器的研究大多集中在直接方法上直接应用求解线性 代数系统的经典方法g a u s s i a n 消去法求解t o e p l i t z 系统的时间复杂度为o ( n 3 ) 但由于t o e p l i t z 矩阵仅由2 ，z 1 个元素决定，所以期望能够找到一种时间复杂度 低7 ：0 ( n 3 ) t o e p l i t z 求解器研究人员经过努力将t o e p l i t z 求解器的时间复杂度 降到t o ( n 2 ) ，例血n l e v i n s o n t 6 ( 1 9 4 6 ) ，t r e n c h t 7 1 ( 1 9 6 4 ) 和z o h a r 8 ( 1 9 7 4 ) ，但要求n 1 阶 主子矩阵可逆2 0 世纪8 0 年代，b r e n t l 9 ( 1 9 8 0 ) ，b i t m e a d t l 0 ( 1 9 8 0 ) ，m o r f1 1 1 ( 1 9 8 0 ) 以 及a m m a r l l 2 ( 1 9 8 8 ) 等，提出了时间复杂度为o ( 礼l 0 9 2 佗) 的快速直接t o e p l i t z 求解器， 但要求in 2i 阶主子矩阵的可逆然而对于对称正定t o e p l i t z 矩阵，b u n c h 1 3 】研究 了上述直接求解器的稳定性，指出当矩阵有奇异或病态的主子矩阵时算法会 崩溃( b r e a k d o w no rn e a r - b r e a k d o w n ) ，最终导致不精确的计算结果大量的研究人 员研究了如何避开奇异子矩阵或病态的子矩阵从而避免算法的崩溃f l 引，特别 的c h a n 和h a n s e n ( 19 9 2 ) t1 4 j 首次引入l o o k a h e a d 技术改进了l e v i n s o n 算法( 1 0 0 k a h e a d v a r i a n to ft h el e v i n s o na l g o r i t h m ) 但l o o k a h e a d 技术改进的l e v i n s o n 算法的时间复杂 度取决于病态主子矩阵的数目而且在最坏的情况下时间复杂度为d ( 佗3 ) t 1 9 1 最近利用预处理的共轭梯度法作为求解t o e p l i t z 系统的迭代方法获得了广泛 的关注预处理的共轭梯度法的重大突破在于，如果能够到选择合适的预处理矩 阵( p r e c o n d i t o n e r ) ，则求解一大类t o e p l i t z 系统的时间复杂度将降为o ( n l o g n ) ，优于 直接t o e p l i t z 求解器的时间复杂度而且直接求解器非常不稳定的一大类t o e p l i t z 系 统，例如不定t o e p l i t z 矩阵，病态t o e p l i t z 矩阵和某些非h e r m i t i a n t o e p l i t z 矩阵等，迭 代方法是一种有效方法1 9 8 6 年，s t r a n g t 2 0 1 和o l k i n t 2 1 】各自独立的提出了循环矩 阵作为预处理矩阵的p c g 方法求解t o e p l i t z 系统其后研究者又提出了很多有效 的t o e p l i t z 系统的预处理矩阵 但不管如何构造，预处理矩阵的构造必须遵循以下最基本的原则【3 1 ( 预处理后 系统为片1 l z = 写1 b ，其一i - r 为预处理矩阵) ： 1 ) 预处理矩阵r 容易构造； 2 ) r u = 容易求解； 3 ) 露1 瓦的谱聚集 下面介绍一些按照以上原则构造的有效的t o e p l i t z 系统预处理子： 4 第一章绪论 1 2 - 2 1 循环预处理矩阵 s 七= t k n ，【n 2 t k 0 j 七 n 2 佗j ， i ，克， 【s n + 七，0 一尼 0 ，且属于w i e n e r 类，即i t k ( f ) i o c ， 则对于充分大的n ，( s ( 瓦) ) _ 1 瓦的谱半径聚集在l 附近 2 、t c h a n 预处理矩阵【2 2 】 对- 于t o e p l i t z 矩阵，使得l l c t l | f 最小的循环矩阵为t c h a n 预处理矩阵( 其 中f 为f r o b e n i u s 范数) ，因此t c h a n 预处理矩阵也称为最优循环预处理矩阵，记 作c ( 瓦) ；而t y r t y s h n i k o v t 3 0 j 考虑了使l i ，一c 7 1 1 f 的最小的循环矩阵作为预处理矩 阵，称为超最优循环预处理矩阵c ( 墨) 的各对角线元素也可以显示的表示如下： r 一j 虹訾虹，0 歹 死， 。 ic ，i 卅，0 - j 0 ，则对于充分大的n ， c ( 已) 。死的谱聚集在l 附近 由定理1 2 2 和f r o b e n i u s 范数的酉不变性知0 c t i l f = i i f + a f t 峙，进一 步得至u c ( t ) = f a f + ，其中对角矩阵的对角元素为f 卯+ 的对角元素利用快 速f o u r i e r 变换构造c ( 丁) 的时问复杂度为o ( n l o g n ) t c h 柚预处理矩阵的良好的计 算性质很自然的启发从其它的酉不变或正交快速变换出发构造预处理矩阵，如正弦 变换t 2 4 】、余弦变换【2 5 l 并i h a r t l e y 变换【2 6 i 3 、r c h a n 预处理矩阵【2 7 】 r c h a r t 预处理矩阵7 ( 丁) 是对角线元素的定义如下的循环矩阵： 住= 2 时，o 妤= 0 ，则a = ( ，) 1 t ， 0 ，i = 1 ，2 ，n 证明：由推论2 2 4 和正定矩阵的充分必要条件易得口 1 3 电子科技大学硕士学位论文 注释2 2 2 如果满足定理2 2 - 2 条件，则存在l u 分解的特殊情形c h o l e s k y 分解， 即a = l l t 在定理2 2 1 的基础上，本节提出了求一般五对角矩阵逆矩阵w = ( ) 1 ，歹n 的算法2 2 i 算法2 2 i 输入：矩阵维数，l ，主对角线元素口1 ，a 2 ，上第一对角线元素b l ，b 2 ，k 一“上 第二对角线元素c l ，c 2 ，一2 ，下第一对角线元素d 2 ：如，如和下第二对角线元 素e 3 ，e 4 ，e n 输出：五对角矩阵逆矩阵w = a _ 1 的元素埘玎( 1 i n ，1 歹扎) 步骤is e tx l = t z l ，i f3 7 1 = 0 ，i n p u t ( f a i l u r e ) ，s t o p s e ty l2 b l ，勿= 茹a _ z l ，e 3 = z e a l 步骤2s e tz 2 = a 2 一1 勿 i fx 2 = 0 ，i n p u t ( f a i l u r e ) ，s t o p s e t 垅= 6 2 一z 2 c i ，z 3 = 警，e 4 = 嚣 步骤3f o rf - 3 ：n 一2 x i2 啦一珧一1 筋一e i c i _ 2 i fx i = 0 ，i n p u t ( f a i l u r e ) ，s t o p s e t y i = 玩一筋q 一1 ，z i + l = 生丝二薏丛丝土，e 件2 = 笋 步骤4s e tz n l = 口n l 一一2 一1 一e n - 1 c ，l 一3 i fz t l 一1 = 0 ，i n p u t ( f a i l u r e ) ，s t o p s e t 蜘一12 k 一1 一一1 ( ：，l 一2 ，= 虫警 步骤5s e tz n = a n 一一1 z n e n c n 一2 i fz n = 0 ，i n p u t ( t h em a t r i xai ss i n g u l a r ) ，s t o p 步骤6f o ri = 1 ：n s e tu i i = 1 ：u 以2i 1 e n d 步骤7s e t 一1 ，n = 一蛆；e n - - i 土z n ，一1 ，n = 0 f o ri = n 一2 ，1 f o r 歹= 礼，i + 2 1 4 第二章一般五对角矩阵的求逆 e n d s e tl 切= 0 s e tu o = 一囊讹+ 2 j 一罢u i + l j e n d s e t u ，i + 1 = 一z 鸶u i + i ，i + 1 ，仇，i + 1 = 0 步骤8s e tv 2 1 = 一勿，u 2 1 = 0 f o ri = 3 ，n f o rj = 1 ，i 一2 s e tu o = 0 ，= 一e i v i 一2 , j z i o i 一1 , j e n d s e t v i ，i 一12 一z i v i 一1 ，t 一1 ，t t i ， 一1 = 0 e n d 步骤9f o ri = 1 ，7 , f o rj = 1 ，死 七= m a x ( ，j ) s e t w i j = u i k v k j l = k e n d e n d 注释2 2 3 如果z 知0 ，其中忌= 1 ，2 ，n 一1 ，则算法2 2 1 求一般五对角矩阵 行列式运算量为ll n 一1 7 优于s o g a b e 的1 4 n 一2 8 1 4 7 1 如果玩= 0 ，其中i n 一1 ，贝t d o o l i t d e 分解不能继续进行如果z n 0 ( h i j a t l z 奇异) ，利用选主元的d o o l i t t l e 分解可以得到p a = l u ，其中p 是转置矩阵但选主元 的d o o l i t t l e 分解会破坏五对角矩阵的特殊结构和稀疏性注意到鼢实际上只是中间 辅助量，所以当戤= 0 时，其中i 儿一1 ，不妨令兢= 使得d o o l i t t l e 分解继续进行( 得 到的d o o l i t t l e 分解称为，“义d o o l i t t l e 分解) ，进一步利用符号运算计算n 妖( 亡) 得到关 于f 的多项式如果多项式的常数项系数z o 不为零，即矩阵a 的行列式不为零，则利用 符号运算，类似于算法2 2 1 求得关于t 的i y ( t ) 元素最后令t = 0 ，则得到一般五对角 矩阵逆矩阵w 的元素上述思想能够在计算机代数系统( 女l l m a t l a b 、m a p l e 等) 上实 现 基于上述讨论提出了一种适合在计算机代数系统( 如m a t l a b 、m a p l e 等) 上实现 的一般五对角矩阵求逆的算法2 2 2 1 5 电子科技大学硕士学位论文 算法2 2 2 步骤1 如果兢= 0 ，i 1 ，2 ，几一1 ) ，令钇= t 由式( 2 2 ) 计算z 件l ，z 礼 步骤2 计算并简化多项式p ( t ) = 1 7 款 步骤3 如果多项式常数项x 0 系数不等于零，则进行下一步；否则中断程序( 此时 矩阵奇异) 步骤4 利用符号运算类似算法2 2 1 计算w ( t ) = a _ 1 关于t 元素令t = 0 ，则得到 一般五对角矩阵逆矩阵w 的元素 注释2 2 4 如果飘= 0 ，其中i n 一1 ，则一般五对角矩阵的行列式利用算 法2 2 。2 可以得到 注释2 2 5 【4 4 中一般三对角矩阵符号t r i n v 算法克服了数值版易崩溃的缺 点且不破坏矩阵的特殊结构和稀疏性三对角矩阵是五对角矩阵的特殊情形，算 法2 2 2 可以看做是t r i n v 算法的推广而定理2 2 1 及其推论保证了算法2 2 2 继承符 号t r i n v 算法的优良特性 注释2 2 6 最近周期五对角矩阵，周期反五对角矩阵( p e r i o d i ca n t i p e n t a d i a g o n a l m a t r i x ) 的求逆算法受到广泛的关注 4 9 ，5 0 1 ，本节算法2 2 2 稍作修改很容易推广到周 期五对角矩阵，周期反五对角矩阵( p e r i o d i ca n t i - p e n t a d i a g o n a lm a t r i x ) 的情形 注释2 2 7 由定理2 2 1 得到五对角矩阵广义的d o o l i t t l e 分解a = l u ，则求解五 对角系统a x = 6 等价于两个三角形系统的求解： ( 1 ) 求解己1 y = b ，得向量y ； ( 2 ) 求解u l x = y ，得五对角系统的的解秒 而上述三对角系统1 y = b , n 下三对角系统以z = 可的求解就是回代( b a c k - s u b s t i t u t i o np r o c e s s ) 和消元( e l i m i n a t i o np r o c e s s ) 的过程进一步由定理2 2 1 得到五 对角矩阵广义d o o l i t t l e 分解a = l 扩，则a _ 1 可以构造如下： ( 1 ) 分别求解l y i = 乞，其中i = 1 ，2 ，n ； ( 2 ) 分别求解u 铂= 玑，其中i = 1 ，2 ，n 则a - 1 = p 1 ，z 2 ，z n 】，其中e i 是n 阶单位矩阵的第i 列由于( 1 ) 中系统l y i = e i 求解 过程相互独立，其中i = 1 ，2 ：扎，则可以在n 个处理器上同时进行同样( 2 ) 中系 统u x f = 玩的求解过程也相互独立，其中i = l ：2 ，您，则也可以在船个处理器上同 时进行综上所述知算法2 2 2 稍作修改则适合在n 个处理器上并行计算，这样将大 大提高了算法2 2 2 的效率 五对角t o e p l i t z 矩阵是五对角矩阵的特殊情形，【5 】给出了五对角t o e p l i t z 的求 逆的t r e n c h 算法，但是要求主子矩阵非奇异如何避开奇异或病态子块，除了前 1 6 第二章一般五对角矩阵的求逆 面提到的l o o k h e a d 技术，本节给出的算法2 2 2 提供了另一种解决的思路但是算 法2 2 2 求五对角t o e p l i t z 矩阵的逆只利用了五对角矩阵( 2 1 ) 的带状结构，没有充分 利用t o e p l i t z 矩阵的特殊结构但是t o e p l i t z 矩阵( 1 1 ) 的特殊结构的本质是什么，怎么 量化t o e p l i t z 矩阵与其它矩阵的差异，这些问题得不到解决，就谈不上研究充分利 用t o e p l i t z 矩阵的特殊结构的快速算法第三章将介绍刻画t o e p l i t z 矩阵特殊结构的 核心概念位移秩 2 3 数值例子 本节给出了说明上述算法的例子 例2 3 1 考虑如下五对角矩阵： a = 11 11 2 6 o 2 o o 0 o 3 0 2 2 31 4 2 13 03 00 0 0 5 0 31 14 5 互1 利用算法2 2 2 ，得至u p ( t ) = - 1 3 9 t 一8 6 8 ，d e t ( a ) = - 8 6 8 ， a 一1 = 0 7 8 8 00 0 0 5 80 1 0 3 10 7 0 6 20 1 4 0 00 2 9 2 6 一o 4 9 3 10 1 6 0 10 1 6 6 50 1 6 7 1 一o 0 0 8 6 0 2 6 5 0 0 2 3 5 0 0 0 5 5 3 一o 0 8 9 90 1 7 9 7 0 0 4 3 8 0 0 0 9 2 一o 3 8 2 50 4 7 2 4一o 0 4 4 90 0 8 9 9 0 0 2 1 9 0 0 0 4 6 0 2 1 2 00 2 5 5 80 0 2 1 90 0 4 3 8 0 0 1 5 00 2 0 7 4 0 1 7 5 10 2 7 6 50 0 5 0 7 一o 1 0 1 40 2 8 1 1 0 0 4 6 1 例2 3 2 考虑如下矩阵 211o 2 221 0 0 肛l 。1 ；。1 三： 00 - 18 + 23 + o t 1 7 电子科技大学硕士学位论文 利用算法2 2 2 知对任意的q 和p 有d e t ( b ) = 一3 ，且 3 矿悖3 - 一3 6 一a ( 2 一p ) 1 2 + q ( 2 一p ) 3u 2 8 3u 1 2 一a ( - 2 + 2 ) - 1 8 + a ( - 2 + 2 3 1 6 - 2 + 2 口 例2 3 3 考虑如下的_ j = h e s s e n b e r g 矩阵 强朦 利用算法2 2 2 ，得到逆矩阵b 一1 的元素如下， 一3 9 一a ( - 2 3 + 1 1 - 1 5 + a ( - 2 j + 1 ) 6 2 口+ 1 w 1 1 ：二! 型丛塑至型坦起旺硅l 盗鱼2 盘h 血丝幽幽d 翌坦d 螳匕垒2 鲣虫虹兰坚她， n ， w 1 2 = 蛐型匹巡血型巡警山地盘幽虹蛐坎， w 1 32 - c l a 2 a s a 4 + c i a 2 d s b 4 + b a i b 2 a 5 a 4 - b l b 2 d s b 4 - b l a s d 4 e 2 ， w 1 43 - c x c 2 a 5 d 3 - c l d 5 a 2 c 3 + c l b z a 2 a i s - b l b 2 b 3 a s + b a d 5 c 3 6 2 + b l c 一2 a a a 3 ， w 1 52 c a c 2 b 4 d 3 q - c l a 2 c 3 a 4 - c l a 2 b 3 b 4 - b l _ c 3 厂a 4 b 2 - t - b lb 3 b 4 b , 2 + b l c 2 d 4 c 3 - - b a c 2 一b 4 a 3 ， w 2 12 - ( - a 3 c t s a 4 - 1 - a 3 d s b 4 - 口d s d 4 c 3 + a s d 4 b 3 ) d 一2 ， w 2 22 - ( a 3 a s a 4 - a 3 d s b 4 + q d s d 4 c 3 - a s d 4 b z ) a l ， w 2 32 c l d 2 a s a 4 - c l d 2 d s b 4 - b 2 a l q a s a 4 + b 2 a t d s b 4 + a 5 d 4 a l c 2 ， w 2 4 = 型硅生型也蜓业挚鲥虹血虻必， w 2 52 - - c l d 2 c z a 4 + c l d 2 b z b 4 - c 2 a a d 4 c 3 i + c 2 a l b 4 a 3 - b 2 a l b 3 b 4 + b 2 a l c 3 a 4 ， 姚13 一( a 5 a 4 - 百d s b 4 ) d 2 d 3 ， w 3 2 = 血蜓挚， w 3 32 ( - a s a 4 + d 6 b 4 q ) ( - a 2 a l + b l d a ) ， 1 8 、lliiilillii， o o 以k 船 d 彩如 m 出 其中 w 3 42 砌3 52 w 4 1 = = w 4 22 w 4 32 w 4 42 w 4 52 w 5 12 w 5 22 w 5 32 w 5 42 w 5 52 第二章般五对角矩阵的求逆 虫3 1 鲣= 虫当盟l 幺璺l 鲣垡3 = b 垒2 璺1 酆盘璺垒2 竖i q d 2 c a b l a 4 - d 2 b z b l b 4 - c 2 a l b 4 d 3 - c z a 2 a l a 4 - t - b 3 a 2 a l b 4 n a c t s d 4 ( - a 2 a l + b l d 2 ) q 7 a 5 ( a 3 a 2 a l - a 3 b ld 2 - d z b 2 a l + d 3 d 2 c 1 ) 区2 垡3 垡4 盘 q n q 7 ( - - a 3 a 2 a l + a s b l d 2 + d 3 b 2 a l - d 3 d 2 c 1 ) d 5 a 7 a 4 a 3 a 2 a l - a 4 a s b l d 2 - a 4 d s ，b 2 a ，l ，+ a 4 d s d 2 ，c ，1 - d 4 b s a 2 a 1 + d 4 b 3 b 1 d 2 + d 4 d 3 a 1 c 2 q 口：a 5 9 4 a 3 a 2 a l a 5 a 4 a a b l 如一a s a 4 d 3 b 2 a l + a s a 4 d 3 d 2 c l 一口5 也6 3 0 2 n 1 + a 5 d 4 b 3 b l d 2 + a s d 4 d a a l c 2 一d 5 b 4 a 3 a 2 a l + d 5 b 4 a 3 b l d 2 4 - d 5 b 4 d 3 b 2 a 1 一如b 4 d 3 d 2 c l + 如d 4 c 3 a 2 a l c f 5 d 4 c 3 b l 如 1 9 电子科技大学硕士学位论文 第三章具有特殊结构矩阵及其快速算法 常见的具有特殊结构的矩阵( 见表3 1 ) 有t o e p l i t z 矩阵、h a n k e l 矩 阵、v a n d e r m o n d e 矩阵和c a u c h y 矩阵等，其特点是稠密且只依赖于0 ( 竹) 个参数但 其特殊结构的本质是什么，具有特殊结构矩阵与其它矩阵的逼近程度怎么衡量，这 些问题得不到解决，研究充分利用其特殊结构的快速算法( 如矩阵分解、线性系统 的求解、矩阵求逆、矩阵与向量的乘积和特征值计算等问题) 就无从谈起本章介 绍了位移秩( d i s p l a c e m e n tr a n k ) 概念及其性质，其刻i w it t o e p l i t z 矩阵特殊结构的本 质进一步介绍y 求t o e p l i t z 矩阵逆的一种位移秩方法即n e w t o n 迭代法 3 1 位移秩概念及相关性质 1 9 7 3 k a i l a t h 在解决随机过程的最小二乘估计时首次提出了位移结 构( d i s p l a c e m e n ts t r u c t u r e ) 的概念【5 1 1 ，并将其引入矩阵分析用于衡量给定矩阵 与t o e p l i t z 的逼近程度【5 2 1 位移秩概念由于其深刻的内涵很快受到重视，作为研 究具有特殊结构矩阵的工具被广泛使用；