一类非奇异H-矩阵的细分迭代判别算法

Subdivision Iterative Discriminant Algorithm for a Class of Nonsingular H-Matrix

摘要: 非奇异H-矩阵是一类应用广泛的特殊矩阵，在许多领域都发挥着重要作用。本文就非奇异H-矩阵的判定问题，利用细分区间和迭代系数构造正对角矩阵因子，得到了一类非奇异H-矩阵的细分迭代判别新条件。在此基础上，又相应给出了一组含参数 的判定非奇异H-矩阵的细分迭代算法，并证明了其收敛性，推广与改进了近期的一些结果。最后，用数值算例说明了该算法的优越性。

Abstract: Nonsingular H-matrices are a kind of special matrices which are widely used in many fields. In this paper, we consider the problem of determining nonsingular H-matrices, construct a positive diago-nal matrix factor by using the subdivision interval and iterative coefficient, and obtain a new condi-tion for determining the subdivision iteration of a class of nonsingular H-matrices. On this basis, a set of subdivision iterative algorithms for determining nonsingular H-matrices with parameters are given, and their convergence is proved. Some recent results are extended and improved. Finally, numerical examples are used to illustrate the superiority of the algorithm.

1. 引言

矩阵理论是研究者用来解决实际问题的一种重要工具，而非奇异H-矩阵作为重要的一类特殊矩阵，经过众多学者对其的深入研究(见文献 [1] - [11])，非奇异H-矩阵的判定条件已取得了一系列重要成果，但对于高阶矩阵的判定还存在困难。而随着计算机的普及，关于非奇异H-矩阵不少的判定算法也逐渐被提出，这在一定程度上提高了非奇异H-矩阵的判定效率。其中，文献 [1] 根据文献 [3] 的迭代判定条件给出了相应的含参数 $\epsilon$ 的迭代算法，且在此基础上，进一步减小迭代因子序列后，又得到了另一组迭代次数和迭代时间更少的判定算法。文献 [2] 通过对方阵行下标集和行不同的递进式划分，得到了一组无参数的迭代判定算法。而本文利用文献 [2] 的思路，并通过进一步细分区间和构造新的迭代因子序列的方式，得到比文献 [1] [2] 更小的正对角矩阵因子，进而给出一组迭代次数更少，迭代效率更高的细分迭代判定新条件以及迭代判定新算法，推广和改进了已有的一些相关结论。

记 $C^{n\times n}$ 表示 $n\times n$ 阶复矩阵集合，设 $A=\left(a_{ij}\right)\in C^{n\times n}$， $N=\left\{1,2,\cdots ,n\right\}$， $Z=\left\{0,1,2,\cdots \right\}$， $Z^{+}=\left\{1,2,\cdots \right\}$。记

${\Lambda }_i={\Lambda }_i\left(A\right)={\displaystyle \underset{j\ne i}{\sum }\left|a_{ij}\right|}\text{,}i,j\in N,$

${\tilde{N}}_1=\left\{i\in N:0<\left|a_{ii}\right|\le {\Lambda }_i\left(A\right)\right\},{\tilde{N}}_2=\left\{i\in N:\left|a_{ii}\right|>{\Lambda }_i\left(A\right)\right\},$

${\alpha }_i={\alpha }_i\left(A\right)={\displaystyle \underset{t\in {\tilde{N}}_1,t\ne i}{\sum }\left|a_{it}\right|},{\beta }_i={\beta }_i\left(A\right)={\displaystyle \underset{t\in {\tilde{N}}_2,t\ne i}{\sum }\left|a_{it}\right|},i\in N.$

定义1 [3] 设 $A=\left(a_{ij}\right)\in C^{n\times n}$，如果 $\left|a_{ii}\right|>{\Lambda }_i\left(A\right),i\in N$，则称A为严格对角占优矩阵，记作 $A\in D$。若存在正对角矩阵X，使得 $AX\in D$，则称A为广义严格对角占优矩阵，也称为非奇异H-矩阵，记作 $A\in D^{*}$。

引理1 [2] 设 $A=\left(a_{ij}\right)\in C^{n\times n}$，如果存在 ${\tilde{N}}_1,{\tilde{N}}_2$ 使得 ${\tilde{N}}_1\cup {\tilde{N}}_2=N,{\tilde{N}}_1\cap {\tilde{N}}_2=\varphi$ 及

$\left(\left|a_{ii}\right|-{\alpha }_i\left(A\right)\right)\left(\left|a_{jj}\right|-{\beta }_j\left(A\right)\right)>{\beta }_i\left(A\right){\alpha }_j\left(A\right),i\in {\tilde{N}}_1,j\in {\tilde{N}}_2,$

则A为非奇异H-矩阵。

在本文中假设 $\left|a_{ii}\right|\ne 0,{\Lambda }_i\left(A\right)\ne 0,i\in N$，规定 ${\displaystyle \underset{t\in \varphi }{\sum }•}=0$，并记

$N_1=\left\{i\in N:0<\left|a_{ii}\right|<{\Lambda }_i\left(A\right)\right\},N_2=\left\{i\in N:\left|a_{ii}\right|={\Lambda }_i\left(A\right)\right\},N_3=\left\{i\in N:\left|a_{ii}\right|>{\Lambda }_i\left(A\right)\right\},$

则 $N=N_1+N_2+N_3$，由 $N_1=N_1^{\left(1\right)}\cup N_1^{\left(2\right)}\cup \cdots \cup N_1^{\left(m\right)}$，其中

$N_1^{\left(1\right)}=\left\{i\in N:0<\left|a_{ii}\right|<\frac{1}{m}{\Lambda }_i\left(A\right)\right\},$

$N_{1k}=\left\{i\in N:\frac{k-1}{m}{\Lambda }_i\left(A\right)\le \left|a_{ii}\right|<\frac{k}{m}{\Lambda }_i\left(A\right)\right\},k=2,3,\cdots ,m,$

其中， $N_1^{\left(k\right)}$ 可能为空集。

引理2 [5] 设 $A=\left(a_{ij}\right)\in C^{n\times n}$，如果 $A\in D^{*}$，则 $N_3\ne \varphi$ 且 $\left|a_{ii}\right|\ne 0\left(i\in N\right)$。

引理3 [5] 设 $A=\left(a_{ij}\right)\in C^{n\times n}$，如果 $A\in D^{*}$，则 $\left|a_{ii}\right|>0\left(i\in N\right)$ 且 $N_1=\varphi$。

若 $N_1\cup N_2$ 为空集，则A为非奇异H-矩阵。若 $N_3$ 为空集，则A不是非奇异H-矩阵。因此，本文总假设 $N_1\cup N_2$ 不为空集， $N_3$ 也不为空集。

张万智等在2016年提出一组非奇异H-矩阵的迭代判别算法：

算法1.1 [1] 给定矩阵 $A=\left(a_{ij}\right)\in C^{n\times n}$。

1) 如果存在 $i_0\in N$ 使得 $\left|a_{i_0{i}_0}\right|=0$，则 $A\notin D^{*}$，停止；否则

2) 令 $\tilde{y}=1,A^{\left(0\right)}=A,X_1{}^{\left(0\right)}=I$ ；

3) 计算 $A^{\left(\tilde{y}\right)}=\left(a_{it}^{\left(\tilde{y}\right)}\right)=A^{\left(\tilde{y}-1\right)}{X}_1^{\left(\tilde{y}-1\right)}$ ；

4) 如果 ${\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)=\varphi$，则 $A\notin D^{*}$，停止；如果 ${\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)=N$，则 $A\in D^{*}$，停止；否则

5) 计算

${\lambda }_0^{\left(\tilde{y}\right)}=1,{\psi }_i^{\left(\tilde{y}\right)}=\frac{{\displaystyle \underset{t\in {\tilde{N}}_1\left(A^{\left(\tilde{y}\right)}\right)}{\sum }\left|a_{it}^{\left(\tilde{y}\right)}\right|}}{\left|a_{ii}^{\left(\tilde{y}\right)}\right|-{\displaystyle \underset{t\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right),t\ne i}{\sum }\left|a_{it}^{(\tilde{y})}\right|}}\text{,}{\lambda }_1^{\left(\tilde{y}\right)}=\underset{i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)}{\max }\frac{{\displaystyle \underset{t\in {\tilde{N}}_1\left(A^{\left(\tilde{y}\right)}\right)}{\sum }\left|a_{it}^{\left(\tilde{y}\right)}\right|}}{\left|a_{ii}^{\left(\tilde{y}\right)}\right|-{\displaystyle \underset{t\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(\tilde{y}\right)}\right|}},$

${\lambda }_{l+1}^{\left(\tilde{y}\right)}=\underset{i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)}{\max }{\delta }_{l+1}^{\left(\tilde{y}\right)}\left(l\in Z^{+}\right),$

${\delta }_{l+1,i}^{\left(\tilde{y}\right)}=\frac{{\displaystyle \underset{t\in {\tilde{N}}_1\left(A^{\left(\tilde{y}\right)}\right)}{\sum }\left|a_{it}^{\left(\tilde{y}\right)}\right|}+{\lambda }_l^{\left(\tilde{y}\right)}{\displaystyle \underset{t\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(\tilde{y}\right)}\right|}}{\left|a_{ii}^{\left(\tilde{y}\right)}\right|}\left(i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right),l\in Z\right);$

6) 取定非负整数l和实数 $s\ge 1$。令 $X_1^{\left(\tilde{y}\right)}=diag\left(x_1^{\left(\tilde{y}\right)},x_2^{\left(\tilde{y}\right)},\cdots ,x_n^{\left(\tilde{y}\right)}\right)$，其中

$x_i^{\left(\tilde{y}\right)}=\{\begin{array}{l}1\left(i\in {\tilde{N}}_1\left(A^{\left(\tilde{y}\right)}\right)\right),\\ {\delta }_{l+1,i}^{\left(\tilde{y}\right)}+{\epsilon }_0^{\left(\tilde{y}\right)}\left(i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)\right),\end{array}$

这里当 ${\psi }_i^{\left(\tilde{y}\right)}>{\delta }_{l+1,i}^{\left(\tilde{y}\right)}\left(i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)\right)$ 时 ${\epsilon }_0^{\left(\tilde{y}\right)}=\frac{1}{s}\underset{i\in {\tilde{N}}_2\left(A^{\left(\tilde{y}\right)}\right)}{\min }\left({\psi }_i^{\left(\tilde{y}\right)}-{\delta }_{l+1,i}^{\left(\tilde{y}\right)}\right)$，其余情形 ${\epsilon }_0^{\left(\tilde{y}\right)}={\sigma }_1$， ${\sigma }_1$ 是充分小的正实数；

7) 取 $\tilde{y}=\tilde{y}+1$ 转3。

2. 主要结果

为了叙述方便，进一步引入以下记号：

$x_{1i,k}=\frac{\left|a_{ii}\right|-\frac{k-1}{m+1}{\Lambda }_i\left(A\right)}{{\Lambda }_i\left(A\right)}\left(i\in N_{1k},k=1,2,\cdots ,m\right),$

$x_{2i}=\frac{{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2,t\ne i}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|}}}{\left|a_{ii}\right|}\left(i\in N_2\right),$

$r_0=1,r_1=\underset{i\in N_3}{\max }\left\{\frac{{\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}}{\left|a_{ii}\right|-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|}}\right\},$

$r_{l+1}=\underset{i\in N_3}{\max }\left\{\frac{{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+r_l{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|}}{\left|a_{ii}\right|}\right\}\left(l\in Z^{+}\right),$

$P_{l+1,i}\left(A\right)={\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+r_l{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|}\left(i\in N_3,l\in Z\right),$

$W_{l+1,i}\left(A\right)={\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{P_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}\left(i\in N_3,l\in Z\right),$

$h_{l+1,i}\left(A\right)=\frac{{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}{W_{l+1,i}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}}\left(i\in N_3,l\in Z\right).$

定理1设 $A=\left(a_{ij}\right)\in C^{n\times n}$，若存在 $l\in Z$，有

$\begin{array}{l}\left(W_{l+1,j}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{jt}\right|}\right)\left(\left|a_{ii}\right|x_{1i,k}-{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}-{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}\right)\\ >\left({\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}\right)\left({\displaystyle \underset{t\in N_3}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}\right),i\in N_{1k},k=1,2,\cdots ,m,j\in N_3.\end{array}$ (1)

且当 $i\in N_2$ 时， ${\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}$ 与 ${\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|}$ 不能同时为0，则A是非奇异H-矩阵。

证明 由 $r_1$ 的表达式和(1)式可得，对任意的 $i\in N_3$, ${\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}$ 与 ${\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}$ 不能同时为0。因为，如果 ${\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}=0$，则对任意的 $i\in N_3$，有 $r_1=0$，再由 $r_{l+1}$ 的定义式可知，对任意的 $l\in Z$，都有 $r_{l+1}=0$，所以也便有 $P_{l+1,i}\left(A\right)=0,W_{l+1,i}\left(A\right)=0$，这样会使不等式(1)的两边同时为0，故产生矛盾。

显然 $r_1<1$，又对任意的 $i\in N_{1k},k=1,2,\cdots ,m$，有 $0<x_{1i}^{\left(k\right)}<1$ ；对任意的 $i\in N_2$，有 $0<x_{2i}\le 1$ ；则结合数学归纳法可得到

$\frac{P_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}\le r_{l+1}\le r_l\le \cdots \le r_1<r_0=1,\frac{W_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}\le \frac{P_{l+1,i}\left(A\right)}{\left|a_{ii}\right|},i\in N_3,l\in Z.$ (2)

故对任意的 $i\in N_3$ 有

$h_{l+1,i}\left(A\right)=\frac{{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}{W_{l+1,i}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}}=\frac{W_{l+1,i}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{P_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}}{W_{l+1,i}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}}\le 1.$

根据 $h_{l+1,j}\left(A\right)$ 的表达式及(1)式知，对任意的 $i\in N_{1k},k=1,2,\cdots ,m,j\in N_3$ 有

$\left|a_{ii}\right|x_{1i,k}>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+h_{l+1,j}\left(A\right){\displaystyle \underset{t\in N_3}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|},$

又 $h_{l+1,j}\left(A\right)\le 1$，故而得到

$\left|a_{ii}\right|x_{1i,k}>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+{\displaystyle \underset{t\in N_3}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|},$

进一步可取得充分小的 $\epsilon >0$，使 $0<\frac{W_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}+\epsilon <1$，并满足

$\left|a_{it}\right|x_{1i,k}-\left[{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}+{\displaystyle \underset{t\in N_3}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}\right]>\epsilon {\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|},$

故而有

$\left|a_{it}\right|x_{1i,k}-{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{it}\right|x_{1t,k}}\right)-{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}>{\displaystyle \underset{t\in N_3}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)}\left|a_{it}\right|.$ (3)

可构造正对角矩阵 $X_1=diag\left(x_1,x_2,\cdots ,x_n\right)$，记 $B=A{X}_1=\left(b_{ij}\right)$，其中

$x_i=\{\begin{array}{l}{x}_{1i,k}i\in N_{1k},k=1,2,\cdots ,m,\\ x_{2i}i\in N_2,\\ \frac{W_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}+\epsilon i\in N_3.\end{array}$

再由 $h_{l+1,j}\left(A\right)\le 1$ 可得到，对任意的 $j\in N_3,l\in Z$ 有

$W_{l+1,j}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{jt}\right|}\ge {\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}},$

又对任意的 $j\in N_3$，有 $\left|a_{jj}\right|>{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\left|a_{jt}\right|}$，所以得到

$W_{l+1,j}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{jt}\right|}+\left(\epsilon \left|a_{jj}\right|-\epsilon {\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{jt}\right|}\right)>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}},$

即有

$W_{l+1,j}\left(A\right)+\epsilon \left|a_{jj}\right|-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{jt}\right|}>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}}.$ (4)

1) 由(3)式和(4)式知，对任意的 $i\in N_{1k},k=1,2,\cdots ,m,j\in N_3,l\in Z$ 有

$\begin{array}{l}\left(\left|b_{jj}\right|-{\beta }_j\left(B\right)\right)\left(\left|b_{ii}\right|-{\alpha }_i\left(B\right)\right)\\ =\left(W_{l+1,j}\left(A\right)+\epsilon \left|a_{jj}\right|-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{jt}\right|}\right)\left(\left|a_{ii}\right|x_{1i,k}-{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k},t\ne i}{\sum }\left|a_{ii}\right|x_{1t,k}}\right)}-{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}\right)\\ >\left({\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}}\right)\left({\displaystyle \underset{t\in N_3}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{it}\right|}\right)={\alpha }_j\left(B\right){\beta }_i\left(B\right).\end{array}$

2) 根据 $x_{2i}$ 的表达式可知，对任意的 $i\in N_2$ 有

$\begin{array}{c}\left|a_{ii}\right|x_{2i}={\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2,t\ne i}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|}}\\ >{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2,t\ne i}{\sum }\left|a_{it}\right|x_{2t}}+{\displaystyle \underset{t\in N_3}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)}}\left|a_{it}\right|,\end{array}$ (5)

由(4)式和(5)式可知，对任意的 $i\in N_2,j\in N_3,l\in Z$ 有

$\begin{array}{l}\left(\left|b_{jj}\right|-{\beta }_j\left(B\right)\right)\left(\left|b_{ii}\right|-{\alpha }_i\left(B\right)\right)\\ =\left(W_{l+1,j}\left(A\right)+\epsilon \left|a_{jj}\right|-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{jt}\right|}\right)\left(\left|a_{ii}\right|x_{2i}-{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{ii}\right|x_{1t,k}}\right)}-{\displaystyle \underset{t\in N_2,t\ne i}{\sum }\left|a_{it}\right|x_{2t}}\right)\\ >\left({\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}}\right)\left({\displaystyle \underset{t\in N_3}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{it}\right|}\right)={\alpha }_j\left(B\right){\beta }_i\left(B\right).\end{array}$

3) 由 $W_{l+1,i}\left(A\right)$ 的表达式及 $W_{l+1,i}\left(A\right)\le P_{l+1,i}\left(A\right)$ 可知，对任意的 $i\in N_3,l\in Z$ 有

$W_{l+1,i}\left(A\right)\ge {\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}+{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}}\left|a_{it}\right|,$

又对任意的 $i\in N_3$，有 $\left|a_{ii}\right|>{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|}$，所以得到

$W_{l+1,i}\left(A\right)+\epsilon \left|a_{ii}\right|>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}+{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}\left|a_{it}\right|}+\epsilon {\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|},$

故有

$\left(\frac{W_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}+\epsilon \right)\left|a_{ii}\right|>{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{it}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|x_{2t}}}+{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)}\left|a_{it}\right|,$ (6)

由(4)式和(6)式可知，对任意的 $i\in N_3,j\in N_3,l\in Z$ 有

$\begin{array}{l}\left(\left|b_{jj}\right|-{\beta }_j\left(B\right)\right)\left(\left|b_{ii}\right|-{\alpha }_i\left(B\right)\right)\\ =\left(W_{l+1,j}\left(A\right)+\epsilon \left|a_{jj}\right|-{\displaystyle \underset{t\in N_3,t\ne j}{\sum }\left(\frac{W_{l+1,t}(A)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{jt}\right|}\right)\left(\left|a_{ii}\right|\left(\frac{W_{l+1,i}\left(A\right)}{\left|a_{ii}\right|}+\epsilon \right)-{\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{ii}\right|x_{1t,k}}\right)}-{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}{x}_{2t}\right)\\ >\left({\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}}{\sum }\left|a_{jt}\right|x_{1t,k}}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{jt}\right|x_{2t}}}\right)\left({\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left(\frac{W_{l+1,t}\left(A\right)}{\left|a_{tt}\right|}+\epsilon \right)\left|a_{it}\right|}\right)={\alpha }_j\left(B\right){\beta }_i\left(B\right).\end{array}$

即

$\left(\left|b_{ii}\right|-{\alpha }_i\left(B\right)\right)\left(\left|b_{jj}\right|-{\beta }_j\left(B\right)\right)>{\beta }_i\left(B\right){\alpha }_j\left(B\right)\text{,}i\in N_1\cup N_2,j\in N_3,$

且

$\left(\left|b_{ii}\right|-{\alpha }_i\left(B\right)\right)\left(\left|b_{jj}\right|-{\beta }_j\left(B\right)\right)>{\beta }_i\left(B\right){\alpha }_j\left(B\right)\text{,}i\in N_3,j\in N_3.$

综上所述，由引理1知 $B=A{X}_1\in D^{*}$。故存在正对角矩阵 $X_2$ 使得 $B{X}_2=A{X}_1{X}_2\in D$，而 $X_1{X}_2$ 仍是正对角矩阵，所以 $A\in D^{*}$。证毕。

由上述判定定理条件得到下面新的算法2.1。

算法2.1

输入：矩阵 $A=\left(a_{ij}\right)\in C^{n\times n}$，给定 $m,q,{\sigma }_2$。

输出： $X^{\left(y\right)}=diag\left(x_i^{\left(y\right)}\right)$，若A是非奇异H-矩阵。

1) 如果 $N_3\left(A\right)=\varphi$ 或存在 $i_0\in N\left(A\right)$ 使得 $\left|a_{i_0{i}_0}\right|=0$，则 $A\notin D^{*}$，停止；否则转2；

2) 取 $y=1,A^{\left(0\right)}=A,X^{\left(0\right)}=I$ ；

3) 计算 $A^{\left(y\right)}=A^{\left(y-1\right)}{X}^{\left(y-1\right)}=\left(a_{it}^{\left(y\right)}\right)$ ；

4) 取 $l=1$，计算 ${\Lambda }_i\left(A^{\left(y\right)}\right)={\displaystyle \underset{t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}$ ；

5) 如果 $\left|a_{ii}^{\left(y\right)}\right|>{\Lambda }_i\left(A^{\left(y\right)}\right)$，则 $i\in N_3\left(A^{\left(y\right)}\right)$ ；否则转6；

6) 如果 $\left|a_{ii}^{\left(y\right)}\right|={\Lambda }_i\left(A^{\left(y\right)}\right)$，则 $i\in N_2\left(A^{\left(y\right)}\right)$ ；否则转7；

7) 取 $k\in \left[1,m\right]$，如果 $\frac{k-1}{m}{\Lambda }_i\left(A^{\left(y\right)}\right)<\left|a_{ii}^{\left(y\right)}\right|<\frac{k}{m}{\Lambda }_i\left(A^{\left(y\right)}\right)$，则 $i\in N_{1k}\left(A^{\left(y\right)}\right)$ ；

8) 令 $N_1\left(A^{\left(y\right)}\right)={\displaystyle \underset{k=1}{\overset{m}{\cup }}{N}_{1k}\left(A^{\left(y\right)}\right)}$，如果 $N_1\left(A^{\left(y\right)}\right)\cup N_2\left(A^{\left(y\right)}\right)=\varphi$，则 $A\in D^{*}$，停止；否则转9；

9) 如果 $N_3\left(A^{\left(y\right)}\right)=\varphi$，则 $A\notin D^{*}$，停止；否则转10；

10) 计算

$x_{1i,k}^{\left(y\right)}=\frac{\left|a_{ii}^{\left(y\right)}\right|-\frac{k-1}{m+1}{\Lambda }_i\left(A^{\left(y\right)}\right)}{{\Lambda }_i\left(A^{\left(y\right)}\right)}\left(i\in N_{1k}\left(A^{\left(y\right)}\right),k=1,2,\cdots ,m\right),$

${\alpha }_i^{\left(y\right)}={\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\right)},{\bar{\alpha }}_i^{\left(y\right)}={\displaystyle \underset{k=1}{\overset{m}{\sum }}\left({\displaystyle \underset{t\in N_{1k}\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|x_{1t,k}^{\left(y\right)}}\right),}$

${\beta }_i^{\left(y\right)}={\displaystyle \underset{t\in N_2\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|},{\bar{\beta }}_i^{\left(y\right)}={\displaystyle \underset{t\in N_2\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|x_{2t}^{\left(y\right)}},$

${\mu }_i^{\left(y\right)}={\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|},$

$x_{2i}^{\left(y\right)}=\frac{{\bar{\alpha }}_i^{\left(y\right)}+{\beta }_i^{\left(y\right)}+{\mu }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\left(i\in N_2\left(A^{\left(y\right)}\right)\right);$

11) 取 $r_0^{\left(y\right)}=1$，计算

$r_1^{\left(y\right)}=\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\max }\left\{\frac{{\alpha }_i^{\left(y\right)}+{\beta }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|-{\mu }_i^{\left(y\right)}}\right\}\text{,}$

$r_{l+1}^{\left(y\right)}=\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\max }\left\{\frac{{\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}+r_l^{\left(y\right)}{\mu }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right\}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z^{+}\right),$

$P_{l+1,i}^{\left(y\right)}={\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}+r_l^{\left(y\right)}{\mu }_i^{\left(y\right)}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z\right),$

${\bar{\mu }}_i^{\left(y\right)}={\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\frac{P_{l+1,t}^{\left(y\right)}}{\left|a_{tt}^{\left(y\right)}\right|}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z\right)\text{,}$

$W_{l+1,i}^{\left(y\right)}={\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}+{\bar{\mu }}_i^{\left(y\right)}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z\right),$

${\bar{\eta }}_i^{\left(y\right)}={\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\frac{W_{l+1,t}^{\left(y\right)}}{\left|a_{tt}^{\left(y\right)}\right|}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z\right)\text{,}$

$h_{l+1,i}^{\left(y\right)}=\frac{{\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}}{W_{l+1,i}^{\left(y\right)}-{\bar{\eta }}_i^{\left(y\right)}}\left(i\in N_3\left(A^{\left(y\right)}\right),l\in Z\right);$

12) 令 $\gamma =\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\max }\left\{\frac{{\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}}{W_{l+1,i}^{\left(y\right)}-{\bar{\eta }}_i^{\left(y\right)}}\right\}$ ；

13) 如果

$\left|a_{ii}^{\left(y\right)}\right|x_{1i,k}^{\left(y\right)}>{\bar{\alpha }}_i^{\left(y\right)}+{\bar{\beta }}_i^{\left(y\right)}+\gamma {\bar{\eta }}_i^{\left(y\right)}\left(i\in N_{1k}\left(A^{\left(y\right)}\right)\right)\text{,}$

则 $A\in D^{*}$，输出 $X^{\left(y\right)}=diag\left(x_i^{\left(y\right)}\right)$，停止；否则转14；其中

$x_i^{\left(y\right)}=\{\begin{array}{l}{x}_{1i,k}^{\left(y\right)}i\in N_{1k}\left(A^{\left(y\right)}\right),\\ x_{2i}^{\left(y\right)}i\in N_2\left(A^{\left(y\right)}\right),\\ \frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+{\epsilon }^{\left(y\right)}i\in N_2\left(A^{\left(y\right)}\right).\end{array}$

${\epsilon }^{\left(y\right)}=\{\begin{array}{l}\frac{1}{q}\min \left(\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right)\forall i\in N_3\left(A^{\left(y\right)}\right),{\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\ne 0,\\ {\sigma }_2\exists i\in N_3\left(A^{\left(y\right)}\right),s.t.{\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}=0.\end{array}$

这里 ${\sigma }_2$ 为充分小的数，且 $q>1$ ；

14) 如果 $l<100$，取 $l=l+1$，转11；否则转15；

15) 取 $y=y+1$，转3。

下面我们证明算法2.1的收敛性。

定理2 设矩阵 $A=\left(a_{ij}\right)\in C^{n\times n}$，如果算法2.1经过有限次迭代停止，且得到一个严格对角占优矩阵，那么A是非奇异H-矩阵。

证明充分性：假设算法2.1经过y次迭代后停止，并生成了一个严格对角占优矩阵 $A^{\left(y\right)}=\left(a_{it}^{\left(y\right)}\right)$。由 $A^{\left(y\right)}=A^{\left(y-1\right)}{X}^{\left(y-1\right)}$ 可递推得到

$A^{\left(y\right)}=A^{\left(0\right)}{X}^{\left(0\right)}{X}^{\left(1\right)}\cdots X^{\left(y-1\right)}=AX,$

即存在正对角矩阵 $X=X^{\left(1\right)}{X}^{\left(2\right)}\cdots X^{\left(y-1\right)}$ 使得 $AX\in D$。根据定义1可得，A是非奇异H-矩阵。

必要性利用反证法。假设算法2.1经过有限次迭代后未停止，即不妨设A为非负矩阵，算法2.1在经过无限次迭代后，生成了无穷序列 $\left\{A^{\left(y\right)}\right\}$, $\left\{a_{ii}^{\left(y\right)}\right\}$, $\left\{X^{\left(y\right)}\right\}$。令 $y=0,1,\cdots$，由算法2.1的步骤13可知，对任意的 $i\in N\left(A^{\left(y\right)}\right)$，都有 $0<x_i^{\left(y\right)}\le 1$，即正对角矩阵的对角元小于或等于1。又 $a_{it}^{\left(y\right)}=a_{it}^{\left(y-1\right)}{x}_t^{\left(y-1\right)}$， $A^{\left(y\right)}=A^{\left(y-1\right)}{X}^{\left(y-1\right)}$，则 $A=A^{\left(0\right)}=A^{\left(0\right)}\ge \cdots \ge A^{\left(y\right)}\ge \cdots \ge 0$，所以无穷矩阵序列 $\left\{A^{\left(y\right)}\right\}$ 单调递减且有界，可得 $\underset{y\to \infty }{\lim }{A}^{\left(y\right)}=B$，其中 $B=AX$, $X=X^{\left(1\right)}{X}^{\left(2\right)}\cdots X^{\left(y-1\right)}$。

下面证明： $\underset{y\to \infty }{\lim }{N}_3\left(A^{\left(y\right)}\right)=N_3\left(B\right)=\varphi$。

再利用反证法。假设存在某一 $i\in N_3\left(A^{\left(y\right)}\right)$，使得 $\underset{y\to \infty }{\lim }{N}_3\left(A^{\left(y\right)}\right)\ne \varphi$，则 $1-x_{1i,k}^{\left(y\right)}>0$， $1-x_{2i}^{\left(y\right)}>0$， $1-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-{\epsilon }^{\left(y\right)}>0$，且存在常量 ${\tau }_1,{\tau }_2,{\tau }_3$ 使得 $\left|a_{ii}^{\left(y\right)}\right|\left(1-x_{1i,k}^{\left(y\right)}\right)>{\tau }_1$， $\left|a_{ii}^{\left(y\right)}\right|\left(1-x_{2i}^{\left(y\right)}\right)>{\tau }_2$， $\left|a_{ii}^{\left(y\right)}\right|\left(1-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-{\epsilon }^{\left(y\right)}\right)>{\tau }_3$。取 ${\tau }_0=\min \left\{{\tau }_1,{\tau }_2,{\tau }_3\right\}$，由算法2.1可得

$\left|a_{ii}^{\left(y+1\right)}\right|=\left|a_{ii}^{\left(y\right)}\right|x_{1i,k}^{\left(y\right)}<\left|a_{ii}^{\left(y\right)}\right|-{\tau }_0,$

$\left|a_{ii}^{\left(y+1\right)}\right|=\left|a_{ii}^{\left(y\right)}\right|x_{2i}^{\left(y\right)}<\left|a_{ii}^{\left(y\right)}\right|-{\tau }_0,$

$\left|a_{ii}^{\left(y+1\right)}\right|=\left|a_{ii}^{\left(y\right)}\right|\left(\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+{\epsilon }^{\left(y\right)}\right)<\left|a_{ii}^{\left(y\right)}\right|-{\tau }_0.$

因此递推可得

$\left|a_{ii}^{\left(0\right)}\right|=\left|a_{ii}^{\left(1\right)}\right|>\left|a_{ii}^{\left(2\right)}\right|+{\tau }_0>\cdots >\left|a_{ii}^{\left(y\right)}\right|+\left(y-1\right){\tau }_0,$

当 $y\to \infty$ 时，有 $a_{ii}\to \infty$，产生矛盾。故 $\underset{y\to \infty }{\lim }{N}_3\left(A^{\left(y\right)}\right)=N_3\left(B\right)=\varphi$，由引理2知B不是非奇异H-矩阵。

又已知矩阵A是非奇异H-矩阵，可得 $A=B{X}^{-1}\in D^{*}$，其中 $X^{-1}$ 为正对角矩阵，所以B是非奇异H-矩阵，与上述矛盾。所以算法2.1在有限次迭代后停止，并生成一个严格对角占优矩阵。证毕。

注1与文献 [1] 和文献 [2] 相比，算法2.1不仅进一步细分非占优行指标集，而且构造了更小的迭代因子序列，使得算法的判定范围更广，运行的迭代次数也减少。且乘积形式的不等式放缩条件本就比文献 [1] 中对角元与行和的直接对比形式的条件要弱些，故本文的算法改进了文献 [1] [2] 中的算法主要结果。后面的数值算例也证实了这一点。

注2 由 $x_{1i,k}^{\left(y\right)}$ 的定义、 $x_{2i}^{\left(y\right)}$ 的定义及 $\frac{P_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}<1$ 可知

$\begin{array}{c}{\epsilon }^{\left(y\right)}=\frac{1}{q}\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\min }\left\{\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right\}\\ =\frac{1}{q}\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\min }\frac{{\displaystyle \underset{t\in N_{1k}\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\left(1-x_{1t,k}^{\left(y\right)}\right)+{\displaystyle \underset{t\in N_2\left(A^{\left(y\right)}\right)}{\sum }\left|a_{it}^{\left(y\right)}\right|}\left(1-x_{2t}^{\left(y\right)}\right)+{\displaystyle \underset{t\in N_3\left(A^{\left(y\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(y\right)}\right|}\left(1-\frac{P_{l+1,t}^{\left(y\right)}}{\left|a_{tt}^{\left(y\right)}\right|}\right)}{\left|a_{ii}^{\left(y\right)}\right|}\\ >0,\end{array}$

且有

$\begin{array}{l}\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+{\epsilon }^{(y)}=\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+\frac{1}{q}\underset{i\in N_3\left(A^{\left(y\right)}\right)}{\min }\left\{\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right\}\le \frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+\frac{1}{q}\left(\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right)\\ <\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}+\left(\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}\right)=\frac{{\Lambda }_i^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}<1,\end{array}$

所以 ${\epsilon }^{\left(y\right)}$ 满足 $0<{\epsilon }^{\left(y\right)}<1$ 且 $1-\frac{W_{l+1,i}^{\left(y\right)}}{\left|a_{ii}^{\left(y\right)}\right|}-{\epsilon }^{\left(y\right)}>0$。故本文中 ${\epsilon }^{\left(y\right)}$ 的选取是合理的。

3. 数值算例

例1 考虑矩阵A

$A_1=\left(\begin{array}{cccccc}25& 7.5& 6& 0& 3& 1.8\\ 9.5& 30& 5.8& 4& 0& 0.6\\ 0& 0& 9& 9& 0& 1.8\\ 0& 2& 3& 10& 3& 8\\ 6.3& 7.5& 0& 8& 120& 5\\ 0& 0& 6& 0& 30& 36\end{array}\right).$

$A_2=\left(\begin{array}{ccccccc}1.5& 1.5& 0& 0& 0.5& 0.6& 0.5\\ 1& 1.9& 0& 0& 0.5& 0.3& 1\\ 0.3& 0.2& 4& 0.2& 0.3& 2& 1\\ 0.2& 0.5& 0.1& 3& 0.1& 0.5& 1.6\\ 0.7& 0.1& 0& 0& 4& 0.5& 0.7\\ 1& 0& 0.3& 0& 0.8& 5& 0.7\\ 1& 0& 0.4& 0.4& 1& 1& 30\end{array}\right).$

针对上面两个矩阵 $A_1$ 和 $A_2$，对比一些已有的判定算法结果，并利用Matlab软件编程计算，得到如下表1的具体判定结果。

Table 1. Numerical results of algorithm

表1. 算法数值计算结果

取 $q=10$， ${\sigma }_2=0.001$，由上表可知，相对于算法1.1、文献 [2] 和文献 [4] 中的算法结果来说，本文算法2.1的迭代次数更少些。且与前面三个算法相比，算法2.1可通过改变m值，实现一步变多步计算，故本文算法2.1改进了上述文献结果。

例2 考虑矩阵B

$B={\left(\begin{array}{ccccc}I& O& O& 1.11I& O\\ 0.015E& I& O& 0.025E& 0.005E\\ 0.01E& 0.005E& I& 0.02E& 0.005E\\ 0.01E& 0.015E& 0.01E& I& 0.01E\\ I& O& O& 0.015E& 0.99I\end{array}\right)}_{100\times 100},$

$I={\left(\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)}_{20\times 20},E={\left(\begin{array}{cccc}1& 1& \cdots & 1\\ 1& 1& \cdots & 1\\ ⋮& ⋮& \ddots & ⋮\\ 1& 1& \cdots & 1\end{array}\right)}_{20\times 20},O={\left(\begin{array}{cccc}0& 0& \cdots & 0\\ 0& 0& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 0\end{array}\right)}_{20\times 20}.$

针对上面矩阵B，利用Matlab软件编程计算，得到如下表2的具体判定结果。

Table 2. Number of iterations for different algorithms

表2. 不同算法的迭代次数情况

取 $q=5$， ${\sigma }_2=0.0002$，由表2可知，文献 [2] 在规定迭代次数最大值为1000的情况下，其仍无法判定矩阵B是否为非奇异H-矩阵。另一方面，取 $m=1$ 时，算法1.1与算法2.1均迭代5次，但继续取 $m=2$ 时，本文算法2.1的迭代次数相对减少。故本文算法在一定程度上改进了上述文献结果。

4. 结论

通过数值实验结果对比分析，本文的算法2.1比文献 [1]、文献 [2] 以及文献 [4] 的算法判定所需的迭代次数较少，判定范围更广，故本文给出的算法在一定程度上改进了文献 [1]、文献 [2] 以及文献 [4] 算法的主要结果，且判定效率更高。

致谢

感谢庹清老师对本项目的悉心指导和帮助。

基金项目

国家自然科学基金项目(11461027)；湖南省教育厅科研基金(21C0365)。

NOTES

^*通讯作者。