基于Schur补的SDD₁矩阵逆的无穷范数及应用

The Infinity Norm for Inverse and Application of the SDD₁ Matrices Based on Schur Complement

摘要: 本文基于Schur补给出SDD₁矩阵逆的无穷范数的一个新上界，并将之应用到线性互补问题解的误差界估计中，得到SDD₁矩阵线性互补问题解的误差界的新估计式。数值算例说明新估计式是有效的和可行的。

Abstract: Based on the Schur complement, this paper gives a new upper bound of the infinite norm for inverse of the SDD₁ matrix, and applies it to the error bound estimation of the linear complementarity problem to obtain a new estimate of the error bound of the SDD₁ matrix linear complementarity problem. Numerical examples show that the new estimate is valid and feasible.

1. 引言

线性方程组$Ax=b$ 解的存在性、唯一性及稳定性都是热点研究问题。而线性方程组解的稳定性与其系数矩阵A的条件数$\text{cond}{\left(A\right)}_p={\Vert A\Vert }_p{\Vert A^{-1}\Vert }_p$ 有关，若$\text{cond}{\left(A\right)}_p$ 越大，则线性方程组解的稳定性不好，即病态程度越严重。显然，${\Vert A\Vert }_p$ 容易求出，而对于高阶矩阵，$A^{-1}$ 难以求出，故估计${\Vert A^{-1}\Vert }_p$ 很有意义。近年来，一些学者对H-矩阵及其子类矩阵逆的无穷范数估计进行了系列研究，获得了一些较好的结果[1]-[4]。

线性互补问题是指寻找一个向量$x\in R^n$ ，使得：

$Ax+q\ge 0,x\ge 0,x^{\text{T}}\left(Ax+q\right)=0$

成立，其中$A\in R^{n\times n},q\in R^n$ ，简记为$\text{LCP}\left(A,q\right)$ 。线性互补问题应用广泛，线性规划问题、力学中的障碍自由边界问题、经济学的双矩阵对策问题等都可以转化成线性互补问题进行求解[5] [6]。在研究线性互补问题解的存在性、唯一性及误差界的问题中，${\Vert A^{-1}\Vert }_p$ 的估计与线性互补问题解的误差界有着密切的联系。2006年，文献[7]给出了P-矩阵线性互补问题解的误差界的一个估计式：

$\Vert x-x^{*}\Vert \le \underset{d\in {\left[0,1\right]}^n}{\max }{\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }{\Vert r\left(x\right)\Vert }_{\infty },$

其中，$x^{*}$ 是$\text{LCP}\left(M,q\right)$ 的解，$r\left(x\right)=\min \left\{x,Mx+q\right\}$ ，$D=diag\left(d_i\right)\left(0\le d_i\le 1\right)$ 。可以看出，求线性互补问题解的误差界关键在于${\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }$ 的计算。故对${\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }$ 的估计很有意义。由于具有正对角元的H-矩阵是P-矩阵，随后许多学者对H-矩阵及其子类矩阵线性互补问题解的误差界进行了相关研究[4] [8] [9]。

矩阵Schur补理论在矩阵分析[10]、控制论、统计学[11]和数值分析等领域也有着广泛的应用。特别是在求解高阶线性方程组，运用矩阵Schur补理论将高阶线性方程组转化成低阶线性方程组，再对低阶方程组进行求解，大大减少了计算量。文献[12]给出了详细的Schur补的矩阵形式，并说明了矩阵关于子矩阵的Schur补在求解线性方程组中的重要性。文献[13]-[16]对矩阵关于子矩阵的Schur补是否具有原矩阵的性质进行了相关研究。文献[17]将矩阵Schur补与矩阵的逆建立相应联系，并给出了基于Schur补的严格对角占优矩阵逆的无穷范数的新上界。文献[18] [19]对H-矩阵及其子类进行了相关研究。本文拟通过H-矩阵的相关理论，结合Schur补，对SDD₁矩阵逆的无穷范数上界进行估计，并对SDD₁矩阵线性互补问题解的误差界估计进行研究。

2. 预备知识

令$R^{n\times n}$ 为全体$n\times n$ 实矩阵的集合，单位矩阵记为I。指标集$N=\left\{1,2,\cdots ,n\right\}$ 是一个非空子集，集合$\alpha \subseteq N$ ，$\left|\alpha \right|$ 表示子集$\alpha$ 含有的元素个数。设$A=\left(a_{ij}\right)\in R^{n\times n}$ ，记：

$r_i\left(A\right)={\displaystyle \sum _{j\in N\backslash \left\{i\right\}}^n\left|a_{ij}\right|},R_i\left(A\right)={\displaystyle \sum _{j\in N}\left|a_{ij}\right|},i\in N.$

定义1 [1]设$A=\left(a_{ij}\right)\in R^{n\times n}$ ，若对$\forall i\in N$ ，有：

$\left|a_{ii}\right|>r_i\left(A\right),$

则称A为严格对角占优(SDD)矩阵。

定义2 [2]设$A=\left(a_{ij}\right)\in R^{n\times n}$ ，若对$\forall i,j\in N,i\ne j$ ，有：

$\left|a_{ii}\right|\left|a_{jj}\right|>r_i\left(A\right)r_j\left(A\right),$

则称A为双严格对角占优(DSDD)矩阵。

定义3 [2]设$A=\left(a_{ij}\right)\in R^{n\times n}$ ，定义A的非奇异主子矩阵$A\left(\alpha \right)$ 的Schur补为：

$A/A\left(\alpha \right)=A\left(\overline{\alpha }\right)-A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right),$

其中，$\alpha ,\overline{\alpha }\subseteq N$ ，$\overline{\alpha }=N-\alpha$ ，$A\left(\alpha ,\overline{\alpha }\right)$ 表示A的行序在$\alpha$ 、列序在$\overline{\alpha }$ 的子矩阵；$A\left(\alpha \right)$ 是$A\left(\alpha ,\alpha \right)$ 的简写，$A/A\left(\alpha \right)$ 简记为$A/\alpha$ 。

定义4 [20]设$A=\left(a_{ij}\right)\in R^{n\times n}\left(n\ge 2\right)$ ，若对任意的$i\in N_1\left(A\right)$ ，满足：

$\left|a_{ii}\right|>P_i\left(A\right),$

$P_i\left(A\right)={\displaystyle \sum _{j\in N_1\left(A\right)\backslash \left\{i\right\}}\left|a_{ij}\right|}+{\displaystyle \sum _{j\in N_2\left(A\right)}\frac{r_j\left(A\right)}{\left|a_{jj}\right|}}\left|a_{ij}\right|,$

则称A为SDD₁矩阵。其中，$N_1\left(A\right)=\left\{i|\left|a_{ii}\right|\le r_i\left(A\right)\right\}$ ，$N_2\left(A\right)=\left\{i|\left|a_{ii}\right|>r_i\left(A\right)\right\}$ 。

引理1 [4]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD₁矩阵，且主对角元素为正，则$\tilde{A}=I-D+DA$ 也是SDD₁矩阵，其中$D=diag\left(d_i\right),0\le d_i<1$ 。

引理2 [8]若$\gamma >0$ ，$\eta >0$ ，则对于任意的$x\in \left[0,1\right]$ ，有：

$\frac{1}{1-x+\gamma x}\le \frac{1}{\min \left\{\gamma ,1\right\}},\frac{\eta x}{1-x+\gamma x}\le \frac{\eta }{\gamma }.$

引理3 [13]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 是SDD矩阵，子集$\alpha \subset N$ ，则$A\left(\alpha \right)$ 和$A/\alpha$ 为SDD矩阵。

引理4 [16] (商公式)设A是一个方阵，如果矩阵B是矩阵A的非奇异主子矩阵，矩阵C是B的非奇异主子矩阵，那么$B/C$ 是$A/C$ 的非奇异主子矩阵且：

$A/B=\left(A/C\right)/\left(B/C\right).$

引理5 [19]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 是SDD矩阵，$B_1=\left(b_{ij}\right)\in R^{m\times n}$ ，$B_2=\left(c_{ij}\right)\in R^{n\times m}$ ，有：

${\Vert B_1{A}^{-1}\Vert }_{\infty }\le \underset{j\in M}{\max }{\displaystyle \sum _{i\in N}\frac{\left|b_{ji}\right|\left(1+\varphi r_i\left(A\right)\right)}{\left|a_{ii}\right|}},$

${\Vert A^{-1}{B}_2\Vert }_{\infty }\le \underset{i\ne j}{\underset{i,j\in N}{\max }}\frac{\left|a_{jj}\right|R_i\left(B_2\right)+r_i\left(A\right)R_j\left(B_2\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\right)r_j\left(A\right)},$

其中，

$\varphi =\underset{i\ne j}{\underset{i,j\in N}{\max }}\frac{\left|a_{jj}\right|+r_i\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\right)r_j\left(A\right)}.$

引理6 [20]设$A=\left(a_{ij}\right)\in R^{n\times n}$ 是SDD₁矩阵，则A为H-矩阵。

引理7 [21]设$A\in \text{SDD}$ 或者$A\in \text{DSDD}$ ，则A为H-矩阵。

定理1 [1]设$A=\left(a_{ij}\right)\in R^{n\times n}$ 是SDD矩阵，有：

${\Vert A^{-1}\Vert }_{\infty }\le \underset{i\in N}{\max }\frac{1}{\left|a_{ii}\right|-r_i\left(A\right)}.$

定理2 [2]设$A=\left(a_{ij}\right)\in R^{n\times n}$ 是DSDD矩阵，有：

${\Vert A^{-1}\Vert }_{\infty }\le \underset{i\ne j}{\underset{i,j\in N}{\max }}\frac{\left|a_{jj}\right|+r_i\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\right)r_j\left(A\right)}.$

定理3 [3]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD₁矩阵，则存在正对角矩阵$D=diag\left(d_1,d_2,\cdots ,d_n\right)$ ，使得AD为SDD矩阵。其中，

$d_j=\{\begin{array}{ll}1,\hfill & j\in N_1\left(A\right)\hfill \\ \frac{P_j\left(A\right)}{\left|a_{jj}\right|}+\epsilon ,\hfill & j\in N_2\left(A\right)\hfill \end{array},0<\epsilon <\underset{i\in N}{\min }\frac{\left|a_{{}_{ii}}\right|-P_i\left(A\right)}{{\displaystyle \sum _{j\in N_2\left(A\right)\backslash \left\{i\right\}}\left|a_{ij}\right|}}.$

定理4 [4]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD₁矩阵且主对角元素为正，则有：

${\Vert A^{-1}\Vert }_{\infty }\le \max \left\{\underset{i\in N_1\left(A\right)}{\max }\frac{1}{\left|a_{ii}\right|-P_i\left(A\right)},\underset{i\in N_2\left(A\right)}{\max }\frac{1}{\left|a_{ii}\right|-r_i\left(A\right)}\right\},$

其中，$P_i\left(A\right)={\displaystyle \sum _{j\in N_1\left(A\right)\backslash \left\{i\right\}}\left|a_{ij}\right|}+{\displaystyle \sum _{j\in N_2\left(A\right)}\frac{r_j\left(A\right)}{\left|a_{jj}\right|}}\left|a_{ij}\right|$ ，$N_1\left(A\right)=\left\{i|\left|a_{ii}\right|\le r_i\left(A\right)\right\}$ ，$N_2\left(A\right)=\left\{i|\left|a_{ii}\right|>r_i\left(A\right)\right\}$ 。

定理5 [14]若$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD矩阵，则存在子集$\alpha \subset N$ ，$\overline{\alpha }=N-\alpha =\left\{i_1,\cdots ,i_m\right\}$ 。令$A/\alpha =\left({a^{\prime }}_{ts}\right)$ ，对任意$k\in \overline{\alpha }$ ，有：

$\left|{a^{\prime }}_{kk}\right|-r_k\left(A/\alpha \right)\ge \left|a_{i_k{i}_k}\right|-r_{i_k}^{\overline{\alpha }}\left(A\right)+{\displaystyle \sum _{h\in \alpha }\left|a_{i_{k}h}\right|}\frac{r_h\left(A\right)}{\left|a_{hh}\right|}\ge \left|a_{i_k{i}_k}\right|-r_{i_k}^{\overline{\alpha }}\left(A\right)>0.$

3. 主要结论

设矩阵$A=\left(a_{ij}\right)\in R^{n\times n}$ ，给定$\varnothing \ne \alpha =\left\{j_1,\cdots ,j_l\right\}\subseteq N$ ，$\overline{\alpha }=\left\{i_1,\cdots ,i_m\right\}=N-\alpha$ 。由文献[17]，存在置换矩阵P使得：

$P^{{\rm T}}AP=\left(\begin{array}{cc}A\left(\alpha \right)& A\left(\alpha ,\overline{\alpha }\right)\\ A\left(\overline{\alpha },\alpha \right)& A\left(\overline{\alpha }\right)\end{array}\right).$

若$A\left(\alpha \right)$ 非奇异，则存在矩阵$S,Q$ ，使得：

$A^{-1}=PQ\left(\begin{array}{cc}{\left[A\left(\alpha \right)\right]}^{-1}& 0\\ 0& {\left(A/\alpha \right)}^{-1}\end{array}\right)S{P}^{{\rm T}},$

其中，

$S=\left(\begin{array}{cc}{I}_1& 0\\ -A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}& I_2\end{array}\right),Q=\left(\begin{array}{cc}{I}_1& -{\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\\ 0& I_2\end{array}\right),$

$I_1,I_2$ 分别是l和m阶单位矩阵。

由P是置换矩阵知${\Vert P\Vert }_{\infty }=1$ ，故：

${\Vert A^{-1}\Vert }_{\infty }={\Vert S\Vert }_{\infty }{\Vert Q\Vert }_{\infty }\max \left\{{\Vert {\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty },{\Vert {\left(A/\alpha \right)}^{-1}\Vert }_{\infty }\right\}\le {\Vert P\Vert }_{\infty }{\Vert Q\Vert }_{\infty }{\Vert \left(\begin{array}{cc}{\left[A\left(\alpha \right)\right]}^{-1}& 0\\ 0& {\left(A/\alpha \right)}^{-1}\end{array}\right)\Vert }_{\infty }{\Vert S\Vert }_{\infty }{\Vert P^{{\rm T}}\Vert }_{\infty }.$ (1)

由于${\Vert S\Vert }_{\infty }=1+{\Vert A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty }$ ，${\Vert Q\Vert }_{\infty }=1+{\Vert {\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\Vert }_{\infty }$ 。求${\Vert A^{-1}\Vert }_{\infty }$ 的上界，只要知道${\Vert A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty }$ 、${\Vert {\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\Vert }_{\infty }$ 、${\Vert {\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty }$ 和${\Vert {\left(A/\alpha \right)}^{-1}\Vert }_{\infty }$ 。

引理8 设$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD₁矩阵，若非空子集$\alpha =\left\{j_1,\cdots j_l\right\}\subseteq N_2\subset N$ ，则$A\left(\alpha \right)$ 是SDD矩阵。

证明：因为$\alpha \subseteq N_2$ 且A是SDD₁矩阵，所以对任意$i\in \alpha$ ，有$\left|a_{ii}\right|>r_i\left(A\right)\ge r_i^{\alpha }\left(A\right)=r_i\left[A\left(\alpha \right)\right]$ 。即$A\left(\alpha \right)$ 是SDD矩阵。

引理9 设$A=\left(a_{ij}\right)\in R^{n\times n}$ 为SDD₁矩阵，若子集$N_2\subseteq \alpha \subset N$ ，则$A\left(\alpha \right)$ 是SDD₁矩阵。

证明：定义$\alpha =\left\{j_1,\cdots ,j_l\right\}$ ，$\overline{\alpha }=\left\{i_1,\cdots ,i_m\right\}$ 和$A\left(\alpha \right)=\left(b_{ij}\right)\in R^{l\times l}$ ，且当$p,q\in \alpha$ ，有$b_{pq}=a_{j_p{j}_q}$ 。

假设$N_2\left(A\right)=\left\{j_1,\cdots ,j_k\right\},k\le l$ 。那么$N_1\left(A\right)=\left\{j_{k+1},\cdots ,j_l,i_1,\cdots ,i_m\right\}$ 。对任意$j_p\in N_2\left(A\right)$ ，有$\left|b_{pp}\right|=\left|a_{j_p{j}_p}\right|>r_{j_p}\left(A\right)\ge r_{j_p}^{\alpha }\left(A\right)=r_p\left(A\left(\alpha \right)\right)$ ，得出对$1\le p\le k$ ，有$p\in N_2\left(A\left(\alpha \right)\right)$ 。那么对任意$q\in N_1\left(A\left(\alpha \right)\right)$ ，有$\left|a_{j_q{j}_q}\right|=\left|b_{qq}\right|<r_q\left(A\left(\alpha \right)\right)\le r_{j_q}\left(A\right)$ ，得出$j_q\in N_1\left(A\right)$ 。

对任意$q\in N_1\left(A\left(\alpha \right)\right)$ ，有$j_q\in N_1\left(A\right)$ 。由SDD₁矩阵的定义有：

$\begin{array}{c}\left|b_{qq}\right|=\left|a_{j_q{j}_q}\right|>{\displaystyle \sum _{v\in N_1\left(A\right)\backslash \left\{q\right\}}\left|a_{j_q{j}_v}\right|}+{\displaystyle \sum _{p\in N_2\left(A\right)}\frac{r_{j_p}\left(A\right)}{\left|a_{j_p{j}_p}\right|}}\left|a_{j_q{j}_p}\right|\ge {\displaystyle \sum _{v\in N_1\left(A\left(\alpha \right)\right)\backslash \left\{q\right\}}\left|a_{j_q{j}_v}\right|}+{\displaystyle \sum _{p\in N_2\left(A\left(\alpha \right)\right)}\frac{r_p\left(A\left(\alpha \right)\right)}{\left|a_{j_p{j}_p}\right|}}\left|a_{j_q{j}_p}\right|\\ \ge {\displaystyle \sum _{v\in N_1\left(A\left(\alpha \right)\right)\backslash \left\{q\right\}}\left|b_{qv}\right|}+{\displaystyle \sum _{p\in N_2\left(A\left(\alpha \right)\right)}\frac{r_p\left(A\left(\alpha \right)\right)}{\left|b_{pp}\right|}}\left|b_{qp}\right|,\end{array}$

所以$A\left(\alpha \right)$ 是SDD₁矩阵。

定理6 设$A=\left(a_{ij}\right)\in R^{n\times n}\left(n\ge 2\right)$ 为SDD₁矩阵，若子集$N_2\subseteq \alpha$ ，则$A/\alpha$ 是SDD矩阵。

证明(情况1)：当$N_2=\alpha$ ，因为A是SDD₁矩阵，存在一个正对角矩阵D (如定理3中)。那么$C=AD=\left(c_{ij}\right)$ 是SDD矩阵，有：

$\begin{array}{c}C/\alpha =\left(AD\right)/\alpha =\left(AD\right)\left(\overline{\alpha }\right)-\left(AD\right)\left(\overline{\alpha },\alpha \right){\left[\left(AD\right)\left(\alpha \right)\right]}^{-1}\left(AD\right)\left(\alpha ,\overline{\alpha }\right)\\ =A\left(\overline{\alpha }\right)D\left(\overline{\alpha }\right)-A\left(\overline{\alpha },\alpha \right)D\left(\alpha \right){\left[A\left(\alpha \right)D\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)D\left(\overline{\alpha }\right)\\ =\left[A\left(\overline{\alpha }\right)-\left(A\right)\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\right]D\left(\overline{\alpha }\right)\\ =A/\alpha D\left(\overline{\alpha }\right),\end{array}$

由$\alpha =N_2$ ，故$D\left(\overline{\alpha }\right)=I$ ，即$C/\alpha =A/\alpha$ 。由引理3知$A/\alpha$ 是SDD矩阵。

(情况2)：当$N_2\subset \alpha$ ，由情况1知$A/A\left(N_2\left(A\right)\right)$ 是SDD矩阵。那么由引理4和引理9有：

$A/\alpha =\left[A/A\left(N_2\left(A\right)\right)\right]/\left[A\left(\alpha \right)/A\left(N_2\left(A\right)\right)\right].$

综上，证明成立。

定理7 设$A=\left(a_{ij}\right)\in R^{n\times n}\left(n\ge 2\right)$ 为SDD₁矩阵，若非空子集$\alpha =\left\{j_1,\cdots ,j_l\right\}=N_2$ 且$\left|\alpha \right|\ge 2$ ， $\overline{\alpha }=N-\alpha =\left\{i_1,\cdots ,i_m\right\}$ ，则：

$\begin{array}{c}{\Vert A^{-1}\Vert }_{\infty }\le \left(1+\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{\left|a_{ji}\right|\left(1+\phi r_i^{\alpha }\left(A\right)\right)}{\left|a_{ii}\right|}}\right)\cdot \left(1+\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|R_i^{\overline{\alpha }}\left(A\right)+r_i^{\alpha }\left(A\right)R_j^{\overline{\alpha }}\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}\right)\\ \cdot \max \left\{\phi ,\underset{j\in \overline{\alpha }}{\max }\frac{1}{\left|a_{jj}\right|-r_j^{\overline{\alpha }}\left(A\right)+{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(A\right)}{\left|a_{ii}\right|}}\right\},\end{array}$

其中，$\phi =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|+r_i^{\alpha }\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}$ 。

证明：由公式，我们有：

${\Vert A^{-1}\Vert }_{\infty }\le {\Vert S\Vert }_{\infty }{\Vert Q\Vert }_{\infty }\max \left\{{\Vert {\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty },{\Vert {\left(A/\alpha \right)}^{-1}\Vert }_{\infty }\right\},$

其中，

${\Vert S\Vert }_{\infty }=1+{\Vert A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty },{\Vert Q\Vert }_{\infty }=1+{\Vert {\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\Vert }_{\infty }.$

因为A是SDD₁矩阵和$\alpha =N_2$ ，由引理8和定理6，有$A\left(\alpha \right)$ 和$A/\alpha$ 是SDD矩阵。那么$A\left(\alpha \right)$ 也是DSDD矩阵，故由定理2得：

$\begin{array}{c}{\Vert {\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty }\le \underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|+r_i\left(A\left(\alpha \right)\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\left(\alpha \right)\right)r_j\left(A\left(\alpha \right)\right)}\\ =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|+r_i^{\alpha }\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}=\phi ,\end{array}$ (2)

由$A/\alpha$ 是SDD矩阵，根据定理1和定理5得：

$\begin{array}{c}{\Vert {\left(A/\alpha \right)}^{-1}\Vert }_{\infty }\le \underset{j\in \overline{\alpha }}{\max }\frac{1}{\left|a_{jj}\right|-r_j\left(A/\alpha \right)}\\ \le \underset{j\in \overline{\alpha }}{\max }\frac{1}{\left|a_{jj}\right|-r_j^{\overline{\alpha }}\left(A\right)+{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(A\right)}{\left|a_{ii}\right|}},\end{array}$ (3)

再由引理5，有：

$\begin{array}{c}{\Vert S\Vert }_{\infty }=1+{\Vert A\left(\overline{\alpha },\alpha \right){\left[A\left(\alpha \right)\right]}^{-1}\Vert }_{\infty }\\ \le 1+\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{\left|a_{ji}\right|\left(1+\varphi r_i\left(A\left(\alpha \right)\right)\right)}{\left|a_{ii}\right|}}\\ =1+\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{\left|a_{ji}\right|\left(1+\phi r_i^{\alpha }\left(A\right)\right)}{\left|a_{ii}\right|}},\end{array}$ (4)

及

$\begin{array}{c}{\Vert Q\Vert }_{\infty }=1+{\Vert {\left[A\left(\alpha \right)\right]}^{-1}A\left(\alpha ,\overline{\alpha }\right)\Vert }_{\infty }\\ \le 1+\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|R_i\left(A\left(\alpha ,\overline{\alpha }\right)\right)+r_i\left(A\left(\alpha \right)\right)R_j\left(A\left(\alpha ,\overline{\alpha }\right)\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\left(\alpha \right)\right)r_j\left(A\left(\alpha \right)\right)}\\ =1+\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|R_i^{\overline{\alpha }}\left(A\right)+r_i^{\alpha }\left(A\right)R_j^{\overline{\alpha }}\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)},\end{array}$ (5)

其中，

$\varphi =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|+r_i\left(A\left(\alpha \right)\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i\left(A\left(\alpha \right)\right)r_j\left(A\left(\alpha \right)\right)}=\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|a_{jj}\right|+r_i^{\alpha }\left(A\right)}{\left|a_{ii}\right|\left|a_{jj}\right|-r_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}=\phi ,$

最后结合(1)、(2)、(4)和(5)，即可证明。

定理8 设$A=\left(a_{ij}\right)\in R^{n\times n}\left(n\ge 2\right)$ 是一个具有正对角元素的SDD₁矩阵且$\alpha =N_2\left(A\right)$ 。令$\tilde{A}=I-D+DA$ ，其中$D=diag\left(d_1,\cdots ,d_n\right)$ ，$0\le d_i\le 1$ 。则：

$\begin{array}{c}{\Vert {\left(I-D+DA\right)}^{-1}\Vert }_{\infty }\le \left(1+\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{d_j\left|a_{ji}\right|\left(1+\vartheta r_i^{\alpha }\left(A\right)\right)}{c_i}}\right)\cdot \left(1+\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{d_i\left[c_j{R}_i^{\overline{\alpha }}\left(A\right)+r_i^{\alpha }\left(A\right)R_j^{\overline{\alpha }}\left(A\right)\right]}{c_i{c}_j-d_i{d}_j{r}_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}\right)\\ \cdot \max \left\{\vartheta ,\underset{j\in \overline{\alpha }}{\max }\frac{1}{\min \left\{1,{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(A\right)}{a_{ii}}\right\}}\right\},\end{array}$

其中，$c_t=1-d_t+d_t{a}_{tt}=\underset{i\in \alpha }{\max }\left\{c_i\right\}$ ，$\vartheta =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{c_t+d_i{r}_i^{\alpha }\left(A\right)}{c_i{c}_j-d_i{d}_j{r}_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}$ 。

证明：由引理1知$\tilde{A}=I-D+DA$ 也是SDD₁矩阵，因此对矩阵${\Vert {\tilde{A}}^{-1}\Vert }_{\infty }={\Vert {\left(I-D+DA\right)}^{-1}\Vert }_{\infty }$ 的估计应用定理7的结论，有：

$\begin{array}{c}{\Vert {\left(I-D+DA\right)}^{-1}\Vert }_{\infty }\le \left(1+\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{\left|{\tilde{a}}_{ji}\right|\left(1+\tilde{\phi }{r}_i^{\alpha }\left(\tilde{A}\right)\right)}{\left|{\tilde{a}}_{ii}\right|}}\right)\cdot \left(1+\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|{\tilde{a}}_{jj}\right|R_i^{\overline{\alpha }}\left(\tilde{A}\right)+r_i^{\alpha }\left(\tilde{A}\right)R_j^{\overline{\alpha }}\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|\left|{\tilde{a}}_{jj}\right|-r_i^{\alpha }\left(\tilde{A}\right)r_j^{\alpha }\left(\tilde{A}\right)}\right)\\ \cdot \max \left\{\tilde{\phi },\underset{j\in \overline{\alpha }}{\max }\frac{1}{\left|{\tilde{a}}_{jj}\right|-r_j^{\overline{\alpha }}\left(\tilde{A}\right)+{\displaystyle \sum _{i\in \alpha }\left|{\tilde{a}}_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|}}\right\},\end{array}$

其中，$\tilde{\phi }=\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|{\tilde{a}}_{jj}\right|+r_i^{\alpha }\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|\left|{\tilde{a}}_{jj}\right|-r_i^{\alpha }\left(\tilde{A}\right)r_j^{\alpha }\left(\tilde{A}\right)}$ 。

由$\tilde{A}=I-D+DA$ ，有${\tilde{a}}_{ii}=1-d_i+d_i{a}_{ii}$ ，${\tilde{a}}_{ij}=d_i{a}_{ij}$ ，那么对任意的$i,j\in \alpha$ ，有：

$\begin{array}{c}\tilde{\phi }=\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|{\tilde{a}}_{jj}\right|+r_i^{\alpha }\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|\left|{\tilde{a}}_{jj}\right|-r_i^{\alpha }\left(\tilde{A}\right)r_j^{\alpha }\left(\tilde{A}\right)}\\ =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|1-d_j+d_j{a}_{jj}\right|+{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}}{\left|1-d_i+d_i{a}_{ii}\right|\left|1-d_j+d_j{a}_{jj}\right|-{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}{\displaystyle \sum _{s\in \alpha \backslash \left\{j\right\}}{d}_j\left|a_{js}\right|}},\end{array}$

令对任意的$i\in \alpha$ ，有$c_i=1-d_i+d_i{a}_{ii}$ ，且$c_t=\underset{i\in \alpha }{\max }\left\{c_i\right\}$ 。则：

$\begin{array}{c}\tilde{\phi }=\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{c_j+{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}}{c_i{c}_j-{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}{\displaystyle \sum _{s\in \alpha \backslash \left\{j\right\}}{d}_j\left|a_{js}\right|}}\le \underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{c_t+{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}}{c_i{c}_j-{\displaystyle \sum _{j\in \alpha \backslash \left\{i\right\}}{d}_i\left|a_{ij}\right|}{\displaystyle \sum _{s\in \alpha \backslash \left\{j\right\}}{d}_j\left|a_{js}\right|}}\\ =\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{c_t+d_i{r}_i^{\alpha }\left(A\right)}{c_i{c}_j-d_i{d}_j{r}_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}=\vartheta .\end{array}$ (6)

同理，

$\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{\left|{\tilde{a}}_{ji}\right|\left(1+\tilde{\phi }{r}_i^{\alpha }\left(\tilde{A}\right)\right)}{\left|{\tilde{a}}_{ii}\right|}}=\underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{d_j\left|a_{ji}\right|\left(1+\tilde{\phi }{d}_i{r}_i^{\alpha }\left(A\right)\right)}{\left|1-d_i+d_i{a}_{ii}\right|}}\le \underset{j\in \overline{\alpha }}{\max }{\displaystyle \sum _{i\in \alpha }\frac{d_j\left|a_{ji}\right|\left(1+\vartheta r_i^{\alpha }\left(A\right)\right)}{c_i}}.$ (7)

$\begin{array}{c}\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{\left|{\tilde{a}}_{jj}\right|R_i^{\overline{\alpha }}\left(\tilde{A}\right)+r_i^{\alpha }\left(\tilde{A}\right)R_j^{\overline{\alpha }}\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|\left|{\tilde{a}}_{jj}\right|-r_i^{\alpha }\left(\tilde{A}\right)r_j^{\alpha }\left(\tilde{A}\right)}=\underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{c_j{d}_i{R}_i^{\overline{\alpha }}\left(A\right)+d_i{r}_i^{\alpha }\left(A\right)d_j{R}_j^{\overline{\alpha }}\left(A\right)}{c_i{c}_j-d_i{d}_j{r}_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}\\ \le \underset{i\ne j}{\underset{i,j\in \alpha }{\max }}\frac{d_i\left[c_j{R}_i^{\overline{\alpha }}\left(A\right)+r_i^{\alpha }\left(A\right)R_j^{\overline{\alpha }}\left(A\right)\right]}{c_i{c}_j-d_i{d}_j{r}_i^{\alpha }\left(A\right)r_j^{\alpha }\left(A\right)}.\end{array}$ (8)

因为矩阵A是SDD₁矩阵，对任意的$i\in \overline{\alpha }$ ，有：

$\left|a_{jj}\right|>{\displaystyle \sum _{s\in \overline{\alpha }\backslash \left\{i\right\}}\left|a_{js}\right|}+{\displaystyle \sum _{i\in \alpha }\frac{r_i\left(A\right)}{\left|a_{ii}\right|}}\left|a_{ji}\right|,$

那么

$a_{jj}-{\displaystyle \sum _{s\in \overline{\alpha }\backslash \left\{j\right\}}\left|a_{js}\right|}+{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|}>{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\left(\frac{r_i\left(A\right)}{a_{ii}}+\frac{d_i{r}_i\left(A\right)}{1-d_i+d_i{a}_{ii}}\right)\ge {\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|\frac{r_i\left(A\right)}{a_{ii}},}$

再由引理9，有：

$\begin{array}{c}\underset{j\in \overline{\alpha }}{\max }\frac{1}{\left|{\tilde{a}}_{jj}\right|-r_j^{\overline{\alpha }}\left(\tilde{A}\right)+{\displaystyle \sum _{i\in \alpha }\left|{\tilde{a}}_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|}}=\underset{j\in \overline{\alpha }}{\max }\frac{1}{1-d_j+d_j{a}_{jj}-{\displaystyle \sum _{s\in \overline{\alpha }\backslash \left\{j\right\}}{d}_j\left|a_{js}\right|}+{\displaystyle \sum _{i\in \alpha }{d}_j\left|a_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|}}\\ =\underset{j\in \overline{\alpha }}{\max }\frac{1}{1-d_j+d_j\left(a_{jj}-{\displaystyle \sum _{s\in \overline{\alpha }\backslash \left\{j\right\}}\left|a_{js}\right|}+{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{\left|{\tilde{a}}_{ii}\right|}\right)}\\ \le \underset{j\in \overline{\alpha }}{\max }\frac{1}{\min \left\{1,a_{jj}-{\displaystyle \sum _{s\in \overline{\alpha }\backslash \left\{j\right\}}\left|a_{js}\right|}+{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(\tilde{A}\right)}{c_i}\right\}}\\ \le \underset{j\in \overline{\alpha }}{\max }\frac{1}{\min \left\{1,{\displaystyle \sum _{i\in \alpha }\left|a_{ji}\right|}\frac{r_i\left(A\right)}{a_{ii}}\right\}}.\end{array}$ (9)

最后结合公式(6)~(9)，即可证明。

4. 数值算例

例1

$A_1=\left(\begin{array}{ccc}2& -1& -1.2\\ -1& 2.1& -1\\ -1& -1& 4\end{array}\right).$

我们易验证$A_1$ 是SDD₁矩阵，且$N_1\left(A_1\right)=\left\{1\right\}$ ，$N_2\left(A_1\right)=\left\{2,3\right\}$ ，${\Vert A_1^{-1}\Vert }_{\infty }$ 的真实值为1.3344。由定理4得${\Vert A_1^{-1}\Vert }_{\infty }\le 10.0000$ ，由本文定理7得${\Vert A_1^{-1}\Vert }_{\infty }\le \text{2}\text{.6050}$ 。对${\Vert {\left(I-D+D{A}_1\right)}^{-1}\Vert }_{\infty }$ 的计算，取$d_i=0.5,\left(i=1,2,3\right)$ ，由文献[4]求出${\Vert {\left(I-D+D{A}_1\right)}^{-1}\Vert }_{\infty }\le 10.0000$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_1\right)}^{-1}\Vert }_{\infty }\le 3.0073$ 。当取$d_i=\frac{1}{3},\left(i=1,2,3\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_1\right)}^{-1}\Vert }_{\infty }\le 2.5401$ 。当取$d_i=\frac{1}{8},\left(i=1,2,3\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_1\right)}^{-1}\Vert }_{\infty }\le 1.7054$ 。

例2

$A_2=\left(\begin{array}{ccccc}6& 2& -1& -1& -1\\ -1.4& 5& 2& -1& -1\\ -1& 1& 4& -1& -1\\ -1& 3& -2& 8& -1\\ -1& 4& 3& -1& 10\end{array}\right).$

我们易验证$A_2$ 是SDD₁，且$N_1\left(A_2\right)=\left\{2,3\right\}$ ，$N_2\left(A_2\right)=\left\{1,4,5\right\}$ ，${\Vert A_2^{-1}\Vert }_{\infty }$ 的真实值为0.5237。由定理4得${\Vert A_2^{-1}\Vert }_{\infty }\le \text{6}\text{.3171}$ ，由本文定理7得${\Vert A_2^{-1}\Vert }_{\infty }\le 0.7078$ 。对${\Vert {\left(I-D+D{A}_2\right)}^{-1}\Vert }_{\infty }$ 的计算，取$d_i=0.5,\left(i=1,\cdots ,5\right)$ ，由文献[4]求出${\Vert {\left(I-D+D{A}_2\right)}^{-1}\Vert }_{\infty }\le 6.3171$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_2\right)}^{-1}\Vert }_{\infty }\le 3.2908$ 。当取$d_i=\frac{1}{3},\left(i=1,\cdots ,5\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_2\right)}^{-1}\Vert }_{\infty }\le 3.1931$ 。当取$d_i=\frac{1}{8},\left(i=1,\cdots ,5\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_2\right)}^{-1}\Vert }_{\infty }\le 2.7761$ 。

例3

$A_3=\left(\begin{array}{ccccccc}3& -1& & & & & \\ -1& 1& -1& & & & \\ & -1& 5& -1& & & \\ & & \ddots & \ddots & \ddots & & \\ & & & -1& 5& -1& \\ & & & & -1& 1& -1\\ & & & & & -1& 3\end{array}\right).$

我们易验证$A_3$ 是SDD₁，且$N_1\left(A_3\right)=\left\{2,n-1\right\}$ ，$N_2\left(A_3\right)=\left\{1,3,\cdots ,n-2,n\right\}$ 。由定理4，有${\Vert A_3^{-1}\Vert }_{\infty }\le 3.75$ ，由本文定理7，有${\Vert A_3^{-1}\Vert }_{\infty }\le 1.3162$ 。对${\Vert {\left(I-D+D{A}_3\right)}^{-1}\Vert }_{\infty }$ 的计算，取$d_i=0.5,\left(i=1,2,\cdots ,n\right)$ ，由文献[4]求出${\Vert {\left(I-D+D{A}_3\right)}^{-1}\Vert }_{\infty }\le 3.75$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_3\right)}^{-1}\Vert }_{\infty }\le 2.6278$ 。当取$d_i=\frac{1}{3},\left(i=1,2,\cdots ,n\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_3\right)}^{-1}\Vert }_{\infty }\le 2.1158$ 。当取$d_i=\frac{1}{8},\left(i=1,2,\cdots ,n\right)$ ，由本文定理8求出${\Vert {\left(I-D+D{A}_3\right)}^{-1}\Vert }_{\infty }\le 1.9915$ 。

上述数值实例的结果表明，与文献[4]中的相关结论相比，本文基于Schur补给出的SDD₁矩阵逆的无穷范数的新估计式(定理7)，以及SDD₁矩阵线性互补问题解的误差界估计式(定理8)是可行的、有效的，在一定条件下优于原有文献的相关结果。

NOTES

^*通讯作者。