第22卷 第1期2006年1月福建师范大学学报(自然科学版)
JournalofFujianNormalUniversity(NaturalScienceEdition)Vol.22 No.1Jan.2006
文章编号:1000-5277(2006)01-0012-04
非奇异M-矩阵的降阶判定
韩凤萍,严宣辉
1
2
(1.福建信息职业技术学院,福建福州 350019;2.福建师范大学数学与计算机科学学院,福建福州 350007) 摘要:给出对任意阶非奇异M-矩阵进行简便判定定理,设计了一种降阶判定算法以实现对任意阶矩阵是否为非奇异M-矩阵的快速判定,每次只要进行数的加、减、乘、除简单运算及对其结果判定符号,并对一个已有的逆M-矩阵的性质定理的结论进行修正.
关键词:M-矩阵;逆M-矩阵;Schur补中图分类号:O241.6 文献标识码:A
DecisionofReducingOrderofNonsingularM-matrix
HANFeng-ping,YANXuan-hui
1
2
(1.FujianVocationalCollegeofInformationandTechnology,Fuzhou350019,China;
2.SchoolofMathematicsandComputerScience,FujianNormalUniversity,Fuzhou350007,China)
Abstract:GiveaconvenienttheoremofjudginganarbitraryordernonsingularM-matrix,designanalgorithmofreducingordertojudgewhetheranarbitraryorderM-matrixisanonsingularM-matrix.Everytimeitisonlyrequiredtooperateonaddition,subtract,multiply,divisiontojudgesymbolofitsresult.Itiseasyandsimple.Meanwhile,reviseaprevioustheoremofinverseM-matrix
property.
Keywords:M-matrix;inverseM-matrix,;Schurcomplement
物理学、数学和社会科学中的许多理论问题息息相关,是M-矩阵有广泛的应用背景,它与生物学、
计算数学中使用广泛的一个矩阵类,因此,研究非奇异M-矩阵的判定方法成为矩阵理论研究中极为活跃的一个领域.对M-矩阵的判定方法的研究已有许多成果,但大都是对非奇异M-矩阵的整体进行判定,这对高阶矩阵来说难度较大,因而判定方法难以实现,具有局限性.本文给出对任意阶非奇异M-矩阵进行简便判定的定理,并利用该定理解决了两个问题:1.用算法实现对高阶非奇异M-矩阵的简便判定,每次只要进行数的加、减、乘、除简单运算并对其结果判定符号即可;2.对一个已有的逆M-矩阵的性质定理的结论进行修正.与现在常用的非奇异M-矩阵判定方法相比,本文提供的算法高效且易于实现.
1 M-矩阵的判定方法
定义1 设A=(aij)n×n为实矩阵,其中aij≤0(i≠j),若A
-1
存在且A
-1
≥0,则称A为非奇异
M-矩阵.
定义2 设A=(aij)n×n为非奇异实矩阵,若A-1为M-矩阵,则A为逆M-矩阵.
定义3 设A=(aij)n×n,若存在正对角阵Q,使得QA为正定矩阵,则称A为广义正定矩阵.
收稿日期:2005-03-09
基金项目:福建省教育厅基金资助项目(JB05209)
(),,,,:
第1期 韩凤萍等:非奇异M-矩阵的降阶判定
[1]
13
引理1 设A=(aij)n×n,其中aij≤0(i≠j),则A为非奇异M-矩阵的充要条件是存在正对角阵D,使得DA为正定.
引理2[2] 设An=-BD
-1
AB
CD
C都是广义正定矩阵.
,其中D∈Rm×m,1≤m≤n,则An为广义正定的充要条件是D和A
引理3[3] M-矩阵的主对角元必为正值.
定理1 设An=(aij)n×n,其中aij≤0(i≠j),则An为非奇异M-矩阵的充要条件是An为广义正定矩阵.
证明 An为非奇异M-矩阵阵.
定理2 设An=(aij)n×n,其中aij≤0(i≠j),则An为非奇异M-矩阵的充要条件是D和A-BD-1C都是非奇异M-矩阵.其中An=
证明 An为非奇异M-矩阵
1
-1
1
存在正对角阵Q,使得QAn为正定
3
An为广义正定矩
AC
BD
.
2
1
An为广义正定矩阵D和A-BD
-1
C为广义正定矩阵
D和A-BDC为非奇异M-矩阵.
2 M-矩阵的判定算法分析与实现
记A[nn]=异M-矩阵.
¹A[nn]的对角元有一不大于0,若Dnn≤0,根据引理3得A[nn]不是非奇异M-矩阵,结束判断.否则
1
对n-1阶块A[nn-1]=An-1-Bn-1D-nnCn-1,判断其是否非奇异M-矩阵.
An-1Cn-1
Bn-1Dnn
n×n
>(aij)n×n,设A[nn]=(aij)n×n,其中aij≤0(i≠j),判断A[nn]是否为非奇
对An
[n-1]
=
aij-
ain×anjDnn
(n-1)×(n-1)
>(bij)(n-1)×(n-1)进行分块:
An-2Cn-2
Bn-2Dn-1,n-1
,其中
Dn-1,n-1仍为一阶.
º判断A[nn-1]所有对角元的符号.若有一不大于0,则A[nn-1]不是非奇异M-矩阵,根据定理2知A[nn]
不是非奇异M-矩阵,结束判断.否则对n-2阶块An奇异M-矩阵.
对A
[n-2]n
[n-2]
=An-2-Bn-2Dn-1,n-1Cn-2,判断其是否为非
An-3Cn-3
Bn-3Dn-2,n-2
-1
=
bij-
Dn-1,n-1
bi,n-1×bn-1,j
(n-2)×(n-2)
>(c)
ij
(n-2)×(n-2)
进行分块:,
其中Dn-2,n-2仍为一阶.
»以此进行下去直到判断D11的符号为止.
据以上分析可知,每次只要对
ann, i=n,
Dii=xii-×(xi,i+1×xi+1,i), i=n-1,n-2,…,1
Di+1,i+1
(Dii为一阶的块,xij为每次降价后矩阵An的第i行第j元素)进行简单的数的运算,对其判断符号.这过程可简单描述为:若每一个Dii>0(i=n,n-1,n-2,…,1),则A[nn]是非奇异M-矩阵,若存在一个j∈[1,n]使得Dij≤0,则A[nn]不是非奇异M-矩阵.
通过以上所述知,计算机所处理的只是很简单的数的加、减、乘、除运算,因此对任意阶的An=(aij)n×n(其中aij≤0(i≠j)),判断其是否为非奇异M-矩阵就很容易实现,特别是对高阶矩阵的判断更[i]
14
福建师范大学学报(自然科学版) 2006年
3 程序代码描述
对于本文的算法,利用MatLab6.5科学计算软件编写程序进行实验,程序代码如下: functionm=m—matrix(A,n) m=1;
fori=n:-1:1
if(A(i,i)
breakend
forj=1:i-1 fork=1:i-1
A(j,k)=A(j,k)-A(j,i)*A(i,k)/A(i,i) endend end
if(m==1)
disp(’ItisanonsingularM-matrix’) else
)disp(’ItisnotanonsingularM-matrix’ end
4 数值例子
例1
1.0000
A[44]=
-0.2500-0.2500
-0.2500-0.25001.00000
01.0000
-0.2500
,D44=a44=1.0000>0.
-0.2500-0.2500-0.25001.0000-0.2500-0.2500
-0.25000.9375-0.0625
用本文算法第一次降阶后的3阶矩阵为
A[43]=
-0.2500
-0.0625, D33=0.9375>0,第二次降阶后的2阶矩阵为
A[42]=
第三次降阶后的1阶矩阵为
A4=(, D11=0.8571>0.
每次降阶后的矩阵的Dii>0,根据定理2可知A[44]为非奇异的M-矩阵.
事实上,由于A[44]的逆矩阵为非负矩阵:
[1]
0.9333-0.2667
-0.2667, D22=0.9333>0,
第1期 韩凤萍等:非奇异M-矩阵的降阶判定
15
根据定义1可知A4亦为为非奇异的M-矩阵,算法的结果与其是一致的.
例2 不是M-矩阵的例子:
1.0000
A4=
[4]
[4]
-0.33331.00000-1.0000
-0.2000
01.0000-0.2500
0-1.0000-0.25001.0000
, D44=a44=1.0000>0.
-0.2500-0.2500
用本文算法第一次降阶后的3阶矩阵为
1.0000
A[43]=
-0.2500-0.2500
-0.3333-0.20000-0.2500,-0.2500由于A[43]有一对角元为0,可知A[44]不是非奇异的M-矩阵.
事实上,由于A4的逆矩阵为
1.0000
-0.2500
[4]
-0.2500-0.25001.0000
,
-0.0000-0.2500
-0.2500-0.00001.0000-0.2500-0.0000-0.2500-0.25001.0000
通过大量的例子实验,结果都验证了算法的正确性,在此不一一列举.
此时已不是非负矩阵.根据定义1可知A[44]不是M-矩阵,算法的结果与其是一致的.
5 修正一个定理的结论
引理4 设M是非负奇异的n×n矩阵,其分块M=补为(M/A)=D-CA-1B.
-1
A
CB
,A为非奇异的,A在M中的SchurD
A-1(M/A)-,
(M/A)-1
B
,A为非奇异的,若M是为逆M-矩D
A0C0
B0
,根据定理2可知,D0
A-1(A+B(M/A)-1C)A-1-M=
-(M/A)-1CA-1
由文献[4]知,若M是为逆M-矩阵,则(M/A)是逆M-.
A
定理3 设M是非负奇异的n×n矩阵,其分块M=
C
阵,则A和(M/A)均是逆M-矩阵.
证明 因为M是为逆M-矩阵,即M-1为非奇异M-矩阵.设M-1=
1-1
两个块D0和A0-B0D-0C0都是非奇异M-矩阵,而D0=(M/A)且
-1
A0-B0D0C0=
(A+B(M/A)C)A]-[-AB(M/A)][(M/A)][-(M/A)
-1-1-1-1-1-1-1-1-1A+AB(M/A)CACA-AB(M/A)CA=A.
故A和(M/A)都是逆M-矩阵,这比引理4的结论更加完善.
[A
-1-1-1-1-1-1-1-1
CA]=
参考文献:
[1]张谋成,黎稳.非负矩阵[M].广州:广东教育出版社,1995.
[2]AlbertA.ConditionsforpositiveandnonnegativedefinitenssintennsofpseudvinversesSZAMJ[J].Appl.Math.,
1969,17:430-440.
[3]程云鹏.矩阵论[M].西安:西北工业大学出版社,1989.
[4]ImanLN.TheSchurcomplementandtheinverseM-matrixproblem[J].Lin.Alg.Appl.,1984,62:235-240.
(
第22卷 第1期2006年1月福建师范大学学报(自然科学版)
JournalofFujianNormalUniversity(NaturalScienceEdition)Vol.22 No.1Jan.2006
文章编号:1000-5277(2006)01-0012-04
非奇异M-矩阵的降阶判定
韩凤萍,严宣辉
1
2
(1.福建信息职业技术学院,福建福州 350019;2.福建师范大学数学与计算机科学学院,福建福州 350007) 摘要:给出对任意阶非奇异M-矩阵进行简便判定定理,设计了一种降阶判定算法以实现对任意阶矩阵是否为非奇异M-矩阵的快速判定,每次只要进行数的加、减、乘、除简单运算及对其结果判定符号,并对一个已有的逆M-矩阵的性质定理的结论进行修正.
关键词:M-矩阵;逆M-矩阵;Schur补中图分类号:O241.6 文献标识码:A
DecisionofReducingOrderofNonsingularM-matrix
HANFeng-ping,YANXuan-hui
1
2
(1.FujianVocationalCollegeofInformationandTechnology,Fuzhou350019,China;
2.SchoolofMathematicsandComputerScience,FujianNormalUniversity,Fuzhou350007,China)
Abstract:GiveaconvenienttheoremofjudginganarbitraryordernonsingularM-matrix,designanalgorithmofreducingordertojudgewhetheranarbitraryorderM-matrixisanonsingularM-matrix.Everytimeitisonlyrequiredtooperateonaddition,subtract,multiply,divisiontojudgesymbolofitsresult.Itiseasyandsimple.Meanwhile,reviseaprevioustheoremofinverseM-matrix
property.
Keywords:M-matrix;inverseM-matrix,;Schurcomplement
物理学、数学和社会科学中的许多理论问题息息相关,是M-矩阵有广泛的应用背景,它与生物学、
计算数学中使用广泛的一个矩阵类,因此,研究非奇异M-矩阵的判定方法成为矩阵理论研究中极为活跃的一个领域.对M-矩阵的判定方法的研究已有许多成果,但大都是对非奇异M-矩阵的整体进行判定,这对高阶矩阵来说难度较大,因而判定方法难以实现,具有局限性.本文给出对任意阶非奇异M-矩阵进行简便判定的定理,并利用该定理解决了两个问题:1.用算法实现对高阶非奇异M-矩阵的简便判定,每次只要进行数的加、减、乘、除简单运算并对其结果判定符号即可;2.对一个已有的逆M-矩阵的性质定理的结论进行修正.与现在常用的非奇异M-矩阵判定方法相比,本文提供的算法高效且易于实现.
1 M-矩阵的判定方法
定义1 设A=(aij)n×n为实矩阵,其中aij≤0(i≠j),若A
-1
存在且A
-1
≥0,则称A为非奇异
M-矩阵.
定义2 设A=(aij)n×n为非奇异实矩阵,若A-1为M-矩阵,则A为逆M-矩阵.
定义3 设A=(aij)n×n,若存在正对角阵Q,使得QA为正定矩阵,则称A为广义正定矩阵.
收稿日期:2005-03-09
基金项目:福建省教育厅基金资助项目(JB05209)
(),,,,:
第1期 韩凤萍等:非奇异M-矩阵的降阶判定
[1]
13
引理1 设A=(aij)n×n,其中aij≤0(i≠j),则A为非奇异M-矩阵的充要条件是存在正对角阵D,使得DA为正定.
引理2[2] 设An=-BD
-1
AB
CD
C都是广义正定矩阵.
,其中D∈Rm×m,1≤m≤n,则An为广义正定的充要条件是D和A
引理3[3] M-矩阵的主对角元必为正值.
定理1 设An=(aij)n×n,其中aij≤0(i≠j),则An为非奇异M-矩阵的充要条件是An为广义正定矩阵.
证明 An为非奇异M-矩阵阵.
定理2 设An=(aij)n×n,其中aij≤0(i≠j),则An为非奇异M-矩阵的充要条件是D和A-BD-1C都是非奇异M-矩阵.其中An=
证明 An为非奇异M-矩阵
1
-1
1
存在正对角阵Q,使得QAn为正定
3
An为广义正定矩
AC
BD
.
2
1
An为广义正定矩阵D和A-BD
-1
C为广义正定矩阵
D和A-BDC为非奇异M-矩阵.
2 M-矩阵的判定算法分析与实现
记A[nn]=异M-矩阵.
¹A[nn]的对角元有一不大于0,若Dnn≤0,根据引理3得A[nn]不是非奇异M-矩阵,结束判断.否则
1
对n-1阶块A[nn-1]=An-1-Bn-1D-nnCn-1,判断其是否非奇异M-矩阵.
An-1Cn-1
Bn-1Dnn
n×n
>(aij)n×n,设A[nn]=(aij)n×n,其中aij≤0(i≠j),判断A[nn]是否为非奇
对An
[n-1]
=
aij-
ain×anjDnn
(n-1)×(n-1)
>(bij)(n-1)×(n-1)进行分块:
An-2Cn-2
Bn-2Dn-1,n-1
,其中
Dn-1,n-1仍为一阶.
º判断A[nn-1]所有对角元的符号.若有一不大于0,则A[nn-1]不是非奇异M-矩阵,根据定理2知A[nn]
不是非奇异M-矩阵,结束判断.否则对n-2阶块An奇异M-矩阵.
对A
[n-2]n
[n-2]
=An-2-Bn-2Dn-1,n-1Cn-2,判断其是否为非
An-3Cn-3
Bn-3Dn-2,n-2
-1
=
bij-
Dn-1,n-1
bi,n-1×bn-1,j
(n-2)×(n-2)
>(c)
ij
(n-2)×(n-2)
进行分块:,
其中Dn-2,n-2仍为一阶.
»以此进行下去直到判断D11的符号为止.
据以上分析可知,每次只要对
ann, i=n,
Dii=xii-×(xi,i+1×xi+1,i), i=n-1,n-2,…,1
Di+1,i+1
(Dii为一阶的块,xij为每次降价后矩阵An的第i行第j元素)进行简单的数的运算,对其判断符号.这过程可简单描述为:若每一个Dii>0(i=n,n-1,n-2,…,1),则A[nn]是非奇异M-矩阵,若存在一个j∈[1,n]使得Dij≤0,则A[nn]不是非奇异M-矩阵.
通过以上所述知,计算机所处理的只是很简单的数的加、减、乘、除运算,因此对任意阶的An=(aij)n×n(其中aij≤0(i≠j)),判断其是否为非奇异M-矩阵就很容易实现,特别是对高阶矩阵的判断更[i]
14
福建师范大学学报(自然科学版) 2006年
3 程序代码描述
对于本文的算法,利用MatLab6.5科学计算软件编写程序进行实验,程序代码如下: functionm=m—matrix(A,n) m=1;
fori=n:-1:1
if(A(i,i)
breakend
forj=1:i-1 fork=1:i-1
A(j,k)=A(j,k)-A(j,i)*A(i,k)/A(i,i) endend end
if(m==1)
disp(’ItisanonsingularM-matrix’) else
)disp(’ItisnotanonsingularM-matrix’ end
4 数值例子
例1
1.0000
A[44]=
-0.2500-0.2500
-0.2500-0.25001.00000
01.0000
-0.2500
,D44=a44=1.0000>0.
-0.2500-0.2500-0.25001.0000-0.2500-0.2500
-0.25000.9375-0.0625
用本文算法第一次降阶后的3阶矩阵为
A[43]=
-0.2500
-0.0625, D33=0.9375>0,第二次降阶后的2阶矩阵为
A[42]=
第三次降阶后的1阶矩阵为
A4=(, D11=0.8571>0.
每次降阶后的矩阵的Dii>0,根据定理2可知A[44]为非奇异的M-矩阵.
事实上,由于A[44]的逆矩阵为非负矩阵:
[1]
0.9333-0.2667
-0.2667, D22=0.9333>0,
第1期 韩凤萍等:非奇异M-矩阵的降阶判定
15
根据定义1可知A4亦为为非奇异的M-矩阵,算法的结果与其是一致的.
例2 不是M-矩阵的例子:
1.0000
A4=
[4]
[4]
-0.33331.00000-1.0000
-0.2000
01.0000-0.2500
0-1.0000-0.25001.0000
, D44=a44=1.0000>0.
-0.2500-0.2500
用本文算法第一次降阶后的3阶矩阵为
1.0000
A[43]=
-0.2500-0.2500
-0.3333-0.20000-0.2500,-0.2500由于A[43]有一对角元为0,可知A[44]不是非奇异的M-矩阵.
事实上,由于A4的逆矩阵为
1.0000
-0.2500
[4]
-0.2500-0.25001.0000
,
-0.0000-0.2500
-0.2500-0.00001.0000-0.2500-0.0000-0.2500-0.25001.0000
通过大量的例子实验,结果都验证了算法的正确性,在此不一一列举.
此时已不是非负矩阵.根据定义1可知A[44]不是M-矩阵,算法的结果与其是一致的.
5 修正一个定理的结论
引理4 设M是非负奇异的n×n矩阵,其分块M=补为(M/A)=D-CA-1B.
-1
A
CB
,A为非奇异的,A在M中的SchurD
A-1(M/A)-,
(M/A)-1
B
,A为非奇异的,若M是为逆M-矩D
A0C0
B0
,根据定理2可知,D0
A-1(A+B(M/A)-1C)A-1-M=
-(M/A)-1CA-1
由文献[4]知,若M是为逆M-矩阵,则(M/A)是逆M-.
A
定理3 设M是非负奇异的n×n矩阵,其分块M=
C
阵,则A和(M/A)均是逆M-矩阵.
证明 因为M是为逆M-矩阵,即M-1为非奇异M-矩阵.设M-1=
1-1
两个块D0和A0-B0D-0C0都是非奇异M-矩阵,而D0=(M/A)且
-1
A0-B0D0C0=
(A+B(M/A)C)A]-[-AB(M/A)][(M/A)][-(M/A)
-1-1-1-1-1-1-1-1-1A+AB(M/A)CACA-AB(M/A)CA=A.
故A和(M/A)都是逆M-矩阵,这比引理4的结论更加完善.
[A
-1-1-1-1-1-1-1-1
CA]=
参考文献:
[1]张谋成,黎稳.非负矩阵[M].广州:广东教育出版社,1995.
[2]AlbertA.ConditionsforpositiveandnonnegativedefinitenssintennsofpseudvinversesSZAMJ[J].Appl.Math.,
1969,17:430-440.
[3]程云鹏.矩阵论[M].西安:西北工业大学出版社,1989.
[4]ImanLN.TheSchurcomplementandtheinverseM-matrixproblem[J].Lin.Alg.Appl.,1984,62:235-240.
(