APP下载

矩阵Schur补的非奇异H矩阵判定算法

2016-03-15马胜辉,段复建

桂林电子科技大学学报 2016年1期



矩阵Schur补的非奇异H矩阵判定算法

引文格式: 马胜辉,段复建.矩阵Schur补的非奇异H矩阵判定算法[J].桂林电子科技大学学报,2016,36(1):76-78.

马胜辉,段复建

(桂林电子科技大学 数学与计算科学学院,广西 桂林541004)

摘要:针对非奇异H矩阵的判定问题,提出了一种直接判定算法。该算法通过矩阵Schur补求逆,逐次降阶,判定低阶矩阵是否为非奇异H矩阵。数值算例表明,该算法是有效的。

关键词:非奇异H矩阵;Schur补;数值判定

非奇异H矩阵是一类重要的特殊矩阵,它在计算数学、数学物理和动力系统理论等方面有着重要应用。而许多实际问题的应用都归结到大型非奇异H矩阵的判定问题上,因此,国内外许多学者在研究大型非奇异H矩阵的判定算法,已有许多研究成果。其中有迭代判定算法[1-4],但这些算法有一个共同的缺点,就是不能确定迭代的步数,且当判别的矩阵不是非奇异H矩阵时,可能陷入无限循环。为了避免上述缺点,提出了直接判定算法[5-7],通过逐次降阶的方法,使得一个任意矩阵只需判定低阶矩阵是否为非奇异H矩阵即可。因此,本算法是一种区别于文献[5-7]的直接判定算法,算法在做降阶处理时,将矩阵Schur补求逆的方法应用到其中。

1预备知识

设Cn×n为所有n×n复数矩阵所构成的集合,α、β为N的非空子集,用A(α,β)表示行标集为α、列标集为β的A的子矩阵。A(α,α)缩写为A(α)。N={1,2,…,n},α′=N-α,β′=N-β。随着计算机技术的快速发展,大量工程问题可归结为大规模的矩阵计算问题,而矩阵Schur补是处理大规模矩阵计算的有利工具。

称为矩阵A关于子矩阵A(α)的Schur补。

在诸多领域中,许多问题可转化为具有特殊构造的矩阵问题。例如,偏微分方程中的有限元方法、运筹学中的线性互余问题等常用到M矩阵理论。Z矩阵、M矩阵以及H矩阵是3个特殊构造的矩阵,其定义如下。

定义2 设矩阵A=(aij)n×n∈Rn×n,且非主对角元素aij≤0,则称A是Z矩阵,Z矩阵集合记为Zn×n。

定义3 设A=(aij)n×n∈Rn×n,若A=sI-B,s∈R,s>0,B≥0,若ρ(B)≤s,则称A是M矩阵。若ρ(B)

显然,M矩阵是Z矩阵的特殊情形。

定义4设A=(aij)n×n∈Cn×n,定义μ(A)=(mij)n×n∈Rn×n,其中

则称μ(A)是A的比较矩阵。

定义5 设A=(aij)n×n∈Cn×n,若A的比较矩阵μ(A)是非奇异M矩阵,则称A是非奇异H矩阵。

从定义5可得,对于任意一个矩阵,通过判断其比较矩阵是否为非奇异M矩阵,可判别该矩阵是否为非奇异H矩阵。

2主要结果

引理1设A∈Zn×n,若满足下列条件,则A是非奇异M矩阵。

1)A可逆;

2)A-1≥0。

引理1给出了直接判定一个矩阵是否为非奇异M矩阵的方法。

将逆矩阵A-1的各个分块对应写成Schur补的形式,便得到Schur补求逆矩阵的方法。

由A-1(α′)=(A(α′)-A(α′,α)A(α)-1A(α,α′))-1,根据Schur补定义

A/A(α)=A(α′)-A(α′,α)A(α)-1A(α,α′),

有A-1(α′)=(A/A(α))-1,那么,相应地将α与α′互换,可得到A-1(α)=(A/A(α′))-1。

将A/A(α)=A(α′)-A(α′,α)A(α)-1A(α,α′)代入A-1(α,α′)和A-1(α′,α),可得到

证明 1)必要性。若A是M矩阵,则A(α)也是M矩阵,且有A(α)-1≥0,A-1≥0,从而A-1(α′)≥0。又由引理2中A-1(α′)=(A/A(α))-1,可知(A/A(α))-1≥0。

即A-1≥0,又已知A∈Zn×n,由引理1可得A是M矩阵。

3算法设计

由定理1可知,要判定一个n阶Z矩阵A是否为非奇异M矩阵,只需判定子块A(α)-1和(A/A(α))-1是否为非负矩阵。当n较大时,不失一般性,考虑取A(α)为4阶矩阵,并设

算法1给定矩阵B=(bij)∈Cn×n,令A=μ(B)=(aij)∈Zn×n,其中μ(B)是B的比较矩阵。

1)令A(m)=A,m=0;

3)计算A(m)的阶数n,若n≤4,则转步骤4),否则转步骤5);

并转步骤2);

5)计算(A(m))-1,若不是非负矩阵,则A不是非奇异H矩阵。否则,A是非奇异H矩阵。

4数值例子

例1考虑矩阵

根据算法1,只需运算2次,得到(A(2))-1=0.330 3>0,可知B为非奇异H矩阵。实际上,用计算机求得A-1=(μ(B))-1≥0,为非负矩阵,由定理1可知,B确为非奇异H矩阵。

例2 考虑矩阵

根据算法1,运算1次,得

不是非负矩阵,可知B不是非奇异H矩阵。实际上,用计算机求得A-1=(μ(B))-1不是非负矩阵,可知B的确不是非奇异H矩阵。

5结束语

对于非奇异H矩阵的数值判定算法,将矩阵的Schur补求逆应用到其中,即通过用矩阵的Schur补求逆,并判断该逆矩阵是否为非负矩阵,再作降阶运算,逐次判断,由此判定原矩阵是否为非奇异H矩阵。该算法扩展了非奇异H矩阵在数值判定算法中降阶处理时的方法。

参考文献:

[1]LI B,LI L,HARADA M,et al.An Iterative Criterion for H-matrices[J].Linear Algebra and its Applications,1998,271(1/2/3):179-190.

[2]OJIRO K,NIKI H,USUI M.A new criterion for the H-matrices property[J].Journal of Computational and Applied Mathematics,2003,150:293-302.

[3]HADJIDIMOS A.An extended compact profile iterative method criterion for sparse H-Matrices[J].Liner Algebra and its Applications,2004,389:329-345.

[4]ALANELLI M,HADJIDIMOS A.On iterative for H-and non-H-Matrices[J].Applied Mathematics and Computation,2007,188:19-30.

[5]刘建洲,徐映红.非奇异M矩阵的判定及并行算法的注记[J].高等学校计算数学学报,2003,25(2):317-320.

[6]LI Yaotang,ZHU Yan.A direct algorithm for distinguishing nonsingular M-matrix and H-matrix[J].Numerical Mathematics,2005,14(1):79-86.

[7]郭希娟,纪乃华,姚慧萍.逆M矩阵的判定及并行算法[J].北华大学学报,2004,5(2):97-103.

编辑:梁王欢

An algorithm for distinguishing non-singular H-matrix with Schur complement

MA Shenghui, DUAN Fujian

(School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract:A direct algorithm is presented for distinguishing non-singular H-matrix. In this algorithm, the low order matrix can be determined non-singular H-matrix by successive order reduction based on Schur complement. The numerical examples show that the algorithm is effective.

Key words:non-singular H-matrix; Schur complement; numerical determination

中图分类号:O151.21

文献标志码:A

文章编号:1673-808X(2016)01-0076-03

通信作者:段复建(1965-),女,黑龙江黑河人,教授,博士,研究方向为最优化理论与方法、数值代数。E-mail:duanfj@guet.edu.cn

基金项目:国家自然科学基金(11461015)

收稿日期:2015-09-12