1、1毕业论文开题报告数学与应用数学关于R分块循环矩阵的若干性质一、选题的背景与意义循环矩阵是一门年轻的学科。循环矩阵概念的出现始于1885年美国学者MUIRT，然而直到1950年之前，对于循环矩阵的研究还没有引起数学工作者的足够重视。1950年，GOODIJ对循环矩阵的逆、行列式以及特征值进行研究，从此，循环矩阵开始蓬勃发展。循环矩阵是T矩阵的一种特殊情形，在编码理论、数理统计、理论物理、结构计算、分子轨道理论、数字图像处理等方面有广泛的应用。1950年以来，广大数学工作者对它进行了大量的研究，得到了循环矩阵行列式的计算方法和循环矩阵基本性质的一系列丰硕的成果，关于它的理论研究也得到了飞速的发展
2、。特别是其逆矩阵的求法，是人们一直所关注的问题。1955年，GREENSPAND在总结求逆矩阵的种种方法时，特意以三阶循环矩阵为例对循环矩阵逆矩阵的求法作了说明，但只有结论而无证明。1962年，GILBERTTL利用JORDAN标准形理论，把循环矩阵A化为对角形，然后再求出A的逆矩阵1A，从而事实上给出了GREENSPAND提出的计算方法的一种证明。然而在实际计算时却存在大量困难，于是人们又开始寻求新的较为简便的算法。1979年，SEARLESR给出了与上述两种方法不相同的新的初等算法，它不必用JORDAN标准形和特征根，只用到一些矩阵乘法以及逆矩阵的最简单性质。直到现在，很多学者还在寻找更为
3、简便的一般性的求逆矩阵的方法。迄今为止，对于经典循环矩阵所做的研究已有很多，同时，各种新的循环矩阵被相继提出，R分块循环矩阵就是其中一种，其形式如下021201110ARARAAARAAAAANNN，其中0,1,1,0,RCRNICAMMI。国内的许多学者如何承源、郑强、张光辉等在R分块循环矩阵的性质方面已2经作了比较深入的研究，于是我们想在上述研究的基础上，介绍R分块循环矩阵的推广过程及研究背景，对其特征值、对角化，等基本性质进行总结归纳，概括然后概括R分块循环矩阵可逆的几个充要条件及求逆的各种方法，并参考循环矩阵和R循环矩阵开平方问题的相关著作，讨论并尝试R分块循环矩阵的开平方问题。二、研
4、究的基本内容与拟解决的主要问题现在，各种新的循环矩阵被相继提出，很多学者开始探讨分块循环矩阵的可逆性及其逆矩阵的求法。R分块循环矩阵是循环矩阵、R循环矩阵、分块循环矩阵的推广，本文打算先介绍R分块循环矩阵的推广过程及研究背景，再在深入研究已有文献的基础上，对其特征值、对角化等基本性质进行总结归纳，并加以论证，然后概括R分块循环矩阵可逆的几个充要条件及求逆的各种方法，并参考循环矩阵和R循环矩阵开平方问题的相关著作，讨论并尝试R分块循环矩阵的开平方问题。三、研究的方法与技术路线查阅相关资料，弄清楚R分块循环矩阵的相关概念，对参考文献中的重要结论加以整理和论证，并对R分块循环矩阵的各种性质进行归纳总
5、结，概括R分块循环矩阵的可逆的几个充要条件及其逆矩阵的几种求法，并参考循环矩阵和R循环矩阵开平方问题的相关著作，讨论并尝试R分块循环矩阵的开平方问题。四、研究的总体安排与进度201010201011与指导老师联系，查阅相关论文资料，确定课题。201012201101完成文献综述、文献翻译和开题报告，并上交学院审批。201102201104阅读相关资料，开始毕业设计（论文）的正式写作。20110404前完成毕业设计（论文）初稿，交指导教师审稿、修改；20110429前完成毕业设计（论文）并定稿。五、主要参考文献1CHENSHENGANONTHEEIGENVECTORSOFRCIRCULANTMA
6、TRICESOFPRIMEDIMENSIONJJOFMATH2002,22215752JIANGZHAOLIN，XUZONGBEN，GAOSHUPINGALGORITHMSFORFINDINGTHEINVERSESOFFACTORBLOCKCIRCULANTMATRICESNUMERICALMATHEMATICS，3200611113郑强关于R分块循环矩阵的推广J山东师大学报自然科学报1998,1343763794李天增，王瑜循环矩阵的性质及求逆方法J四川理工学院学报2009，2244735单沪军，郑强，吴强初等R分块循环矩阵的几个性质J山东工业大学学报1999，2932692726张光辉，叶
7、晓丽关于R分块循环矩阵及其对角化问题的探讨J数学理论与应用2007，2711151177钟祥贵，曾立新R循环矩阵的逆矩阵J北京教育学报自然科学版2007，26138岳晓鹏，梁聪刚分块循环矩阵的求逆方法探讨J长江大学学报自然科学版2008，511241269黄赐玺块循环阵的特征值与非异性J山东师大学报自然科学版1995，1014810何承源一类循环分块矩阵的一些结果J四川师范大学学报自然科学版1996，196455011蒋加清R循环矩阵求逆的一种新算法J江西教育学院学报2010，31（3）1312袁中扬，刘三阳对称R循环矩阵的快速算法和并行算法J纯粹数学与应用数学2005，212158613江兆
8、林，刘三阳R循环矩阵求逆和广义逆的EUCLID算法J电子科技大学学报2004,33（3）151214毕业论文文献综述数学与应用数学关于R分块循环矩阵的若干性质循环矩阵是T矩阵的一种特殊情形，有许多特殊而良好的性质和结构。在阅读相关文献的基础上，我对循环矩阵的相关知识有了初步的了解，也促使我想进一步研究关于循环矩阵的有关知识。循环矩阵是一门年轻的学科，在众多的科学和工程领域，如编码理论、数理统计、理论物理、结构计算、数字图像处理等许多方面有着广泛的应用。循环矩阵概念的出现始于1885年美国学者MUIRT，他称如下形式的矩阵011,NNCCIRCCCC012110121230NNNAAAAAAAA
9、AAAA为循环矩阵，如果取01000001000000110000A为基本矩阵，则NC可改写为210121NNNCCICACACA（1），正是由于（1）式的成立才使得循环矩阵NC的研究得以顺利进行。然而直到1950年之前，对于循环矩阵的研究还没有引起数学工作者的足够重视。1950年，GOODIJ对循环矩阵的逆、行列式以及特征值进行了研究。从此，循环矩阵开始蓬勃发展，广大数学工作者对它进行了大量的研究，得到了循环矩阵行列式的计算方法和循环矩阵基本性质的一系列丰硕的成果，关于它的理论研究也得到了飞速的发展。特别是其逆矩阵的求法，是人们一直所关注的问题。1955年，GREENSPAND在总结求逆矩阵
10、的种种方法时，特意以三阶循环矩阵为例对循环矩阵逆矩阵的求法作了说明，但只有结论而无证明。1962年，GILBERTTL利用JORDAN标准形理论，把循环矩阵A化为对角形，然后再求出A的逆矩阵1A，从而事实上给出了GREENSPAND5提出的计算方法的一种证明。然而在实际计算时却存在大量困难，于是人们又开始寻求新的较为简便的算法。1979年，SEARLESR给出了与上述两种方法不相同的新的初等算法，它不必用JORDAN标准形和特征根，只用到一些矩阵乘法以及逆矩阵的最简单性质。1981年，李炯生给出了GREENSPAND的方法的初等证明。1983年，李天林改进了GREENSPAND和李炯生的方法和
11、证明。1992年，王济荣给出了反循环矩阵的概念及求逆方法。直到现在，很多学者还在寻找更为简便的一般性的求逆矩阵的方法。迄今为止，对于循环矩阵所做的研究已有很多，同时，各种新的循环矩阵被相继提出，国内外许多学者也作了较深入的研究，已经取得了一些比较好的结果。文献6中，张光辉，叶晓丽给出了R分块循环矩阵的概念，其形式如下021201110ARARAAARAAAAANNN，其中0,1,1,0,RCRNICAMMI。则A为一个R分块循环矩阵，记为,110NRAAACA。如果R1，A即为分块循环矩阵，如果R1，A即为分块反循环矩阵。文章还对R分块循环矩阵的对角化问题进行了探讨设,110NRAAACA，0
12、W为如下的范德蒙矩阵0W111110111NNNNOOO，W0WME，,1,10NDIAGU其中110,N为NXR0的全部根，则有（1）1,2,100NKUWWKKR，特别地，UWWR00（2）,111MNMMOREEEDIAGWSW,1101MNMMMNEEEEDIAGWPW，其中110,N为NXR0的全部根，NKIKE2，K0,1,N13,1101NFFFDIAGAWW,6其中1110NNXAXAAXF。即任意一个MN阶的R分块循环矩阵必可以准对角化文献10中，何承源曾把循环矩阵的元素换成同阶方阵进行研究，引进了R分块循环矩阵的概念，讨论了它的一般性质，并利用线性方程组和矩阵的相似形给出了
13、R分块循环矩阵求逆的两种方法，如下定理1设011,RMRABCAAABCM，若12,1,MMNXXXXMP是线性矩阵方程组AXE的唯一解，则11,RMRABCXXBCM。定理2设011,RMRABCAAABCM，且R、A均非奇异，则1011,RMRABCBBBBCM，其中1101MTJJTJTBFWKKWM，0,1JM。特别地，文章给出了当RNI时，R分块循环矩阵的块谱分解定理、矩阵范数意义下的圆盘定理以及非奇异的几个充分条件。文献4、7、8对矩阵求逆的问题进行了一系列的探讨，其中文献7给出了R循环矩阵的逆矩阵公式，但其中包含复杂的三角函数运算，所以其意义主要在理论方面，而文献8讨论了几种分块
14、循环矩阵求逆的算法，给出了利用分块循环矩阵的准对角化进行求逆的一种简便方法。文献11利用最大公因式算法给出了任意数域上非奇异卜循环矩阵求逆的一种新算法，该方法不需要计算三角函数并且具有很少的计算量。文献13则利用多项式的EUCLID算法给出了非奇异的R循环矩阵求逆矩阵的一个新算法，该算法同时推广到用于求奇异R循环矩阵的群逆和MOOREPENROSE逆，并给出了应用该算法的数值例子。可见前人在R分块循环矩阵方面已经取得了一些比较好的结果。R分块循环矩阵是循环矩阵、R循环矩阵、分块循环矩阵的推广，于是我想我们可以在上述研究的基础上，介绍R分块循环矩阵的推广过程及研究背景，对其特征值、对角化等基本性
15、质进行总结归纳，并加以论证，然后概括R分块循环矩阵可逆的几个充要条件及求逆的各种方法，并参考循环矩阵和R循环矩阵开平方问题的相关著作，讨论并尝试R分块循环矩阵的开平方问题。7四、主要参考文献1CHENSHENGANONTHEEIGENVECTORSOFRCIRCULANTMATRICESOFPRIMEDIMENSIONJJOFMATH2002,22215752JIANGZHAOLIN，XUZONGBEN，GAOSHUPINGALGORITHMSFORFINDINGTHEINVERSESOFFACTORBLOCKCIRCULANTMATRICESNUMERICALMATHEMATICS，2006
16、11113郑强关于R分块循环矩阵的推广J山东师大学报自然科学报1998,1343763794李天增，王瑜循环矩阵的性质及求逆方法J四川理工学院学报2009，2244735单沪军，郑强，吴强初等R分块循环矩阵的几个性质J山东工业大学学报1999，2932692726张光辉，叶晓丽关于R分块循环矩阵及其对角化问题的探讨J数学理论与应用2007，2711151177钟祥贵，曾立新R循环矩阵的逆矩阵J北京教育学报自然科学版2007，26138岳晓鹏，梁聪刚分块循环矩阵的求逆方法探讨J长江大学学报自然科学版2008，511241269黄赐玺块循环阵的特征值与非异性J山东师大学报自然科学版1995，101
17、4810何承源一类循环分块矩阵的一些结果J四川师范大学学报自然科学版1996，196455011蒋加清R循环矩阵求逆的一种新算法J江西教育学院学报2010，31（3）1312袁中扬，刘三阳对称R循环矩阵的快速算法和并行算法J纯粹数学与应用数学2005，212158613江兆林，刘三阳R循环矩阵求逆和广义逆的EUCLID算法J电子科技大学学报2004,33（3）151218本科毕业设计（20届）关于R分块循环矩阵的对角化和可逆性9摘要【摘要】本文给出了R分块循环矩阵的形式，介绍了它的一些基本性质和R分块循环矩阵的两种推广；描述了R分块循环矩阵的准对角化过程，并在此基础上讨论了R分块循环矩阵的特征
18、值，行列式值等基本性质；说明了普通R分块循环矩阵求逆的一种算法及其计算复杂性，并介绍了一类特殊的R分块循环矩阵，即每个分块都是R循环矩阵的R分块循环矩阵求逆的一种快速傅里叶算法。【关键词】R分块循环矩阵；准对角化；特征值；逆10ABSTRACT【ABSTRACT】INTHISPAPER,WEPRESENTTHECONCEPTBLOCKRCIRCULANTMATRIXTHENWEINTRODUCESOMEOFITSFUNDAMENTALPROPERTIESANDTWOKINDSOFITSPROMOTIONALSOWEDESCRIBESTHEQUASIDIAGONALIZATIONPROCESSO
19、FBLOCKRCIRCULANTMATRIXANDBASEONTHAT,WEDISCUSSESTHEEIGENVALUES,DETERMINANTVALUEANDSOMEOTHERBASICPROPERTIESOFABLOCKRCIRCULANTMATRIXWEINTRODUCEANALGORITHMOFANORMALBLOCKRCIRCULANTMATRIXANDITSCOMPUTINGCOMPLEXITYATLAST,WEINTRODUCETHEFASTFOURIERALGORITHMTOCALCULATINGTHEINVERSEAOFASPECIALKINDOFBLOCKRCIRCULA
20、NTMATRIX,WHOSEBLOCKAALLRCIRCULANTMATRIX【KEYWORDS】RCIRCULANTMATRIXQUASIDIAGONALIZATIONEIGENVALUEINVERSE11目录1绪论1211循环矩阵的历史及研究意义1212R分块循环矩阵122定义和基本定理1321基本概念1322基本定理143主要结果1531R分块循环矩阵的推广1532R分块循环矩阵的准对角化，特征值和行列式1733R分块循环矩阵的逆204算例24参考文献28致谢错误未定义书签。附录错误未定义书签。1绪论11循环矩阵的历史及研究意义循环矩阵是一类重要的特殊矩阵，它有着许多特殊而且优良的结构和
21、性质。循环矩阵在很多的领域，如图象处理、分子振动、线性预测等方面都有着重要的作用，同时，在计算机时序分析、编码理论、自回归滤波器设计等领域中也经常会遇到以这类矩阵为系数的线性系统的求解问题。正是由于循环矩阵在应用方面的广泛性，近年来，对循环矩阵的研究已成为矩阵理论和组合数学中的一项热门课题，不仅受到代数学界人士的重视，而且受到了计算数学界、应用数学界等许多领域研究人员的重视，关于它的理论研究也得到了飞速发展循环矩阵概念的出现始于1885年美国学者MUIRT,他称矩阵,110NNCCCCIRCC032121011210AAAAAAAAAAAANNN为循环矩阵。但循环矩阵当时并没有引起广大数学研究
22、者的重视，直到1955年，IJGOOD等人对循环矩阵的逆、行列式、及特征值的研究，才拉开了循环矩阵研究的历史，在这五六十年的研究历史中，循环矩阵理论得到了快速发展。迄今为止，对于经典矩阵的研究文献已有很多，各种新的循环矩阵概念也被相继提出，R分块循环矩阵就是其中的一种。12R分块循环矩阵R分块循环矩阵是一类重要的循环矩阵，他的定义如下设矩阵1,1,0NSCAMS，称分块矩阵NNIJAA为由110,NAAA所生成的NM阶R分块循环矩阵，简记为RNRBCMAAABCA,110，其中JIRAJIAAIJNIJIJ,国内的许多学者如何承源，沈光星，郑强，张光辉等都对都对R分块循环矩阵的性质做了深入的研
23、究，我想在这些研究成果的基础上，对R分块循环矩阵的对角化，特征值等基本性质进行归纳总结，讨论R分块循环矩阵的求逆问题，并介绍一类特殊的R分块循环矩阵求逆的快速算法。2定义和基本定理21基本概念定义211复数域上如下形式的分块矩阵01321340122310112210ARARARARAAAARARAAAAARAAAAAAANNNNNNNNNN称为NM阶R分块循环矩阵，简记为RNRBCMAAABCA,110，其中1,2,1,0NICAMI，CR，0R。定义212设矩阵MSCA1,2,1,0NS，称分块矩阵NNIJAA为由110,NAAA所生成的NM阶K分块循环矩阵，简记为KNKBCMAAABCA
24、,110，其中JIKAJIAAIJNIJIJ，MCK，特别地，当0RRIKM时，A为一个R分块循环矩阵；当MIK时，A为一个分块循环矩阵；当M1时，A为R循环矩阵。定义213A，B分别是NM阶，QP阶矩阵，则A和B的KRONECKER积BA是一个PQMN阶矩阵，即BABABABABABABABABABANNNNNN212222111211定义214若矩阵MNMNIJCAA，满足,IJRAIJAAIJNIJIJ其中1,1,0,MJARJ均为N阶R循环矩阵，则称A为MN阶分块,RR循环矩阵，简记为,110MRAAABCA。22基本定理定理221任意一个N阶循环矩阵,1210NAAAACA可唯一表示
25、为基本循环矩阵的N1次多项式FA，其中1121NNXAXAAXF，即112210NAAAIAA定理222对于任何一个N阶循环矩阵,1210NAAAACA，必存在一个N阶复可逆矩阵使A对角化，即001101NWFWFWFA其中1122100NINIIIIWAWAWAWAWF，是由1的N次方根1210,NWWWW组成的范德蒙矩阵1112112122211211111111NNNNNNWWWWWWWWW定理223设RMMMMRBCMOOIOBCG,，11111110000,NNNNXAAADIAGXAAADIAGXAAADIAGXF10,NJJJJJXAAADIAG，其中X为MN阶方阵，1,1,0N
26、JAJ为M阶方阵，若RNRBCMAAABCA,110，则有GFA；反之，若GFA，则RNRBCMAAABCA,110。定理224若RNRBCMAAABCA,110，RNRBCMBBBBCB,110,则RNNRBCMBABABABCABBA,111100；RNJJNJNJJNJNJJNJRBCMBABARBABABARBABCBA,10112101101100；RNJJNJNJJNJNJJNJRBCMABABRABABABRABBCAB,10112101101100。3主要结果31R分块循环矩阵的推广定义311设10,NJJJJJXAAADIAGF，其中X为NM阶方阵，JA为M阶方阵1,2,1,
27、0NJ，称XF为行关联矩阵方程。定义312若00,0,MMMMKKIBCG，即MMMMMMMMMMMKKIIG000000000,则称KG为一个K分块循环子。引理311若KG为一个K分块循环子，K的特征值为1,2,1,0MII，则KG的特征值为所有方程0INX的根1,2,1,0NJJI。引理3123若KG、1,1,0MII、1,1,0NJJI如引理311所给，,AAADIAGA，1,2,1,0,10NIDIAGDIMII，,10NDDDIAGD，111211101210NNNNNNMMMMDDDDDDDDIIII则AADFGK,。定理3113若MMSKNKCKNSCABCMAAABCA,1,2
28、,1,0,110，则（1）若KM0则A的特征值为0A的特征值；（2）若K非奇异，则A的特征值为10,NJJJJJDAAADIAGDF的特征值，其中1,2,1,0,10NIDIAGDIMII，,10NDDDIAGD，JI为方程0INX的N个根1,2,1,0,1,2,1,0NJMI。证若KM0，结论显然成立，下设K非奇异，如引理313所设，可以验证1DGK，1110110DFDADAGFANJJJNJJK，因此，A的特征值为F（D）的特征值。定理3126设K是一个可以对角化的非奇异矩阵，相应的ID满足1,1,0,NJIAJDIDIAJ，则I,1101NDFDFDFDIAGAIIDETDETDETD
29、ET110NMNMNMNMNDFEDFEDFEAEIIIDETDETDETDET110NDFDFDFA定理313由R分块循环矩阵是K分块循环矩阵在0RRIKM时的特例，可以将K分块循环矩阵求特征值的结果推广到R分块循环矩阵。由MRI的特征值为R（M重），即1,1,0MIRI，JI为0RXN的根1,1,0NJ，即,2,121NKERNKN。推论3116设,110NRAAACA，0W为如下的范德蒙矩阵1111101100111NNNNNUUUUUUW，MEWW0，ME为M阶单位矩阵，其中110,NUUU为0RXN的全部根，1110NNXAXAAXF，则有I,1101NUFUFUFDIAGAWWII
30、DETDETDETDET110NUFUFUFAIIIDETDETDETDET110NMNMNMNMNUFEUFEUFEAE32R分块循环矩阵的准对角化，特征值和行列式定义321矩阵NNRNNNCRJ,与分块矩阵MNMNRMNMNNCSRP,定义为,1111NNRNNNEEREEEEJ，,1111NNRNNNIIRISIIIP，其中TMMMMMITIEIE0,0,0,0,0,0,1,0,0，M0和ME是M阶零矩阵和M阶单位矩阵。引理3213若A为R分块循环矩阵，则根据其性质和定义321有（1）NNRRE（2）1,2,1NKEEESMKRKMKRKMRKR（3）MNMMNMNRNRREEREES（
31、4）10NKKKRAA（5）设NNMMCBCA,，则AEN与MEB可交换。引理322设,110NRAAACA，10NKKKNXAEXF，则有ARSF。定理3216,110NRAAACA，0W，W，110,NUUU均为推论311中的定义，1110NNXAXAAXF，,110NUUUDIAGU，则有1,1101MNMMREUEUEUDIAGWSW，,1101MNMMMNEEEEDIAGWPW其中110,NUUU为0RXN的全部根，1,1,0,2NKENKIK2,1101NUFUFUFDIAGAWW,其中1110NNXAXAAXF。即任意一个NM阶的R分块循环矩阵必可以准对角化。证（1）由MRMMR
32、REWEWEWS00，另由于MMMMNMMEUWEUEWEUEUEUWDIAG,00110，再由1,2,100NKUWWKKR容易得到,1101MNMMREUEUEUDIAGWSW令R1，即得到,1101MNMMMNEEEEDIAGWPW（2）由（1），我们有,1101MNMMREUEUEUDIAGWSW其中110,NUUU为0RXN的全部根，计算可得1,2,1,1101NKEUEUEUDIAGWSWMKNMKMKKR，又由引理322，得10NKKRKNRSAESFA。结合引理321（5），可得WSAEWAWWNKKRKN1011101NKKRKNWSAEW10110,NKKKNKKKKAUA
33、UAUDIAG,110NUFUFUFDIAG即任意一个NM阶的分块R循环矩阵必可以准对角化。定理322推论311的结论I，即为R分块循环矩阵的准对角化过程。即设,110NRAAACA，0W为范德蒙矩阵1111101100111NNNNNUUUUUUW，MEWW0，ME为M阶单位矩阵其中110,NUUU为0RXN的全部根，1110NNXAXAAXF，则,1101NUFUFUFDIAGAWW，此即R分块循环矩阵的准对角化。定理323由推论311的结论IIIDETDETDETDET110NMNMNMNMNUFEUFEUFEAE可得R分块循环矩阵的特征值为对角线上的分块矩阵1,1,0NIUFI的特征值
34、的集合。由推论311的结论IIDETDETDETDET110NUFUFUFAR分块循环矩阵的行列式的值为对角线上的分块矩阵的行列式值的乘积，即10DETNIIUF。33R分块循环矩阵的逆定理331由推论311II的结果，即,110NRAAACA为R分块循环矩阵，0W为范德蒙矩阵1111101100111NNNNNUUUUUUW，MEWW0，ME为M阶单位矩阵其中110,NUUU为0RXN的全部根，1110NNXAXAAXF，则有DETDETDETDET110NUFUFUFA。可得R循环矩阵可逆的一个充要条件是0DET10NIIUF。定义3311,1,0NJWJ表示方程0RRXN的N个根。引理3
35、3114设RNRBCMAAABCA,110，若TNXXXX,21是线性矩阵方程组NEAX的解，其中,2,1NJXJ都是M阶方阵，则RNNRBCMXXXBCA,111定义332设RNRBCMAAABCA,110，RNRBCMBBBBCB,1101110NNXAXAAXF，1110NNXBXBBXG。引理33214设MNNMNMNMNMNMMMMNMMMMMMMIWIWIWIWIWIWIWIWIWIWIWIWIIIIE11121110212221201210矩阵A、B的定义如定义332所给，则有,1100MNMNMMIWGIWFIWGIWFEDIAGABE。引理33314A、B、XF、XG的定义如
36、定义322所给，令M阶方阵MJIPWF，MJIPWG，JA，JB1,1,0NJ的元素分别为,2,1,1,1,0J,MLKNBAGFKLJKLJKLJKLJ则MIIPWF可由下面式子计算得到,2,1,1111111111011211242121102MLKAPPAAWWWWWWWWWFFFKLNNKLKLNNNNNKLNKLKL定理33214NM阶矩阵RBCMA求逆的计算复杂性为LOG322NMNNMO。证若R0，由块TOETLITZ三角阵求逆的性质，结论显然。若R0,设RNRBCMAAABCA,110非奇异，由引理331知RBCA1，故可令,1101NRBBBBCBAXF，XG定义如定义332
37、所给。由引理332可知，1,1,0,1NJIPWFIPWGMJMJ若令MJIPWF，MJIPWG，JA，JB1,1,0NJ的元素分别为,2,1,1,1,0J,MLKNBAGFKLJKLJKLJKLJ则有下面的式（I）,2,1,1111111110112112111102MLKGGGWWWWWWNBPPBBKLNKLKLNNNNKLNNKLKL则计算RBCA的逆阵可分为以下步骤（1）由引理333计算矩阵MJIPWF，1,1,0NJ，利用FFT算法，计算量为LOG22NNMO；（2）由1,1,0,1NJIPWFIPWGMJMJ，利用通常的矩阵求逆方法，计算量为3NMO；（3）由式（I）计算矩阵，利
38、用逆FFT算法，计算量为LOG22NNMO。综合上述三步，得NM阶矩阵RBCMA求逆的计算复杂性为LOG322NMNNMO。引理33415设矩阵,110MRAAACIRCA，其子块1,1,0MJAJ，R均为N阶R循环矩阵，且A，R均非奇异，则,1101MRBBBCIRCA，且其子块,1,0MJBJ仍为N阶R循环矩阵。定理33315设非奇异矩阵,110MRAAACIRCA，非奇异矩阵,110MRRRRCIRCR，1,1,0,110MJAAACIRCAJNJJRJ，设10NTTTTXRXR，101,1,0NTTTJTJMJXAXF，101,1,0,MJJJKKNJKNKXWFXG，1011,1,0
39、,1MPPPMKKNKXWGMXH，101,1,0,11NKKJMKJKJMJXWHNXD则,1101MRBBBCIRCA，,110JNJJRJBBBCIRCB，其中1,1,0,1,1,0,1,NTMJWDBRTNJTJTN,1,2SIN2COS2ININWN1,1,0NKWRMKNK此即R循环分块矩阵求逆的快速傅里叶算法。推论331注意到0,0,IMRCIRCRR，易得定理333的结论可适用于R分块循环矩阵RNRBCMAAABCA,110，在每个1,1,0,1010NJAAACIRCAJJJRJ，即定理333适用于每个分块矩阵JA为R循环矩阵的R分块循环矩阵逆的求解。4算例例1设200001
40、2400201201A，对A进行准对角化，求出A的特征值，A。解,110NRAAACA，20010A，00121A，R2，应用第三章中的结论有20U，21U，22110W，2020020210100101W，2022212001220010100UAAUF2022212001220011101UAAUF20002221000020002221,101UFUFDIAGAWW2211，2212，2432822221221A例2设2020012410201201A，对A进行准对角化，求出A的特征值，A。解,110NRAAACA，20010A，10121A，R2，应用第三章中的结论有20U，21U，2
41、2110W，2020020210100101W，22022212101220010100UAAUF22022212101220011101UAAUF2200022210000220002221,101UFUFDIAGAWW2211，222，2213，222142222122221A例3设10816014824101201A，判断A是否奇异，若A非奇异，求1A解,110NRAAACA，10010A，24121A，R4，应用第三章中的结论有20U，21U，22110W，2020020210100101W，58252241210010100UAAUF38232241210011101UAAUF3800230000580025,101UFUFDIAGAWW631691625A所以A非奇异。注意到A满足推论331的条件，其中10010A，24121A，4004R，R4。用快速傅里叶算法计算1A步（1）1,24NW4404111111RR，2,210步（2）110111111100FF042211111111FF步（3）798111111111111110000FFGG110111111111111111011FFGG步（4）7191111010GG，11111111GG
