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



矩阵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