一类非奇异H-矩阵的细分迭代判别算法 Subdivision Iterative Discriminant Algorithm for a Class of Nonsingular H-Matrix

doi:10.12677/AAM.2022.118531

Advances in Applied Mathematics
Vol. 11 No. 08 ( 2022 ), Article ID: 54355 , 12 pages
10.12677/AAM.2022.118531

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

董杰，庹清^*，谢智慧

●How to Cite this Article

吉首大学数学与统计学院，湖南吉首

收稿日期：2022年7月1日；录用日期：2022年7月27日；发布日期：2022年8月4日

摘要

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

关键词

非奇异H-矩阵，细分迭代判别算法，收敛性

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

Jie Dong, Qing Tuo^*, Zhihui Xie

College of Mathematics and Statistics, Jishou University, Jishou Hunan

Received: Jul. 1^st, 2022; accepted: Jul. 27^th, 2022; published: Aug. 4^th, 2022

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 diagonal matrix factor by using the subdivision interval and iterative coefficient, and obtain a new condition 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.

Keywords:Nonsingular H-Matrix, Subdivision Iterative Discriminant Algorithm, Convergence

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

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

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

$Λ_{i} = Λ_{i} (A) = \sum_{j \neq i} | a_{i j} |, i, j \in N,$

${\tilde{N}}_{1} = {i \in N : 0 < | a_{i i} | \leq Λ_{i} (A)}, {\tilde{N}}_{2} = {i \in N : | a_{i i} | > Λ_{i} (A)},$

$α_{i} = α_{i} (A) = \sum_{t \in {\tilde{N}}_{1}, t \neq i} | a_{i t} |, β_{i} = β_{i} (A) = \sum_{t \in {\tilde{N}}_{2}, t \neq i} | a_{i t} |, i \in N .$

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

引理1 [2] 设 $A = (a_{i j}) \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} = ϕ$ 及

$(| a_{i i} | - α_{i} (A)) (| a_{j j} | - β_{j} (A)) > β_{i} (A) α_{j} (A), i \in {\tilde{N}}_{1}, j \in {\tilde{N}}_{2},$

则A为非奇异H-矩阵。

在本文中假设 $| a_{i i} | \neq 0, Λ_{i} (A) \neq 0, i \in N$ ，规定 $\sum_{t \in ϕ} • = 0$ ，并记

$N_{1} = {i \in N : 0 < | a_{i i} | < Λ_{i} (A)}, N_{2} = {i \in N : | a_{i i} | = Λ_{i} (A)}, N_{3} = {i \in N : | a_{i i} | > Λ_{i} (A)},$

则 $N = N_{1} + N_{2} + N_{3}$ ，由 $N_{1} = N_{1}^{(1)} \cup N_{1}^{(2)} \cup \dots \cup N_{1}^{(m)}$ ，其中

$N_{1}^{(1)} = {i \in N : 0 < | a_{i i} | < \frac{1}{m} Λ_{i} (A)},$

$N_{1 k} = {i \in N : \frac{k - 1}{m} Λ_{i} (A) \leq | a_{i i} | < \frac{k}{m} Λ_{i} (A)}, k = 2, 3, \dots, m,$

其中， $N_{1}^{(k)}$ 可能为空集。

引理2 [5] 设 $A = (a_{i j}) \in C^{n \times n}$ ，如果 $A \in D^{*}$ ，则 $N_{3} \neq ϕ$ 且 $| a_{i i} | \neq 0 (i \in N)$ 。

引理3 [5] 设 $A = (a_{i j}) \in C^{n \times n}$ ，如果 $A \in D^{*}$ ，则 $| a_{i i} | > 0 (i \in N)$ 且 $N_{1} = ϕ$ 。

若 $N_{1} \cup N_{2}$ 为空集，则A为非奇异H-矩阵。若 $N_{3}$ 为空集，则A不是非奇异H-矩阵。因此，本文总假设 $N_{1} \cup N_{2}$ 不为空集， $N_{3}$ 也不为空集。

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

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

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

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

3) 计算 $A^{(\tilde{y})} = (a_{i t}^{(\tilde{y})}) = A^{(\tilde{y} - 1)} X_{1}^{(\tilde{y} - 1)}$ ；

4) 如果 ${\tilde{N}}_{2} (A^{(\tilde{y})}) = ϕ$ ，则 $A \notin D^{*}$ ，停止；如果 ${\tilde{N}}_{2} (A^{(\tilde{y})}) = N$ ，则 $A \in D^{*}$ ，停止；否则

5) 计算

$λ_{0}^{(\tilde{y})} = 1, ψ_{i}^{(\tilde{y})} = \frac{\sum_{t \in {\tilde{N}}_{1} (A^{(\tilde{y})})} | a_{i t}^{(\tilde{y})} |}{| a_{i i}^{(\tilde{y})} | - \sum_{t \in {\tilde{N}}_{2} (A^{(\tilde{y})}), t \neq i} | a_{i t}^{(\tilde{y})} |}, λ_{1}^{(\tilde{y})} = \max_{i \in {\tilde{N}}_{2} (A^{(\tilde{y})})} \frac{\sum_{t \in {\tilde{N}}_{1} (A^{(\tilde{y})})} | a_{i t}^{(\tilde{y})} |}{| a_{i i}^{(\tilde{y})} | - \sum_{t \in {\tilde{N}}_{2} (A^{(\tilde{y})}), t \neq i} | a_{i t}^{(\tilde{y})} |},$

$λ_{l + 1}^{(\tilde{y})} = \max_{i \in {\tilde{N}}_{2} (A^{(\tilde{y})})} δ_{l + 1}^{(\tilde{y})} (l \in Z^{+}),$

$δ_{l + 1, i}^{(\tilde{y})} = \frac{\sum_{t \in {\tilde{N}}_{1} (A^{(\tilde{y})})} | a_{i t}^{(\tilde{y})} | + λ_{l}^{(\tilde{y})} \sum_{t \in {\tilde{N}}_{2} (A^{(\tilde{y})}), t \neq i} | a_{i t}^{(\tilde{y})} |}{| a_{i i}^{(\tilde{y})} |} (i \in {\tilde{N}}_{2} (A^{(\tilde{y})}), l \in Z);$

6) 取定非负整数l和实数 $s \geq 1$ 。令 $X_{1}^{(\tilde{y})} = d i a g (x_{1}^{(\tilde{y})}, x_{2}^{(\tilde{y})}, \dots, x_{n}^{(\tilde{y})})$ ，其中

$x_{i}^{(\tilde{y})} = {\begin{cases} 1 (i \in {\tilde{N}}_{1} (A^{(\tilde{y})})), \\ δ_{l + 1, i}^{(\tilde{y})} + ε_{0}^{(\tilde{y})} (i \in {\tilde{N}}_{2} (A^{(\tilde{y})})), \end{cases}$

这里当 $ψ_{i}^{(\tilde{y})} > δ_{l + 1, i}^{(\tilde{y})} (i \in {\tilde{N}}_{2} (A^{(\tilde{y})}))$ 时 $ε_{0}^{(\tilde{y})} = \frac{1}{s} \min_{i \in {\tilde{N}}_{2} (A^{(\tilde{y})})} (ψ_{i}^{(\tilde{y})} - δ_{l + 1, i}^{(\tilde{y})})$ ，其余情形 $ε_{0}^{(\tilde{y})} = σ_{1}$ ， $σ_{1}$ 是充分小的正实数；

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

2. 主要结果

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

$x_{1 i, k} = \frac{| a_{i i} | - \frac{k - 1}{m + 1} Λ_{i} (A)}{Λ_{i} (A)} (i \in N_{1 k}, k = 1, 2, \dots, m),$

$x_{2 i} = \frac{\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}, t \neq i} | a_{i t} | + \sum_{t \in N_{3}} | a_{i t} |}{| a_{i i} |} (i \in N_{2}),$

$r_{0} = 1, r_{1} = \max_{i \in N_{3}} {\frac{\sum_{t \in N_{1}} | a_{i t} | + \sum_{t \in N_{2}} | a_{i t} |}{| a_{i i} | - \sum_{t \in N_{3}, t \neq i} | a_{i t} |}},$

$r_{l + 1} = \max_{i \in N_{3}} {\frac{\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + r_{l} \sum_{t \in N_{3}, t \neq i} | a_{i t} |}{| a_{i i} |}} (l \in Z^{+}),$

$P_{l + 1, i} (A) = \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + r_{l} \sum_{t \in N_{3}, t \neq i} | a_{i t} | (i \in N_{3}, l \in Z),$

$W_{l + 1, i} (A) = \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}, t \neq i} \frac{P_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} | (i \in N_{3}, l \in Z),$

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

$\begin{array}{l} (W_{l + 1, j} (A) - \sum_{t \in N_{3}, t \neq j} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{j t} |) (| a_{i i} | x_{1 i, k} - \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i t} | x_{1 t, k}) - \sum_{t \in N_{2}} | a_{i t} | x_{2 t}) \\ > (\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t}) (\sum_{t \in N_{3}} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |), i \in N_{1 k}, k = 1, 2, \dots, m, j \in N_{3} . \end{array}$ (1)

且当 $i \in N_{2}$ 时， $\sum_{t \in N_{1}} | a_{i t} |$ 与 $\sum_{t \in N_{3}} | a_{i t} |$ 不能同时为0，则A是非奇异H-矩阵。

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

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

$\frac{P_{l + 1, i} (A)}{| a_{i i} |} \leq r_{l + 1} \leq r_{l} \leq \dots \leq r_{1} < r_{0} = 1, \frac{W_{l + 1, i} (A)}{| a_{i i} |} \leq \frac{P_{l + 1, i} (A)}{| a_{i i} |}, i \in N_{3}, l \in Z .$ (2)

故对任意的 $i \in N_{3}$ 有

$h_{l + 1, i} (A) = \frac{\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t}}{W_{l + 1, i} (A) - \sum_{t \in N_{3}, t \neq i} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |} = \frac{W_{l + 1, i} (A) - \sum_{t \in N_{3}, t \neq i} \frac{P_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |}{W_{l + 1, i} (A) - \sum_{t \in N_{3}, t \neq i} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |} \leq 1.$

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

$| a_{i i} | x_{1 i, k} > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + h_{l + 1, j} (A) \sum_{t \in N_{3}} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |,$

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

$| a_{i i} | x_{1 i, k} > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |,$

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

$| a_{i t} | x_{1 i, k} - [\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |] > ε \sum_{t \in N_{3}} | a_{i t} |,$

故而有

$| a_{i t} | x_{1 i, k} - \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i t} | x_{1 t, k}) - \sum_{t \in N_{2}} | a_{i t} | x_{2 t} > \sum_{t \in N_{3}} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} | .$ (3)

可构造正对角矩阵 $X_{1} = d i a g (x_{1}, x_{2}, \dots, x_{n})$ ，记 $B = A X_{1} = (b_{i j})$ ，其中

$x_{i} = {\begin{cases} x_{1 i, k} i \in N_{1 k}, k = 1, 2, \dots, m, \\ x_{2 i} i \in N_{2}, \\ \frac{W_{l + 1, i} (A)}{| a_{i i} |} + ε i \in N_{3} . \end{cases}$

再由 $h_{l + 1, j} (A) \leq 1$ 可得到，对任意的 $j \in N_{3}, l \in Z$ 有

$W_{l + 1, j} (A) - \sum_{t \in N_{3}, t \neq j} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{j t} | \geq \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t},$

又对任意的 $j \in N_{3}$ ，有 $| a_{j j} | > \sum_{t \in N_{3}, t \neq j} | a_{j t} |$ ，所以得到

$W_{l + 1, j} (A) - \sum_{t \in N_{3}, t \neq j} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{j t} | + (ε | a_{j j} | - ε \sum_{t \in N_{3}, t \neq i} | a_{j t} |) > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t},$

即有

$W_{l + 1, j} (A) + ε | a_{j j} | - \sum_{t \in N_{3}, t \neq j} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{j t} | > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t} .$ (4)

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

$\begin{array}{l} (| b_{j j} | - β_{j} (B)) (| b_{i i} | - α_{i} (B)) \\ = (W_{l + 1, j} (A) + ε | a_{j j} | - \sum_{t \in N_{3}, t \neq j} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{j t} |) (| a_{i i} | x_{1 i, k} - \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}, t \neq i} | a_{i i} | x_{1 t, k}) - \sum_{t \in N_{2}} | a_{i t} | x_{2 t}) \\ > (\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t}) (\sum_{t \in N_{3}} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} |) = α_{j} (B) β_{i} (B) . \end{array}$

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

$\begin{matrix} | a_{i i} | x_{2 i} = \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}, t \neq i} | a_{i t} | + \sum_{t \in N_{3}} | a_{i t} | \\ > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}, t \neq i} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} |, \end{matrix}$ (5)

由(4)式和(5)式可知，对任意的 $i \in N_{2}, j \in N_{3}, l \in Z$ 有

$\begin{array}{l} (| b_{j j} | - β_{j} (B)) (| b_{i i} | - α_{i} (B)) \\ = (W_{l + 1, j} (A) + ε | a_{j j} | - \sum_{t \in N_{3}, t \neq j} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{j t} |) (| a_{i i} | x_{2 i} - \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i i} | x_{1 t, k}) - \sum_{t \in N_{2}, t \neq i} | a_{i t} | x_{2 t}) \\ > (\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t}) (\sum_{t \in N_{3}} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} |) = α_{j} (B) β_{i} (B) . \end{array}$

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

$W_{l + 1, i} (A) \geq \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}, t \neq i} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} |,$

又对任意的 $i \in N_{3}$ ，有 $| a_{i i} | > \sum_{t \in N_{3}, t \neq i} | a_{i t} |$ ，所以得到

$W_{l + 1, i} (A) + ε | a_{i i} | > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}, t \neq i} \frac{W_{l + 1, t} (A)}{| a_{t t} |} | a_{i t} | + ε \sum_{t \in N_{3}, t \neq i} | a_{i t} |,$

故有

$(\frac{W_{l + 1, i} (A)}{| a_{i i} |} + ε) | a_{i i} | > \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{i t} | x_{2 t} + \sum_{t \in N_{3}, t \neq i} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} |,$ (6)

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

$\begin{array}{l} (| b_{j j} | - β_{j} (B)) (| b_{i i} | - α_{i} (B)) \\ = (W_{l + 1, j} (A) + ε | a_{j j} | - \sum_{t \in N_{3}, t \neq j} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{j t} |) (| a_{i i} | (\frac{W_{l + 1, i} (A)}{| a_{i i} |} + ε) - \sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{i i} | x_{1 t, k}) - \sum_{t \in N_{2}} | a_{i t} | x_{2 t}) \\ > (\sum_{k = 1}^{m} (\sum_{t \in N_{1 k}} | a_{j t} | x_{1 t, k}) + \sum_{t \in N_{2}} | a_{j t} | x_{2 t}) (\sum_{t \in N_{3}, t \neq i} (\frac{W_{l + 1, t} (A)}{| a_{t t} |} + ε) | a_{i t} |) = α_{j} (B) β_{i} (B) . \end{array}$

即

$(| b_{i i} | - α_{i} (B)) (| b_{j j} | - β_{j} (B)) > β_{i} (B) α_{j} (B), i \in N_{1} \cup N_{2}, j \in N_{3},$

且

$(| b_{i i} | - α_{i} (B)) (| b_{j j} | - β_{j} (B)) > β_{i} (B) α_{j} (B), 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 = (a_{i j}) \in C^{n \times n}$ ，给定 $m, q, σ_{2}$ 。

输出： $X^{(y)} = d i a g (x_{i}^{(y)})$ ，若A是非奇异H-矩阵。

1) 如果 $N_{3} (A) = ϕ$ 或存在 $i_{0} \in N (A)$ 使得 $| a_{i_{0} i_{0}} | = 0$ ，则 $A \notin D^{*}$ ，停止；否则转2；

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

3) 计算 $A^{(y)} = A^{(y - 1)} X^{(y - 1)} = (a_{i t}^{(y)})$ ；

4) 取 $l = 1$ ，计算 $Λ_{i} (A^{(y)}) = \sum_{t \neq i} | a_{i t}^{(y)} |$ ；

5) 如果 $| a_{i i}^{(y)} | > Λ_{i} (A^{(y)})$ ，则 $i \in N_{3} (A^{(y)})$ ；否则转6；

6) 如果 $| a_{i i}^{(y)} | = Λ_{i} (A^{(y)})$ ，则 $i \in N_{2} (A^{(y)})$ ；否则转7；

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

8) 令 $N_{1} (A^{(y)}) = \cup_{k = 1}^{m} N_{1 k} (A^{(y)})$ ，如果 $N_{1} (A^{(y)}) \cup N_{2} (A^{(y)}) = ϕ$ ，则 $A \in D^{*}$ ，停止；否则转9；

9) 如果 $N_{3} (A^{(y)}) = ϕ$ ，则 $A \notin D^{*}$ ，停止；否则转10；

10) 计算

$x_{1 i, k}^{(y)} = \frac{| a_{i i}^{(y)} | - \frac{k - 1}{m + 1} Λ_{i} (A^{(y)})}{Λ_{i} (A^{(y)})} (i \in N_{1 k} (A^{(y)}), k = 1, 2, \dots, m),$

$α_{i}^{(y)} = \sum_{k = 1}^{m} (\sum_{t \in N_{1 k} (A^{(y)}), t \neq i} | a_{i t}^{(y)} |), {\bar{α}}_{i}^{(y)} = \sum_{k = 1}^{m} (\sum_{t \in N_{1 k} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | x_{1 t, k}^{(y)}),$

$β_{i}^{(y)} = \sum_{t \in N_{2} (A^{(y)}), t \neq i} | a_{i t}^{(y)} |, {\bar{β}}_{i}^{(y)} = \sum_{t \in N_{2} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | x_{2 t}^{(y)},$

$μ_{i}^{(y)} = \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} |,$

$x_{2 i}^{(y)} = \frac{{\bar{α}}_{i}^{(y)} + β_{i}^{(y)} + μ_{i}^{(y)}}{| a_{i i}^{(y)} |} (i \in N_{2} (A^{(y)}));$

11) 取 $r_{0}^{(y)} = 1$ ，计算

$r_{1}^{(y)} = \max_{i \in N_{3} (A^{(y)})} {\frac{α_{i}^{(y)} + β_{i}^{(y)}}{| a_{i i}^{(y)} | - μ_{i}^{(y)}}},$

$r_{l + 1}^{(y)} = \max_{i \in N_{3} (A^{(y)})} {\frac{{\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)} + r_{l}^{(y)} μ_{i}^{(y)}}{| a_{i i}^{(y)} |}} (i \in N_{3} (A^{(y)}), l \in Z^{+}),$

$P_{l + 1, i}^{(y)} = {\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)} + r_{l}^{(y)} μ_{i}^{(y)} (i \in N_{3} (A^{(y)}), l \in Z),$

${\bar{μ}}_{i}^{(y)} = \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | \frac{P_{l + 1, t}^{(y)}}{| a_{t t}^{(y)} |} (i \in N_{3} (A^{(y)}), l \in Z),$

$W_{l + 1, i}^{(y)} = {\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)} + {\bar{μ}}_{i}^{(y)} (i \in N_{3} (A^{(y)}), l \in Z),$

${\bar{η}}_{i}^{(y)} = \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | \frac{W_{l + 1, t}^{(y)}}{| a_{t t}^{(y)} |} (i \in N_{3} (A^{(y)}), l \in Z),$

$h_{l + 1, i}^{(y)} = \frac{{\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)}}{W_{l + 1, i}^{(y)} - {\bar{η}}_{i}^{(y)}} (i \in N_{3} (A^{(y)}), l \in Z);$

12) 令 $γ = \max_{i \in N_{3} (A^{(y)})} {\frac{{\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)}}{W_{l + 1, i}^{(y)} - {\bar{η}}_{i}^{(y)}}}$ ；

13) 如果

$| a_{i i}^{(y)} | x_{1 i, k}^{(y)} > {\bar{α}}_{i}^{(y)} + {\bar{β}}_{i}^{(y)} + γ {\bar{η}}_{i}^{(y)} (i \in N_{1 k} (A^{(y)})),$

则 $A \in D^{*}$ ，输出 $X^{(y)} = d i a g (x_{i}^{(y)})$ ，停止；否则转14；其中

$x_{i}^{(y)} = {\begin{cases} x_{1 i, k}^{(y)} i \in N_{1 k} (A^{(y)}), \\ x_{2 i}^{(y)} i \in N_{2} (A^{(y)}), \\ \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + ε^{(y)} i \in N_{2} (A^{(y)}) . \end{cases}$

$ε^{(y)} = {\begin{cases} \frac{1}{q} \min (\frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |}) \forall i \in N_{3} (A^{(y)}), \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | \neq 0, \\ σ_{2} \exists i \in N_{3} (A^{(y)}), s . t . \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | = 0. \end{cases}$

这里 $σ_{2}$ 为充分小的数，且 $q > 1$ ；

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

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

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

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

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

$A^{(y)} = A^{(0)} X^{(0)} X^{(1)} \dots X^{(y - 1)} = A X,$

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

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

下面证明： $\lim_{y \to \infty} N_{3} (A^{(y)}) = N_{3} (B) = ϕ$ 。

再利用反证法。假设存在某一 $i \in N_{3} (A^{(y)})$ ，使得 $\lim_{y \to \infty} N_{3} (A^{(y)}) \neq ϕ$ ，则 $1 - x_{1 i, k}^{(y)} > 0$ ， $1 - x_{2 i}^{(y)} > 0$ ， $1 - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} - ε^{(y)} > 0$ ，且存在常量 $τ_{1}, τ_{2}, τ_{3}$ 使得 $| a_{i i}^{(y)} | (1 - x_{1 i, k}^{(y)}) > τ_{1}$ ， $| a_{i i}^{(y)} | (1 - x_{2 i}^{(y)}) > τ_{2}$ ， $| a_{i i}^{(y)} | (1 - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} - ε^{(y)}) > τ_{3}$ 。取 $τ_{0} = \min {τ_{1}, τ_{2}, τ_{3}}$ ，由算法2.1可得

$| a_{i i}^{(y + 1)} | = | a_{i i}^{(y)} | x_{1 i, k}^{(y)} < | a_{i i}^{(y)} | - τ_{0},$

$| a_{i i}^{(y + 1)} | = | a_{i i}^{(y)} | x_{2 i}^{(y)} < | a_{i i}^{(y)} | - τ_{0},$

$| a_{i i}^{(y + 1)} | = | a_{i i}^{(y)} | (\frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + ε^{(y)}) < | a_{i i}^{(y)} | - τ_{0} .$

因此递推可得

$| a_{i i}^{(0)} | = | a_{i i}^{(1)} | > | a_{i i}^{(2)} | + τ_{0} > \dots > | a_{i i}^{(y)} | + (y - 1) τ_{0},$

当 $y \to \infty$ 时，有 $a_{i i} \to \infty$ ，产生矛盾。故 $\lim_{y \to \infty} N_{3} (A^{(y)}) = N_{3} (B) = ϕ$ ，由引理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_{1 i, k}^{(y)}$ 的定义、 $x_{2 i}^{(y)}$ 的定义及 $\frac{P_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} < 1$ 可知

$\begin{matrix} ε^{(y)} = \frac{1}{q} \min_{i \in N_{3} (A^{(y)})} {\frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |}} \\ = \frac{1}{q} \min_{i \in N_{3} (A^{(y)})} \frac{\sum_{t \in N_{1 k} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | (1 - x_{1 t, k}^{(y)}) + \sum_{t \in N_{2} (A^{(y)})} | a_{i t}^{(y)} | (1 - x_{2 t}^{(y)}) + \sum_{t \in N_{3} (A^{(y)}), t \neq i} | a_{i t}^{(y)} | (1 - \frac{P_{l + 1, t}^{(y)}}{| a_{t t}^{(y)} |})}{| a_{i i}^{(y)} |} \\ > 0, \end{matrix}$

且有

$\begin{array}{l} \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + ε^{(y)} = \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + \frac{1}{q} \min_{i \in N_{3} (A^{(y)})} {\frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |}} \leq \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + \frac{1}{q} (\frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |}) \\ < \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |} + (\frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} - \frac{W_{l + 1, i}^{(y)}}{| a_{i i}^{(y)} |}) = \frac{Λ_{i}^{(y)}}{| a_{i i}^{(y)} |} < 1, \end{array}$

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

3. 数值算例

例1 考虑矩阵A

$A_{1} = (\begin{matrix} 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{matrix}) .$

$A_{2} = (\begin{matrix} 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{matrix}) .$

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

Table 1. Numerical results of algorithm

表1. 算法数值计算结果

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

例2 考虑矩阵B

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

$I = {(\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 \end{matrix})}_{20 \times 20}, E = {(\begin{matrix} 1 & 1 & \dots & 1 \\ 1 & 1 & \dots & 1 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 1 & \dots & 1 \end{matrix})}_{20 \times 20}, O = {(\begin{matrix} 0 & 0 & \dots & 0 \\ 0 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 0 \end{matrix})}_{20 \times 20} .$

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

Table 2. Number of iterations for different algorithms

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

取 $q = 5$ ， $σ_{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)。

文章引用

董杰,庹清,谢智慧. 一类非奇异H-矩阵的细分迭代判别算法
Subdivision Iterative Discriminant Algorithm for a Class of Nonsingular H-Matrix[J]. 应用数学进展, 2022, 11(08): 5062-5073. https://doi.org/10.12677/AAM.2022.118531

参考文献

1. 张万智, 徐仲, 陆全, 张骁. 广义严格对角占优矩阵的迭代判别方法[J]. 高等学校计算数学学报, 2016, 38(4): 301-312.

2. 丁碧文, 刘建州. 广义严格对角占优矩阵的充分条件[J]. 高等学校计算数学学报, 2009, 31(4): 310-318.

3. 黄泽军, 刘建州. 非奇异H矩阵的一类新迭代判别法[J]. 工程数学学报, 2008(5): 939-942.

4. 张骁, 陆全, 徐仲, 崔静静. 非奇H-矩阵的一组迭代判别法[J]. 数值计算与计算机应用, 2015, 36(1): 59-68.

5. 孙玉祥. 广义对角占优矩阵的充分条件[J]. 高等学校计算数学学报, 1997(3): 216-223.

6. Farid, F.O. (2011) Notes on Matrices with Diagonally Dominant Properties. Linear Algebra and Its Applications, 435, 2793-2812. https://doi.org/10.1016/j.laa.2011.04.045

7. 张骁, 陆全, 徐仲, 等. 非奇H-矩阵判别的充要条件[J]. 应用数学, 2016, 29(1): 50-57.

8. Gu, J., Zhou, S., Zhao, J., et al. (2021) The Doubly Diagonally Dominant Degree of the Schur Complement of Strictly Doubly Diagonally Dominant Matrices and Its Applications. Bulletin of the Iranian Mathematical Society, 47, 265-285. https://doi.org/10.1007/s41980-020-00382-w

9. Kalhoro, Z.A., Guan, J., Abro, K.A., et al. (2016) A Modified Iterative Algorithm for Classifying Generalized Strictly Diagonally Dominant Matrices. Sci. Int. (Lahore), 28, 4157-4162.

10. Guan, J., Lu, L., Li, R.C., et al. (2016) Self-Corrective Iterations (SCI) for Generalized Diagonally Dominant Matrices. Journal of Computational and Applied Mathematics, 302, 285-300. https://doi.org/10.1016/j.cam.2016.02.021

11. 关晋瑞, 任孚鲛. 广义严格对角占优矩阵的一种判别法[J]. 应用数学, 2019, 32(3): 676-681. https://doi.org/10.13642/j.cnki.42-1184/o1.2019.03.015

NOTES

^*通讯作者。

期刊菜单