走阶r循环矩阵开平方的快速算法兴

《走阶r循环矩阵开平方的快速算法兴》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3卷第1期杭州师范学院学报(自然科学版)Vol.3No.12004年1月JournalofHangzhouTeachersCollege(NaturalScienceEdition)Jan.2004文章编号;1008-9403(2004)01一0017一052走阶r-循环矩阵开平方的快速算法兴黄德超(杭州师范学院信息工程学院.浙江杭州31(012)摘要:对n(=护，是二三])阶r-循环矩阵的开平方运算进行了研究.利用矩阵分块逐次降阶的方法，给出r_..个快速算法，用来计算r循环矩阵的同型平方根矩阵(平方根矩阵也为r-循环矩阵).证明了同型平方根矩阵的个数为2"，计算一个同型平方根矩阵的时间

2、复杂性为O(n!og，n)，计算全部同型平方根矩阵时间复杂性为。(n2"!og，n).关键词:扩阶r循环矩阵;开平方;降阶方法;同型平方根矩阵;算法和复杂'性中图分类号;0241.6文献标识码;AO引言r-循环矩阵是一类很重要的特殊矩阵，它在数字图像处理、线性预测、自回归滤波器设计、计算机时序分析、编码理论、密码学、结构计算等许多实际问题中有着广泛的应用.近年来，对其特性及有关快速算法的研究引起了人们的普遍重视.目前，已有计算全部特征值、求逆、相乘等运算的快速算法，其时间复杂性都为ο(nlogzn)[1.2J.文章试图对开平方运算进行研究.但因某些循环矩阵的平方根的矩阵有无穷多个，且没有一定

3、的规则，而由文[lJ知，r循环短阵的平方仍为χ循环阵，所以文章仅局限于研究平方根矩阵为[pJ型矩阵的开平方运算，利用矩阵分块逐次降价的方法，给出了计算n(Z舟，走注1)阶r-循环矩阵的向型平方根矩阵的快速算法，证明了同型平方根矩阵的个数为211，计算一个同樱平方根矩阵的时间复杂性为。Cnlogz川，计算全部同型平方根矩阵的时间复杂性为ο(nZ"logz月).文章给出的算法，具有计算量少，思路清晰，易于编制程序及在计算机上实现等特点，是较为实用的算法.不失一般性，在此假设r手O.1快速算法定义1[IJ若矩阵A=(ajj)εCnX满足[aj…j,J二三1;a，.气1.n,lra叶;_j，j

4、,其中r为参数，则称A为n阶严循环矩阵，简记为收稿日期;2003-10-27作者简介:黄德超0972一九男，浙江苍商人，基础数学专业算法设计与计算机软件方向02级研究生传论文获杭州师范学院第五届"挑战杯"大学生课外科技比赛作品一等奖18杭州师范学院学报(自然科学版)2004年A=C~(ao,a1,…,a"-1)仨CM;，当r1时(此时r可省略)为通常的循环矩阵;当r=一1时为通常的反循环矩阵.2定义2[2J设AεCMr，β廷CM"若B=A，则称B为A的(一个)同型平方根矩阵;记为B=At"一l在此约定用ω/j=汇百-1)表示方程x"=r(手0)的根，并记f(x)=三Jaj1=01.若AεCM

5、;'，显知A可分块为ikl)A(2)lA=(1)ωA())rAA(1)Aω1其中、都是2'阶Toeplitz矩阵.2.令G主c;(O，l，O，…，0)仨CM:~.则显然有第J十l个G1=C;(O,…,0,1，0，…，0)εCM;,0<.j<.n-1.O并有G=1,G"r1，其中I为n阶单位阵.引理1[IJ若A=C;(ao，al'…，an一1)εCM;，则A=f(G);反之若A=f(G)，则A=C;(ao,al'…,a"-I)ECM;.引理2[3J设A=C;'(ao.a1，…，即-1)ECM;'，分块如(I)，则FrM)」Lr1)+J7Aω=C♂去(aO+rra2'-1,a1+rra沪It1'

6、a2+rra2'--1+2,时1←1+rr时1)εCM♂去(2)GJA)主AU)-J7A{2〉zCflr(ao-J7时1,a1-rra2'-1+1，a2一刀、沪1+2,…，a2卜1-1-rr时1)ξCM2~-I，r;:-(3)定理1设A=cf(ao，al,…,a2'-1)εCMf，BzCf&(boJl,…,b2'_-I)ECM;'，分块如(1)，若B2=A，则B())士/F，(互7士/G立王))/2，(4)B(2)=(土A丁五丰/Gr(A))/2rr,其中F，.(A)，Gr(A)的意义如引理2.证明令r11K=I1rr1-rrlJ其中I为2'-1阶单位方阵，则不难验证AEr=Erdiag(F

7、r(A),Gr(A))(5)及BEr=Erdiag(Fr(B),Gr(B))(6)其中F，.(B)主(ß(])十rrB(勺εCM2是元，Gr(ß)主(ß(])-rrB(勺εCM~-I_厅'由(6)式可得AEr=BBEr=BErdiag(Fr(B),Gr(ß))=Erdiag(Fr(B),Gr(ß))Xdiag(Fr(B),G..(ß))=Erdiag(F..(ß)2,Gr(B)2))(7)比较(5)、(7)两