（应用数学专业论文）几类循环矩阵的算法及其反问题的最小二乘解.pdf

摘要 循环矩阵是一类很重要的特殊矩阵，日益成为应用数学领域中一个非常活跃 和重要的研究方向 本支在几种常见的循环矩阵的算法和反问题的最小二乘解方面做了一些工作， 具体如下： 1 首先给出了，一循环矩阵的反问题的最小二乘解的存在性定理及它的一般 表示，并证明了逼近矩阵的存在唯一性量给出它的具体表达然后，给出了一种判 断对称，一循环线性系统是否有解的快速算法和并行算法 2 首先给出了一种求打阶鳞状因子循环矩阵的逆阵、自反g 一逆、群逆、 m o o r e - p e n r o s e 逆的快速算法，然后给出了计算两一阶鳞状因子循环矩阵之乘积 阵的一种快速算法，最后，给出了一种判断鳞状因子循环线性系统是否有解的快 速算法和并行算法 3 首先给出了一种求玎阶置换因子循环矩阵的逆阵、自反g 一逆、群逆、 m o o r e - p e n r o s e 逆的快速算法，然后给出了计算两一阶置换因子循环矩阵之乘积 阵的一种快速算法最后给出了其反问题的最小二乘解的存在性定理及它的一般 表示，并证明了逼近矩阵的存在唯一性且给出它的具体表达式 关键词：，一循环矩阵 鳞状因子循环矩阵 对称，一循环矩阵 置换因子循环矩阵 a b s t r a c t c i r c u l a n tm a 打i c e sh 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 da c t i v er e s e a r c h f i e l d so f a p p l i e dm a t h e m a t i c si n c r e a s i n g l y , i nt h ep a p e r 。、) v ei n t r o d u c eo u rs o m ew o r ki na l g o r i t h m sa n dt h el e a s t - s q u a r e s o l u t i o n so f i n v e r s e p r o b l e m s f o rd e t a i l ，w e c o n c l u d et h e ma sf o l l o w s ： 1 。t h el e a s t - s q u a r es o l u t i o n so fi n v e r s ep r o b l e m sa n dt h eo p f i m a la p p r o x i m a t i o n p r o b l e m sf o rt h er - c i r c u l a n tm a t r i xa l ed i s c u s s e d t h e n t af a s ta n dp a r a l l da l g o r i t h m f o rd e t e r m i n i n gw h e t h e rs y m m e t r i cr - c i r c u l a n tm a t r i xl i n e a rs y s t e mi ss o l v a b l eo rn o t i sp r e s e n t e d 2 af a s ta l g o r i t h mf o rc a l c u l a t i n gt h ei n v e r s ea n dm o o r e - p e n r o s ei n v e r s eo ft h e s c a l e df a c t o rc i r e u l a n tm a t r i xi sp r e s e n t e d t h e n ，af a s ta l g o r i t h mf o rt h ep r o d u c t so f t h es c a l e df a c t o rc i r e u l a n tm a t r i xi sg i v e n f i n a l l y af a s ta n dp a r a l l e la l g o r i t h mf o r d e t e r m i n i n gw h e t h e r s c a l e df a c t o rc i r c u l a n tm a t r i xl i n e a rs y s t e m si ss o l v a b l eo rn o ti s p r e s e n t e d 3 af a s ta l g o r i t h mf o rc a l c u l a t i n gt h ei n v e r s ea n dm o o r e - p e m o s ei n v e r s eo ft h e p e r m u t a t i o n f a c t o rc i r e u l a n tm a t r i xi sp r e s e n t e d t h e n , af a s ta l g o r i t h mf o rt h e p r o d u c t o f t h e p e r m u t a t i o nf a c t o rc i r e u l a n tm a t r i x i sg i v e n f i n a l l y ，t h el e a s t - s q u a r es o l u t i o n s o fi n v e r s ep r o b l e m sa n dt h eo p t i m a la p p r o x i m a t i o np r o b l e m sf o rt h e p e r m u t a t i o n f a c t o rd r e u l a n tm a t r i xa r ed i s c u s s e d k e y w o r d s ：r - c i r e u l a n t m a t r i x s y m m e t r i cr , e i r c u h m tm a t r i x s c m e df a c t o re i r e u l a n tm a t r i x p e r m u t a t i o nf a c t o rc i r c u l a n tm a t r i x 创新性声明 y 6 9 5 7 0 8 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 日期：盈匹厶华 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印，缩印或其他复制手段保存论文。( 保密的论文 在解密后遵循此规定) 本人签名： 导师签名： 坶 社 日期：滥 如 b 凝t 矽j i 1 辱 第一章绪论与预备知识 第一章绪论与预备知识 本章首先介绍了循环矩阵类的研究现状及几种常见循环矩阵，其次给出了在 矩阵理论和矩阵计算中经常用到的矩阵的k r o n e c k e r 积、置换矩阵、f o u r i e r 矩 阵、正规矩阵及广义逆等基本概念和一些基础知识最后说明了全文的主要内容 及具体安排 1 1 循环矩阵类的研究现状 循环矩阵的概念是t m u i r 【l 】于1 8 8 5 年首先提出的，他对其进行了一些研究 ( 参阅文献【2 ，5 】) 然而，直到1 9 5 0 年至1 9 5 5 年i j g o o d 等才分别对循环矩 阵的逆、行列式以及特征值( 参阅文献【6 1 0 】) 进行了研究近年来，循环矩阵类 已成为矩阵理论和应用数学领域中一个非常活跃和重要的研究方向，在现代科技 工程领域中被广泛地应用例如在信号处理、图象处理、小波变换、优化设计、自 回归滤波器设计等领域( 1 1 1 - 1 7 1 ) 常常要用到这类特殊矩阵另外，由予循环矩 阵类有许多特殊而良好的性质和结构，已被广泛应用在应用数学和计算数学的许 多领域如最优化、矩阵分解、多目标决策、图论、傅氏变换等( 【1 8 3 2 】) 由于循环矩阵类在应用方面的广泛性及迅猛发展，自从1 9 5 0 年以后，对它的 研究引起了人们的高度重视它不仅受到代数学界人士的重视，而且受到了计算数 学界、应用数学界等许多领域研究人员的重视。另外，关于它的理论研究方面也 得到了飞速发展迄今为止，对于经典循环矩阵的所做的研究已有很多同时。 各种新的循环矩阵被相继提出至今，已有几十种如：r 一循环矩阵【3 4 4 3 】，向 后( 对称) ，一循环矩阵 3 7 - 3 8 。4 4 - 4 5 ，鳞状因子循环矩阵 4 6 - 4 7 ，置换因子循 环矩阵【4 8 】等在文 4 6 - 4 8 的基础上，我们在第三章进一步讨论了鳞状因予循环矩 阵；在第四章进一步讨论了置换因子循环矩阵 求解线性方程组的问题经常出现在相当广泛的实际问题中，特别是一些高阶 线性方程组的解。用克莱姆法则，当_ ，l 很大时，需要大得惊人的计算工作量因 此，对于实际求解一个较高阶的线性方程组来说，理论上十分漂亮的克莱姆法则 并不适用于是，寻求适用于计算机的切实可行的方法就是应用数学的一个重要 的研究方向循环线性方程组的求解，在线性预涮、误差控制码、自回归滤波器设 计领域内起着重要作用我们在2 2 给出了对称，一循环线性方程组求解的快速 算法：在3 5 ，给出了鳞状因子循环线性方程组求唯一解的快速算法 2西安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最4 , - - - 乘解 对给定的1 维向量x 和b ，求某类玎阶矩阵4 。使其满足出= b ，称为线性方 程组血= b 的反问题矩阵反问题在电学和自动控制中有着广泛的应用例如，为 了考察线性系统、建立数学模型、认识或推测该线性系统内部的结构和特性，需 要分析线性系统输入和输出的线性关系 4 9 5 1 ，这就归结为一个矩阵反问题近年 来，对矩阵反问题丘r = b 的研究己取得一系列的结果【5 2 】。获得了解存在的条件， 但由于实际问题中z ，b 由实验给出，很难保证满足矩阵反问题解存在的条件，因 此有必要研究其最 b - - 乘解。我们在2 1 和4 5 中分别就，一循环矩阵和置换因 子循环矩阵反问题的最t b - 乘问题及其最佳逼近问题进行探讨 关于循环矩阵类的研究，主要是对其代数性质、特殊性质、特殊结构、各种 多项式表示形式、对角化、谱分解、秩、非奇异性、行列式、特征值、特征向量、 特征多项式、极小多项式、逆阵、自反g 一逆、群逆及m o o r e - p c o z o s e 逆的各种算 法、有关方程组及反问题的求解以及有关算法的计算复杂性分析特别是关于其 逆阵盼决速算法和应用方匾 1 1 3 2 1 的研究最为活跃 下面介绍几种常见循环矩阵 定义1 1 1 【”如下形状的矩阵 a = 称为循环矩阵，为方便，记为a = c i r c ( c o ，c 1 ，c 2 c c ) 定义1 1 p 3 1 如下形状的矩阵 a = 称为斜循环矩阵，为方便记为a = c i r c i ( ，c i ，c 2 ，。) 定义1 1 3 如下形状的矩阵 a = c oc | c ic 2 c 2c 3 c qc o c 一一2o c ic o o l c c p 2 纠彬7“ 钆； 勺q ；岛q钆：吒 l 2 气o；q 印印印；办 ； 一 ； 3 吒q ；叼q q ； q；吨 吨 气；叩 办一一以 以岛“；n 第一章绪论与预备知识 称为向后( 对称) 循环矩阵，记为4 = r e t r o c i r c ( c o ，c l ，c 2 ，c 月一1 ) 定义1 1 4 如下形状的矩阵 一= 称为g - 循环矩阵( 其中g 为任意整数，下指标以模疗同余，即；如果f = j ( m o d n ) ， 贝0 口，= 口j ) ，记为4 = g - c i r c ( c o ，c l ，c 2 ，c 。- i ) 1 2 矩阵的k r o n e c k e , r 积 定义1 2 1 设一和占分别是m 啊p x 口阶的矩阵，则称如下分块矩阵 4 8 b = 口l i 曰a 1 2 b a h b a 2 1 ba b a 2 b ：!i ； q m l ba m 2 b a b 为彳与b 的k r o n e c k e r 积，简记为彳o b 显然a o b 和丑0 a 是同阶矩阵，但一般说来彳固b 簪雪0 彳 k r o n e c k e r 积有下述重要性质 ( 1 ) ( 鲥) o 占= 4 0 ( a 田) = 口( 4 0 功，口是纯量 ( 2 ) ( 一+ 功0 c = ( 彳0 占) + ( 口0 c ) ( 3 ) a o ( 暑+ c ) = ( 彳。聊+ ( o c ) ( 4 ) 爿o ( b o c ) = ( 爿。曰) o c ( 5 ) ( 0 b x c o d ) = ( 爿c ) 9 ( b 研 这里4 c ，b d 均有意义 性质( 5 ) 还可推广成更一般的形式： ( 5 。) ( 4 0 以o 固一p ) ( 县9 丑2 0 一。固b p ) = 4 马0 4 如9 圆z ，b p ， 和( 4 0 马) ( 4 ：o b z ) ( 一，o b p ) = ( 4 一，) o ( 盈b 一4 ) 1山； 0取即丫以 n 时 ： 如一喜i 。 口 + h q茔西舻即 4西安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最小= 乘解 上面两个式子只要等号右边有意义，则左边也有意义，而且两边相等 ( 6 ) 设4 、b 非奇异，则a 圆b 也非奇异，且( 一。丑) = a “o b ( 7 ) ( o 动。= a 7o b 7 ；( a o b ) = a 圆b ( 8 ) 设爿、b 为复矩阵，有a 固b ：j o 百 ( 9 ) 设a 为胧阶复矩阵，b 为h 阶复方阵，分别有特征值，a 2 ，a 。与 屈，屈，成则a o b 为川一阶复方阵，其特征值为q ，1 i s 小。1 s ，s ，1 ( 1 0 ) d e t ( a o 鳓= ( d e t , 4 ) ”( d e t b ) ” ( 1 1 ) t r ( a o b 、= ( t r ( a ) x t r ( b ) ) ( 1 2 ) 因方阵的秩等于该方阵的非零特征值( 记入重数) 的个数，所以有： r a n k ( aob 、= r a n k ( a ) r a n k ( b ) ( 1 3 ) 两个方阵的k r o n e c k e r 积往往可以保持原方阵的一些性质，因此有结论： 设a 、b 分别为m ，拧阶复方阵，若4 与b 皆为正规( 酉、h e m f i t e 、对称、h e r m i t e 正定、h e r m i t e 正半定) 矩阵，则一。占为m ，l 阶复矩阵，它也是正规( 酉、h e r m i t e 对称、h e r m i t e 正定、h e n n i t e 正半定) 矩阵 ( 1 4 ) k r o n e c k e r 积虽不满足交换律，但可以通过对行、列的置换把一0 b 化成 b o a 即，存在，印阶和w 阶置换方阵只q 使 h a o 功q = ( b o 爿) 特别地，当m - 啪，p i 鼋时，一定存在冲l p 阶置换方阵p ，使p 臼0 8 ) p 7 = b o a ( 1 5 ) 设伊y ) = x 。y ta 和b 分别是m 阶和一阶方阵， p , o i o 伊( 爿，功= 艺彳o 矿，那么伊( 爿，国的特征值是 j l o l 曲 p ( 4 ，以) ，= l ，m ，s = 1 ，疗， 其中以和雎分别是一和口的特征值 ( 1 6 ) a ，ko 戤= ( 以。o i b ) ( i 。o 氏) 7 1 3 置换矩阵 定义1 3 1 如果矩阵p 在它的每一行和每一列只有一个元素为i ，而其余所有 第一章绪论与预备知识 的元素均为0 ，则称p 为置换矩阵 一般地，一个置换矩阵左乘或右乘一个向量，相当于对这个向量的各个分量 进行重排矩阵4 左乘以一个置换矩阵p 就是互换彳的行，而矩阵a 右乘以一个 置换矩阵p 就是互换a 的列 置换矩阵的行列式是l 或- 1 ，因而置换矩阵一定是非奇异的虽然置换矩阵关 于乘法一般是不交换的，但两个置换矩阵的乘积还是一个置换矩阵显然对每个置 换矩阵尸，有p 7 = p 因为。如果置换矩阵p 以某种方式互换行，则p 7 ：p 一就 以同一方式互换列，所以，变换爿寸，p r 以相同的方式互换么的行和列，这个 变换相当于重排诸元的足码 下面介绍三个重要的、在循环阵理论中扮演了最基本角色的置换阵： ( 1 ) 基本循环置换矩阵： ol 00 00 1o o o l0 o 1 0o 容易证明 疗7 = 疗= 石= 厅”丌4e l 。 ( 2 ) 后向单位置换矩阵 k = o0 ol oo 1o 1o oo 易证 k = k 。k 2 = l ，k = k 一1 ( 3 ) 分块后向单位置换矩阵： k = 0 0 0 ， 0 0 厶0 ，- 0 0 0 易证 鼯k 。k 2 = k ，k _ k 1 4f o u r i e r 矩阵与正规矩阵 设一为大于等于1 的固定整数，记 ( i - 2 ) ( i - 3 ) 6西安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最小= 乘解 ：罂1 ：c o s 垒+ fi n 望(1-4)exp g i n1 - 4 = 卜j = c o s 一+ l l nhn 其中i = 一1 ，为，2 次本原单位根，它有下列性质： ( 1 ) ”= 1 ；( 2 ) 五= l ；( 3 ) 石= 脚一1 ；( 4 ) 国= 由= “一； ( 5 ) 1 + 脚+ 2 + + 国“= 0 ；( 6 ) o + 彩1 4 + + 国o - i ) = 0 ； ( 7 ) m o + 2 c o l + + 玎( n - i ) k ：一三 1 一 n 阶f o u r i e r 矩阵用f ( = 以) 表示 ，：占曲( j 1 x 川) ： h吖甩 ( 1 5 ) 注意到上式左边是共轭转置，序列国( 七= o ，1 ，2 ，) 是周期的，因此h 阶f o u r i e r 矩阵仅有n 个不同的元素，它也可以写成 f ：上 吖r 容易证明：f = f 7 。f l11 l 1国脚2c o “1 l国2国4m “一2 1 珊”一国“ = ( f ) r ：i ，f ：i f o u r i e r 矩阵有下列重要结论： 引理1 4 1f o u r i e r 矩阵是酉矩阵 f f = f f = i 或f = f 引理1 4 2f ”= f f = 1o oo 00 ol oo 10 oloo s i 理1 4 3 f ”= i ，f ”= f q ( f ) = i f = f 我们可将f o u r i e r 矩阵写成如下形式 ，= 忻 = ，2 ( 1 6 ) ( 1 7 ) ( 1 8 ) 。h 一 0 j冰 。妒、呶 。矿矿 第一章绪论与预备知识 引理1 4 4f 的特征值是1 ，f 及其恰当的重数 引理1 4 5f l = f d i a g ( 1 ，曲“) 只其中万同( 1 1 ) 式，f 同( i - 5 ) 式 定义1 , 4 1 设a 为n 以阶复矩阵，如果a = 以，则称爿为正规阵 例酉矩阵、h e r m i t e 矩阵、斜h e r m i t e 矩阵都是正规矩阵，因此，实对称， 斜对称以及正交矩阵也都是正规矩阵 1 5 广义逆 定义1 5 1 【5 5 】设a ，b e c ”“，有下列5 个方程 a b a = a( i ) b a b = b( i i ) (ab)=ab(iii) ( 县z ) = b a( i v ) a b = b a( v ) 则称满足方程( i ) ，( i i ) ，( i i i ) ，( i v ) 的矩阵盘为4 的m o o r e p e n r o s e 逆。记为a + ： 称满足方程( i ) ，( i i ) 的矩阵b 为彳的自反g 逆，记为a 0 , 2 | ：称满足方程( i ) ， ( i i ) ，( v ) 的矩阵口为a 的群逆，记为一1 1 卫”或记为a 8 ：称满足方程( i ) ，( i i ) 且其非零特征值是a 的非零特征值的倒数的矩阵b 为的谱逆，记为彳1 定义1 5 2t ，l 设a c “，我们称满足方程i m a k a “= r a n k a 的最小非负整数 k 为a 的指标，记为i n d ( a ) = k 若彳非奇异，则i n d ( a ) = 0 ，若彳奇异，则 t a d ( a ) 1 引理1 5 1 一个非零矩阵a 有唯一谱逆a 。当且仅当彳有指标l ， 此时a 。也是a 的群逆。 s l 理1 。5 2 m 设z 是一个有不同特征值的n n 阶矩阵，表示所有 与z 可换的矩阵组成的集合则吼中的每一个矩阵一都有指标l 并且么的唯一谱 逆a 5 是a 在仡中仅有的广义逆，进一步地，如果z 是正规的，则a s = a + 引理l 5 3 ”i 若矩阵爿非奇异，刚线性方程组血= b 的唯一解为x ；a 一1 6 若矩阵奇异且线性方程组a x = 6 有解，则a x = b 的通解为 8两安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最小二乘解 x = a m 2 1 6 + ( l a 1 ，2 “) l 其中l ，是任意的”维列向量 1 6 本文内容及安排 本文是作者攻读硕士学位期间在刘三阳教授的指导下完成的部分研究工作， 主要是关于几种循环矩阵的算法和反问题的最小二乘解的研究全文的主要内容 及具体安排如下： 全文共分四章第一章介绍了循环矩阵类的研究现状和若于预备知识；第二 章讨论了，一循环矩阵的反问题的最小二乘问题及其最佳逼近问题和一种判断对 称，一循环线性系统是否有解的快速算法和并行算法第三章讨论了以阶鳞状因子 循环矩阵的逆阵、自反g 一逆、群逆、m o o r e p e n r o s e 逆和两露阶鳞状因子循环矩 阵之乘积阵的快速算法，以及判断鳞状因子循环线性系统是否有解的快速算法和 并行算法第四章讨论了一阶置换因子循环矩阵的逆阵、自反g 一逆、群逆、 m o o r e p e n r o s e 逆和两甩阶置换因子循环矩阵之乘积阵的快速算法，以及置换因 子循环矩阵的反问题的最小二乘问题及其最佳逼近问题 最后是结束语、致谢、参考文献、本人在攻读硕士学位期间发表的论文目 录、以及参加的科研项目 第二章r 一循环矩阵 9 第二章r 一循环矩阵 2 1 引言 数学以及应用科学中的许多问题都与周期性有关，从而导致一类特殊形式的 线性系统，一循环线性系统r 一循环线性系统的求解在谱分析、线性预测、最 小二乘估计、误差控制码及自回归滤波器设计等领域起着重要的作用 本章首先就一类与周期性有关的r 一循环矩阵的反问题的最 j 、- - 乘问题及其 最佳逼近问题进行探讨，给出了其最小二乘解的存在性定理及它的一般表示，并 证明了逼近矩阵的存在唯一性且给出它的具体表达然后，借助快速付立叶变换 ( f f t ) 技术，给出了一种判断对称，一循环线性系统是否有解的快速算法和并行 算法，并在有解的情况下求出其解，又将该算法推广到线性同余系统 2 2r 一循环矩阵 本节介绍，一循环矩阵的有关定义和基本结果 定义2 2 1 1 4 1 1 若彳具有形状 一= 口l口2 ，一i口0q i o n 2r a n 1a o m r a 2r a + 一1 巩2 ， _ 口。 则称彳为卜- 循环矩阵因彳决定于其第一行元素口o ，口l ，一及参数，。简记为 a 一= c ：( a o ，q ，i ) 所有n 阶，- 循环矩阵的集合记作c m ， 特别地，当r = 1 时，a 即为循环矩阵；当r = 一l 时，称之为斜循环矩阵( 或反 循环矩阵) ；当，；0 时，即为( 上) 三角t o e + p l i t z 矩阵 定义2 2 2 t “1 称n 阶r 循环矩阵 i1 0西安电子科技大学硕士论文；几类循环矩阵的算法及其反问题的最小二乘解 鲁= o o0 l o0 o 01 o o0 为基本r 一循环矩阵，简记为鲁= c r ( 0 ，1 ，o ，0 ) 显然，尊c m ，且有彰= c r ( o ，0 ，。l ，o ，o ) ，等= 厶，等= 吃 引理2 2 1 1a e c m ，的充要条件是4 = 厂( 毒) ，其中a i 吒，吼是4 的第一 行元素，鲁= e ( o ，1 ，o ，o ) ，( 工) = q 一称为4 的表示多项式 引理2 2 2 “1 设a = c , ( a i ，a 2 ，吒) 是复数域上的一个r 一循环矩阵， d ，= d i a g ( 1 ，万，j 2 ，占”4 ) ，其中占= 盯，o ；c 是一个f o u r i e r 矩阵且满足 目= 了1w ( t - i x j - i ) , lsf 甩， 其中= e x p ( 导) 是疗次本原单位根，令人= d ，则 一= a d i a g ( 2 l ，五，a ) a 一， 且4 的特征值是 乃= ，( 删) = a , ( o w d 。，_ ，= l ，b 其中a l v a n 是a 的第一行元素，研叼( - ，= l ，疗) 是r r = 0 的月个不同根 显然，当l r l = l 时，人= ( d r f ) 一= f 一1 p 一= f “彤= a ”，即人为酉矩阵， 定义2 2 3 1 若矩阵一具有形状 a = 口l吼q 2 一i q口2玛a n i r q 0 n 2a s气r 0 4r q _ -_ 。lr a o r a ；，一3r a , 一2 则称a 为对称r 循环矩阵，简记为 a = s c ，( a o ，q ，a n 。1 ) 所有h 阶对称r 循环矩阵的集合记作s c m ， 第二章r 一循环矩阵 1 i 特别地，当，= 1 时，a 即为对称循环矩阵；当，= - 1 时，称之为对称斜循环 阵( 或对称反循环矩阵) ；当r = o 时，即为( 上) 三角h a n k c l 阵 引理2 2 3 t 4 ”设4 s c m ，令d ，= d i a g ( 1 。坑艿2 ，j “- 1 ) ，其中j = 靠，r o ， 则a = 研a k d , = 其中d = a n t 占。，0 i m o d f ，魁易证a 对模f 有逆存在，盈 巧1d i a g ( 1 ，j ，万一”。) r o o d f , , 根据数论变换理论( 见【6 0 】) 。存在整数口，使( e ，一，口) 构成一个数论变换令 f 瓴( - i x i - i ) ) 。m o d f ， 则f ；n - i 。“。一) 。m o d f , ，若令口i ( a n 一2 占，a 0 6 ”1 ) m o d f , ， 五= ( 矗， ，矗一，) 7 z f a m o d f , 。则同引理2 2 4 样可以证明 ai n k d , f b f 1 五c 1modft，(2-14) 其中b = d i a g ( 2 0 ， ，以。) 若令舌= f - 研1 bm o d f , ，则由( 2 1 4 ) 式可知方程 组( 2 ，1 3 ) 有解的充要条件为如下方程组有解： 毋否r o o d f , ， ( 2 1 5 ) 而方程组( 2 - 1 5 ) 有解的充要条件为： ( 五，互) l 抚，0 f s 嚣一1 ( 2 - 1 6 ) 因此，我们得到判断( 2 - 1 3 ) 是否有解和解此方程组的如下算法： 算法2 4 2 ： 步1 。计算1 i f a m o d f , ，其中口。( 吒m 口丹- 2 艿，a q 8 ”1 ) 7m o d e , 步2 计算b s f l d i 6r o o d f 步3 。判断条件( 2 - 1 6 ) 是否满足，若满足雯眭继续进行下一步；否则，方程组无 解 步4 取方程组( 2 - 1 3 ) 的一个解弘计算x z 一1 肋r 砂m o d e ，则x 便为方程组 几 ( 2 1 3 ) 的一个解 方程组( 2 - 1 5 ) 实际上是求解方程五m - - - b , m o d 只，o s i s n 1 这n 个方程组 互相独立且都是一元一次线性同余方程，它的求解是很容易的在上述算法中，1 和2 及4 中的主要计算都是对模互求矩阵f 或f 1 和一个向量相乘，由于缓，口) 构成一个数论变换，所以它们的计算都可以采用快速数论变换( f n t t ) 来完成( 见 f 6 0 】) ，所需的运算置为o ( n l o g n 个模互中的加乘运算，并且若利掰 t 台处理杌并 行处理，只需o ( 1 0 9 n ) 步因此，方程组( 2 - 1 3 ) 的求解只需花费o 协l o g 帕个模只中 第二章，一循环矩阵 1 9 的加乘运算即可化为方程组( 2 1 5 ) 的求解，而( 2 - 1 4 ) 的求解非常简单 由( 2 1 4 ) 还可以得到矩阵_ 可逆的充要条件为： 对模e 可逆，0 i n - i 1 在a 可逆的假定下，可知其逆矩阵为一个对称三一循环矩阵，所以只需求解方程组 ， 4 x ze ( 1 ) r o o d f , ，其中e ( 1 ) = ( 1 ，o ，够m o d f , ，由一个解x 便可以生成够1 例2 4 1 421 2 4】4 1 ，利用( 2 4 2 ) 中所述的方法求a l 1 2 1 6j 角* 蠢t 盱t f=i：j1：；，r=4，-=diqs。，t4。2，z，2szs4， 计算过程如f ： 1 计算a = f d 口，口= ( 2 ，4 ，3 ，1 ) 7 ，d , a = ( 2 ，5 6 5 6 9 ，6 ，2 8 2 8 4 ) 7 五= f d 4 a = ( 1 6 4 8 5 3 ，- 4 + 2 8 2 8 4 i ，- 0 4 8 5 3 ，- 4 - 2 8 2 8 4 0 7 2 由于o ，o s j s 3 ，所以可逆 3 计算y = ( 筇1 ，耳1 ，五，苜) ( 1 111 ) r ，这里向量乘法表示相应的分量相 乘 y = ( o 0 6 0 6 6 0 , - - 0 1 6 6 6 6 8 0 1 1 7 8 5 1 1 ，- 2 0 6 0 5 8 1 ，一0 1 6 6 6 6 8 + 0 1 1 7 8 5 i i ) 4 计算c = 二皿毋，f y = ( - 2 3 3 3 2 5 7 ，2 3 5 6 9 4 3 ，- i 6 6 6 5 8 5 ，1 8 8 5 5 3 9 ) 7 ， 一 所以c = ( 1 3 3 3 2 5 6 ，- 0 8 3 3 2 9 3 ，0 8 3 3 2 9 7 ，- - 0 5 8 3 3 1 4 ) 这便是矩阵。的第一列 若直接对采用g a u s s 消去法解方程组a c = 0 ，0 , 0 ，0 ) 7 ，可求得爿_ 1 的第一列 为e = 0 3 3 3 3 3 3 ，- 0 8 3 3 3 3 3 ，0 8 3 3 3 3 3 ，- 0 5 8 3 3 3 3 ) 7 ，和前面所求得的c 相比误差很 小 1 3 4 2 ，。，。，。l = a 搜 2 0西安电予科技大学硕士论文：几类循环矩阵的算法及其反问题的最小二乘解 第三章鳞状因子循环矩阵 3 1 引言 鳞状因子循环矩阵及鳞状因子循环系统的求解在图象恢复和重建领域起着 重要作用 1 3 1 ，近些年来，对其特性及有关算法的研究引起了人们的重视 1 4 6 - 4 7 , 6 2 - 6 3 j l s t u a r t 和j r w e a v e r i ”1 提出并研究了鳞状因子循环矩阵的基本性 质，岑建苗【4 6 1 讨论了其谱分解及其应用，江兆林等给出了求鳞状因子循环矩阵的 逆阵及广义逆阵的快速算法、e u c l i d 算法，并给出求其逆阵的插值算法 6 2 - 6 3 】 本章在上述文献的基础上，借助快速付立叶变换( f f t ) ，首先给出了一种求玎 阶鳞状因子循环矩阵的逆阵、自反g 一逆、群逆、m o o r e p e n r o s e 逆的快速算法： 然后给出了计算两玎阶鳞状因子循环矩阵之乘积阵的一种快速算法：最后，借助 快速付立叶变换( f f t ) 技术，给出了一种判断鳞状因子循环线性系统是否有解的 快速算法和并行算法。并在有解的情况下求出其解，又将该算法推广到线性同余 系统 3 2 鳞状因子循环矩阵 以下设肘。为复数域上所有，l 阶方阵组成的集合 定义3 2 1 1 4 7 1 设c 为一阶基本循环矩眸，即 c = 0loo oo1o 0oo 1 1oo 0 ，而矩阵d = 为非奇异的对角阵如果孵= d c 则称9 l 为基本鳞状因子循环矩阵 定义3 2 2 ”1 对于帆中的矩阵一，如果满足彳巩= 刚，则称a 为鳞状因子循 环矩阵如果d = d i a g ( 1 ，l ，) ，那么鳞状因子循环矩阵就是第二章介绍的，循环 第三章鳞状因子循环矩阵 2 i 矩阵，因此鳞状因子循环矩阵是卜循环矩阵的推广用y t s c m 。表示m 。中所有 鳞状因子循环矩阵组成的集合 弓l 理3 2 1 ”1 a y l s c m 。的充要条件是4 = ，何) ，其中，( - - z 吼t 4 x 。， ，= d d 2 d l ，规定= l ；锨o = ，j 为以阶单位阵称，( x ) 为a 的表示多项式 由于a o ，口l 一，口正好是一的第一行元素，为方便，将第一行元素为a 0q ，a n i 的 鳞状因子循环矩阵a 记为：a = s c a c i r e r ( a o ，q ，一1 ) 引理3 2 2 设a = s e a c i r e m ( a o ，q ，巳- 1 ) 是复数域上的一个鳞状因子循环矩 阵，f 是一f o u r i e r 矩阵且满足吒：下1 f - 1 ) u - t ) , 1 - =i圳坝 一 卜 d 盱咿咿 2 肌。孵孵 观 ，砑盱 w w 州；屯=i圳坝 。盱譬咿 一 ，噼砑咿。吸孵盱 l 1 1 1 1 l i 心h 心；雠 ：2 巧o o = 肺一心以 、“叫l 悖m 4 m 一 一 i l 南 屯 、， 5 m m镐“，弘 = 、， 鳓一心以知a 如 ，。l 2步 嚣；缸 。筹咿 一 。雾咿。吲略旷 3 0西安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最小二乘解 所以a b = s c a c i r c ( 8 1 。3 7 ，3 3 ，6 4 ) 8 l3 7 1 2 88 l 1 3 26 4 7 43 3 3 36 4 7 41 3 2 8 11 4 8 3 28 l 3 5 鳞状因子循环矩阵的快速算法和并行算法 鳞状因子循环矩阵及鳞状因子循环系统的求解在图象恢复和重建等领域起着 重要作用，近些年来对其特性及有关算法的研究引起了人们普遍重视。但提出的 算法需要的运算量较大，且很少考虑计算复杂性问题本节从快速算法和复杂性的 角度来考虑这种矩阵的计算 3 5 i 方程血= b 的求解 设n 西o ，令否= f 8 r 一1 6 则根据( 3 2 ) 可证方程止= 6 有解的充要条件是 f z l 方程缈= 舌有解。所以，若令 k = j i = 0 , 0 茎f s 行一1 ) k = “i 0 , 0 s i 一一1 ， 则方程a x = 6 有解的充要条件为 - j = 0 ( 对任意的f e m ) ( 3 1 3 ) 因此，我们得到判断和求解方程组i x = b 的如下算法： 算法3 5 1 ： 步1 计算a ；f a ，其中口i = ( ，耳a a , ，础d ”1 。) 7 步2 计算吾= f s f , 1 b 步3 判断条件( 3 1 3 ) 是否满足，若满足则继续进行下一步；若不满足， 则方程组无解 步4 取向量) ，满足咒= 催取，鲁 第三章鳞状因子循环矩阵 步5 。计算x ：! r 毋，则x 便为方程组出：b 的一个解 7 在上述算法中，步1 和步2 及步5 中的主要计算都是矩阵f 或，”和一个向量 相乘它可队采用快速付立叶变换( f f t ) 来做，所需的运算量为o ( n l o g n ) ，并且 着利用月台处理机并行处理，所需的步数为o ( 1 0 9 n ) ( 见文献【5 9 】) 因此，判断方 程组a x = b 是否有解和求解该方程组，复杂性仅为o ( n l o g n ) ，若利用 台处理机 并行处理只需o ( 1 0 9 n ) 步 3 5 2 a 的逆矩阵 由( 3 - 2 ) 式可知彳可逆的充要条件是b 可逆，因此爿可逆的充要条件是 z 0 , 0 i n - 1 不难证明，若彳可逆，则其逆矩阵也是鳞状因子循环矩阵所以由a “的第一 行便可以生成整个矩阵a ，因而求爿。只需求解方程组a x = 8 ( ”，其中 e ( ”= ( 1 , 0 ，o ) 7 设c 为a 一1 的第一行，则根据( 3 2 ) 式得 c ：( 三r f b 。f h f 一1 、e ( 1 ) ：三r 一1 ，”b 一1 f f e ( i ) f f e 。易直接算出为( 1 ，1 ，l ，1 ) ，所以 。 c _ 1 厅f - f ”b 气l i l ，l 1 ) = 丢r - 1 f ”( 础石，硭厅疗 。 因此计算c 的主要运算量是一个长一的离散付立叶变换( d f t ) 和一个长n 的 离散付立叶逆变换( i d f t ) 的计算若b 不可逆，则说明a 不可逆，因此计算出一 个d f t 即可判断a 是否可逆 n 阶矩阵爿的反射g 逆阵和m o o r - p e n r o s o 逆矩阵分别是指满足下述条件( i ) 、 ( i i ) 和( i ) - ( i v ) 的矩阵b ： ( i ) , 4 b a = a ， ( i i ) b a b = 丑。 ( i i i ) ( a b f 。a b ， ( i v ) ( 翩) = b a 根据( 3 2 ) 式易证彳的一个反射g 逆阵为 3 2西安电子科技大学硕士论文：几类循环矩阵的算法及其反问题的最小二乘解 g ：1 t f d i a g ( 式，t 1 ) f “r i n ( 3 1 4 ) 其寺醚= 黑篙? 特别地，若d d ”= 盯，易证g 便是a 的m o o r - p e n r o s e 逆a + ( 见 4 1 ) 由( 3 1 4 ) 式可以看出g 仍为鳞状因子循环矩阵，所以g 的元素由g 的第一 行所生成，因而。只要算出c = g 7 e ( 1 即可知道g 由( 3 1 4 ) 式 c ：( 1 f f d i a g ( 砧，五：一1 ) f ”厂1 ) 7 p ( 1 ) ；三r 一1 f nd i a g ( 矗，尤- 1 ) f f e ( 1 ) 这里的主要计算仍为f 或f ”和一个向量相乘根据f f t 算法，所需的运算量 为o ( n l o g n ) 注：当兀z = 0 时，a 为一个上三角型t o e p l i t z 矩阵，对该类情况的讨论参见 文献【3 6 3 5 3 同余线性方程组的求解 现将以上讨论的方法推广到更一般的域( 或环) 中线性方程缎的求解问题考 虑如下同余线性方程组