约束的奇异半定远线性方程组的迭代解法

约束的奇异半定远线性方程组的迭代解法

0半收敛矩阵的解析确定1965年，keell研究了难以置信的hetle函数。Ax=b(1)的迭代解法,证明了一个著名的结果:若A=M-N是P-正则分裂(即M非奇异,且M*+N为正定阵),则迭代xj+1=M-1Nxj+M-1b(2)是半收敛的(指迭代阵M-1N是半收敛阵)当且仅当A是半正定阵.1997年,Ern与Giovangigli研究了求解约束方程组Ax=b,x∈L(3)的问题,其中A∈Rn×n是奇异的对称半正定阵,L为Rn的子空间,满足如下条件:b∈R(A)与L♁N(A)=Rn.(4)据文报道,形如(3)的约束方程组的求解问题,有着多方面的应用背景.文首先给出了Keller定理的一个很长的新证,然后在Keller定理的基础上,借助于迭代(2),提出了所谓的“投影迭代算法”(Projectediterativealgorithms):y0=PL,N(A)x0,yj+1=PL,N(A)M-1Nyj+PL,N(A)M-1b,j=0,1,2,…,(5)并证明了两个主要的结论:(1)ρ(PL,N(A)M-1N)<1;(6)(2)y∞=limj→∞yj=limj→∞ΡL,Ν(A)xj=Ζb(7)(2)y∞=limj→∞yj=limj→∞PL,N(A)xj=Zb(7)是(3)的惟一解,其中Z是A的对称半正定(1,2)-逆,且R(Z)=L.本文的目标有两个:一是给出Keller定理的新证,它比文给出的新证浅显而简洁,并据之给出文关于投影迭代(5)的两个主要结论的简证;二是提出求解约束方程组(3)的两个十分简单的迭代格式.附带地,我们将给出半收敛阵的几个等价描述以及四分块三角阵半收敛的充要条件.本文采用文中关于广义逆矩阵与投影算子的记号.另外,σ(A)表示A的谱,ρ(A)表示A的谱半径,在A仅有实特征值时,用λmax(A)与λmin(A)分别表示A的最大与最小特征值.一如通常,若limj→∞Aj=0limj→∞Aj=0,则称A为收敛阵;若limj→∞Ajlimj→∞Aj存在(其值无需为零阵),则称A为半收敛阵.引理0.1设A∈Cn×n.则下列提法是互相等价的:(1)A半收敛.(3)(I-A)#存在,且ρ(A(I-A)(I-A)#)<1.(4)(I-A)#存在,且δ(A)≡max{|λ|:λ∈σ(A),λ≠1}<1.(5)(I-A)#存在,且ρ(APL,N(I-A))<1,其中L为N(I-A)的任一补子空间.证明注意(I-A)#存在当且仅当I-A可逆或可表为,其中C可逆,并用关系式ρ(FG)=ρ(GF).(1)(I-G)#存在当且仅当如下两个条件成立:(a)A#与B#均存在,(b)(I-BB#)C(I-AA#)=0;(8)其中W=B#2C(I-AA#)+(I-BB#)CA#2-B#CA#.(10)(2)G半收敛当且仅当如下两个条件成立:(a)I-A与I-B均半收敛,即A#与B#均存在,ρ((I-A)AA#)<1,且ρ((I-B)BB#)<1;(11)(b)(I-BB#)C(I-AA#)=0,(12)此时其中Z=-(I-BB#)CA#-B#C(I-AA#).证明(1)熟知,(I-G)#存在⇔对某个矩阵X有I-G=(I-G)2X,即[A0CB]=[A20CA+BCB2][X1X2X3X4][AC0B]=[A2CA+BC0B2][X1X3X2X4]⇔{A=A2X1①,0=A2X2②,C=(CA+BC)X1+B2X3③‚B=(CA+BC)X2+B2X4④①表明了A#存在.以A#左乘②的两边得AX2=0⑤以A#左乘①的两边得AX1=AA#⑥从③与⑥推出C=CAA#+BCX1+B2X3⑦由⑦得C(I-AA#)=BCX1+B2X3,左乘以(I-BB#)得到(8)中所示的条件(b).又,从⑦与⑤可得CX2=BCX1X2+B2X3X2,代入④,并注意⑤,可得B=B2(CX1X2+BX3X2+X4).此式即表明B#存在.以上证明了条件(8)的必要性.反之,若条件(8)中的两个条件(a)与(b)成立,则可直接验明,(9)式右边的矩阵是(I-G)#.这证明了条件(8)的充分性.(2)据引理0.1之(3)知,G半收敛⇔(I-G)#存在且ρ(G(I-G)(I-G)#)<1.(1)中已证明(I-G)#存在⇔条件(8)成立,且此时(I-G)#的显式为(9).不难算得其中Q=-CAA#+(I-B)B#C(I-AA#)+(I-BB#)CA#.(14)从(13)式易见ρ(G(I-G)(I-G)#)<1⇔ρ((I-A)AA#)<1且ρ((I-B)BB#)<1.(15)条件(15)与(8)合在一起就是条件(11)与(12).计算I-(I-G)(I-G)#,即得极限limj→∞Gj的显式.引理0.2设约束方程组(3)满足条件(4).则:(1)Bott-Duffin逆A(-1)(L)存在,且它是A的对称半正定(1,2)-广义逆,也就是上面(7)式中的Z.(2)对任何b∈R(A),方程组(3)有唯一解A(-1)(L)b.1半收敛及半收敛定理1.1设A是n阶Herminte阵,A=M-N是A的P-正则分裂.记H≡M-1N.则H半收敛当且仅当A半正定.证明不失一般性,可以假定A=[A11A12A*12A22]‚rankA=rankA11=r,A11是非奇异Hermite阵,0<r<n.此时A有分解式因为M非奇异,所以存在某个n阶非奇异阵˜D=[˜D11˜D12˜D21˜D22]使得M可表为令,其中D11∈Cr×r,则不难算得可以看出,H≡M-1N与是相似的.因此,H半收敛当且仅当ˆD半收敛.从而只需研究ˆD的半收敛性.据定理0.1,可知ˆD半收敛当且仅当下述三个条件成立:(a)(D11A11)#存在,(b)D21A11=D21A11(D11A11)(D11A11)#,(c)ρ((Ir-D11A11)D11A11(D11A11)#)<1.因为[D11D12D21D22]与A11均非奇异,而用条件(b)可得所以D11是非奇异的;进而可知条件(c)就是ρ(Ir-D11A11)<1.(22)反之,若条件(22)成立,则D11A11是非奇异的,从而条件(a)、(b)、(c)成立,故ˆD是半收敛阵.这样,我们证明了:H≡M-1N半收敛⇔ρ(Ir-D11A11)<1.(23)我们还需要一个恒等式A-H*AH=(I-H)*(M*+N)(I-H).(24)为此,我们采用文的办法:对任一x∈Cn,令˜x≡Ηx=Μ-1Νx与y≡x-˜x=(Ι-Η)x.易知Μy=Ax,Νy=A˜x,从而有x*Ax-˜x*A˜x=x*Μy-˜x*Νy.用x*Ν*=˜x*Μ*‚Μ=Μ*-Ν*+Ν代入上式,可以得到x*(A-H*AH)x=x*(I-H)*(M*+N)(I-H)x.(25)注意到A-H*AH与(I-H)*(M*+N)(I-H)均为Hermite阵,x是任意的,所以从(25)立得(24).现在将A,H,I-H,M*+N的表达式全部代入(24)式,然后在所得等式的两边,以[I,0]左乘,以[Ι0]右乘,可得等式由于M*+N是正定阵,[D11D21]是列满秩阵,A11是非奇异Hermite阵,所以(26)式右端的矩阵是正定阵.据古典的Stein定理,立即可知ρ(Ir-D11A11)<1⇔A11是正定阵.(27)现在将两个等价性(23)与(27)连接起来,就完成了证明.次之定理是对文关于投影迭代法的主要结论的简证,而文的证明相当烦琐.定理1.2设约束方程组(3)与投影迭代法(5)如上.则:(1)ρ(PL,N(A)M-1N)<1;(2)y∞≡limj→∞yj=limj→∞ΡL,Ν(A)xj=ΡL,Ν(A)x∞=A(-1)(L)b.是(3)的唯一解,其中xj是由迭代(2)产生的项,x∞≡limj→∞xj.证明(1)设L=R(E),此中E∈Rn×rr,A=[A11A12AΤ12A22]如上.从(16)式容易看出,N(A)=N([Ir,A-111A12]),且从(4)中的直和分解L♁N(A)=Rn知,[Ir,A-111A12]E是r阶可逆阵,从而有PL,N(A)=PL,N(I-M-1N)=E([Ir,A-111A12]E)-1[Ir,A-111A12].(28)用(19)式中的H≡M-1N的表达式,不难算得PL,N(A)M-1N=E([Ir,A-111A12]E)-1(Ir-D11A11)[Ir,A-111A12].(29)由于ρ(AB)=ρ(BA),用(22)式所示的条件,从(29)立得ρ(PL,N(A)M-1N)=ρ(([Ir,A-111A12]E)-1(Ir-D11A11)[Ir,A-111A12]E)=ρ(Ir-D11A11)<1.实际上,由M-1N的半收敛性,用引理0.1之(5),直接可得ρ(PL,N(A)M-1N)=ρ(M-1NPL,N(I-M-1N))<1.(2)由(1)中的结论知,对任何b∈R(A),我们有y∞≡limj→∞yj=(Ι-ΡL,Ν(A)Μ-1Ν)-1ΡL,Ν(A)Μ-1b.(30)注意到b∈R(A)可写成b=A˜b,˜b任意,并注意到A(-1)(L)A=A(1‚2)L‚L⊥A=PL,N(A),(31)所以为证y∞=A(-1)(L)b,只需证明次之等式PL,N(A)M-1A=(I-PL,N(A)M-1N)A(-1)(L)A.(32)用(31)式及N(A)=N(I-M-1N),可得(32)式的右端=PL,N(A)(I-M-1N)PL,N(A)=PL,N(A)(I-M-1N)=PL,N(A)M-1A.另外,等式(32)等价于PL,N(A)M-1N=PL,N(A)M-1NPL,N(A),据此等式及迭代格式(2)与(5),用归纳法易证yj=PL,N(A)xj,j=0,1,2,…,2有m#n到b的迭代格式事实上,文的投影迭代法中要使用A的P-正则分裂与斜投影算子PL,N(A),而这两者的构造、计算均是不容易的.现在我们来提出两个简单的迭代格式,它们均不需要借助于P-正则分裂与Keller定理,也不需要PL,N(A).定理2.1设约束方程组(3)与条件(4)如上.设L=R(E),E列满秩.令0<α<λmin(EΤE),Μ=1αAEEΤ,Ν=Μ-A,(33)并建立迭代格式xj+1=M+Nxj+M+b.(34)则:(1)ρ(M+N)<1,(2)对任意初始向量x0与任何b∈R(A),迭代(34)均收敛到(3)的唯一解A(-1)(L)b.证明(1)因AE是列满秩阵,故M+=αET+(AE)+,从而有M+N=M+M-M+A=ET+ET-αET+(AE)+A(35)进而有ρ(M+N)=ρ((ET-α(AE)+A)ET+)=ρ(I-α(ETE)-1)(36)据α的取法,易证ρ(M+N)=ρ(I-α(ETE)-1)<1.(2)据(1)中结论知,迭代(34)对任意x0与任何b∈R(A)收敛到x∞≡limj→∞xj=(Ι-Μ+Ν)-1Μ+b.(37)为证对任何b∈R(A)有x∞=A(-1)(L)b,只需证明等式M+A=(I-M+N)A(-1)(L)A.(38)但这是容易的,因为用(35)式可得(38)式的右端=[I-EE++αET+(AE)+A]A(-1)(L)A=αET+(AE)+A=M+A.定理2.2设L=R(E),E列满秩.令0<α<2/λmax(EΤAE),Μ=1αE(EΤE)-2EΤ,Ν=Μ-A.(39)则:(1)M为对称半正定阵,M+=M#=αEET,ρ(M#N)<1,(40)(2)迭代xj+1=M#Nxj+M#b(41)对任何x0与任何b∈R(A)收敛到(3)的唯一解A(-1)(L)b.证明(1):只需证ρ(M#N)<1.首先易证ETAE为正定阵.其次,可算得M#N=MM#-M#A=E(ETE)-1ET-αEETA,(42)因此有ρ(M#N)=ρ((ETE)-1ETE-αETAE)=ρ(Ir-αETAE).据α的取法,易知ρ(Ir-αETAE)<1,此即ρ(M#N)<1.(2):据(1)中所证,可知迭代(41)对任何x0与任何b∈R(A)收敛到x∞≡limj→∞xj=(Ι-Μ#Ν)-1Μ#b.(43)为证x∞=A(-1)(L)b,只需证明M#A=(I-M#N)A(-1)(L)A.(44)注意到MM#=MM+=PR(E)=PL,(I-MM#)A(-1)(L)=0,可知(44)式的右端=(I-MM#+αEETA)A(-1)(L)A=αEETA=M#A.注因为(42)式中的MM#