矩陣Schur補(bǔ)的非奇異H矩陣判定算法

?

矩陣Schur補(bǔ)的非奇異H矩陣判定算法

引文格式： 馬勝輝，段復(fù)建.矩陣Schur補(bǔ)的非奇異H矩陣判定算法[J].桂林電子科技大學(xué)學(xué)報，2016,36(1)：76-78.

馬勝輝，段復(fù)建

(桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林541004)

摘要：針對非奇異H矩陣的判定問題，提出了一種直接判定算法。該算法通過矩陣Schur補(bǔ)求逆，逐次降階，判定低階矩陣是否為非奇異H矩陣。數(shù)值算例表明，該算法是有效的。

關(guān)鍵詞：非奇異H矩陣；Schur補(bǔ)；數(shù)值判定

非奇異H矩陣是一類重要的特殊矩陣，它在計算數(shù)學(xué)、數(shù)學(xué)物理和動力系統(tǒng)理論等方面有著重要應(yīng)用。而許多實(shí)際問題的應(yīng)用都?xì)w結(jié)到大型非奇異H矩陣的判定問題上，因此，國內(nèi)外許多學(xué)者在研究大型非奇異H矩陣的判定算法,已有許多研究成果。其中有迭代判定算法[1-4]，但這些算法有一個共同的缺點(diǎn)，就是不能確定迭代的步數(shù)，且當(dāng)判別的矩陣不是非奇異H矩陣時，可能陷入無限循環(huán)。為了避免上述缺點(diǎn)，提出了直接判定算法[5-7]，通過逐次降階的方法，使得一個任意矩陣只需判定低階矩陣是否為非奇異H矩陣即可。因此，本算法是一種區(qū)別于文獻(xiàn)[5-7]的直接判定算法，算法在做降階處理時，將矩陣Schur補(bǔ)求逆的方法應(yīng)用到其中。

1預(yù)備知識

設(shè)Cn×n為所有n×n復(fù)數(shù)矩陣所構(gòu)成的集合，α、β為N的非空子集，用A(α,β)表示行標(biāo)集為α、列標(biāo)集為β的A的子矩陣。A(α,α)縮寫為A(α)。N={1,2,…,n},α′=N-α,β′=N-β。隨著計算機(jī)技術(shù)的快速發(fā)展，大量工程問題可歸結(jié)為大規(guī)模的矩陣計算問題，而矩陣Schur補(bǔ)是處理大規(guī)模矩陣計算的有利工具。

稱為矩陣A關(guān)于子矩陣A(α)的Schur補(bǔ)。

在諸多領(lǐng)域中，許多問題可轉(zhuǎn)化為具有特殊構(gòu)造的矩陣問題。例如，偏微分方程中的有限元方法、運(yùn)籌學(xué)中的線性互余問題等常用到M矩陣?yán)碚摗矩陣、M矩陣以及H矩陣是3個特殊構(gòu)造的矩陣，其定義如下。

定義2 設(shè)矩陣A=(aij)n×n∈Rn×n，且非主對角元素aij≤0，則稱A是Z矩陣，Z矩陣集合記為Zn×n。

定義3 設(shè)A=(aij)n×n∈Rn×n，若A=sI-B,s∈R,s>0,B≥0,若ρ(B)≤s，則稱A是M矩陣。若ρ(B)

顯然，M矩陣是Z矩陣的特殊情形。

定義4設(shè)A=(aij)n×n∈Cn×n，定義μ(A)=(mij)n×n∈Rn×n，其中

則稱μ(A)是A的比較矩陣。

定義5 設(shè)A=(aij)n×n∈Cn×n，若A的比較矩陣μ(A)是非奇異M矩陣，則稱A是非奇異H矩陣。

從定義5可得，對于任意一個矩陣，通過判斷其比較矩陣是否為非奇異M矩陣，可判別該矩陣是否為非奇異H矩陣。

2主要結(jié)果

引理1設(shè)A∈Zn×n，若滿足下列條件，則A是非奇異M矩陣。

1)A可逆；

2)A-1≥0。

引理1給出了直接判定一個矩陣是否為非奇異M矩陣的方法。

將逆矩陣A-1的各個分塊對應(yīng)寫成Schur補(bǔ)的形式，便得到Schur補(bǔ)求逆矩陣的方法。

由A-1(α′)=(A(α′)-A(α′,α)A(α)-1A(α,α′))-1，根據(jù)Schur補(bǔ)定義

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

有A-1(α′)=(A/A(α))-1，那么，相應(yīng)地將α與α′互換，可得到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算法設(shè)計

由定理1可知，要判定一個n階Z矩陣A是否為非奇異M矩陣，只需判定子塊A(α)-1和(A/A(α))-1是否為非負(fù)矩陣。當(dāng)n較大時，不失一般性，考慮取A(α)為4階矩陣，并設(shè)

算法1給定矩陣B=(bij)∈Cn×n，令A(yù)=μ(B)=(aij)∈Zn×n，其中μ(B)是B的比較矩陣。

1)令A(yù)(m)=A，m=0；

3)計算A(m)的階數(shù)n，若n≤4，則轉(zhuǎn)步驟4)，否則轉(zhuǎn)步驟5)；

并轉(zhuǎn)步驟2)；

5)計算(A(m))-1，若不是非負(fù)矩陣，則A不是非奇異H矩陣。否則，A是非奇異H矩陣。

4數(shù)值例子

例1考慮矩陣

根據(jù)算法1，只需運(yùn)算2次，得到(A(2))-1=0.330 3>0，可知B為非奇異H矩陣。實(shí)際上，用計算機(jī)求得A-1=(μ(B))-1≥0，為非負(fù)矩陣，由定理1可知，B確為非奇異H矩陣。

例2 考慮矩陣

根據(jù)算法1，運(yùn)算1次，得

不是非負(fù)矩陣，可知B不是非奇異H矩陣。實(shí)際上，用計算機(jī)求得A-1=(μ(B))-1不是非負(fù)矩陣，可知B的確不是非奇異H矩陣。

5結(jié)束語

對于非奇異H矩陣的數(shù)值判定算法，將矩陣的Schur補(bǔ)求逆應(yīng)用到其中，即通過用矩陣的Schur補(bǔ)求逆，并判斷該逆矩陣是否為非負(fù)矩陣，再作降階運(yùn)算，逐次判斷，由此判定原矩陣是否為非奇異H矩陣。該算法擴(kuò)展了非奇異H矩陣在數(shù)值判定算法中降階處理時的方法。

參考文獻(xiàn):

[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].高等學(xué)校計算數(shù)學(xué)學(xué)報,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]郭希娟,紀(jì)乃華,姚慧萍.逆M矩陣的判定及并行算法[J].北華大學(xué)學(xué)報,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

文獻(xiàn)標(biāo)志碼：A

文章編號：1673-808X(2016)01-0076-03

通信作者：段復(fù)建(1965-)，女，黑龍江黑河人，教授，博士，研究方向為最優(yōu)化理論與方法、數(shù)值代數(shù)。E-mail:duanfj@guet.edu.cn

基金項目：國家自然科學(xué)基金(11461015)

收稿日期：2015-09-12