矩阵_广义逆的加速计算

矩阵_广义逆的加速计算 矩阵 α-β 广义逆的加速计算 12范大付 ，唐高华 (1. 广西百色学院 数学与计算机信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 系，广西 百色，533000) (2. 广西师范学院 数学科学学院，广西 南宁，530001) m×n 摘 要:研究矩阵 A?C的 α-β 广义逆的加速计算并且给出了误差界。最后还给出了数值算例。 关键词:矩阵，广义逆;矩阵 αβ 广义逆;迭代格式，算法 - 中图分类号:O151 文献标识码:A 文章编号:1001-7119(2012)09-0004-04 Successive Matrix Squaring s for Computing the Generalized Algorithm -1Inverse A of a Given Matrixα,β 12 FAN Dafu，TANG Gaohua (1. Department of maths and computer Science, Baise College ,Baise 533000, China ; 2.School of Mathematical Sciences, Guangxi Normal University, Nanning 533000，China ) Abstact:In this paper，we investigate successive atrix squaring (SS) algoriths for coputing the generalized inverse rmMmm -1m×n A of a given matrix A?Cand also give numerical example.α,β Key words:matrix;the generalized inverse; the generalized inverse α-β of a given matrix ;iterative; algorithm . [1] 满足(见) 0 引言与引理 φ(λx，(1,λ)y)，λφ(x)，(1,λ)φ(y) (0.1) m n 定义 2 设 α，β 分别为 C和 C上的 e,s,c,范 数，矩阵广义逆在数值代数和数理统计等领域 m×n[17]-对任何的 A?C，我们可定义 α,β 广义逆， 中有着非常重要的作用，文献给出许多关于广 [1]1 - [1,3,5,7-14]): A 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示(见 α,β 义逆的研究。文献研究了各种计算广义逆- 1 [7,9,11][15]A,(I,P)A P(0.2) α,βN(A)，βR(A)，α 的迭代方法和算法。本文运用的方法对文献 [16] 文 分别给出了矩阵加权α ,β 广义逆的定义的迭代格式作加速计算并且应用这个加速算法 [5] (文给出了线性算子的情况)。计算 α,β 广义逆。 m n 定义 3 设 α，β 分别为 C和 C上的 e,s,c,范 下面给出本文需要的概念 (本文采用的记号m×n[15]数，对任何的 A?C，我们可定义 α,β 广义逆， 和文一致) 。-1 m×n A表示(见[1]):α,β 设 A?C表示复数域上 m×n 的矩阵，我们 -1 * -1R(A)，α ,(I,PP(0.3) A )A M，N α,β N(A)，β ，A和 rank(A)分别表示矩阵 A 的 α,β 广用 A α,β mn ?C，N ?C都是正定矩阵 A是关于 其中 M ， M，N 义逆，共轭转置和秩。 n M，N 的加权 M-P 广义逆。定义 1 称 C上的范数 φ 是本性严格凸 (简 (文[15])给出迭代格式称为 e,s,c,)，如果对所有 x?0 和 y埸,μx?μ0,，φ ? 收稿日期:2011-11-13 基金项目:国家自然基金(11161006)，广西自然基金(2011GXNSFA018139) 作者简介范大付:(1974-)，男，硕士，广西灌阳人，广西百色学院数学与计算机信息工程系，研究方向:基础数学，概率与统 计。E-mail:fdf9919@163.com 5 第 9 期 范大付等.矩阵 α-β 广义逆的加速计算 ，1 和迭代(1.4)，有 R,P,AX，X,XR，X，k,0，1，2，… (0.4)()α，10kRA，kkkk -1作者证明了(0.4)收敛于 A圳(I -P)X =X ， α,β n N(A)，β 0 0 ρ(R)，1。 0 对偶的迭代格式 R=I-P-XA，X=RX，X，k,0，1，2，… kN(A)，βkk，1k0k (0.5) -1则(0.5)的迭代格式收敛于 A圳 ，P= ，XX α,β 0 ()，α 0 NA ρ(R)，1。 0 (1.7) 由(1.5)~(1.6)，我们可给出下面的算法: 算法 1 1 矩阵 广义逆的加速计算- step 1: 输入矩阵 A，X，0 step 2: 给 Q 赋值 X;本文主要对迭代格式(0.4)(0.5)进行加速且将 0 step 3: 计算 P坩P-AQ ;鄹坩I+P;其应用于计算矩阵 α,β 广义逆。 R(A)，α1 m×n 赞 e坩‖X-X‖定理 1 设 A?C,序列,X,收敛于 α,β 广 10k step 4: 判断当 e，e，执行 P坩P?P;X坩X+P;e坩 -1k+1k 当且仅当义逆 A α,β ‖X-X‖k+1k -1赞 (I-P)X,X，ρ(R)，1。此时‖A-X‖α,β k n()，β000NA step 5: 输出 X; k+1 k+1 2-1 ?q (1-q)‖X‖ (1.1) 0step 6: 将 QX赋值给 Xk+1 其中 q=‖R‖。 0算法结束。 同理，我们可以推广我们的算法得到结论。 证明:若令 P=R=P-AX，Q=X(1.2)0R(A)，α00 m×n赞 定理 2 设 A?C，序列,X,收敛于 α,β 广 k 由(1.2)，可定义义逆圳(I-P)X,X，ρ(R)，1。此时 nN(A)，β000 (1.3) k+1 T= = 0 00 0 -1 -1mX0 P 0 ‖A(1,q)‖X ‖ (1.8) 赞 0 ‖?q -Xα,β k 0 R0I Q I 所以 其中 q=‖R‖。0 Σ Σ k Σ Σ P 0 Σ Σ 证明:假设 k Σ (1.4) 00Σ k-1 I Σ Σ P 0 Σ Σk =Σ T= ΣΣ Σ IX k-1 Σ Σ Q Σ ΣΣi = 0 Σ Σ 下面我们定义: 2 T=T，T=T，k,0，1，2，… (1.5)k 0k+1Σ Σ k Σ Σ P 0 Σ Σ k ΣΣ 2 Σ Σ k-1 ΣΣT=T = Σ kΣ Σ Σ Σ Σ QI ΣΣ Σ= 0 i Σ Σ 赞 =X，则 kk若设 X 2 -1 Σ Σ k k Σ Σ P 0 Σ Σ2 Σ Σ 0 0 = Σ Σ QI Σ0 P (1.6) Σ k-1 Σ Σ Σk Σ ΣT=XI kΣ Σ 2-1 Σ Σ i = 0 Σ Σ (1.9)赞 由迭代格式(0.4)，我们容易证明序列,X,收k -1敛于 α,β 广义逆 A当且仅当(I -P)X =X ，α,β n ()，β 0 0 NA类似 (1.5)，我们定义: 5 第 9 期 范大付等.矩阵 α-β 广义逆的加速计算 ρ(R)，1。这里省略掉其证明。下面只给出定理后 20 ，k,0，1，2，… (1.10)T =T，T=T k0 k+1 k 2 -1 i 赞 k所以=蒡PQ。由 ρ(R) 半部分的证明。因为X=X 0k2 -1 i=0 6 科 技 通 报 第 28 卷 k，1 2 -1 ,1赞,‖?qX‖A(1,q) ‖X‖ (1.14) α,βk0 其中 q,‖R‖。0 m×n赞 定理 4. 设 A?C，序列,,收敛于 α,β 广 Xk 义逆圳XP,X，ρ(R)，1。此时 0R(A),α00 k，1 m1 - 赞,1‖A,X‖?q(1,q) ‖X‖ (1.15) α,βk0 其中 q,‖‖。R0 (1.11) 赞 k 假设 X,，则 X k2 矩阵加权 α,β 广义逆的加速计算( ,1 )m 2 Tk, = 1.12 在这一节我讨论迭代格式 (0.4) 对矩阵加权 k X ( ) * 0 0 * 赞 α,β 广义逆的加速计算。首先，给出下面的引理: X*(2 ,1)m * k [5],1赞 引理 1. 设 A( α，β)为定义 3 中的矩阵加权 由迭代格式(0.4)，我们容易证明序列,,收敛于Xk, MN -1α,β 广义逆 A当且仅当(I ,P)X =X ，α,β n N(A),β 0 0 α,β 广义逆，则有下面性质:,1 (1)AA(α，β),P， ρ()，1。这里省略掉其证明。下面只给出定理后RR(A),α0M,N k 2 ,1,1 ,1 ,1 赞 i(2)A(α，β)AA(α，β)=A(α，β)，M,NM,Nk,MNX半部分的证明。因为,X ,蒡PQ。由 ρ(R)i,0k0 2 ,1 ,1 é(3)A(α，β)A=(I-P)P , M,NN(A),β，1 和迭代(1.4)，有 R(A ),N(A) ,1(4)AA(α，β)A=A, , MN,1 (5)N(A(α，β)),N(P)。,N MR(A),α é-1 其中 =NM。AA* 由以上的引理 1 和第二部分我们可以容易得 到。 m×n赞 定理 5.设 A?C,序列,X,收敛于 α,β 广义 k -1é圳(I,P)P 逆 AX ,X ，ρ(R)，1。此时 0 0 0 α,βnN(A),βR(A ),N(A) k，1 2 -1 ,1赞 ‖A(1,q)‖X ‖ (2.1),X‖?q0α,βk (1.13) 其中 q,‖R‖。 0类似算法 1 且由(1.9)~(1.12)，我们有以下算 m×n赞 X法:定理 6.设 A?C，序列,,收敛于 α,β 广k(1)给 Q 赋值:Q=X 0é 义逆圳(I,P)P ,，ρ()，1。此时XXRnN(A),β000R(A ),N(A) k，1(2)定义整数且赋值:n,100 m -1 ,1赞 ‖A(1,q) ‖X‖ (2.2),X‖?q0,βkα (3)计算:i,1?n 其中 q,‖R‖。0P;X,I，P iii P,P-AQ;P,P?i(),αi，1iRA (4)判断:e，e 执行 3 算例 P=P?P;P,P?P;P=P?P; imii，1mi，1mmm XX+P+P+…+Pi+1i m m-1 1本节给出用迭代格式(0.4)的加速算法 2 来计 e=‖X-X‖k+1k算矩阵 A 的 α,β 广义逆。 0 0 002 1 1 1 0 0 X=QX 00k+10 0 000 2 0 0 004×4 00例 3.1 设 A, ?C,假设 α，β 都表 结束000 0 0 0 2 0 0 0 m×n赞 00定理 3.设 A?C, 序列,X,收敛于 α,β 广 k000 0 0 0 0 0 -1范数，则有知道α ，β 都是本质严格凸范示‖?‖义 逆 A 圳 , ，ρ ()，1。 此 时XPXR2 α,β 0 N (A),α 0 0 7 第 9 期 范大付等.矩阵 α-β 广义逆的加速计算 0 0 00 数。因此可以算出-0.2432 -0.2432 0 0.4992 0 0 000 0 00I00 0.4992 0 0 0 0 3 0 0 4×44×4 0 0 X= , P= ?C，P= ?C ，30 00 0R(A),αN(A),β 0 0 000 0 0.4992 0 0 1 0 0 0 0 000 00 0 0 0 003×3I 3?C0 0 000.4998 -0.2483 -0.2483 0 0 0 由定义 2，我们容易得到 0 0 000 0 0 0 0 0.4998 0 0 0 0 000.5000 -0.2500 -0.2500 0 0 0X= , 0 0 40 0 00 000 0 0.4998 0 00 0 00 0 0.0000 0.5000 -0.0000 0 00 (3.1)0 0 0 0 0= α,β -1 0 0 0 0 A0 0000 0.0000 0.0000 0.5000 0 - 00 0 00 0 0 00 0 0.5000 0.2496 0.2496 0 -- 00000 0 0 0 0 0 0 0 00 000 0.5000 0 0 0 0 若选初值: 00X= , 50 0 0 0 0 0.5000 0 0 0 0 000 0 0.4 0 0 0 00 00 000 0 0 0 0 0 0 0 00 0 0 0 0.4 0 00 04×400 ? C00Q=X= 0 0 05000 -0.2499 -0.2499 0 0. 0 0 0.4 0 0 0 0 0.5000 0 0 0 0 00 000 0 0 0 00 000 0 0.5000 0 0 0 000 0 0 0 000 0 X = , 6 000 0 0 0 则由(1.2), 我们有 0 0 000 0 0 0 0 0 00 000.2000 -0.4000 -0.4000 0 00000 0 000.5000 -0.2500 -0.2500 0 00 00 0 0 0 0.2000 0 0 0 00 0 00 00P=R= 0 000 0.5000 0 0 00 001 - 000 0 0.2000 0 0 0=AX = 7 α, β0 0 0 0 000 00 0 0.5000 0 0 0 0 00 0 0 0 00 00 0 00 0 0 0 0 0 由算法 2，我们可以得到 0 0 (3.3) 000.4992 -0.2432 -0.2432 0 000 0 因此从(3.2)和(3.3)，我们可以知道到由算法2 只 0 00 0 0 0.4992 0 0 00 00X= , 1 需要 3 步就可以得到结果了，但是由迭代格式0 0 0 0 0 0 0.4992 0 00 0 0 (0.4)我们需要 7 次迭代。0 0 0 0 0 0 00 000 0 0.5000 0.2496 0.2496 0 -- 00 0 0 参考文献: 000 0 0 0.5000 0 0 0 0[1] A Ben -Israel，T N E Greville. Generalized Inverses: 00X= , 20 00 0 0 0 0.5000 0 Theory and Applications [M]. seconded，Springer Verlag， 00 000 00 0 0 0 0 0 New York，2003: 125-134. 0 0 000.5000 -0.2500 -0.2500 0 [2] 蔡静，朱超，陈果良.α-β 广义逆的扰动理论及其应用[J].0 0 000 0华东师范大学学报，2001，(4): 2227. - 0 00 0.5000 0 0 0 0 -1 00X= =A α, β30 0 [3] 刘国明. 关于计算矩阵 α-β 广义逆的迭代法[J]. 山东师 0 00 0 0.5000 0 0 0 00大学报(自然科学版)，2000，15(1): 16-18. 000 0 0 0 0 0 [4] Wang G，wei Y，Qiao S，Generalized Inverses: Theory and (3.2)Computations[M]，Science Press，Beijing/New York，2003. 但是由迭代格式(0.4)得到[5] Wei Z X，Chen G L.The definition and computing methods 000 0 0.4800 0.1600 0.1600 0 --0 0 of weighted-gengeralized inverse[J]. Journal of East China 0 0 000 0 0 0.4800 0 0 Normal University，2001，106(4): 1-9.000 0X= , 100 0 00 0 0.4800 0 [6] Wei Y M. A characterization and repres enta ti on of the 0 0 00(2) 0 0generalized inverse A and its applicat ons [J]. Linear 0 0 0 0 00T,S 00 Algebra and its Applications，1998，280(23): 87-96.-0 0 0.4960 -0.2240 -0.2240 0 00 0 00 0[7] B Codenotti，M Leoncini，G Resta. Repeated matri x squa - 000 0.4960 0 0 0 0 00X= , ring for the parallel solution of linear systems [J]. Lecture 20 0 000 0 0.4960 0 0 0 0 00 0 0 0 0 0 0 0 ,下转第 19 页, 19 第 9 期 李晓东.平面图全染色的一个注记 + Uspekhi Mat.Nauk 1968，3:,:117-134(in Russian). max{d(ν)，…，d(ν)}=421i- [3] W F Wang. Total chromatic number of planar graphs with 35 , ω(ν)?ω(ν),2-5× - -1=0maximum degree ten[J]. J. Graph Theory,54(2007)91-102. 44 [4] X Y Sun, J L Wu, Y W Wu, J F Hou.Total colorings of a ν)=0。 (6)n=3，f(3 planar graphs without adjacent triangles[J], Discrete Math. 设 ν 相邻的七个顶点依次为ν ，ν，ν，ν，ν， 123452009,309:202-206. ν，ν。由引理 3 可知，ν 的 2-邻点不能出现在同 67[5] O V Borodin, A V Kostochka, D R Woodall. Total coloring 一个 4-面中，不妨设 d(ν)=d(ν)=d(ν)=2，由引 135of planar graphs with large maximum degree [J]. J. Graph 理 5 中，图 1.1-1.4 知， theory 1997,26:53-59. +++ d(ν)=4，d(ν)=4，max{d(ν)，d(ν)}=4， 2467[6] O V Borodin, A V Kostochka, D R Woodall. Total coloring 从而，由 R，R和 R，有 12 3of planar graphs with large girth[J]. Europ.J.Combinatorics 1998,19:19-24. 3,1，0。 - ω(ν)?ω(ν),2-6× [7] J F Hou, G Z Liu, J S Cai.List edge and list total coloring 4 of planar graphs without 4-cycles[J]. Theoretical Computer (7)n=3，f(ν)=1。3 Science. 2006,369:250-255. 设 ν 相邻的七个顶点依次为ν ，ν，ν，ν，ν， 12345[8] L Shen,Y Q Wang, Planar graphs with maximum degree 7 ν，ν。不妨设，ν 关联的一个 3-面为(ν，ν，ν)面。 6767and without 5-cycles are 8-totally-colorable [J], Discrete 由引理 3 可知，ν 的 2-邻点不能出现在同一个 4- Math. 2010,310:2372-2379. 面中，所以 d(ν)=d(ν)=d(ν)=2，由引理 5 中，图 135[9] H P Yap.Total colourings of graphs [C]//Lecture Notes in + 1.1-1.4 知，d(ν) =4 ，i ?{2,4,6,7}，从而，由R ，R Mathematics, vol.1623, Springer, Londen,1996. i12 [10] D Z Du,L Shen,Y Q Wang.Planar graphs with maximum 和 R，有3 degree 8 and without adjacent triangles are 9 -totally - 35 , ω(ν)?ω(ν),2-6× - ，0。colorable[J].Discrete Math.2009,157:2778-2384. 44 [11] O V Borodin. On the total coloring of planar graphs [J].J. 证毕。 Reine Angew Math. 1989,394:180-185. [12] L Shen,Y Q Wang.Total colourings of planar graphs with 参考文献: maximum degree at least 8 [J].Science in China A. Vol. [1] M Behzad.Graphs and their chromatic numbers, Ph.D. 52,No.8, 1733-1742. Thesis, Michigan State Univerity,1965. [2] V G Vizing.Some unsolved problems in graph theory, ,上接第 页, 7 Notes in Computer Science 605，Springer，New York，Math Comput，203，(2008):19-29. 1992: 725-732. [12] Pierre Courrieu. Fast Computation of Moore -Penrose [8] Liu X J ，Yu Y M，Hu C M. The iterative methods for Inverse Matrices [J]. Neural Informa Process，8，(2005): (2)computing the generalized inverse A of the bounded 25-29. T,S linear operator between Banach spaces [J]. Appl Math Katsikis，D Pappas. Fast Computation of Moore [13] V N - Comput，214，(2009):391-410. Penrose Inverse Matrices[J]，Electronic Journal of Linear Algebra，17 (2008)，637-650. [9] Wei Y M. Successive matrix squaring algorithm for com- puting the Drazin inverse [J]. Appl Math Comput，108， [14] F Toutounian，A Ataei. A new method for computing (2000):67-75. Moore -Penrose inverse matrices [J]. J Comput Appl [10] Chen Y. Iterative methods for computing the generalized Math，228 (2009)，412-417. (2) of a matrix [J]. Appl Math Comput，75，(2 [15] 周光平，刘晓冀.αβ 广义逆的迭代法[J]. 工程数学报， --inverse A T,S 3)，(1996):207-222.2011 28(4) 513-518. [11] P S Stanimirovi，D S Cvetkovi -Ili Successive matrix [16] E H Moore. On the reciprocal of the general algebraic squaring algorithm for computing outer inverses[J]，Appl matrix[J] (Abstract). 1920(26).