弱链对角占优M-矩阵逆的无穷范数新上界估计

New Upper Bound Estimates of the Infinite Norm for the Inverse of Weakly Chain Diagonally Dominant M-Matrices

摘要: 根据弱链对角占优M-矩阵A的逆矩阵元素，定义新的参数，结合不等式放缩技巧，给出的新上界估计式。理论分析和数值例子说明，新估计式改进了现有文献的有关结果。

Abstract: According to the inverse matrix elements of weakly chain diagonally dominant M-matrix A, the new parameters are defined and the inequality scaling technique is used to obtain . Theoretical analysis and numerical examples show that the new estimate improves the relevant results in the existing literature.

1. 引言

弱链对角占优矩阵在现代经济学、网络、信息论和算法设计等领域都有着广泛的应用。从1974年开始，众多学者对弱链对角占优M-矩阵的逆矩阵的无穷范数的上界估计进行了广泛研究，得到了一些不同的估计结果并将其进行了应用(见文献 [1] - [8])。本文将通过定义关于弱链对角占优M-矩阵A的元素的新参数，同时结合 $A^{-1}$ 的元素，从新的角度给出弱链对角占优M-矩阵 ${\Vert A^{-1}\Vert }_{\infty }$ 的新上界估计式，并验证结果的有效性。

$C^{n\times n}\left(R^{n\times n}\right)$ 表示n阶复(实)矩阵集，设 $A=\left(a_{ij}\right)\in C^{n\times n}$， $N=\left\{1,2,\cdots ,n\right\}$，为方便叙述给出下列符号：

$R_i={\displaystyle \underset{k\ne i}{\sum }\left|a_{ik}\right|},$

$d_i=\frac{R_i}{\left|a_{ii}\right|},$

$r_{ij}=\frac{\left|a_{ij}\right|}{\left|a_{ii}\right|-{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|}}j\ne i,$

$s_{ij}=\frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|r_{kj}}}{\left|a_{ii}\right|}j\ne i,$

$v_{ij}=\frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|s_{kj}}}{\left|a_{ii}\right|}j\ne i,$

$v_i=\underset{j\ne i}{\max }\left\{v_{ji}\right\},$

$m_{ki}=\{\begin{array}{l}\frac{\left|a_{ki}\right|}{\left|a_{kk}\right|-{\displaystyle \underset{j=i+1,j\ne k}{\overset{n}{\sum }}\left|a_{kj}\right|s_{ji}}}\left|a_{ki}\right|\ne 0,\\ 0\left|a_{ki}\right|=0.\end{array}$

$m_i=\{\begin{array}{l}\underset{i+1\le k\le n}{\max }\left\{m_{ki}\right\}1\le i\le n-1,\\ 0i=n.\end{array}$

定义1 [1] 设 $A=\left(a_{ij}\right)\in R^{n\times n}$，若 $\forall i\in N$，有 $d_i\le 1$， $J\left(A\right)=\left\{i\in N|d_i<1\right\}\ne \varphi$，且 $\forall i\in N$， $i\notin J\left(A\right)$，有 $a_{i{i}_1}{a}_{i_1{i}_2}\cdots a_{i_r{i}_k}\ne 0$，( $i\ne i_1,i_1\ne i_2,\cdots ,i_r\ne i_k$ )， $0\le r\le k-1$， $i_k\in J\left(A\right)$，则称A为弱链对角占优矩阵。

定义2 [1] 设 $A=\left(a_{ij}\right)\in Z_n=\left\{A=\left(a_{ij}\right)\in R^{n\times n}|a_{ij}\le 0,i,j\in N,i\ne j\right\}$，若 $A^{-1}\ge 0$，则称A为M-矩阵；若 $\forall i\in N$，有 $a_{ii}>0$，则称A为L-矩阵。弱链对角占优L-矩阵为M-矩阵。

定义3 [1] 设 $A=\left(a_{ij}\right)\in R^{n\times n}$，A为弱链对角占优矩阵，若 $A=\left(a_{ij}\right)\in Z_n$， $A^{-1}\ge 0$，则称A为弱链对角占优矩阵M-矩阵。

引理1 [1] 设A为n阶弱链对角占优M-矩阵，则 $A^{\left(k,n\right)}\left(k=1,2,\cdots ,n-1\right)$ 为弱链对角占优M-矩阵。

引理2 [1] 若 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵， $B=A^{\left(2,n\right)}\in R^{\left(n-1\right)\times \left(n-1\right)}$， $A^{-1}=\left({\alpha }_{ij}\right)$， $B^{-1}=\left({\beta }_{ij}\right)$，则

${\alpha }_{11}=\frac{1}{\Delta },$

${\alpha }_{i1}=\frac{1}{\Delta }{\displaystyle \underset{k=2}{\overset{n}{\sum }}{\beta }_{ik}}\left(-a_{k1}\right),$

${\alpha }_{1j}=\frac{1}{\Delta }{\displaystyle \underset{k=2}{\overset{n}{\sum }}{\beta }_{kj}}\left(-a_{1k}\right),$

${\alpha }_{ij}={\beta }_{ij}+{\alpha }_{1j}{\displaystyle \underset{k=2}{\overset{n}{\sum }}{\beta }_{ik}}\left(-a_{k1}\right),$

$\Delta =a_{11}-{\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{1k}\left({\displaystyle \underset{k=2}{\overset{n}{\sum }}{\beta }_{ki}{a}_{i1}}\right)}>0.$

引理3 [1] 若 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵， $A^{-1}=\left({\alpha }_{ij}\right)$，则 $\forall i,j\in N$， $i\ne j$，有

$\left|{\alpha }_{ij}\right|\le d_i\left|{\alpha }_{jj}\right|\le \left|{\alpha }_{jj}\right|.$

引理4 [2] 若 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵，且 $J\left(A\right)=\left\{i_1,i_2,\cdots ,i_k\right\}$，那么存在一个N的置换 $\left\{i_1,i_2,\cdots ,i_n\right\}$，使得对所有的 $j\in N$，有

$g_i=\left|a_{i_j{i}_j}\right|-{\displaystyle \underset{l=j+1}{\overset{n}{\sum }}\left|a_{i_j{i}_l}\right|}>0.$

引理5 若 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵， $n\ge 2$， $A^{-1}=\left({\alpha }_{ij}\right)$，满足 $u_1<1$，则

${\alpha }_{11}\le \frac{1}{a_{11}\left(1-m_1{d}_1\right)}.$

证明

因A为M-矩阵，则 $A^{-1}\ge 0$，设 $Am=x$，其中 $m={\left(1,m_1,\cdots ,m_1\right)}^{\text{T}}$， $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$，因为 $0\le m_1\le 1$， $u_1={\displaystyle \underset{k=2}{\overset{n}{\sum }}\left|a_{1k}\right|/\left|a_{11}\right|}<1$，则

$x_1=a_{11}+{\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{1k}{m}_1}=\left|a_{11}\right|-{\displaystyle \underset{k=2}{\overset{n}{\sum }}\left|a_{1k}\right|m_1}\ge \left|a_{11}\right|-{\displaystyle \underset{k=2}{\overset{n}{\sum }}\left|a_{1k}\right|}>0,$

对 $\forall i\in N$， $2\le i\le n$，有

${\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{ik}}=\left|a_{ii}\right|-{\displaystyle \underset{k\in N,k\ne 1,i}{\sum }\left|a_{ik}\right|}\ge \left|a_{ii}\right|-{\displaystyle \underset{k\in N,k\ne i}{\sum }\left|a_{ik}\right|}\ge 0.$

当 $a_{i1}=0$ 时， $x_i={\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{ik}{m}_1}\ge 0$ ；当 $a_{i1}\ne 0$ 时， $x_i=a_{i1}+{\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{ik}{m}_1}\ge a_{i1}+\left({\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{ik}}\right)m_{i1}=0$，即

$x_1>0,x_i\ge 0\left(i=2,\cdots ,n\right)\text{.}$

再由 $A^{-1}x=m$， $A^{-1}\ge 0$，有

${\alpha }_{11}\le \frac{1}{x_1}=\frac{1}{a_{11}+m_1{\displaystyle \underset{k=2}{\overset{n}{\sum }}{a}_{1k}}}=\frac{1}{a_{11}\left(1-m_1{d}_1\right)}.$

引理6 设 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵，且 $A^{-1}=\left({\alpha }_{ij}\right)$，对 $\forall i,j\in N$， $i\ne j$，有

$\left|{\alpha }_{ij}\right|\le \frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|s_{kj}}}{\left|a_{ii}\right|}\left|{\alpha }_{jj}\right|\le v_j\left|{\alpha }_{jj}\right|\le \left|{\alpha }_{jj}\right|.$

证明

根据引理3，设

$s_{ji}\left(\epsilon ,1\right)=\{\begin{array}{l}\frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|r_{kj}}+\epsilon }{\left|a_{ii}\right|}i\in J\left(A\right),\\ 1i\in N,i\notin J\left(A\right).\end{array}$

其中 $\epsilon >0$ 足够小，使得 $0<s_{ji}\left(\epsilon ,1\right)\le 1\left(i,j\in N,i\ne j\right)$。

设

$S_j\left(\epsilon ,1\right)=diag\left(s_{j1}\left(\epsilon ,1\right),\cdots ,s_{jj-1}\left(\epsilon ,1\right),1,s_{jj+1}\left(\epsilon ,1\right),\cdots ,s_{jn}\left(\epsilon ,1\right)\right),j\in N.$

显然，当 $S_j\left(\epsilon ,1\right)=diag\left(1,1,\cdots ,1\right)=I$ 时， $A{S}_j\left(\epsilon ,1\right)$ 是弱链对角占优矩阵，且当 $S_j\left(\epsilon ,1\right)\ne I$ 时， $A{S}_j\left(\epsilon ,1\right)$ 是严格对角占优矩阵，所以， $A{S}_j\left(\epsilon ,1\right)$ 一定是一个弱链对角占优矩阵，从而

$\frac{\left|{\alpha }_{ij}\right|}{s_{ji}\left(\epsilon ,1\right)}\le \frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|s_{kj}}\left(\epsilon ,1\right)}{\left|a_{ii}\right|s_{ji}\left(\epsilon ,1\right)}\left|{\alpha }_{jj}\right|,i\ne j$

也就是

$\left|{\alpha }_{ij}\right|\le \frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|s_{kj}}\left(\epsilon ,1\right)}{\left|a_{ii}\right|}\left|{\alpha }_{jj}\right|,i\ne j$

当 $\epsilon \to 0$ 时，得

$\left|{\alpha }_{ij}\right|\le \frac{\left|a_{ij}\right|+{\displaystyle \underset{k\ne i,j}{\sum }\left|a_{ik}\right|s_{kj}}}{\left|a_{ii}\right|}\left|{\alpha }_{jj}\right|\le v_j\left|{\alpha }_{jj}\right|\le \left|{\alpha }_{jj}\right|,i\ne j.$

2. 主要结果

1974年，P N Shivakumar在文献 [1] 中给出弱链对角占优M-矩阵A的 ${\Vert A^{-1}\Vert }_{\infty }$ 的上界：

${\Vert A^{-1}\Vert }_{\infty }\le {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left[a_{ii}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(1-u_j\right)}\right]}^{-1}}.$ (1)

2012年，潘淑珍在文献 [3] 中给出优于文献 [1] 的弱链对角占优M-矩阵A的 ${\Vert A^{-1}\Vert }_{\infty }$ 的上界估计式：

${\Vert A^{-1}\Vert }_{\infty }\le \frac{1}{\left|a_{11}\right|\left(1-u_1{t}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{\left|a_{ii}\right|\left(1-u_i{t}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(1+\frac{u_j}{1-u_j{t}_j}\right)}\right]}.$ (2)

其中

$t_i=\{\begin{array}{l}\underset{i+1\le k\le n}{\max }\left\{t_{ki}\right\}1\le i\le n-1,\\ 0i=n.\end{array}0\le t_i\le 1,\forall i\in N$

$t_{ki}=\{\begin{array}{l}\frac{\left|a_{ki}\right|}{\left|a_{kk}\right|-{\displaystyle \underset{j=i+1,j\ne k}{\overset{n}{\sum }}\left|a_{kj}\right|}}\left|a_{ki}\right|\ne 0,\\ 0\left|a_{ki}\right|=0.\end{array}\forall k\in N,i+1\le k\le n,1\le i\le \left(n-1\right)$

本文继续给出弱链对角占优M-矩阵A的 ${\Vert A^{-1}\Vert }_{\infty }$ 的新上界估计式。

2.1. 定理1

设 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵， $n\ge 2$， $A^{-1}=\left({\alpha }_{ij}\right)$， $B=A^{\left(2,n\right)}$， $B^{-1}=\left({\beta }_{ij}\right)$，满足 $u_1<1$，则

${\Vert A^{-1}\Vert }_{\infty }\le \max \left\{\frac{1}{a_{11}\left(1-m_1{d}_1\right)}+\frac{d_1{\Vert B^{-1}\Vert }_{\infty }}{1-m_1{d}_1},\frac{v_1}{a_{11}\left(1-m_1{d}_1\right)}+\left(\frac{v_1{d}_1}{1-m_1{d}_1}+1\right){\Vert B^{-1}\Vert }_{\infty }\right\}.$

证明

记 $r_i={\displaystyle \underset{j=1}{\overset{n}{\sum }}{\alpha }_{ij}}$， $M_A={\Vert A^{-1}\Vert }_{\infty }$， $M_B={\Vert B^{-1}\Vert }_{\infty }$，即 $M_A=\underset{i\in N}{\max }\left\{r_i\right\}$， $M_B=\underset{2\le i\le n}{\max }\left\{{\displaystyle \underset{j=2}{\overset{n}{\sum }}{\beta }_{ij}}\right\}$，由引理2和引理5可得

$\begin{array}{c}{r}_1={\alpha }_{11}+{\displaystyle \underset{j=2}{\overset{n}{\sum }}{\alpha }_{1j}}=\frac{1}{\Delta }+\frac{1}{\Delta }{\displaystyle \underset{k=2}{\overset{n}{\sum }}\left(-a_{1k}\right){\displaystyle \underset{j=2}{\overset{n}{\sum }}{\beta }_{kj}}}\le \frac{1}{\Delta }+\frac{1}{\Delta }{\displaystyle \underset{k=2}{\overset{n}{\sum }}\left(-a_{1k}\right)M_B}\\ =\frac{1}{\Delta }+\frac{1}{\Delta }{a}_{11}{d}_1{M}_B\le \frac{1}{a_{11}\left(1-m_1{d}_1\right)}+\frac{d_1}{1-m_1{d}_1}{M}_B,\end{array}$ (3)

对 $2\le i\le n$，由引理3知，

${\alpha }_{i1}\le {\alpha }_{11},$

对 $2\le j\le n$，由引理6知，

${\alpha }_{ij}={\beta }_{ij}+{\alpha }_{1j}{\displaystyle \underset{k=2}{\overset{n}{\sum }}{\beta }_{ik}\left(-a_{k1}\right)}\le {\beta }_{ij}+{\alpha }_{1j}{v}_1,$

则

$\begin{array}{c}{r}_i={\alpha }_{i1}+{\displaystyle \underset{j=2}{\overset{n}{\sum }}{\alpha }_{ij}}\le v_1{\alpha }_{11}+{\displaystyle \underset{j=2}{\overset{n}{\sum }}\left({\beta }_{ij}+{\alpha }_{1j}{v}_1\right)}=r_1{v}_1+M_B\le v_1\left(\frac{1}{a_{11}\left(1-m_1{d}_1\right)}+\frac{d_1{M}_B}{1-m_1{d}_1}\right)+M_B\\ =\frac{v_1}{a_{11}\left(1-m_1{d}_1\right)}+\left(\frac{v_1{d}_1}{1-m_1{d}_1}+1\right)M_B,\end{array}$ (4)

由(3)式和(4)式可得

$\begin{array}{c}{M}_A=\max \left\{r_1,r_i:2\le i\le n\right\}\\ \le \max \left\{\frac{1}{a_{11}\left(1-m_1{d}_1\right)}+\frac{d_1{\Vert B^{-1}\Vert }_{\infty }}{1-m_1{d}_1},\frac{v_1}{a_{11}\left(1-m_1{d}_1\right)}+\left(\frac{v_1{d}_1}{1-m_1{d}_1}+1\right){\Vert B^{-1}\Vert }_{\infty }\right\}.\end{array}$

2.2. 定理2

设 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵，且对 $\forall k\in N$，有 $u_k<1$，则

$\begin{array}{l}{M}_A\le \max \{\frac{1}{a_{11}\left(1-m_1{u}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{a_{ii}\left(1-m_i{u}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(\frac{u_j}{1-m_j{u}_j}\right)}\right]},\\ \frac{v_1}{a_{11}\left(1-m_1{u}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{v_i}{a_{ii}\left(1-m_i{u}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(\frac{v_j{u}_j}{1-m_j{u}_j}+1\right)}\right]}\}.\end{array}$ (5)

证明

设A为弱链对角占优M-矩阵，对 $\forall k\in N$， $1\le k\le n-1$， $A^{\left(k,n\right)}$ 为弱链对角占优M-矩阵，由定理1关于k对 $A^{\left(k,n\right)}$ 做数学归纳法可得。

注

设 $A=\left(a_{ij}\right)\in R^{n\times n}$ 为弱链对角占优M-矩阵，且对 $\forall k\in N$，满足 $u_k<1$，由 $v_i$， $m_i$， $t_i$ 表达式可知 $0\le v_i\le 1$， $0\le m_i\le t_i\le 1$，那么(5)式中 ${\Vert A^{-1}\Vert }_{\infty }$ 的上界小于等于(2)式中的上界，即

$\begin{array}{l}\max \{\frac{1}{a_{11}\left(1-m_1{u}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{a_{ii}\left(1-m_i{u}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(\frac{u_j}{1-m_j{u}_j}\right)}\right]},\frac{v_1}{a_{11}\left(1-m_1{u}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{v_i}{a_{ii}\left(1-m_i{u}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(\frac{v_j{u}_j}{1-m_j{u}_j}+1\right)}\right]}\}\\ \le \frac{1}{\left|a_{11}\right|\left(1-u_1{t}_1\right)}+{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{\left|a_{ii}\right|\left(1-u_i{t}_i\right)}{\displaystyle \underset{j=1}{\overset{i-1}{\prod }}\left(1+\frac{u_j}{1-u_j{t}_j}\right)}\right].}\end{array}$

3. 数值算例

例1设

$A=\left(\begin{array}{ccc}4& -1& -1\\ -2& 5& -3\\ -1& -2& 4\end{array}\right).$

$J=\left\{1,3\right\}$，易得到A为弱链对角占优M-矩阵， ${\Vert A^{-1}\Vert }_{\infty }=1.100$。

应用(1)式得

${\Vert A^{-1}\Vert }_{\infty }\le 2.7500;$

应用(2)式得

${\Vert A^{-1}\Vert }_{\infty }\le 1.500;$

应用定理2得

${\Vert A^{-1}\Vert }_{\infty }\le \mathrm{1.1503.}$

例2 设

$A=\left(\begin{array}{ccc}4& -2& -1\\ -1& 3& -2\\ -1& 0& 2\end{array}\right).$

易得到A为弱链对角占优M-矩阵， ${\Vert A^{-1}\Vert }_{\infty }=1.54$。

应用(1)式得

${\Vert A^{-1}\Vert }_{\infty }\le 11;$

应用(2)式得

${\Vert A^{-1}\Vert }_{\infty }\le 5.6667;$

应用定理2得

${\Vert A^{-1}\Vert }_{\infty }\le \mathrm{1.996.}$

4. 结论

理论证明本文所得弱链对角占优M-矩阵逆矩阵无穷范数的新上界估计式优于文献 [1] [3] 中的结果，数值算例亦说明了本文所得新上界估计式的有效性和可行性。

致谢

感谢莫宏敏老师对本篇论文的悉心指导和帮助。

基金项目

吉首大学研究生科研项目(JDY21012)。

NOTES

^*通讯作者。