（计算数学专业论文）鳞状因子循环矩阵的快速算法.pdf

摘要 由于循环矩阵类在现代科技工程领域中被广泛地应用并且有着许多特殊 和良好的性质和结构，近年来，循环矩阵类已成为矩阵理论和应用数学领域中 个非常活跃和重要的研究方向，各种新的形式和推广也相继被提出鳞状 因子循环矩阵便是其中的一类，在现代科技工程中有广泛的应用如：信号处 理、编码理论、控制理论、图象处理、图论、纠错码理论等领域 在文【2 9 】中j ，l s t u a r t 和j r w e a v e r 提出并研究了鳞状因子循环矩阵的 基本性质，岑建苗 2 5 】讨论了其谱分解及其应用江兆林等给出求鳞状因子 循环矩阵的逆阵及广义逆阵的多项式快速算法 1 6 】、e u c l i d 算法 1 8 j ，并给 出其求逆的插值算法 1 9 】本论文在一f - 述文献的基础上，给出与n 阶鳞状因子 循环矩阵相关的问题的快速算法 第一章，我们简单介绍了循环矩阵的研究现状，给出了鳞状因子循环矩阵 的定义和一些性质，同时也给出了与本论文有关的几类特殊矩阵的定义及性 质 第二章，我们借助于傅立叶变换( f f t ) ，给出一种求n 阶鳞状因子循环矩 阵的逆阵、自反邋g 一逆、群逆、m o o r e - p e n r o s e 逆的一种快速算法 第三章，我们利用f h t 技术提出求解鳞状因子循环实线性方程组新的算 法由于傅立叶变换定义在复数域上，而实际问题中的数据大多数为实数，因 此用f f t 快速求解鳞状因子循环方程组时须将实数转化为复数运算而影响效 率而离散h a r t l e y 变换定义在实数域上，同时具有类似f f t 快速算法，从 而比f f t 更加高效 第四章，我们对鳞状因子循环矩阵开平方运算进行研究，利用快速傅立叶 算法( f f t ) ，给出了一个计算鳞状因子循环矩阵的同型平方根矩阵的快速算 法，同时分析了该算法的复杂性 关键词：鳞状因子循环矩阵，快速算法，逆阵，广义逆，开平方 a b s t r a c t f o ry e a r s ，c i r c u l a n tm a t r i c e s ，w h i c ha r ea ni m p o r t a n tc o m p o n e n to ft h e m a t r i xt h e o r ya n da p p l i e dm a t h e m a t i c s b e c a u s eo fm a n yg o o dp r o p e r t i e sa n d s t r u c t u r e so fs u c hm a t r i c e s ，t h e yh a v eb e c o m eo n eo ft h em o s ti m p o r t a n ta n d a c t i v er e s e a r c hf i e l d so fa p p l i e dm a t h e m a t i c sa n dc o m p u t a t i o nm a t h e m a t i c s s om a n yk i n d so fc i r c u l a u tm a t r i c e sh a v eb e e nd i s c u s s e d ，s u c ha 8t h es c a l e d f a c t o rc i r c u l a n tm a t r i c e s ，w h i c hh a v eaw i d e l yr a n g eo fa p p l i c a t i o ni ns i g n a l p r o c e s s i n g ，c o d et h e o r y , i m a g ep r o c e s s i n g ，a n ds oo n 。 i np a p e r 2 9 ，j ls t u a r ta n dj r w e a v e rg a v et h ed e f i n i t i o no ft h es c a l e d f a c t o rc i r c u l a n tm a t r i c e sa n dd i s c u s s e dt h eb a s i cp r o p e r t i e so fs u c hm a t r i c e s c e nj i a n n f i a o 2 5 d i s c u s s e dt h es p e c t r a ld e c o m p o s i t i o no ft h es c a l e df a c t o r c i r c u l a n tm a t r i c e sa n di t sa p p l i c a t i o n s j i a n gz h a o l i na n dl i us a n y a n gp r e s e n t e daf a s ta l g o r i t h mo fc a l c u l a t i n gt h ei n v e r s ea n dt h eg e n e r a l i z e di n v e r s e o fs c a l e df a c t o rc i r c u l a n tm a t r i c e sb yt h ef a s ta l g o r i t h mf o rc o m p u t i n gp o l y n o n f i a l s 1 6 a n de u c l i da l g o r i t h m 1 8 a n da f a s ta l g o r i t h mf o rc a l c u l a t i n gt h e r e v e r s eb yu s i n go n l yi n t e r p o l a t i o nm e t h o d s 1 9 】 i nt h i sp a p e r s e v e r a lf a s ta l g o r i t h m sf o rs c a l e df a c t o rc i r c u l a n ti u a t r i e e s h a v eb e e nd e r i v e d a st h e o r e t i c a la n dn u m e r i c a le x p e r i m e n t sr e s u l t ss h o w ， t h e s ef a s ta l g o r i t h m si sv e r yu s e f u l i nc h a p t e r1 ，w eg i v eab r i e fi n t r o d u c t i o nt ot h ei m p o r t a n c ea n dt h e c u r r e n tr e s e a r c hs i t u a t i o no nc i r c u l a n tm a t r i c e s m o r e o v e r ，s o m ed e f i n i t i o n a n dp r o p e r t i e so ft h es p e c i a ls t r u c t u r e dm a t r i c e sw h i c ha r ed i s c u s s e di n0 1 1 1 p a p e r ，h a v eb e e ng i v e n i nc h a p t e r2 ，w ep r e s e n ts e v e r a lf a s ta l g o r i t h m sf o rc o m p u t i n gt h ei n v e r s e ，s e l f - r e f l e c t i v eg - i n v e r s e ，t h eg r o u pi n v e r s ea n dt h em o o r e - p e n r o s ei n v e r s eo f i i as c a l e df a c t o rc i r c u l a n tm a t r i x u s i n gff t i nc h a p t e r3 ，w ed e r i v e dan e wf a s ta l g o r i t h mf o rs o l v i n gl i n e a rs y s t e m s o ft h er e a ls c a l e df a c t o rc i r c u l a n tt y p eb yf h t a sw ek n o w ，d f ti sd e f i n e d i nc o m p l e xf i e l d h o w e v e r ，i nm a z l yp r a c t i c a la p p l i c a t i o n s ，m a n yd a t aa r er e a l s ow h e nw es o l v eal i n e a rs y s t e m so fs c a l e df a c t o rc i r c u l a n tm a t r i c e su s i n g f 门，w em u s tc o n v e r tt h er e a ln u m b e r st ot h ec o m p l e xn u m b e r sf i r s t l y , w h i c h w i l ld e c r e a s et h ee f f i c i e n c yo ft h ea l g o r i t h m b e c a u s et h ed i s c r e t eh a r t l e y t r a n s f o r m a t i o ni sd e f i n e di nr e a lf i e l da n dh a saf a s ta l g o r i t h mw h i c hi ss i m i l a r t of f t ，s o l v i n gal i n e a rs y s t e m so fs c a l e df a c t o rc i r c u l a n tm a t r i c e su s i n gf h t m i z q tb em o r ee f f i c i e n t i nc h a p t e r4 、w er e s e a r c h e dt h er a d i c a t i o no fs c a l e df a c t o rc i r e u l a n ti n a t r i o a s b yu s i n gf f t ，w p , p r e s e n t e daf a s ta l g o r i t h mf o rr a d i c a t i o no fs u c h m a t r i c e so fo r d e rna n dt h ec o m p u t a t i o nt i m ec o m p l e x i t yi sc ) ( 扎2 ) f o rc a l c u l a t i n go n er a d i c a lm a t r i x k e yw o r d s ：s c a l e df a c t o rc i r c u l a n tm a t r i c e s ，f a s ta l g o r i t h m ，i n v e r s em a t r i x g e n e r a l i z e dh l v e r s e ，r a d i c a t i o n i i i 第一章绪论与预备知识 5 1 1引言 循环( c i r c u l a n t ) 矩阵的概念是t m u i r 3 0 】于1 8 8 5 年首先提出的，初期研 究成果可参阅综述文献( 3 1 h 3 4 】) 然而，直到1 9 5 0 年至1 9 5 5 年，i j g o o d 等才分别对循环矩阵的逆 1 0 】、行列式 2 3 】以及特征值 2 6 】进行了研究近年 来，循环矩阵类已成为矩阵理论和应用数学领域中一个非常活跃和重要的研究方 向，在现代科技工程领域中被广泛地应用特别是在信号处理 2 】、编码理论 7 】、 图象处理f 2 3 7 】、纠错码理论 3 5 等领域中常常要用到这类特殊矩阵；另外，由 于循环矩阵类有许多特殊而良好的性质和结构，被广泛应用在应用数学和计算数 学的许多领域，如控制理论 1 5 】 2 2 】、最优化 1 3 、求解( 偏) 微分方程 2 5 】， 矩阵分解 2 8 、多目标央策 2 0 、预条件共轭梯度法 3 6 】、图论 1 2 、傅氏变 换 2 4 等 由于循环矩阵类在应用方面的广泛性及迅猛发展，对它的研究引起了人们的高 度重视自从1 9 5 0 年以后，它不仅受到代数学界人士的重视，而且受到了计算 数学界、应用数学界等许多领域研究人员的重视另外，关于它的理论研究方面 也得到了飞速发展，各种新的循环矩阵被相继提出+ 至今，已有几十种如：向 后( 对称) 循环矩阵、卜循环矩阵、块循环矩阵、块r 一循环矩阵和块对称r 一 循环矩阵、二重( r l ，r 2 ) 循环矩阵、块因子循环分块矩阵、块因子对称循环分块矩 阵、多重循环矩阵、鳞状因子循环矩阵、循环随机矩阵等 对循环矩阵类的研究，主要是对其代数性质、特殊性质、特殊结构、各种多项 式表示形式、对角化、谱分解、秩、非奇异性、行列式、特征值、特征向量、特 征多项式、极小多项式、逆阵、自反g 一逆、群逆及m o o r e 。p e n r o s e 逆的各种算 法、有关方程组及反问题的求解以及有关算法的计算复杂性分析特别是关于其 逆阵的快速算法和应用方面的研究最为活跃 箜达固煎墅生堕堕迭鎏差鎏 2 求解线性方程组的问题经常出现在相当广泛的实际问题中，特别是一些高阶线 性方程组的解，用克莱姆法则，当n 很大时，需要大得惊人的计算工作量因此， 对于实际求解一个较高阶的线性方程组来说，理论上十分漂亮的克莱姆法则并不 适用于是。寻求适用于计算机的切实可行的方法就是应用数学的一个重要的研 究方向循环线性方程组的求解，在线性预测、误差控制码、自回归滤波器设计 领域内起着重要作用 例如；图象恢复和重建技术中，要将图象退化的过程模型化，并据此采取相反 的过程以得到原始的图象常见具体退化模型示例 37 ，图1 - 1 给出4 种常见 具体退化模型的示意图 图1 - 14 种常见的具体退化模型 这4 神模型中，图( a ) ，( b ) ，( c ) 所示是空间不变的，而图( b ) ，( c ) ，( d ) 所示可以 是线性的下面分别介绍： ( 1 ) 图( a ) 是一种非线性退化的情况，摄影胶片的冲洗过程可用这种模型表 示摄影胶片的光敏特性是根据胶片上留下的银密度为暴光量的对数函数来表示 的，光敏特性除中段基本线性外，两端都是曲线 ( 2 ) 图( b ) 表示的是一种模糊造成的退化。对许多实用的光学成象系统来说， 由于孔径衍射产生的退化可用这种模型表示 ( 3 ) 图( c ) 表示的是一种目标运动造成的模糊退化 ( 4 ) 图( d ) 表示的是随机噪声的迭加，这也可看作一种具有随机性的退化 下面来讨论退化模型的计算，先看一维时的情况假设对2 个函数f ( x ) 和 ( z ) 进行均匀采样，其结果放到尺寸为n 。和乱2 的2 个数组对，( z ) ，z 的取 鳞状因子循环矩阵的快速算法 3 值范围是0 ，1 ，2 ，一，凡l 一1 ； 对 ( z ) ，z 的取值范围是0 ，1 ，2 ，- 一，礼2 1 借助卷积来计算g ( x ) 为了避免卷积的各个周期重叠( 设每个采样函数的周期 为肘) ，我们取m2n l + n 2 1 ，并将函数用零扩展补齐如果用，e ( 茁) 和 。( 。) ，表示扩展的函数其卷积为： m l 吼( z ) = ，e ( z ) h 。扛一m ) ，z = 0 ，1 ，m 一1 i 竺0 因为丘( 茁) 和 。0 ) 的周期为m ，所以9 e ( z ) 的周期也是m 如果用矩阵形式表 示上式可写成g = h f 或 根据危。( z ) 的周期性可知，h 。( z ) = h 。如+ m ) ，故上式中的日可进一步写成； h 。( 0 ) h 。( 一1 )k ( 1 ) 、 h 一一l e ( 1 ) h e ( o ) 。( 2 ) l 一一 i 。( m 1 ) h 。( m 一2 ) 。( o ) 这里日就是一个特殊的鳞状因子循环矩阵，退化系统是由日决定的 鳞状因子循环矩阵是一类非常重要曲特殊矩阵，在现代科技工程中有广泛蟪应 用如：在信号处理、数字图象处理、编码理论、自回归滤波器设计等领域中， 经常会遇到以鳞状因子循环线性系统的求解由于这类特殊矩阵有许多特殊而良 好的性质和结构，对其进行推广并探讨其性质和应用显得很有必要在文f 2 9 中 j l s t u a r t 和j r w e a v e r 提出并研究了鳞状因子循环矩阵的基本性质，岑建苗 1 2 5 讨论了其谱分解及其应用江兆林等给出末鳞状因子循环矩阵的逆阵及广义 逆阵的多项式快速算法 1 6 】、e u c l i d 算法【1 8 l 。并给出其求逆的插值算法【1 9 】 本文在上述文献的基础上，借助于傅立叶变换( f f t ) ，首先给出一种求n 阶 鳞状因子循环矩阵的逆阵、自反逆乎逆、群逆、m o o r e - p e n r o s e 逆的一种快速 算法；然后利用快速h a l t l e y 变换算法求解鳞状因子循环实线性方程组；最后给 出一种求1 1 阶鳞状因子循环矩阵开平方的一种快速算法 u 吣” 一 烈烈 d 砷 + + ， m m i | 和 卜卜 舰舵 ， 动秭肛” d 一 m 一k = d u 一 以以；乳 鳞状因子循环矩阵的快速算法 4 1 2 几类特殊矩阵的定义及性质 本节将给出本文所涉及到的几类特殊矩阵的定义及耜关曲性质，其中的性质 均只列出参考文献而不给出证明 设n 为大于等于1 的固定墨效，记 训= e 印( 等) = c 。s i 2 z r + i s i l l 等 其中i = 、，仁t ，i 1 为n 次本原单位根，它有下列性质： ( 1 ) 叫“= 1 ；( 2 ) 训丽= 1 ；( 3 ) _ = w 一1 ；( 4 ) 一w k = w = w 胁； ( 5 ) 1 + w + w 2 + + 叫4 1 = o ；( 6 ) 叫o + 训1 七+ + 叫( “一1 冲= o ； ( 7 ) 叫。碴+ 2 w l 自+ + r 。叫江一1 进= 一丁兰毛 定义1 2 1n 阶f o u r i e r 矩阵定义如下 r =( 1 ) 其中w = e 警，i 为虚数单位 众所周知，f o u r i e r 矩阵是酉矩阵，并且一个f o u r i e r 矩阵乘以一个向量相当 于对这一向量作离散f o u r i e r 变换( 即d f t ) 1 9 6 5 年，j w c o o l e y 给出了 著名的快速傅里叶变换算法( 即f f t ) 引理1 2 2 6 1 对长度为n 的向量作离散f o u r i e r 变换及逆离散f o u r i e r 变换 所需的运算量及存储空间均为o ( n l o a n ) 查誓 。事而而，扣而 坐 。而。而铲而矿丽。而上面。而，而 定义1 2 3n 阶c i r c u l a n t 矩阵定义如下z g = c ( t 1 ，x 2 ，一，。) = z lz n x 2 ；e 1 孔3 ：2 霈n z n 一1 - 2 = 2 x 3 敏 ： 苴1 显然，c i r c u l a n t 矩阵完全由它的第一列元素确定1 9 7 4 年，d h e l l e r 证 明了如下定理 弓l 理1 2 。4 ( 1 4 1 若c 为n 除c i r c u l a z l t 矩降且它的第一列为嚣= ( z 1 ，。2 ，一，。) t ： 则r c k r h - - d i a g ( 击r z ) ，即c i r c u l a n t 矩阵可以被f o u r i e r 矩阵对角化 引理1 2 5 1 4 1 计算一个n 阶c i r c u l a n t 矩阵c j 与任一1 1 维向量的乘积所需 的计算量为o ( n l o g n ) 由引理1 2 4 和引理1 2 5 ，容易推出 定理1 。2 ，6 隶解系数矩阵为n 陡c i r c u a n t 矩阵的线性方程组所需的运算量 为o ( n l o g n ) 。 4 乱 鳞状因子循环矩阵的快速算法 6 1 3 鳞状因子循环矩阵的定义及性质 以下设j i 靠为复数域上所有扎阶方阵组成的集合 定义l 3 1 1 2 9 1 设c 为n 阶基本循环矩阵，印c = c i r c ( o ，1 ，0 ，- ，o ) ，而 d = d i a g ( d 1 ，d z ，矗) 且为非奇异的记r = d c ，称r 为基本鳞状因子循 环矩阵 定义1 3 2 1 2 9 1 对于螈中的矩阵a ，如果满足a 冗= 冗a ，则称a 为鳞状 因子循环矩阵，如果d = d i a g ( 1 ，1 ，一，r ) ，那么鳞状因子循环矩阵就是卜循环 矩阵，因此鳞状因子循环矩阵就是r - 循环矩阵的推广用r s c 靠表示慨中 的所有与r 可换的鳞状因子循环矩阵组成的集合 引理1 3 3 2 9 】a r s c 且靠的充要条件是a = y ( n ) ，其中，( 茁) = a i 百1 x 规定鳓= 1 ，印= i ，i 为n 阶单位阵，称f ( x ) 为a 的表示多项式 由于“o ，a 一，n 。一1 正好是a 的第一行元素，为方便，此时记 a = s c a c i r r ( a n ，n 1 ，r ，8 n 一1 ) 引理1 3 4 兄的特征多项式和极小多项式都是妒一d ，d 2 d n 证明tr 的特征多项式 9 ( x ) = z 0 0 一以 - d 1 z -_ 0 0 0 0 厶一1 z x “一d l d 2 磊 由于d 为非奇异的对角阵，所以d l d 2 如0 ，故g ( x ) 在复数域上有n 个不 同的特征根，所以r 的特征多项式与极小多项式相同 引理1 3 5 2 5 1设a = s c n c i r 冠( 铂，8 l ，一1 ) 是复数域上的一个鳞状因 子循环矩阵，f 是一个f o u r i e r 矩阵且满足 南= 而l 础胖。一1 1 ，1s i ，j 礼 。喝；|o o 其中= e x p ( 譬) 是n 次本原单位根，且设= d i a g ( t f l ，如，厶) 并且满 足 吗+ l = 石d 砖，1 js n ，1 = 6 l 则a = ( a f ) d i a g ( a o ， l ，一，a j ，- 一，a 。1 ) ( f ) ，且a 的特征值是 j = 0 ，1 ，一，n 一1 其中d = “兀巩0 vt = l 引理1 r 3 6 2 5 1 设a s r c m ，若a 是非奇异矩阵，则a 一1 s r c 螈；若 a 奇异，则a 8 = 川r s c m ，如果还满足d d + = k i ( k 为正实数) ，则 a + r s c 磊。，且a + = a 4 引理1 3 7 1 2 5 1a s r c m , ，f = d i a g ( 1 ，酊1 d ，0 1 扩一1 ) 其中d = nd t 0 ，k i = d l d 2 d i ，( i = 0 ，1 ，一，咒一1 ) ( f 是文 2 9 中a 的改进) ，则 a 7 = f - 1 a f 是一个循环矩阵，且其首行元素为( n m a l d k 7 1 ，a * * - t d n - 1 砖0 1 ) 。 引理1 3 8 设a ，b s n c m , , ，则a b = b a s r g m 。 证明t 由于a ，b s r c 坛，则存在，( 茁) ，g ( x ) 满足a = ，( r ) ，b = g ( 兄) ， 又因为f ( x ) a ( x ) = 9 扛) ，( z ) 令z = r ，得f ( n ) g ( r ) = 9 ( 兄) ，( r ) ，即a b = b a s r c 呱 引理1 3 9 1 2 1 1 设 冠 留为p q 矩阵序列，做下列变换： 巧= 置t ”挈，j = 0 ，1 ，n 一1 则其逆变换式为 ：。萎州iu，：0xi 1 i 0 ，1 ，亿一1 则其逆变换式为= 。州i u ，= ，亿一 ，= u 勃 也 垮 n = 蛾 “ = b 鳞状因子循环矩阵的快速算法 8 1 4 广义逆 定义1 4 1 设有下列5 个方程 a b a = a b a b = b f a b ) 4 = a b f b a ) + = b a a b = b a ( i ) ( i i ) ( 谢) ( 伽) ( 郇) 则称满足方程( i ) ( i i ) ( i i i ) ( i v ) 的矩阵b 为a 的m o o r - p e n r o s e 逆，记为a + ；称 满足方程( i ) ( i i ) 的矩阵b 为a 的自反9 一逆，记为川1 ，2 ；称满足方程( i ) ( i i ) ( v ) 趵矩阵8 为a 的群逆，记为a t l ，2 ，5 或；称满足方程( i ) ( i i ) 且其非零特征值 是a 的非零特征值的倒数的矩阵日为a 的谱逆，记为a 8 引理1 4 2 若矩阵a 非奇异，则线性方程组a x = b 的唯一解为z = a b 。 若矩阵a 奇异且线性方程组a x = b 有解，则a x = b 的通解为 z = 4 1 , 2 6 + ( 厶一a ( 1 ，2 1 a ) y 其中y 是任意的扎维列向量。 本文采用下面一些基本符号 d f t f f t d h t f h t c m r s c m s c a c z r r 离散傅里叶变换 快速傅里叶变换 离散h a r t l e y 变换 快速h a r t l e y 变换 循环矩阵 复数域中所有与r 可换的鳞状因子循环矩阵组成的集合 鳞状因子循环矩阵 鳞状因子循环矩阵的快速算法 1 0 第二章鳞状因子循环矩阵求逆的快速算法 2 1 算法推导 定理2 1 1 设n 阶可逆鳞状因子循环矩阵a = s c a c i r r ( a 。，铆，a n 1 ) = ，( r ) ，其中，( z ) = n 三- i l 七= 1 矿为a 的表示多项式， 乜= d l d 2 - d i ( i = 1 ，2 ，一，一1 ) ，= 1 若a q = s c 主r r ( ，5 1 ，t 一，一1 ) = 吠兄) ，其中 9 ( z ) ：宅6 t k t 矿，为a 一1 的表示多项式，则g ( d 训) ：，( d 叫，) 证明：由引理1 35 知的a 特征值为f ( d w j ) ，j = 0 ，1 ，n 一1 , a _ 1 的特征 值是g ( d w j ) ，j = 0 ，1 ，一，n 一1 ，故f ( d w j ) = g ( d w j ) 一 定理2 1 2 设n 阶鳞状因子循环矩阵a = s c a c i r r ( a o ，a l ，a 。一1 ) 可逆，且 其逆阵a 一1 = 5 西强( ，挽，一，b n - 1 ) 一n - i 岛百1 r ，则 玩2 ：觑菩( 托i ) 叫，( d ) 1 证明：设a = s c a c i r n ( a o ，a o ，一，a n - 1 ) ，由引理1 3 5 得： a = ( a f ) d i a g ( a o ，a 1 ，一，a 。一1 ) ( f ) - 1 于是 ( a f ) 一a ( a f ) = d i a g ( x o ，a 1 ，a 。一1 ) 类似地，( a f ) - 1 a _ 1 ( a f ) 一d i a g ( t l o ，t 1 ，一，心，t 一，p 。1 ) ，其中 心= ，( 凼峨) 一1 = 吼舟f 1 ( d w ：) 4 ，j 一0 ，1 ，n 一1 t = o 从而 ，= ( n f ) 一1 a ( a f ) ( a f ) 一1 a 一1 ( a f ) = d i a g ( a o p o ， l p l ，a 。一1 p 。一1 ) 鳞状因子循环矩阵的快速算法 l l 即1 = a ，如= ，( d 峨) n 爵- - 1 订1 ( d 她) 由引理1 3 9 得： 玩= ：觑n 邑- - i ，( 如i ) 一1 ( d t 蟛) 一证毕口 类似可得如下结论t 定理2 1 3 设a = s c a c i r n ( a o ，a o ，a n - 1 ) 是一个奇异的鳞状因子循环矩 阵，则 a 5 = a l = s c a c i r r ( b o ，b l ，一，k 一1 ) 其中阢= 觑蔓a ；_ ( 蟛) 一 弘 苫簪兰：= 薹卅( 蚓驴，扩， k i 2 d t d 2 - 哦( 扛1 ，2 ，n 一1 ) ，= 1 , d = n = l d t o ，w n 28 印( 等) 若d d 4 一k i ( k 为正实数) ，则a + = a t 由定理2 1 2 、定理2 1 3 ，我们得到求n 阶鳞状因子循环矩阵的逆阵、自反 逆g - 逆、群逆、m o o r e - p e n r o s e 逆的快速算法2 2 1 ，其步骤如下： 设a = s c a c i r n ( a o ，a o ，- ，a n a l ) s t e p1 求方程扩= d l d 2 如的n 个不同的根拙，j = 0 ，1 ，- 一，n 一1 s t e p2 由( x ) = 毗f 1 岔，如= d l d 2 也( t = l ，2 ，r 一，竹一1 ) ，k o = 1 ， 算出b = ，( d 加：) ， 若o ，j = 0 ，1 ，一，n 一1 ，则a 非奇异，转s t e p3 ； 若如= 0 ，j = 0 ，1 ，一，n 一1 ，则a 奇异，转s t e p4 ； s t e p t3 由魄= j 赶e ，( 托i ) _ 1 ( 螂) 一，从而得到a _ 1 = s c a c i r n ( b o ，b l ，一，h n 一1 ) j = l j s t e p t4 算出譬，坟= 。1 n 急- t ，_ + 。i ) 一，从而得到 = a 4 = s c a c i r 冗( b o ，6 1 ，k 一1 ) 上述算法的第一步为离散f o u r i e r 变换( d f t ) ，第3 步及第4 步可采用快 速f o u r i e r 变换( f f t ) ，其计算复杂性为o ( n l o g ) 箜迭圈至遁堑堑睦塑遮望篡鎏 1 2 2 2 数值例子 i 234 、 例2 _ 3 1 判断矩阵a = 8 z ；14 ：荨8 ) 的非异性，若矩阵a 可逆求321， 解由于矩阵a 可表示成a = j4 - 2 r + i ( r ) 2 + ( r ) 3 ， 其中r = d c 个鳞状因子循环矩阵 步1 解方程x 4 1 6 = 0 ，得4 个根分别为2 ，一2 ，2 i ，一2 i 步2算出( a o ，a 1 ，儿，a 3 ，) = ( 1 5 ，一1 ，一5 ，- 5 ) ，由于0 ，j 故a 为非奇异阵， 步3 由b i = ；k ；毫f ( d w j ) 一1 ( 州) 一。算出( 6 0 ，6 ，6 z ，6 3 ) = 去( i = 0 于是a 一1 = s 西r c 兄( 寻，丽2 ，吾，击) = 击 = 0 ，1 ，2 ，3 ， 一5 ，2 ，一1 ，4 ) 一 是 a 以所 、， 0 o l o o 。o o 妒 l o 0 0 0 o o l 1 2 ，o+ = 妒 、i，32 0 o o 2 + 0 o 4 o 勘 o 2 o 。h 1 o 0 o = ；l砧 i l “ d 、， 4 4 8 巧 1 4 七22 西4 l o 叫o ， 鳞状因子循环矩阵的快速算法 1 3 第三章鳞状因子循环线性系统的快速h a r t l e y 变换算法 3 1 引言 由于傅立叶变换定义在复数域上，而实际问题中的数据大多数为实数，因此用 f f t 快速求解鳞状因子循环方程组时须将实数转化为复数运算而影响效率近年 来，实值变换开始在信号处理和其他领域发挥越来越重要的作用，而离散h a r t l e y 交换1 1 1 定义在实数域上，同时具有类似f f t 的快速算法，从而比f f t 更加 高效本章利用f h t 技术提出求解鳞状因子循环方程组新的算法，运算量约为 6 ? 叼f ，为f f t 算法的i 3 当线性方程组无解时，本文建立鳞状因子矩阵的 m o o r e p e n r o s e 广义逆与h a r l e y 变换矩阵之间的关系，给出了快速计算最小二 乘解的一般形式，计算其中一特解运算量仍约为6 n l o g 本文只讨论实线性方程组的求解。 3 2 用f 日t 快速求解鳞状因子循环线性方程组 考虑线性方程组 c x = b ( 3 ) 其中z ，b 是n 维向量，c 是i 阶鳞状因子循环矩阵 若d = d 兀d t 0 ，由引理1 3 7 知，a = r _ 1 g i 、是一个循环矩阵，设 虿= f 一1 茁，5 = f 一1 b ，贝0 方程( 3 ) 变为 g z = b ( 4 ) 鳞状因子循环矩阵的快速算法 1 4 上述表明鳞状园子循环线性方程组可通过循环线性方程组求解得到，因此本 文仅讨论循环线性方程组的快速求解首先简要描述循环线性方程组的f f t 算 法过程 ( 1 ) 计算序列 的广义d f t ( g f t ) 和序列 b d 的广义逆d f t ( i g f t ) 嘉塾一狲，小- ( 5 ) ( 2 ) 计算 巍= i ，善警兰吉 c e ， ( 3 ) 计算序列 巍 的g f t 得到 z ：基反训* ，：o 1 2 ，一1( 7 ) 当 k ， c k j 是实数时，用f f t 计算( 5 ) 一( 7 ) 式需实乘和实加总数约为 1 5 n l 0 9 2 n ，而循环线性方程组的求解算法实运算量总计约为1 0 n l 0 9 2 n 8 3 。2 1 非奇异循环线性系统的快速求解 首先引进离散h a r t l y 变换( d h t ) 的概念 实序列 n 。) ，札= 0 ，1 ，2 ，一，n 一1 的定义为 耻豢衄s 萼肛叭忍卅 其中c d s n = c o s a + s i n q 设h o = x o ，6 d = b o ，h i = x n 一1 ，以= b n 。i = 1 ，2 ，- ，一1 则方程组( 3 ) 有下列等价形式 k = c 。h ( 。一。 。，m = 0 ，1 川2 一，n 一1 ( 9 ) h u n u 脚 | | q 鳞状因子循环矩阵的快速算法 其中 表示关于模的最小非负剩余 假定k ，和h 。的d h t 分别是风，g ，皿，设b = 岛，c n = c b ，h n = 凰现在讨论取，g ，矾之间的关系 定理3 2 1 设 则 d 七= 互1 、c 女+ 圆一，e 女= ；( g 一一，南= o ，1 ，2 ，一1 b k = d k 风+ e k h n 一，南= 0 ，1 ，2 ，一，一1( 1 0 ) 又若( d k ，e k ) ( 0 ，0 ) 则 h k = d a b k 一b + e 2 证明：首先证明( 届) 成立事实上 k = 0 ，1 ，2 ，n 一1 ( 1 1 ) 靠= 窆蝴s 等恿= 窆埘n 萼， z ，一， n = 0 。 n = 0 1 c s 2 k ( n l 广+ n 2 ) t r = c n 8 2 k n r l r r c 。5 2 k n r 2 r c + s 2 k n l ( 面n 一- k ) t r s m 2 k n r 2 r“5 丙7 2 8 叮一5 矿一+ 8 面一8 m r 因此 b k 2 七( 一n 1 ) r r 衄5 。厂 2 n l ( n 一七) 2 3 严 ：n 三- lk s 学= n - 1 羔n - 。1 k n m c n s 可2 f f e t v ：k s 2 铲= k n m c n s 矿 n = un = u m = u 。 笔1 羔。n 一 n h mc a 8 、 c h m = on = 0 皇1 笠1 。礼一竹t s 学c 。s 可2 k r r t t r + c a s 业蛐ns 讥学】 m = 0n = 0 1 。 = 点n - 。1 。n 圣- 1 。 小s 学c o s 学+ c a s 哕芦s 伽擎】 一d k i t k + e h n k 鳞状因子循环矩阵的快速算法 则 ( 1 0 ) 式成立在( 1 0 ) 式中用一k 代替k 并注意到d k = d 一女，e k = 一e 。一k b k = d k h n k e k 风，k = 0 ，1 ，2 ，n 一1 ( 1 2 ) 若( d k ，e ) ( 0 ，0 ) 由d k ( 1 0 ) 一x ( 1 2 ) 知( 1 1 ) 成立 现在讨论( d k ，e k ) ( 0 ，0 ) 的条件由于 也+ j e k = c r | 嵋，w 。= e x p 2 r j ，j = 了 n = 0 因而d k + j e k 构成循环矩阵c 的全部特征值 8 1 _ 当c 可逆时( d k ，e k ) ( 0 ，0 ) 对k = 0 ，l ，2 ，一，n 一1 成立设 2 酊d i 哥，胁2 虿- - 暖e i ，诘o ，1 ：2 ，一1 定义排列矩阵j = ( ，) ，0 i ，jsn l ，1 1 = ( 五，j ) ( ，0si ，j 茎n 一1 满足 五一= 1 誓委毳2 。ri + 。= ，。j 7 ：；| 1 ) = 1 。, ，i 其+ 他j = 一1 矩阵g = d i a g ( a o ，n 1 ，血一1 ) + j l d i a g ( g 一1 ，鼬一2 一，阮) 日= ( c n s 等) 铀肛l 其中e o = 0 ，h 是一个h a r t l e y 变换矩阵，因而满足h 一1 = h 1 4 定理1 可 描述为下列矩阵形式，即有 定理3 2 2d k ，e k 与定理3 2 1 相同，矩阵g 可逆，则( d k ，e k ) ( 0 ，0 ) 对 k = 0 ，1 ，2 ，n 一1 成立且 而( 3 ) 的解可表示为 c 一1 = j h g h j z = j h g h j b ( 1 3 ) ( 1 4 ) 鳞状因子循环矩阵的快速算法 1 7 从( 1 4 ) 知循环线性方程组可通过两次换序( j 与向量乘积) ，三个d h t 以及一 个矩阵g 与向量乘积得到，由于n 点通过 f 硝一百n 次实乘以及；f d 9 一； 次实加得到 4 ，故总的运算量约为6 n l o g ，约为d f t 算法的； 3 2 2 奇异循环系统的最小二乘解 我们知道，线性方程组的最小乘解与系数矩阵的m o o r e - p e n r o s e 广义递有着 密切的关系，因此本节讨论的c 广义逆求法由前面的讨论知道，仅需讨论循环 矩阵地广义逆。 设o q ，屈含义与定理3 2 1 中相同，令 q ：= 。j 擞。引0 g = 豁垮0 l 对g = d i a g ( a o ，一，q v 一1 ) + 1 l d i a g ( 踟一1 ，风一2 一阮) 中元素n 。，觑 分别用n ：，觑代替得到新的矩阵g ，则有 定理3 2 3 若循环矩阵c 奇异，则其广义逆c + 满足 c = j h g 。h j ( 1 5 ) 其中z 日与定理3 2 1 中相同 证明：设d = d i a g ( d o ，d l ，一，d n 一1 ，e = d i a g (