n阶复方的谱半径和最优松弛因子的确定

n阶复方的谱半径和最优松弛因子的确定

1rakena算法使用cnn表示所有nn复合矩阵组成的集合。如果A∈Cn×n,则ReA=12(A+A*),ΙmA=12i(A-A*)分别表示A的实部与虚部,其中i=√-1,同时trA,rankA,|A|F分别为A的迹,秩和Frobinious范数。如果AA*=A*A,则称其为正规矩阵。Gerschgorin圆盘定理给出了矩阵特征值偏离其对角元素的一个良好而又实用的估计。文献给出任意方阵的任一特征值相对于其所有特征值的算术平均或相对于它的所有对角元素的算术平均的偏离估计,即对任一n阶方阵A的任一特征值都位于如下的单一圆盘中:D:{z:|z-trAn|≤r1=√n-1n(|A|2F-|trA|2n)}.(1)但是,文献的结论没有体现矩阵的非正规性对上述偏离估计的影响。式(1)的估计区域主要依赖于下面的不等式:∑nj=1|λj|2≤|A|2F,其中,λ1,λ2,…,λn是A的所有的特征值。∑nj=1|λj|2的上界估计越小,则圆盘的半径也越小。引理1如果A∈Cn×n,λ1,…,λn是A的所有特征值,则n∑j=1|λj|2≤√|A|4F-12|AA*-A*A|2F.(2)引理2如果A∈Cn×n,则有如下的不等式成立:|trA|2≤rankA√|A|4F-ΔA,(3)|trReA|2≤rankA|ReA|2F,(4)|trΙmA|2≤rankA|ΙmA|2F.(5)其中,ΔA=12|AA*-A*A|2F.证明设λ1(A),…,λn(A)为A的特征值,由矩阵的酉相似性可知,存在酉矩阵U使得UAU*=R=[λ1(A)*λ2(A)⋱0λn(A)].(6)再设A有s个非零特征值,则s≤rankA。不失一般性,令λ1(A),…,λs(A)为非零特征值,于是由引理1和舒尔定理可知s∑j=1|λj|2≤√|A|4F-12|AA*-A*A|2F,(7)s∑i=1|Reλi(A)|2≤|ReA|2F,(8)s∑i=1|Ιmλi(A)|2≤|ΙmA|2F.(9)因而有|trA|2=|s∑j=1λj|2≤ss∑j=1|λj|2≤rankAs∑j=1|λj|2≤rankA√|A|4F-ΔA,|trReA|2=|s∑i=1Reλi(A)|2≤ss∑i=1|Reλi(A)|2≤s|ReA|2F≤rankA|ReA|2F.于是式(3)和式(4)得证。类似可证明式(5)。推论1对任一n阶复方阵A,当下列三个不等式有一个成立|trA|2|A|F4-ΔA>n-1,(10)|trReA|2|ReA|F2>n-1,(11)|trΙmA|2|ΙmA|F2>n-1.(12)则detA≠0。定理1对任一n阶复方阵A,则A的所有特征值都位于如下的圆盘中D:{z:|z-trAn|≤R1=n-12n-1×n-1nq+q2-2n-1n2ΔA}‚(13)并有R1≤r1且等号成立的充分必要条件为A是正规矩阵。其中q=|A|F2-1n|trA|2,ΔA=12|AA*-A*A|F2.证明设A∈Cn×n,并令M=λI-A,其中λ是A的任一特征值,由detM=0,则有rankM=rank(λI-A)≤n-1,由引理2可得|trΜ|2≤rankΜ|Μ|F4-ΔΜ≤(n-1)|Μ|F4-ΔΜ.再由ΔM=ΔA,可知|tr(λΙ-A)|2≤(n-1)|λΙ-A|F4-ΔA,(14)分别计算|tr(λΙ-A)|2和|λΙ-A|F4,则有|tr(λΙ-A)|2=tr(λI-A)tr(λΙ-A¯)=n2|λ|2-nλtrA*-nλ¯trA+|trA|2=nδ+|trA|2,|λΙ-A|F4=(tr(λΙ-A)(λ¯Ι-A*))2=(n|λ|2-λtrA*-λ¯trA+|A|F2)2=(δ+|A|F2)2.其中,δ=n|λ|2-λtrA*-λ¯trA。从上两式消去δ得到|λΙ-A|F4=(1n(|tr(λΙ-A)|2-|trA|2+|A|F2)2.令t=|λ-trAn|2,q=|A|F2-1n|trA|2,则|tr(λΙ-A)|2=n2t‚|λΙ-A|F4=(nt+q)2.于是有n2t≤(n-1)(nt+q)2-ΔA.整理后可得t=|λ-trAn|2≤n-12n-1(n-1nq+q2-2n-1n2ΔA).两边开平方后上述定理得证。由于ΔA≥0,所以R1≤r1=n-1nq且等号成立的充分必要条件为ΔA=0,即A是正规矩阵,从而可知此定理的估计圆盘半径R1比文献的估计圆盘半径在A是非正规矩阵情况下小,而且矩阵的非正规性越大,即ΔA越大,则圆盘半径就越小。而当A是正规矩阵的情况下,即ΔA=0,则估计圆盘半径与式(1)相同。推论2对任一n阶复方阵A,其所有特征值都位于如下的圆盘中:D:{z:|z-trAn|≤r1=n-1nq},(15)其中,q=|A|F2-1n|trA|2。定理2对任一n阶复方阵A=(aij),令|A|=(|aij|),B=(bij)≥(|aij|2),即bij≥|aij|2,i,j=1,⋯,n,则A所有的特征值位于如下的圆盘中:D:{z:|z-trAn|≤n-1n(nρ(B)-1n|trA|2)}.(16)特别地,令B=(|aij|2),由于ρ(B)≤ρ2(|A|),上述结论隐含下面的结果:D:{z:|z-trAn|≤n-1n(nρ2(|A|)-1n|trA|2)},(17)其中,ρ(B)是B的谱半径。证明首先,假设B是正矩阵,即其所有元素都是正的。由Perron-Frobenius定理,可令v=(v1,v2,…,vn)T>0是对应于ρ(B)的特征向量,即ρ(B)v=Bv。令W=diag(v1,v2,⋯,vn),并构造C=W-1AW,则C与A有相同的特征值。同时|C|F2∑i,j=1nvi-1|aij|2vj≤∑i,j=1nvi-1bijvj=∑i=1nvi-1∑j=1nbijvj=∑i=1nvi-1ρ(B)vi=nρ(B).由推论2,C的所有特征值位于如下的圆盘中:D:{z:|z-trCn|≤n-1nq≤n-1n(nρ(B)-1n|trA|2)},由于trA=trC,所以可证明定理的第一部分。当B≥0即它是一个非负矩阵时,可构造B′=(|bij|2+ε),其中ε>0。对B′作上述证明并令ε→0即可证明定理的后一部分。定理3对任一n阶复方阵A,A的所有特征值的实部与虚部分别位于如下的两个区间:[trReAn-n-1nqRe,trReAn+n-1nqRe],(18)[trΙmAn-n-1nqΙm,trΙmAn+n-1nqΙm].(19)其中qRe=|ReA|F2-1n(trReA)2,qΙm=|ΙmA|F2-1n(trΙmA)2.证明对任一n阶方阵A,令M=λI-A,λ是A的特征值,则ReM=ReλI-ReA,ImM=ImλI-ImA,且有rankM≤n-1.由引理2可得|trReΜ|2≤rankΜ|ReΜ|F2≤(n-1)|ReΜ|F2,|trΙmΜ|2≤rankΜ|ΙmΜ|F2≤(n-1)|ΙmΜ|F2.类似定理1可证明此定理。推论3对任一n阶复方阵A,如果-trReA>n-1|ReA|F,则A是稳定矩阵,即A的所有特征值的实部都小于零。证明由定理3,A的所有特征值的实部都位于如下的区间:[trReAn-n-1nqRe,trReAn+n-1nqRe],所以,如果trReAn+n-1nqRe<0,即-trReA>n-1|ReA|F,则A是稳定矩阵。2超松弛因子的确定在求解大型稀疏线性方程组Ax=b,A=(aij)∈Rn×n时常用迭代法。其主要方法是对系数矩阵A做如下的分解:令A=D-L-U,D=diag(a11,a22,…,ann),L,U分别是由A的下三角与上三角元素的取向号所得到的严格下三角与上三角矩阵,则BJ=I-D-1A,BG=(D-L)-1U,Bω=(D-ωL)-1(ωU+(1-ω)D)分别称为Jacobi,Gauss-Seidel,SOR迭代矩阵。判断这三种迭代是否收敛完全取决于它们的谱半径,由于谱半径很难计算,因此在实际应用上常需要给以估计。定理4n阶实方阵A的Jacobi迭代矩阵的谱半径ρ(BJ)满足如下的不等式ρ(BJ)≤R=n-12n-1×(n-1n(|D-1A|F2-n)+(|D-1A|F2-n)2-2n-1n2ΔD-1A)1/2,(20)同时也隐含着较粗的估计ρ(BJ)≤r=n-1n(|D-1A|F2-n).(21)证明Jacobi迭代矩阵BJ的迹trBJ=0,由q=|BJ|F2-1n|trBJ|2=|Ι-D-1A|F2=|D-1A|F2-n,ΔBJ=ΔD-1A,利用定理4可得证。很显然,当R<1时,Jacobi迭代法收敛。而R<1等价于|D-1A|F4-ΔD-1A<n4(n-1)2,所以有如下的推论。推论4当|D-1A|F4-ΔD-1A<n4(n-1)2时,线性方程组Ax=b,A=(aij)∈Rn×n求解的Jacobi迭代法必收敛。证明令q=|A|F2-n,则R<1⇔n-1nq+q2-2n-1n2ΔD-1A<2n-1n-1⇔q2+2nq-ΔD-1A-n2(2n-1)(n-1)2<0⇔(q+n)2<ΔD-1A+n4(n-1)2,由q+n=|A|F2即可得证。在解线性方程组的超松弛(SOR)迭代法中,最佳松弛因子ωopt的选取是很困难的,而当A是具有性质A的矩阵时,即存在置换矩阵P使得ΡAΡ-1=[D1ΗΤD2],其中,D1和D2为两个对角矩阵,或者当A是对称正定矩阵时,有ωopt=21+1-ρ2(BJ),于是,相应地,当|D-1A|F4-ΔD-1A<n4(n-1)2,或者|D-1A|F2<n2n-1,即R<1,可借助式(15)给出ωopt的上界,即ωopt≤21+1-R2,其中R是式(15)的右端项,于是可得如下