广义严格对角占优矩阵的一种判别法

时间：2024-06-19

关晋瑞,任孚鲛

(太原师范学院数学系,山西晋中030619)

1.引言

广义严格对角占优矩阵是一类很重要的特殊矩阵,在矩阵理论,数值分析,控制论及数理经济学中都有着广泛的应用[2−3,8,11,14−16].有关广义严格对角占优矩阵的判定一直是人们研究的一个重点.近年来很多学者都对此问题作了深入的研究,得到了大量的成果[1,4−7,9−10,12−13].

为了方便讨论,下面我们首先给出有关广义严格对角占优矩阵的一些基本概念,术语符号及常见结论.设A=(aij)∈Cn×n,记N={1,2,··· ,n},对任意的i ∈N,令以及

定义1.1[8,16]设A=(aij)∈Cn×n,若对任意的i ∈N,都有|aii|>ri(A),则称A为严格对角占优矩阵.若存在正对角矩阵D,使得AD为严格对角占优矩阵,则称A为广义严格对角占优矩阵.

定义1.2[16]设A=(aij)∈Cn×n,若存在置换矩阵P,使得

其中A11,A22分别为k×k,(n −k)×(n −k)的矩阵,1≤k < n,则称矩阵A是可约的.否则称A是不可约的.

定义1.3[8,16]设A=(aij)∈Cn×n不可约,若对任意的i ∈N,有|aii|≥ri(A),且至少有一个严格不等式成立,则称A为不可约对角占优矩阵.

定义1.4[16]设A=(aij)∈Cn×n,称m(A)=(αij)∈Rn×n为A的判别矩阵,其中

下面是广义严格对角占优矩阵的几个基本性质[7−8,16].

引理1.1设A为广义严格对角占优矩阵,则对任意的i ∈N,有aii0.

引理1.2设A为广义严格对角占优矩阵,则N1(A)∅.

引理1.3设A=(aij)∈Cn×n,则A为广义严格对角占优矩阵当且仅当AD为广义严格对角占优矩阵,其中D为正对角矩阵.

引理1.4设A是不可约对角占优矩阵,则A为广义严格对角占优矩阵.

现有文献中关于广义严格对角占优矩阵的判别法大多数都是直接法,但直接法判定范围狭窄,复杂且不实用,相比之下,迭代判别法具有更大的优势,并且可以充分利用计算机来实现[1,7].本文研究广义严格对角占优矩阵的迭代判别法,在第2节我们提出广义严格对角占优矩阵的一种迭代判别法,并证明了相应的收敛性理论,在第3节中用数值算例展示了该判别法的有效性.

2.主要结果

文[13]提出如下一个广义严格对角占优矩阵的迭代判别法.

算法2.1

输入：不可约矩阵A=(aij)∈Cn×n.

输出：“A不是广义严格对角占优矩阵”或者“A是广义严格对角占优矩阵”.

1) 若对某个i ∈N,有aii=0 ,“A不是广义严格对角占优矩阵”,停止；否则

2) 令k=0,A0=A；

3) 对i ∈N,计算ti(Ak),及

若u ≥1,“A不是广义严格对角占优矩阵”,停止；

若v ≤1,“A是广义严格对角占优矩阵”,停止；

否则计算Ak+1=AkDk,其中Dk=diag(d1,d2,··· ,dn),且

4) 令k=k+1,返回第3步.

该算法的优点是运算量小,每步迭代只需要O(n)的运算量,而其他的一些判别法每步都需要O(n2)的运算量.对于不可约广义严格对角占优矩阵,该算法具有良好的收敛性.

通过数值实验我们发现当所要判别的矩阵不是广义严格对角占优矩阵时,算法2.1所需的迭代次数比较多,因此有待进一步改进.通过对算法2.1的深入研究,我们发现其基本思想是不断缩小占优行对角元所在列元,从而最终得到矩阵是否为广义严格对角占优矩阵的结论.经过分析我们认为如果同时对占优行对角元所在列进行不断缩小,以及对占劣行对角元所在列进行不断放大,这样会取得更好的效果,避免了其缺陷.下面按照这个想法我们对算法2.1进行改进.

设A=(aij)∈Cn×n不可约,构造序列{Ak}如下：

依此类推,可以得到矩阵序列{Ak}.由构造过程可以看到该矩阵序列元素的绝对值不断变大.对于该矩阵序列,我们有下面的结论.

引理2.1设A=(aij)∈Cn×n不可约,若A不是广义严格对角占优矩阵,对角线元素非零且判别矩阵m(A)非奇异,则对于上述构造的矩阵序列{Ak},存在一个正整数K,当k > K时,有N1(Ak)=∅.

证首先注意到当k增加时,集合N1(Ak)的元素个数不增,而N0(Ak)∪N2(Ak)的元素个数不减.这是因为∀i ∈N1(Ak),设tp(Ak)=max1≤i≤nti(Ak),则tp(Ak)>1,且.从而

这样有可能ti(Ak+1)≥1,进而1(Ak+1).而对于当i=p时,很明显i ∈N0(Ak+1),而当ip时,

其次,假设引理结论不成立,即对任意正整数k,都有N1(Ak)∅.根据上面的分析则存在一个正整数l,使得∀m >0,有N1(Al)=N1(Al+m).为了讨论方便,不妨设N1(Al)={1,2,··· ,k},且

其中A11是k×k的.这样Al的前k行是严格对角占优行,且由上面假设对于任意m > l,Am的前k行也是严格对角占优行.而根据引理的条件,Al的后n −l行必存在严格对角占劣行,否则Al将是广义严格对角占优矩阵,从而A是广义严格对角占优矩阵,这与引理条件矛盾.类似的对于任意m>1,Am的后n −k行必存在严格对角占劣行.这样对于Al而言,当l增大时,对应的子块A12中的元素将不断增大,但是由于前k行是严格对角占优行,于是A12中的元素存在上界,从而必有极限.设

我们来看看最后极限结果中的B和C.容易证明Aω后n −k列不会趋于无穷大,而且

因此Aω无严格对角占劣行.若Aω前k行存在严格对角占优行,则Aω是广义严格对角占优矩阵,从而A是广义严格对角占优矩阵,与定理条件矛盾.若Aω前k行不存在严格对角占优行,即有ti(Aω)=1,则m(Aω)奇异,从而m(A)也奇异,这也与定理假设矛盾.从而对于充分大k必有N1(Ak)=∅.证毕.根据前面的分析以及上述定理,我们提出下面的判别法.

算法2.2

输入：不可约矩阵A=(aij)∈Cn×n.

输出：“A不是广义严格对角占优矩阵”或者“A是广义严格对角占优矩阵”.

1) 若对某个i ∈N,有aii=0 ,“A不是广义严格对角占优矩阵”,停止; 否则

2) 令k=0,B0=A,C0=A;

3) 对i ∈N,计算ti(Bk),及p=min1≤i≤nti(Bk),[q,qq]=max1≤i≤nti(Bk);

若p ≥1,“A不是广义严格对角占优矩阵”,停止;

若q ≤1,“A是广义严格对角占优矩阵”,停止;

否则计算Bk+1=BkDk,其中Dk=diag(d1,d2,··· ,dn),且

4) 对i ∈N,计算ti(Ck),及[u,uu]=min1≤i≤nti(Ck),v=max1≤i≤nti(Ck)；

若u ≥1,“A不是广义严格对角占优矩阵”,停止；

若v ≤1,“A是广义严格对角占优矩阵”,停止；

否则计算Ck+1=CkDk,其中Dk=diag(d1,d2,··· ,dn),且

5) 令k=k+1,返回第3步.

下面我们分析算法2.2的收敛性.

定理2.1对任意给定的不可约矩阵A=(aij)∈Cn×n,假设判别矩阵m(A)非奇异,则算法2.2总是收敛的.

证若矩阵A对角线有零元素,则算法2.2直接可以停止.若矩阵A对角线无零元素,当矩阵A是广义严格对角占优矩阵时,根据文[13]中的结论,算法2.2中第4步可以在有限步内停止.当矩阵A不是广义严格对角占优矩阵时,根据引理2.1,算法2.2中第3步可以在有限步内停止.证毕.

定理2.2对任意给定的不可约矩阵A=(aij)∈Cn×n,若算法2.2收敛,则它的结论是正确的.

证当算法终止时,有两个输出结果: “A不是广义严格对角占优矩阵”和“A是广义严格对角占优矩阵”.下面我们分情况讨论.

当输出结果为“A不是广义严格对角占优矩阵”时,可能在第1、3或4步.若在第1步停止,则对某个i ∈N,有aii=0,根据引理1.1,A不是广义严格对角占优矩阵.若在第3步停止,则对任意i ∈N,有ti(Bk)≥1,即有N1(Bk)=∅,根据引理1.2,Bk不是广义严格对角占优矩阵,从而由引理1.3,A不是广义严格对角占优矩阵.若在第4步停止,则对任意i ∈N,有ti(Ck)≥1,即有N1(Ck)=∅,根据引理1.2,Ck不是广义严格对角占优矩阵,从而A不是广义严格对角占优矩阵.

当输出结果为“A是广义严格对角占优矩阵”时,可能在第3、4步.若在第3步停止,则对任意i ∈N,有ti(Bk)≤1,由于前面已经处理了ti(Bk)≥1的情形,此时有ti(Bk)≤1,且至少有一个不等式是严格的,从而根据引理1.4,Bk是广义严格对角占优矩阵,从而A是广义严格对角占优矩阵.若在第4步停止,则对任意i ∈N,有ti(Ck)≤1,由于前面已经处理了ti(Ck)≥1的情形,此时有ti(Ck)≤1,且至少有一个不等式是严格的,根据引理1.4,Ck是广义严格对角占优矩阵,从而A是广义严格对角占优矩阵.证毕.