（计算数学专业论文）hermitian+toeplitz矩阵向量积的计算.pdf

摘要 本文主要讨论h e r m i t i a nt o e p l i t z 矩阵与向量的乘积利用h e r m i t i a nt o e p l i t z 矩 阵的结构和性质，我们首先将它变换成一个实对称t o e p l i t z 矩阵与一个h a n k e l 矩 阵的和；然后，利用f f t 方法，我们设计了基于嵌入、多水平方法和分裂方法的 快速算法最后用一个实例来说明这三种方法的计算量以及跟传统算法计算量的 比较。 本文共分为六章，结构如下： 第一章为引言主要介绍了本论文的研究背景和选题依据，以及研究内容和 创新 第二章主要介绍了一些在本文中要用到的基本概念和符号表示 第三章将t o e p l i t z 矩阵嵌入到一个循环矩阵，得出了用f f t 方法计算h e r m i t i a n 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 矩阵与向量的乘积的快速算法 第五章将实对称t o e p l i t z 矩阵分裂成一个循环矩阵和一个反循环矩阵的和，从 而得出了基于该分裂来计算h e r m i t i a nt o e p l i t z 矩阵与向量的乘积的快速算法 关键词：h e r m i t i a nt o e p l i t z 矩阵；f f t ；乘积；快速算法 a b s t r a c t t h i st h e s i sc o n c e r n st h ec o m p u t a t i o no fh e r m i t i a nt o e p l i t zm a t r i x - v e c t o rp r o d u c t e x p l o i t i n gt h es t r u c t u r ea n dp r o p e r t i e s o fh e r m i t i a nt o e p l i t zm a t r i c e s ，w ef i r s t t r a n s f o r ma nh e r m i t i a nt o e p l i t zm a t r i xi n t ot h es u mo far e a lt o e p l i t zm a t r i xa n da h a n k e lm a t r i x t h e nw ed e v e l o pt h r e ef a s ta l g o r i t h m sf o rc o m p u t i n gt h eh e r m i t i a n t o e p l i t zm a t r i x v e c t o rp r o d u c t ，w h i c h a r eb a s e do ne m b e d d e dm e t h o d ，m u l t i l e v e l m e t h o da n ds p l i t t i n gm e t h o dv i af f ta p p r o a c h ，r e s p e c t i v e l y f i n a l l y ，w eg i v ea n u m e r i c a le x p e r i m e n tt os h o wt h ec o m p u t a t i o n a lc o s t so ft h ea b o v et h r e ea l g o r i t h m s a n dac o m p a r i s o no fo u ra l g o r i t h m sw i t ht h ec o n v e n t i o n a la l g o r i t h m t h i st h e s i sc o n s i s t so ff i v ec h a p t e r sw h i c ha r eo r g a n i z e da sf o l l o w s ： t h ef i r s tc h a p t e ri sa ni n t r o d u c t i o n w em a i n l yi n t r o d u c et h eb a c k g r o u n d ，t h e m a i nc 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 r ，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 na n dn o t a t i o nw h i c h w i l lb eu s e di ns e q u e l i nt h et h i r dc h a p t e r ，w ed e v e l o paf a s ta l g o r i t h mf o rc o m p u t i n gt h eh e r m i t i a n t o e p l i t zm a t r i x v e c t o rp r o d u c ti n w h i c hat o e p l i t zm a t r i xi sf i r s te m b e d d e di na c i r c u l a n tm a t r i xa n dt h e na nf f tp r o c e d u r ef o l l o w s i nt h ef o u r t hc h a p t e r ，w ed e v e l o paf a s ta l g o r i t h mf o rc o m p u t i n gt h eh e r m i t i a n t o e p l i t zm a t r i x v e c t o rp r o d u c t i nw h i c ham u l t i - l e v e li d e ai sa p p l i e d i nt h ef i f t hc h a p t e r ，w ed e v e l o paf a s ta l g o r i t h mf o rc o m p u t i n gt h eh e r m i t i a n t o e p l i t zm a t r i x v e c t o rp r o d u c t i nw h i c har e a ls y m m e t r i ct o e p l i t zm a t r i xi ss p l i ti n t oa s u mo fac i r c u l a n ta n ds k e w c i r c u l a n tm a t r i xa n dt h e naf f tp r o c e d u r ef o l l o w s k e y w o r d s ：h e r m i t i a nt o e p l i t zm a t r i x ；f f t ；v e c t o rp r o d u c t ；f a s ta l g o r i t h m i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：杏惠日期：之，p 年上 月了日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。同时授权中国科学技术信息研究所将本论文收录到中国学位论 文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 李专、 玉竹乞 日期：酗j0 年s 月2 弓e l e t 期：二ol 晖j 月阳 1 1 研究背景 第一章引言 从物理学和信息学的角度来看，任何信息都可以从多种角度进行研究在工 程和实际应用中有许多问题实际上最终都归结为矩阵计算，而且有许多需要计算 的矩阵是一些具有特殊结构的矩阵，最常见的一些结构矩阵有t o e p l i t z e 矩阵、 h a n k e l 矩阵、v a n d e r m o d e 矩阵、c a u c h y 矩阵等等t o e p l i t z 矩阵在数值分析 h - 9 1 、 自动控制、数字信号处理、系统辨识、最小二乘估计等众多科学领域中都有广泛 的应用，是应用最广泛的特殊矩阵之一t o e p l i t z 系统还应用于时间序列中固定自 返模式未知参数的求解，偏微分方程组的求解，卷积型积分方程组的p a d e 逼近 求解，三维地震资料的预处理，以及控制论中的最小实现问题等。而利用这一矩 阵结构，人们也许能设计更快和( 或) 更精确的算法它还可能帮助产生具有更准确 物理意义的解 目前，在国内外已经出现多个研究群体，主要有以t h o m a sk a i l a t h 为代表的 研究群体( 位移秩方法) ，以g e o r gh e i n i g 为代表的研究群体( 四种基本类型位 移结构矩阵的计算，矩阵广义逆的位移结构) ，以v i c t o ryp a n 为代表的研究群 体( 多项式与结构矩阵的计算，牛顿结构迭代算法) ，以v a d i mo l s h e r v s k y 为代 表的研究群体( 有理插值与结构矩阵的快速算法的研究【3 9 h 4 3 】) 等其实，早在1 9 0 9 年，h a a r 通过在 0 ，1 】区间引入简单的方波函数作为基函数，并实施平移得到h a a r 正交变换，1 9 2 3 年，w a l s h 则建立了一种完备的w a l s h 正交函数系统。1 9 6 5 年， c o o l e y 与t u k e y 等人在离散f o u r i e r 变换( d f t ) 的基础上，提出的快速傅里叶 变换( f f t ) 算法，大大降低了d f t 计算的时间复杂度1 9 7 4 年，印度科学家 a h m e d 和n a t a r a j i a n 提出以三角变换作为基函数离散化，从而得到了离散三角变 换【1 1 h ”】2 0 世纪9 0 年代以前，这些算法以直接法为主2 0 世纪9 0 年代以后， t o e p l i t z 系统的求解算法多集中在迭代法上，尤其是预条件共轭梯度法h 3 1 1 和多 重网格法作为一种迭代法，预条件共轭梯度法可以看作是在共轭梯度法的迭代 中加入了预条件矩阵，其优点在于如果选择合适的预条件，则求解刀阶t o e p l i t z 矩阵的计算复杂度可由快速直接算法的o g l 0 9 2 刀) 降为o ( n l o g 刀) 在国内，西安交通大学的游兆永、李磊、路浩等在t o e p l i t z e 矩阵、循环矩阵 求逆的快速算法与复杂性分析方面，西北工业大学的徐仲、张凯院、陆全【2 2 1 等在 v a n d e r m o d e 、t o e p l i t z 矩阵类的快速算法方面都做了大量的研究工作 1 2 选题依据，研究内容和创新 1 2 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 矩阵的特点是主对角线上的各元素彼此相等，平行于主对角线的各 对角线上的元素也彼此相等。若t 是可逆的，由次对称矩阵的性质可知1 仍是 次对称矩阵，但是，它一般不再是t o e p l i t z 矩阵，因此求t o e p l i t z 矩阵的逆矩阵 有一定的困难h e r m i t i a nt o e p l i t z 2 ”1 矩阵是t o e p l i t z 5 1 矩阵中的一种特殊 情况在物理学等领域有非常广泛的应用，但目前有关这方面的研究相对较少，因 此，对h e r m i t i a nt o e p l i t z 矩阵的研究以及设计相关的算法是很有研究价值的 本论文中主要讨论h e r m i t i a nt o e p l i t z 矩阵与向量x 的乘积 2 1 2 2 本文的主要创新 本文利用h e r m i t i a nt o e p l i t z 矩阵的结构性质，先将它酉变换成一个实对称 t o e p l i t z 矩阵和一个h a n k e l 矩阵的和，对于实对称t o e p l i t z 矩阵，我们再次对 它进行酉变换成一个实对称t o e p l i t z 矩阵和一个h a n k e l 矩阵的和，如此重复 下去，维数每次减少到原来的一半对于h a n k e l 矩阵与向量乘积的计算，我们先 将h a n k e l 矩阵右乘j 矩阵使之变换成实对称t o e p l i t z 矩阵，再利用多水平方法 来做 3 第二章预备知识 本章中主要介绍了在论文里面将要用到的一些记号和相关知识，对于在后面 章节中单独出现的概念再另做介绍 2 1 相关定义的介绍 定义2 1 1 n 9 1 以阶t o e p l i t z 矩阵定义丁= g t lt 从= f h ，k = 0 ，1 ，刀一1 形如： 瓦= t ot lt 一2 f ll l t 2t lt 0 t n - i 定义2 1 2 n 6 “例 刀阶h a n k e l 矩阵定义为日= ，七lh z 。t = h t + t ，k = o ，1 ，刀一1 形如： h 。= 定义2 1 3 1 9 1 玎阶对称t o e p l i t z p l u s h a n k e l 矩阵定义为 彳= g la l , k = t i ，一划+ ，+ t ，k = 0 ，1 ，刀一1 定义2 1 4万阶h e r m i t i a n 矩阵膏定义为 詹= 骨，其中詹兰厅r ：lj , ，尼：o ，1 ，咒一1 定义2 1 5 设矩阵u m 。，若u u = ，就称u 是酉矩阵，若还有 u m 。伍) ，就称u 是实正交矩阵 因为酉矩阵u 有u 一= u ，所以，如果u 是酉矩阵，那么由a u + a u ； 气 一 f l z“；k 胁从；m氟舷；加氟；缈 给出的m 上的变换是相似变换这种特殊的相似形式称为酉相似或酉等价 定义2 1 6 c 定义为刀阶离散的快速f o u r i e r 变换矩阵，那么 c = 眈lf j k = c o ：k 这里q p ( 半) s ( 等) 粕i n ( 斜 定义2 1 7 c h = g l 。叮r 脚称为中心对称矩阵，如果c h 的元素满足 c h u = c h ，一札州+ l ，这里1 f p ，l j q 对于中心对称矩阵，有以下引理 2 2 相关引理的介绍 引理2 2 1 ( 1 ) c r “是一个中心对称矩阵，这时( c ) 是中心对称的，且如 果c 是非奇异的，那么c j 是中心对称矩阵的 ( 2 ) 如果h 是一个中心对称矩阵，那么h t 是一个q p 阶的中心对称矩 ( 3 ) 如果e ，f 都是中心对称矩阵，那么e f 都是中心对称矩阵 ( 4 ) 如果a r “，b r 舨7 都是中心对称矩阵，那么a b r 蒯是中心对称 矩阵 假设a 是t l xm 阶中心对称矩阵，以= 2 k ，研= 2 1 将a 分成四个k ，块， 那么有 定义 彳：l 垒- 4 a ：i l 以彳1 2 以彳。i k ，j q = 托 ( 2 2 1 ) 其中s = 2 t ，易知，q 是酉矩阵，且簖1 = q 日我们可以得到下面的引理 引理2 2 2 如果a c h “m ，q 如( 1 ) 式所示，那么 5 钟彳q 埘= 瞄 r e ( “a n “+ a l ：2 山j l ；- r e 【i m ( a u _ - a ：l 川2 j 1 ) j 1 剞“ 这里r e ( r ) 和i m ( t ) 分别表示矩阵t 的实部和虚部 下面证明一个以阶的h e r m i t i a nt o e p l i t z 矩阵酉变换成一个中心对称 t o e p l i t z 矩阵和h a n k e l 矩阵的和 对于一个刀阶的h e r m i t i a nt o e p l i t z 矩阵a 我们定义 q = 托埘 亿2 力 其中s = 2 t ，易知，q 是酉矩阵，且9 1 = o h 那么 ：如a i 2 以j t r e ( a 2 乏册肼 + ) l l 一彳1 2 ) j 哉1 + r e a n 也i m a 如i 2 j 纠t 这里丁= 瞄：冀1 ，日= 瞄- r e a l ：1 地i m a 1 2 j t 由于彳舢e n 脚m z 矩阵，故 一( i r a a l l ) r = i m a t l 易知丁是一个实对称t o e p l i t z 矩阵，即为一个中心对称t o e p l i t z 矩阵日是 一个h a n k e l 斜中心对称矩阵这样一个h e r m i t i a nt o e p l i t z 矩阵a 通过一个酉 变换成了一个中心对称t o e p l i t z 矩阵和一个h a n k e l 矩阵的和即 q ：a q = t + h 于是有a = q 仃+ 讲 这样h e r m i t i a nt o e p l i t z 矩阵彳与向量x 的乘积转化成 a x = q 仃+ h ) q n x 这里，我们令q h nx = y ，则 6 ，j-、，j_l、 ： 嘣叫n 一一r【 j i = 瓯 4 钟 a x = q ，虹+ h ：x = q 。仃+ 日涉 = q n r y + q h y ( 2 2 3 ) 注意：这里r 为 阶中心对称t o e p l i t z 矩阵，日为n 阶h a n k e l 矩阵 7 第三章f f t 方法计算h e r i nitia nt o e p l itz 矩阵与向量 3 1f f t 方法的推导 的乘积 我们先看( 2 2 3 ) 式右边的前半部分q 砂，考虑胛阶实t o e p l i t z 矩阵r ， 我们将它嵌入一个2 一1 ) x ( 2 n 一1 ) 阶的循环矩阵c ，即 c = 容易看出，c 的咒阶顺序主子式阵为t o e p l i t z 矩阵j r t 给定一个疗维的向量 y = ，y ：，y 。) 7 计算矩阵与向量的乘积z = t y ，令夕为一( 2 刀一1 ) 维的向量 夕= 。l ，y ，y 。，0 l vy 2，0 一，o ) 7 y 2 l ，n ，u j 容易看出，z 为向量u 的前刀个向量，其中u 暑 由于循环矩阵与向量的 积可用f f t 来计算，即 = 够协p ) 舻) ) 其中d 为矩阵t 的第一列由于护0 ) 的计算复杂度为o ( n l o g n ) 这样，可 得到下面引理 引理3 1 1 2 1 任一n 阶t o e p l i t z 矩阵与任一以维向量的乘积的计算复杂度为 l 2 d 刁 ， “加；纠彬；“ 1 = ；：。o； 叫o“；乞气；o h 1 一 纠；以幻幻；纱 q 屯； o q 也； 1缈；如幻以； o； ： 1 q； ：气；h；乞 如幻；彬彬； o ( nl o g n ) 3 2 关于f f i 方法的算法及计算量 由引理2 2 2 可以得到如下算法： 算法1 该算法利用f f t 计算n 维向量y 与n 阶t o e p l i t z 矩阵r 的乘积 z ，即z = t y ； 第一步 定义一个( 2 以一1 ) 一维的向量夕，其中夕= 。，y ：，y 。，0 ，o ，o ) r ； 第二步 由公式谚= 够咖p ) 护) ) ，计算向量“，其中d 为循环矩阵c 的第一列； 第三步令“= g l ，“2 ，“2 川，“2 川y ，则z = g l ，“2 ，“。y 现描述一刀阶对称t o e p l i t z p l u s - h a n k e l 矩阵彳与任一刀维向量z 的 乘积的一种算法， 即计算a x ，其中a = 幺p + 日! 胖因而以阶对称 t o e p l i t z p l u s h a n k e l 矩阵彳与任一n 维向量的乘积 a x = q 仃+ 日涉 就转化为万阶t o e p l i t z 矩阵和咒阶h a n k e l 矩阵分别与一个n 维向量的乘积 计算记，为以阶次单位矩阵，因而有，2 = i 由t o e p l i t z 矩阵和h a n k e l 矩 阵的结构特点，可得 h j = 巧( 3 1 1 ) 其中乃为t o e p l i t z 矩阵因而上式可转化为 a x = q 仃+ h 涉 = q ( r y + 缈) = q ：v + q ( m x j v ) = q n + q ) 其中为t o e p l i t z 矩阵，) 为一刀维向量，因而巧( ) 仍可运用算法1 o 来实现 算法的复杂度：计算f f t 需要的运算量为o ( n l o g n ) ，故整个算法的运算量 为o ( n l o g n ) 用 t o e p l i t z 矩阵，这 质，在第四章讨论 法的计算量 算例1 f f t 方法解t o e p l i t z 矩 罩没有用到( 2 2 3 ) 式中 阵与向量的乘积适用于所有的实 t o e p l i t z 矩阵丁的中心对称这一性 的方法将用到这一性质下面我们以4 阶矩阵为例说明f f t 方 令4 阶h e r m i t i a nt o e p l i t z 矩阵a = 工= 0 ，2 ，2 ，1 ) 7 ，求a x 令q ：车 二 于是 3 - 又q h x - , 2 2 刎f ， l 刎r l l f 2 2 f 2 2 f l f 经过酉变换之后 8 5 一f 4 一f 2 3 一f “b + 1 0 5 + f 8 5 一f 4 一f 2 4 + f 2 5 + f 8 5 一f 卜 卜 向量 1j “抛“8 3 争5 z_i _ 工 - 1 2 1 0 2 o o ，o o 屯 3 4 5 8 4 5 8 5 5 8 5 4 8 5 4 3 o o 乞o 。o o 乞 2 o o 1 2 1 0 3 4 5 8 4 5 8 5 5 8 5 4 8 5 4 3 由算法1 可以得到a x =封 对于4 阶的h e r m i t i a nt o e p l i t z 矩阵而言，利用算法1 需要的运算量为2 0 + 8 1 0 9 2 第四章多水平方法计算h e rmitia nt o e pi itz 矩阵 与向量的乘积 4 。1 本章用到的定义及引理的证明 定义4 1 1 【1 1 ，1 ，。= g 。，e 剃，p i ) 巳是第1 个元素为1 的单位向量，根据 中心对称矩阵的定义，中心对称矩阵a r 9 等价于p = 彳 利用矩阵的分块，中心对称的性质，块中心对称矩阵可以写成如下形式： ( 1 ) 当n = 2 研时，中心对称矩阵可以写成如下形式： 彳：降厶1 ( 4 1 1 ) l ct ，。c j 。j 这时b ，c 都是m xm 矩阵块 ( 2 ) 当n = 2 m + l 时，中心对称矩阵可以分块成如下形式 彳：l ；乞6 髫i 1cb ，。虬j 这里b ，c r 肼“，a ，b er 刖7 ，a 是一个标量 ( 4 1 2 ) 引理4 1 1 【l 】- 【3 1定义彳是一个中心对称矩阵，那么a 正交相似到一个块 对角矩阵 证明：( 1 )如果n 是一个偶数，令n = 2 m ，选择正交矩阵 容易得到下面的关系 n 五i m 妒t l 一厶 q 7 彳q = b 一，m cb + ，。c 1 2 ( 4 1 3 ) 得到 ( 2 )如果n 是一个奇数，令n = 2 m + 1 ，选择正交矩阵 q 啦压鲁 - b - j 。c q r 彳q ：l a 【历棚6 ( 4 1 4 ) 等式( 4 1 3 ) 和( 4 1 4 ) 的右边是中心对称矩阵彳的简单形式，他们分别对应 等式( 4 1 1 ) 和( 4 1 2 ) 4 2 多水平方法的推导 对于( 2 2 3 ) 式a x = 幺r y + q 缈，对于h y 中的h a n k e l 矩阵h 可先用 ( 3 1 1 ) 式转化成中心对称t o e p l i t z 矩阵，稍后我们将具体讲到h y 的计算下 面我们来计算矽，此处丁为刀阶中心对称t o e p l i t z 矩阵由引理4 1 1 ，先讨 论以为偶数时的情况 q = 孚点甜 易知q l 为酉矩阵，有 q f r q , = 互疋 其中五= 曰一j m c ，正= b + 厶c ，则 嘲 互正k 1 3 ( 4 2 1 ) r 村，l 厄h厄 令讲y = z ，则 r z 巧= q l l 1 l ， 讲y 1 2 j 这里互，t 2 都是兰阶的实对称t o e p l i t z + h a n k e l 矩阵，那么互z - ，正z ：又是 一个t o e p l i t z + h a n k e l 矩阵与向量乘积的t - j 题至此 4 y = q n q i 豳+ q 协 2 i 丢z ：! | + q 协 这里我们可以分别对五z 。，正z ：重复上面的过程下面以互为例说明 互可以写成正= ( z + 。) z l ，此处h 。乙中的h a n k e l 矩阵h 。可先用 ( 3 1 1 ) 式转化成中心对称t o e p l i t z 矩阵，稍后我们将具体讲到h 。z 。的计算对 于实对称t o e p l i t z 结构的部分又可经过酉变换分成两部分，即 弘q h ：卜 2 那么 耻q h l 2 kl 上 j 令醇z = 7 ，则 耻q h ：卜 这里互钆正z ：都是阶为三的实对称t o e p l i t z + h a n k e l 矩阵，至此 互 五王 i_1 i_。l 9 q = = ， ， 口上 同样的道理 则 a x = qq i q 2 互z 。= 亿+ 日，) z ， _ q 2 互- l 个i y + h l 乙 1 1 2 j = 皱p 劢：卜。 编：q 2 p l 互2 儿 正：以j + 吼z 2 + 蚴p l 1 印：j + q 趴 注意五t ，正z ，正t ，正z 又都是阶为三的实对称t o e p l i t z + h a n k e l 矩阵，故对 于五，互：，互，正z 矩阵的实对称t o e p l i t z 结构部分又可以酉变换成阶为詈 的实对称t o e p l i t z + h a n k e l 矩阵，h a n k e l 结构部分可分别利用( 3 1 1 ) 式转化成 实对称t o e p l i t z 结构，而对于实对称t o e p l i t z 矩阵与向量的乘积可重复我们刚才 所讲的过程来进行计算，直到最后一步歹n 为止，此时 a x = qq l q q 巨国l 1 5 e r ， + c l + q 。n y ( 4 2 3 ) 其中等式右边第二部分e 和第三部分q 砂都是h a n k e l 矩阵与向量的乘积， 可以利用( 3 1 1 ) 式转化成实对称t o e p l i t z 结构，而对于实对称t o e p l i t z 矩阵与 向量的乘积可重复我们刚才所讲的过程来进行计算，等式右边第一部分e 哆是 二阶实对称t o e p l i t z 矩阵与向量的乘积，计算量很小这样，l 阶h e m i t i a n t 0 e p l i t z 矩阵彳当刀为偶数时与向量z 的乘积血就计算出来了下面讨 论当，l 为基数时的情形 得到 ( 2 ) 如果n 是一个奇数，令以= 2 m + 1 ，选择正交矩阵 蜴啦 压 卯盼h b 料 2 舢 q ，7 抱。= i a厄r i ( 4 2 - 4 ) l 历。互j 这里b ，c r “4 ，a ，b r “7 ，a 是一个标量其中互= b - j 。c ，疋= b + j 。c ， 嘲 互五6 廿 令讲y = z ，则有 嘲k 6 廿 1 6 f - 互 r y ：q l i 口 【- 历。6 这里仃是一个标量0 t r + x 2 a7 盯，历。b 是很容易计算的量，剩下互z 。，正z ： 是一个阶2 m 为即偶数的实对称t o e p l i t z + h a n k e l 矩阵，那么互乙，互z 2 又是 一个t o e p l i t z + h a n k e l 矩阵与向量乘积的问题至此 a y ：q n q 。一x 1 2 a r 盯 + q n b y = i l a 盯+ 7 盯i + 【凰b + t z z ：j 这里我们可以分别对正z l ，瓦z 2 重复上面的过程下面以五为例说明 互可以写成正= 亿+ 日。) z 。，此处矩阵互矩阵的h a n k e l 结构的部分h 可先用( 3 1 1 ) 式转化成中心对称t o e p l i t z 矩阵，稍后我们将具体讲到h 。z i 的 计算实对称t o e p l i t z 结构的部分又可经过酉变换分成两部分，即 那么 令彰z = y ，则 弘q h l l 2 klj 耻幺严互：k 互2 ：q 2 | - 互t 个 y l1 1 2 - j 这里互- ，互2 都是阶为三的实对称t o e p l i t z + h a n k e l 矩阵，至此 1 7 ( 4 2 5 ) 乙盯 乞，。_ 口 z反正 乙厄件 砰“伽 t i 掂厄 同样的道理 则 血= qq l q 2 互z l = 亿+ 日1 ) z i 互l y 却1 小即。 = q 正1 7 1 互：7 ： + h ，乙 疋z ：皱卜 l l + h ，z ， 疋z r ；j 2。 a o - 七压0 叮 压j m b + t 2 i y + q 。q 。 h i z 2a 仃+ 乙7 仃日：z ： + q 。局少 正jm b + t 2 2 y 注意互，五z ，正，正：又都是阶为三的实对称t o e p l i t z + h a n k e l 矩阵，故对 于互- ，正z ，正- ，正z 矩阵的实对称t o e p l i t z 结构部分又可以酉变换成阶为詈 的实对称t o e p l i t z + h a n k e l 矩阵，h a n k e l 结构部分可分别利用( 3 1 1 ) 式转化成 实对称t o e p l i t z 结构，而对于实对称t o e p l i t z 矩阵与向量的乘积可重复我们刚才 所讲的过程来进行计算直到最后一步歹n 为止，此时 a x = q nq l q 2 q ， e l 缈l + 幺卿 e 。彩。 a 叮+ 矗0 叮 e m + i m + l e f ? ( 4 2 6 ) 其中等式右边第二部分只和第三部分姨缈都是h a n k e l 矩阵与向量的乘积， 可以利用( 3 1 1 ) 式转化成实对称t o e p l i t z 结构，而对于实对称t o e p l i t z 矩阵与 向量的乘积可重复我们刚才所讲的过程来进行计算，等式右边第一部分e q 是 二阶实对称t o e p l i t z 矩阵与向量的乘积，由于阶数很小所以计算量很小这样万 阶h e r m i t i a nt o e p l i t z 矩阵4 当n 为奇数时与向量x 的乘积血就计算出 来了 4 3 多水平方法的算法及计算量的讨论 算法2 ( i ) 当n 为偶数时， 第一步通过酉变换，将r 变换成( 4 2 1 ) 式的形式 第二步 通过酉变换，将互，疋变换成( 4 2 2 ) 式的形式 第三步 重复上面的酉变换过程，知道r 矩阵的t o e p l i t z 部分变成一阶 1 9 为止，此时，通过( 4 2 3 ) 式计算a x ( i i ) 当刀为奇数时， 第一步通过酉变换，将r 变换成( 4 2 4 ) 式的形式 第二步 通过酉变换，将正，正变换成( 4 2 5 ) 式的形式 第三步 重复上面的酉变换过程，知道丁矩阵的t o e p l i t z 部分变成一阶 为止，此时，通过( 4 2 6 ) 式计算a x 算法2 的运算量为o ( n l o g n ) 下面以4 阶矩阵为例说明 算例：对于算例l 令4 阶h e r m i t i a nt o e p l i t z 矩阵a = 工= 0 ，2 ，2 ，1 ) 7 ，求a x 由算法3 可以得到a x = 7 2 7 6 6 4 4 4 8 5 一f 4 一f 2 3 一f 5 + f 8 5 一f 4 一f 2 4 + f 2 5 + f 8 5 一f 3 + f 4 + f 2 5 + f 8 ，向量 对于4 阶的h e r m i t i a nt o e p l i t z 矩阵而言，利用算法2 需要的运算量为2 0 + 8 1 0 9 2 ， 虽然较算法l 运算量没有减少，但是算法2 避开了把实对称t o e p l i t z 矩阵t 嵌 入到循环矩阵中，维数没有扩充 第五章基于分裂的快速算法计算h e r mitia nt o e pi tz 矩阵与向量的乘积 5 1 基于分裂的快速算法的推导 对于( 2 2 3 ) 式血= q 砂+ 包缈，下面我们讨论基于分裂的快速算法此处 r 为以阶中心对称t o e p l i t z 矩阵矩阵能分裂为如下形式：t = c + s 3 们 c ：1 2 s ：1 2 口0 口一l + a n l 2 口一n + 2 + 口2 a l + t 2 - n + 1t 2 2 + a - n + 2a h 一2 + a 一2a p i + a i 2 d o 2 a - n + l + 口l口- n + 2 2 口l + a n “ 2 d o + a 2d - n + 3 + a 3 222 a 0 口一l a ”- l 2 口- n + 2 一a 2 a o 口一i + a h i 2 2 a n 一2 + 口一2 2 口l + a - n + i 2 a o 口1 + a - n + 1 a 2 一a - n + 2a ”一2 一a 一2 口h i 一口一l 2 d o 口一l 一口p i 2 a - n + i 一口la - n + 2 2 口l 一口- n + l a 2a - n + 3 一口3 222 a 0 口一i 一口 一i 2 这里c 是一个循环矩阵，s 是一个反循环矩阵，于是有 砂= ( c + s ) y = + s y d o 这样一个t o e p l i t z 矩阵与向量的乘积就转化成了一个循环矩阵与向量的乘积与一 2 l 宁 也2 ；半 2 个反循环矩阵与向量的乘积的和而对于( 2 2 3 ) 式中的h a n k e l 矩阵日，我们 知道 h j = 乃 其中乃为t o e p l i t z 矩阵因而上式可转化为 a x = q r y + q h y = q r y + ( h j x j y ) = q r y + q 乙) 其中巧为t o e p l i t z 矩阵，) 为一以维向量，因而也可分裂为如下形式： 其中 1 2 1 。 2 a o a i + a n l 2 口一h + 2 + a 2 a o a i a 一i 2 a - n + 2 。a 2 t h = c h + s h a l + a - n + 1a 2 + a h + 2a h 一2 + a 一2a 月一l + a i 2 d o a 一1 + a 月一1 2 a l + a - n + i 2 a o 口一肘2 + a 2a - n + 3 + a 3 22 口0 a l + a h i 2 2 a h 一2 + a 一2 2 口l + a - n + l 2 a 0 口l + 口一h + ia 2 一a - n + 2a n 一2 一a 一2a h i a i 2 d o a i a p l 2 a j a - n + l 2 a o 2 a - n + 1 一a ia - n + 2 一a 2a - n + 3 一a 3 222 a o a l 一口n 一1 2 这里c 为循环矩阵，s 为反循环矩阵这样( 2 2 3 ) 式 2 a n 一2 一a 一2 2 口l a - n + i 2 a 0 盘2 a x = q 7 y + q 毋 = q ( 1 + $ ) + q ( + s x 山) 对于 我们可以用矩阵乘向量的算法 5 2 基于分裂的快速算法 算法3 f o rf = 1 ：以 f o rj = 1 ：刀 e n d e n d 少( f ) = c ( f ，j ) x ( j ) ( 5 1 1 ) 对于( 5 1 1 ) 式妙，c n xs z ) 也可以用到上述的算法，这样对于h e r m i t i a n t o e p l i t z 矩阵与向量x 的乘积 a x = q r y + 包缈 = q ( c y + 妙) + q ( c 0 + s x j r ) 就计算出来了这里计算量为d g 2 ) 下面以4 阶矩阵为例说明 对于算例1 令4 阶h e r m i t i a nt o e p l i t z 矩阵么= z = 0 ，2 ，2 ，1 ) 7 ，求a x 8 5 一f 4 一f 2 3 一f 5 + f 8 5 一f 4 一f 2 4 + f 2 5 + f 8 5 一f 3 + f 4 + f 2 5 + f 8 ，向量 由算法3 可以得到a x = 7 2 7 6 6 4 4 4 对于4 阶的h e r m i t i a nt o e p l i t z 矩阵而言，利用算法3 需要的运算量为2 0 + 8 1 0 9 2 ， 而不经过酉变换计算h e r m i t i a nt o e p l i t z 矩阵a 与向量z 的乘积需要的计算 量为5 6 不过，当这里的向量积是矩阵积即一个h e r m i t i a nt o e p l i t z 矩阵与另一个 刀甩阶矩阵的乘积的时候计算量会明显减少 参考文献 【1 】z y l i u ，h d 。c a o ，h j c h e n an o t eo nc o m p u t i n gm a t r i x v e c t o rp r o d u c t sw i t h g e n e r a l i z e dc e n t r o s y m m e t r i c ( c e n t r o h e r i t i a n ) m a t r i c e s a p p l i e dm a t h e m a t i c sa n d c o m p u t a t i o n ，2 0 0 5 ，1 3 3 2 1 3 4 5 【2 】z y l i u ，h f a b b e n d e r s o m ep r o p e r t i e so fg e n e r a l i z e dk - c e n t r o s y m m e t r i ch - m a t r i c e s j o u r n a lc o m p u t a t i o n a la n da p p l i e dm a t h e m a t i c s ，2 0 0 7 3 】z y l i u ，y l z h a n g ，r r a l h a c o m p u t i n gt h es q u a r er o o t so fm a t r i c e sw