一类非奇异H-矩阵快速迭代判定新算法

A New Algorithm of Fast Iterative Criterion for Non-Singular H-Matrices

摘要: 通过对迭代矩阵因子和收敛条件的改进，得到一组非奇异H-矩阵新的快速迭代判定算法，并从理论上说明了算法的收敛性。最后，利用Matlab数值仿真实验结果表明所得算法迭代收敛速度更快，稳定性更好。

Abstract: By improving the iterative matrix factors and convergence conditions, a new fast iterative criterion algorithm for non-singular H-matrices is obtained, and the convergence of the algorithm is theoretically explained. Finally, the results of Matlab numerical simulation experiments show that the proposed algorithm has faster convergence and better stability.

1. 引言

H-矩阵在计算数学，数学物理，控制论，统计学，弹性力学等众多领域中有着广泛应用。由于H-矩阵广泛的应用范围，其判定方法一直是人们关注的热点问题。因此，判别一个矩阵是否为H-矩阵及讨论其性质如何具有重大意义。由于近年来计算机的发展，国内外许多学者提出不少关于H-矩阵的迭代判定算法 [1] - [6] 。文献 [7] 以细化的思想通过对方阵行下标集及矩阵行和不同的递进式划分，得到了非奇异H-矩阵的若干判定定理和相应的迭代判定算法，增大对H-矩阵判定的范围，改进了文献 [8] [9] 中的结果。本文主要基于文 [7] 思路，针对文献 [10] 的判定结果做出改进得到一类迭代判定新算法，同时改进了文献 [10] 的判定定理范围和文献 [7] 的部分算法结果，最后用数值仿真结果说明了新算法判定的稳定性和高效性。

文 [7] 中给出了如下一个迭代判别算法。

算法A

输入：矩阵 $A=\left(a_{ij}\right)\in M_n(C)$

输出： $D=D^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m\right)}$ ，如果A是H-矩阵。

步骤1. 如果 $N_2\left(A\right)=\varphi$ 或存在 $i\in N$ 使 $a_{ii}=0$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤2. 设 $m=1$ ， $A^{\left(0\right)}=A$ ， $D^{\left(0\right)}=I$ ，

步骤3. 计算 $A^{\left(m\right)}=A^{\left(m-1\right)}{D}^{\left(m-1\right)}=\left(a_{ij}^{\left(m\right)}\right)$ ，

步骤4. 如果 $N_1\left(A^{\left(m\right)}\right)=\varphi$ ，则“A是非奇异H-矩阵”，停止；否则，

步骤5. 如果 $N_2\left(A^{\left(m\right)}\right)=\varphi$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤6. 计算 ${\Lambda }_i\left(A^{\left(m\right)}\right)={\displaystyle \underset{t\in N,t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|},\forall i\in N$ ，

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

${\Lambda }_i^{\left(1\right)}\left(A^{\left(m\right)}\right)={\displaystyle \underset{t\in N_1\left(A^{\left(m\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|}+{\displaystyle \underset{t\in N_2\left(A^{\left(m\right)}\right)}{\sum }\left|a_{it}^{\left(m\right)}\right|}\frac{{\Lambda }_t\left(A^{\left(m\right)}\right)}{\left|a_{tt}^{\left(m\right)}\right|},\forall i\in N_1\left(A^{\left(m\right)}\right)$ ,

$N_1^{\left(1\right)}\left(A^{\left(m\right)}\right)=\left\{i\in N:0<\left|a_{ii}^{\left(m\right)}\right|\le {\Lambda }_i^{\left(1\right)}\left(A^{\left(m\right)}\right)\right\}$ , $N_2^{\left(1\right)}\left(A^{\left(m\right)}\right)=\left\{i\in N:{\Lambda }_i\left(A^{\left(m\right)}\right)\ge \left|a_{ii}^{\left(m\right)}\right|>{\Lambda }_i^{\left(1\right)}\left(A^{\left(m\right)}\right)\right\}$ , ${\alpha }_i^{\left(m\right)}={\displaystyle \underset{t\in N_1\left(A^{\left(m-1\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|}$ , ${\beta }_i^{\left(m\right)}={\displaystyle \underset{t\in N_2\left(A^{\left(m-1\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|},i\in N$

步骤7. 令 $r=\underset{i\in N_2\left(A^{\left(m-1\right)}\right)}{\max }\frac{{\alpha }_i^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|-{\beta }_i^{\left(m\right)}}$ 。

步骤8. 如果 $\left|a_{ii}^{\left(m\right)}\right|>{\alpha }_i^{\left(m\right)}+r{\beta }_i^{\left(m\right)},\forall i\in N_1\left(A^{\left(m-1\right)}\right)$ ，则“A是H-矩阵”，停止；否则，

步骤9. 设 $d=\left(d_i\right)$ ，其中

$d_i=\{\begin{array}{l}1i\in N_1^{\left(1\right)}\left(A^{\left(m-1\right)}\right)\\ \frac{{\Lambda }_i^{\left(1\right)}\left(A^{\left(m\right)}\right)}{\left|a_{ii}^{\left(m\right)}\right|}i\in N_2^{\left(1\right)}\left(A^{\left(m-1\right)}\right)\\ \frac{{\Lambda }_i\left(A^{\left(m\right)}\right)}{\left|a_{ii}^{\left(m\right)}\right|}i\in N_2\left(A^{\left(m-1\right)}\right)\end{array}$

步骤10. $D^{\left(m\right)}=diag\left(d\right),m=m+1$ ，返回步骤3。

2. 主要结果

主要基于文 [7] 的思想，本文通过对文 [10] 中H-矩阵判定结果的改进得到新的无参数迭代判别算法B，又适当选取参数得到更高效的带参数迭代判定算法C。

通过对算法中迭代阵因子及收敛条件的改进，下面给出较算法A判定范围更广的一个迭代算法。

设 $M_n\left(C\right)\left(M_n\left(R\right)\right)$ 为n阶复(实)矩阵的集合。 $A=\left(a_{ij}\right)\in M_n\left(C\right)$ ，记

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

$N_1=\left\{i\in N|0<\left|a_{ii}\right|={\Lambda }_i\left(A\right)\right\}$ , $N_2=\left\{i\in N|0<\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\oplus N_2\oplus N_3$

$r=\underset{i\in N_3}{\max }\left\{\frac{{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_1}{\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_1=\underset{i\in N_3}{\max }\left\{\frac{{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}}{\left|a_{ii}\right|-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|\frac{P_{t,r}\left(A\right)}{\left|a_{tt}\right|}}}\right\}$ ,

$P_{i,r}\left(A\right)={\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}+r{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|}\left(i\in N_3\right)$ ,

$P_{i,r_1}\left(A\right)={\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|}+r_1{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|\frac{P_{t,r}}{\left|a_{tt}\right|}}\left(i\in N_3\right)$ ,

$w_i=\frac{{\Lambda }_i\left(A\right)}{{\Lambda }_i\left(A\right)+\left|a_{ii}\right|}\left(i\in N_2\right)$ , $\delta =\max \left\{r_1,w_i\right\}$ , $h=\underset{i\in N_3}{\max }\left\{\frac{\delta \left({\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}\right)+{\displaystyle \underset{t\in N_2}{\sum }\left|a_{it}\right|w_t}}{P_{i,r_1}\left(A\right)-{\displaystyle \underset{t\in N_3,t\ne i}{\sum }\left|a_{it}\right|\frac{P_{t,r_1}\left(A\right)}{\left|a_{tt}\right|}}}\right\}$ .

$S_i\left(A\right)=\left|a_{it}\right|w_i-\delta {\displaystyle \underset{t\in N_1}{\sum }\left|a_{it}\right|}-{\displaystyle \underset{t\in N_2,t\ne i}{\sum }\left|a_{it}\right|w_t}-h{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|\frac{P_{t,r_1}(A)}{\left|a_{tt}\right|}}\left(i\in N_2\right)$ , $R_i=\frac{1}{{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}\right|}}{S}_i$ .

2.1. 无参数算法

算法B

输入：矩阵 $A=\left(a_{ij}\right)\in M_n(C)$

输出： $D=D^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m\right)}$ ，如果A是H-矩阵。

步骤1. 如果 $N_3\left(A\right)=\varphi$ 或存在 $i\in N$ 使 $a_{ii}=0$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤2. 设 $m=1$ ， $A^{\left(0\right)}=A$ ， $D^{\left(0\right)}=I$ ，

步骤3. 计算 $A^{\left(m\right)}=A^{\left(m-1\right)}{D}^{\left(m-1\right)}=\left(a_{ij}^{\left(m\right)}\right)$ ，

步骤4. 如果 $N_2\left(A^{\left(m\right)}\right)=\varphi$ ，则“A是非奇异H-矩阵”，停止；否则，

步骤5. 如果 $N_3\left(A^{\left(m\right)}\right)=\varphi$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤6. 计算 ${\delta }^{\left(m\right)},w_i^{\left(m\right)},h^{\left(m\right)},P_{i,r_1}^{\left(m\right)}\left(A^{\left(m\right)}\right)$ ，

步骤7. 如果

$\left|a_{ii}^{\left(m\right)}\right|w_i^{\left(m\right)}>{\delta }^{\left(m\right)}{\displaystyle \underset{t\in N_1\left(A^{\left(m\right)}\right)}{\sum }\left|a_{it}^{\left(m\right)}\right|}+{\displaystyle \underset{t\in N_2\left(A^{\left(m\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|w_t^{\left(m\right)}}+h^{\left(m\right)}{\displaystyle \underset{t\in N_3\left(A^{\left(m\right)}\right)}{\sum }\left|a_{it}^{\left(m\right)}\right|}\frac{P_{t,r_1}^{\left(m\right)}}{\left|a_{tt}^{\left(m\right)}\right|},\forall i\in N_2\left(A^{\left(m\right)}\right)$ ,

且 $N_1\left(A^{\left(m\right)}\right)=\varphi$ 或 $i\in N_1\left(A^{\left(m\right)}\right)\ne \varphi$ 时，存在 $t\in N_2\left(A^{\left(m\right)}\right)\cup N_3\left(A^{\left(m\right)}\right)$ ，使得 $a_{it}^{\left(m\right)}\ne 0$ ，则“A是非奇异H-矩阵”，停止；否则，

步骤8. 设 $d^{\left(m\right)}=\left(d_i^{\left(m\right)}\right)$ ，其中

$d_i^{\left(m\right)}=\{\begin{array}{l}{\delta }^{\left(m\right)}i\in N_1\left(A^{\left(m\right)}\right)\\ w_i^{\left(m\right)}i\in N_2\left(A^{\left(m\right)}\right)\\ \frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}i\in N_3(A^{(m))}\end{array}$

步骤9. $D^{\left(m\right)}=diag\left(d^{\left(m\right)}\right),m=m+1$ ，返回步骤3。

注1：由上述符号可知， ${\delta }^{\left(m\right)}<1$ ， $w_i^{\left(m\right)}<1$ 。则 $\forall i\in N_3\left(A^{\left(m\right)}\right)$ ， $h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}<1$ ，有

$\frac{{\Lambda }_i\left(A^{\left(m\right)}\right)}{\left|a_{ii}^{\left(m\right)}\right|}<\frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}$ .

所以，算法B具有比算法A更少的迭代次数。

在算法B的基础上，我们选取了适当的参数得到了下述算法C，它在一定程度上扩大了算法B的判定范围，修正了它判定结果的准确率，减少了运行迭代次数及时间。

2.2. 带参数算法

算法C

输入：矩阵 $A=\left(a_{ij}\right)\in M_n(C)$

输出： $D=D^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m\right)}$ ，如果A是H-矩阵。

步骤1. 如果 $N_3\left(A\right)=\varphi$ 或存在 $i\in N$ 使 $a_{ii}=0$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤2. 设 $m=1$ ， $A^{\left(0\right)}=A$ ， $D^{\left(0\right)}=I$ ，

步骤3. 计算 $A^{\left(m\right)}=A^{\left(m-1\right)}{D}^{\left(m-1\right)}=\left(a_{ij}^{\left(m\right)}\right)$ ，

步骤4. 如果 $N_2\left(A^{\left(m\right)}\right)=\varphi$ ，则“A是非奇异H-矩阵”，停止；否则，

步骤5. 如果 $N_3\left(A^{\left(m\right)}\right)=\varphi$ ，则“A不是非奇异H-矩阵”，停止；否则，

步骤6. 计算 ${\delta }^{\left(m\right)},w_i^{\left(m\right)},h^{\left(m\right)},P_{i,r_1}^{\left(m\right)}\left(A^{\left(m\right)}\right)$ ，

步骤7. 如果

$\left|a_{ii}^{\left(m\right)}\right|w_i^{\left(m\right)}>{\delta }^{\left(m\right)}{\displaystyle \underset{t\in N_1\left(A^{\left(m\right)}\right)}{\sum }\left|a_{it}^{\left(m\right)}\right|}+{\displaystyle \underset{t\in N_2\left(A^{\left(m\right)}\right),t\ne i}{\sum }\left|a_{it}^{\left(m\right)}\right|w_t^{\left(m\right)}}+h^{\left(m\right)}{\displaystyle \underset{t\in N_3\left(A^{\left(m\right)}\right)}{\sum }\left|a_{it}^{\left(m\right)}\right|\frac{P_{t,r_1}^{\left(m\right)}}{\left|a_{tt}^{\left(m\right)}\right|}},\forall i\in N_2\left(A^{\left(m\right)}\right)$ ,

且 $N_1\left(A^{\left(m\right)}\right)=\varphi$ 或 $i\in N_1\left(A^{\left(m\right)}\right)\ne \varphi$ 时，存在 $t\in N_2\left(A^{\left(m\right)}\right)\cup N_3\left(A^{\left(m\right)}\right)$ ，使得 $a_{it}^{\left(m\right)}\ne 0$ ，则“A是非奇H-矩阵”，停止；否则，

步骤8. 设 $d^{\left(m\right)}=\left(d_i^{\left(m\right)}\right)$ ，其中

$d_i^{\left(m\right)}=\{\begin{array}{l}{\delta }^{\left(m\right)}i\in N_1\left(A^{\left(m\right)}\right)\\ w_i^{\left(m\right)}i\in N_2\left(A^{\left(m\right)}\right)\\ \frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}+{\epsilon }^{\left(m\right)}i\in N_3(A^{(m))}\end{array}$

${\epsilon }^{\left(m\right)}=\{\begin{array}{l}\frac{1}{q}\min S_i^{\left(m\right)}\exists i\in N_2\left(A^{\left(m\right)}\right),{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}^{\left(m\right)}\right|}=0\\ \min R_i^{\left(m\right)}\forall i\in N_2\left(A^{\left(m\right)}\right),{\displaystyle \underset{t\in N_3}{\sum }\left|a_{it}^{\left(m\right)}\right|}\ne 0\end{array}$

其中 $q>1$ 。

步骤9. $D^{\left(m\right)}=diag\left(d^{\left(m\right)}\right),m=m+1$ ，返回步骤3。

3. 算法收敛性分析

下面通过定理1给出算法B作为H-矩阵迭代判定的收敛性分析。

定理1. 矩阵 $A=\left(a_{ij}\right)\in C^{n\times n}$ 是H-矩阵当且仅当算法B经有限次迭代生成一个严格对角占优矩阵而停止。

证明 假设矩阵A是非负矩阵。用 $A^{\left(m-1\right)}$ 和 $A^{\left(m\right)}$ 表示算法A的迭代过程中前一次和当前次迭代矩阵，其中m是某一迭代次数。

充分性：假设算法B经过m次迭代停止生成一个严格对角占优矩阵，则得到一个严格对角占优矩阵 $A^{\left(m\right)}=A^{\left(0\right)}{D}^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m-1\right)}=AD$ ，其中 $D=D^{\left(0\right)}{D}^{\left(1\right)}\cdots D^{\left(m-1\right)}$ 是正对角矩阵。显然此时A是H-矩阵。

必要性：令A是H-矩阵。利用反证法，假设算法B经过有限次迭代不停止。由算法B可知 $A^{\left(m\right)}=A^{\left(0\right)}{D}^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m-1\right)}=AD$ ，其中 $D=D^{\left(0\right)}{D}^{\left(1\right)}\cdots D^{\left(m-1\right)}$ 是对角元小于1的正对角矩阵，则

$A=A^{\left(0\right)}=A^{\left(1\right)}\ge \cdots \ge A^{\left(m\right)}\ge \cdots \ge 0$ ,

即无穷矩阵序列 $\left\{A^{\left(m\right)}\right\}$ 单调递减且有界，因此有

$\underset{m\to \infty }{\lim }{A}^{\left(m\right)}=B\ge 0$ ,

其中 $B=AF$ ， $F=D^{\left(1\right)}{D}^{\left(2\right)}\cdots D^{\left(m\right)}\cdots$ 是正对角矩阵。

接下来，要证明

$\underset{m\to \infty }{\lim }{N}_3\left(A^{\left(m\right)}\right)=N_3\left(B\right)=\varphi$ .

再次利用反证法，假设 $\underset{m\to \infty }{\lim }{N}_3\left(A^{\left(m\right)}\right)\ne \varphi$ ，则 $1-{\delta }^{\left(m\right)}>0$ ， $1-w_i^{\left(m\right)}>0$ ， $1-\frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}>0$ 且存在某一 $i\in N_3\left(A^{\left(m\right)}\right)$ 及常量 ${\epsilon }_1,{\epsilon }_2,{\epsilon }_3$ 使得

$\left|a_{ii}^{\left(m\right)}\right|\left(1-{\delta }^{\left(m\right)}\right)>{\epsilon }_1$ , $\left|a_{ii}^{\left(m\right)}\right|\left(1-w_i^{\left(m\right)}\right)>{\epsilon }_2$ , $\left|a_{ii}^{\left(m\right)}\right|\left(1-\frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}\right)>{\epsilon }_3$ , $m=1,2,3,\cdots$

令 ${\epsilon }_0=\min \left\{{\epsilon }_1,{\epsilon }_2,{\epsilon }_3\right\}$ 。

由算法B，有

$0<a_{ii}^{\left(m+1\right)}=a_{ii}^{\left(m\right)}{\delta }^{\left(m\right)}<a_{ii}^{\left(m\right)}-{\epsilon }_1<a_{ii}^{\left(m\right)}-{\epsilon }_0$ ,

$0<a_{ii}^{\left(m+1\right)}=a_{ii}^{\left(m\right)}{w}_i^{\left(m\right)}<a_{ii}^{\left(m\right)}-{\epsilon }_2<a_{ii}^{\left(m\right)}-{\epsilon }_0$ ,

$0<a_{ii}^{\left(m+1\right)}=a_{ii}^{\left(m\right)}\frac{h^{\left(m\right)}{P}_{i,r_1}^{\left(m\right)}}{\left|a_{ii}^{\left(m\right)}\right|}<a_{ii}^{\left(m\right)}-{\epsilon }_3<a_{ii}^{\left(m\right)}-{\epsilon }_0$ .

因此

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

令 $m\to \infty$ ，则 $a_{ii}\to \infty$ ，产生矛盾。故

$\underset{m\to \infty }{\lim }{N}_3\left(A^{\left(m\right)}\right)=N_3\left(B\right)=\varphi$ .

这说明矩阵B不是H-矩阵。另一方面，由于A是不可约H-矩阵，则存在一个正对角矩阵E使得 $AE=B\left(F^{-1}E\right)$ 是严格对角占优的。易知， $F^{-1}E$ 仍是正对角矩阵，从而可得矩阵B是H-矩阵，产生矛盾。故算法B经有限次迭代停止。

算法A是利用对矩阵下标集的迭代细分来划分其占优与非占优指标集，一定程度上增大了它判定的范围，但迭代过程相对繁琐导致运行迭代次数与时间相对增加。算法B是构造新的迭代因子得到的新算法，由更小的对角阵迭代因子将使得算法运行的迭代次数和时间相比算法A需要的更少，且乘积因子对不等式的放缩使得判定范围比前者更广。在算法B基础上添加参数得到算法C，相比前两个算法运行的迭代次数和时间更小、判定范围更广，且在一定程度上修正了前两个算法判定结果的正确率，后面的数值仿真实验结果也说明了这一点。

4. 数值仿真

本文通过数值仿真实验测试比较了3个算法程序的性能，测试中随机选取近年来H-矩阵迭代算法相关论文的18个真实样本。综合实例的适用度，在带参数的算法C中q的取值为q = 4。实验机器选用联想台式机，具体配置：(Inter(R)Core(TM)i5-4590 CPU@3.30GHz，双核处理器8.00G内存64位windows操作系统)，用Matlab R2013a语言编程实现。

根据算法A、B、C对不同样本运行产生的迭代次数，我们得到了数值仿真结果如图1所示(横坐标为样本编号，纵坐标为迭代次数)。由图1可以看出三个算法中算法C产生的迭代次数相对是最小的。针对算法有无参数对算法B、C产生的迭代次数作出对比可以看出，算法C相较算法B产生的迭代次数相对较少。综合图像来看，算法A的迭代次数明显高于后两个算法，且对某些样本实例的判定次数偏高，出错率也是三者中最高。算法B、C产生的次数相对较少且稳定在低次数段，两者的出错率相比算法C更低。

Figure 1. Curve: system result of iterative Algorithm

图1. 算法迭代结果曲线

Table 1. Resulting data of Algorithm runtime

表1. 算法运行时间结果数据

根据以上3个算法对不同实例产生的运行时间，得到运行时间表1。对算法产生的运行时间，运用SPSS软件对其做单因素方差分析。由其中的一项输出结果表2，单因素方差分析表，可以看出方差检验统计量F = 31.120，相应的sig值等于0.000，小于显著性0.05，因此我们认为不同算法的运行时间有显著性差异。再根据表1的结果可以说明算法A运行的时间与其他两个算法有较大差异，算法A花费的时间最多。

Table 2. One-way analysis of variance (ANOVA)

表2. 单因素方差分析表

为了检验不同的算法对不同实例结果判定的正确性，得到相应算法的正确率表3。

Table 3. Table of Algorithmic correct rate

表3. 算法正确率表

考虑到算法运行产生的迭代次数、判定结果的正确率和时间对算法的重要性不同，运用层次分析法做出了比较矩阵，并在matlab上实现依次得到它们的权重系数为0.5390、0.2973、0.1638。根据上述结果，对本文中3个算法做出算法综合评估表4。

Table 4. Data of Algorithmic comprehensive performance

表4. 算法综合性能数据

注2：本文在实例判定结果上，将运行判定结果出错或者无限循环结果在迭代次数中记迭代次数为0次，在正确率判定中判定为结果错误。在运行迭代次数及运行时间的数据处理中，将出错结果的迭代次数和时间分别用其它实例的平均迭代次数和时间替代，以减少对其它数据的影响。

5. 结论

从上述数值仿真分析结果来看，算法B的综合性能值是最低的，即算法B从迭代产生的次数、时间和正确率综合来看相较其他算法是最好的。从算法的判定式语句来看(即步骤7或者步骤8)，算法C对H-矩阵的判定范围较算法B更广，且这两个算法判定H-矩阵的范围亦优于算法A的判定范围。其次，综合性能值较低的带参数算法C，它对实例判定结果的准确度最高，在对准确度的需求最高的情况下，它无疑是最好的选择。总体来看，得到的两个新算法不论在迭代产生的次数、时间还是正确率方面，相较文 [7] 的算法A都是有显著优势的。

致谢

感谢王海波等同学在算法数值仿真实验中所做的工作。

基金项目

国家自然科学基金(11461027)和湖南省教育厅科研基金(16A173)。

NOTES

^*通讯作者。