$M{B}_{\pi }^R$-矩阵线性互补问题解的误差界新估计

A New Estimate of Error Bounds for Solutions of $M{B}_{\pi }^R$-Matrix Linear Complementarity Problems

摘要: 基于线性互补问题的等价形式，结合不等式的放缩技巧，给出了MBπR-矩阵线性互补问题解的误差界新估计式。数值实例说明，该误差界改进了现有文献的有关结果。

Abstract: Based on the equivalent form of the linear complementarity problem, the error bound for solutions ofMBπR-matrix linear complementarity problemsis obtained by combining the inequality scaling technique. Numerical examples show that this error bound improves the results of the existing literature.

1. 引言

线性互补问题应用广泛，在双矩阵对策的纳什平衡点，轴颈轴承的接触问题和自由边界等问题中有各种应用(见[1]-[3])。线性互补问题(Linear Complementarity Problem)是指寻找一个向量$x\in R^n$ ，使

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

成立，其中$M\in R^{n\times n},q\in R^n$ ，简记为$\text{LCP}\left(M,q\right)$ 。当M是P-矩阵时，对任何向量$q\in R^n$ (1)有唯一解[4]。

2006年，文献[5]给出了当M为P-矩阵时，相应的线性互补问题解的误差界估计式：

${\Vert x-x^{*}\Vert }_{\infty }\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^{*}$ 是LCP的解，$r\left(x\right)=\min \left\{x,Mx+q\right\},D=\text{diag}\left(d_i\right),0\le d_i\le 1$ 。

近年来，许多学者基于文献[6]的研究，对一些特殊矩阵线性互补问题解的误差界进行了研究，如SB-矩阵[4] [6]，P-矩阵[5] [7]，具有正对角元素的H-矩阵[7] [8]，B-矩阵[9]，B^S-矩阵[10]，DB-矩阵[11]和∑SDD-矩阵[12]。

2014年，文献[13]给出了$M{B}_{\pi }^R$ -矩阵线性互补问题解的误差界。设$M=\left(m_{ij}\right)\in R^{n\times n}$ 是$M{B}_{\pi }^R$ -矩阵，$B^{+}\left(\pi \right)=\left(b_{ij}\left(\pi \right)\right)\in R^{n\times n}$ ，$i,j\in \left\{1,2,\cdots ,n\right\}$ ，$C^{+}\left(\pi \right)\in R^{n\times n}$ 。

令${\beta }_i\left(\pi \right)=b_{ii}\left(\pi \right)-{\displaystyle \sum }_{\begin{array}{c}j\ne i\end{array}}\left|b_{ij}\left(\pi \right)\right|$ ，$\beta \left(\pi \right)=\underset{i\in N}{\min }\left\{{\beta }_i\left(\pi \right)\right\}$ ，则

$\underset{d\in \left[0,1\right]}{\max }{\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }\le \frac{n-1}{\min \left\{\beta \left(\pi \right),1\right\}}.$

本文利用线性互补问题的等价条件，得到了P-矩阵的一个子类$M{B}_{\pi }^R$ -矩阵的LCP新误差界。

本文第2节主要介绍相关定义、引理及符号说明；第3节中，给出了$M{B}_{\pi }^R$ -矩阵线性互补问题解的新误差界，并讨论了在不同参数下$M{B}_{\pi }^R$ -矩阵线性互补问题解的估计式结果；最后，通过数值例子验证了该误差界估计式的有效性和可行性。

2. 定义及符号说明

为方便叙述，本文先给出几个符号说明，$R^{n\times n}$ 表示$n\times n$ 阶实矩阵的集合，$N=\left\{1,2,\cdots ,n\right\}$ 。

定义1 [14]设$M=\left(m_{ij}\right)\in R^{n\times n}$ ，若$m_{ij}\le 0,\forall i\ne j,i,j\in N$ ，则称M为Z-阵，Z-阵的全体记为Z。

定义2 [14]设$M=\left(m_{ij}\right)\in R^{n\times n}$ ，若$\left|m_{ii}\right|>{\displaystyle \sum }_{i\ne j}\left|m_{ij}\right|,i\in N$ ，则称M为严格对角占优矩阵，记为SDD阵。若$\left|m_{ii}\right|\left|m_{jj}\right|>{\displaystyle \sum }_{i\ne k}\left|m_{ik}\right|{\displaystyle \sum }_{j\ne k}\left|m_{jk}\right|,\forall j\ne i,i,j\in N$ ，则称M为双严格对角占优矩阵。

定义3 [15]设$M=\left(m_{ij}\right)\in R^{n\times n},\forall i\ne j,i,j\in N$ ，若M的所有主子式都大于零，则称M为P-阵。

定义4 [15]设$A\in Z^{n\times n}=\left\{\left(a_{ij}\right)\in R^{n\times n}:a_{ij}\le 0,i\ne j,i,j\in N\right\}$ ，若$A=sI-B,B\ge 0,s>\rho \left(B\right)$ ，其中$\rho \left(B\right)$ 为

矩阵B的谱半径，则称A为M-矩阵。若A的所有顺序主子式均大于零(或$A^{-1}>0$ 等)，则称A是非奇异M-矩阵。M-矩阵的主对角线元素全是非负的，而其它一切元素全是非正。

定义5 [15] A的比较矩阵：$M\left(A\right)=\left(m_{ij}\right)\in R^{n\times n},i,j\in N$ 称为A的比较矩阵，其中：

$m_{ij}=\{\begin{array}{l}\left|a_{ii}\right|,i=j,\\ -\left|a_{ij}\right|,i\ne j.\end{array}$

定义6 [15]如果A的比较矩阵是非奇异M-矩阵，则称其为非奇异H-矩阵。

定义7 [16]设$M=\left(m_{ij}\right)\in R^{n\times n}$ ，满足$R_i\left(M\right)={\displaystyle \sum }_{j\in N}{m}_{ij}>0,\forall i\in N$ ，$R={\left[R_1\left(M\right),\cdots ,R_n\left(M\right)\right]}^{\text{T}}$ ，且存在向量$\pi ={\left[{\pi }_1,\cdots ,{\pi }_n\right]}^{\text{T}}$ ，满足$0\le {\displaystyle \sum }_{j\in N}{\pi }_j\le 1,\forall j\ne i,i,j\in N$ ，

${\pi }_j{R}_i\left(M\right)>m_{ij},$

则称为$B_{\pi }^R$ -阵，$B_{\pi }^R$ -阵的全体记为$B_{\pi }^R$ 。

定义1 [17]设$M=\left(m_{ij}\right)\in R^{n\times n}$ ，若存在$\pi ={\left[{\pi }_1,\cdots ,{\pi }_n\right]}^{\text{T}}$ ，${\pi }_{j_t}>0$ ，${\displaystyle \sum }_{j\in N}{\pi }_{j_t}\le 1$ ，${\pi }_{j_t}\ne i$ ，$j_t\ne t$ ，$i\ne t$ ，$i,{\pi }_{j_t}\in N$ ，使$m_{ii}-\frac{r_i^{+}}{n{\pi }_{j_t}}>0$ ，且使得$M=B^{+}\left(\pi \right)+C^{+}\left(\pi \right)$ 的分裂如下(2)式，若$B^{+}\left(\pi \right)$ 是非奇异M-阵，则称M为$M{B}_{\pi }^R$ -矩阵，$M{B}_{\pi }^R$ -矩阵的全体记为$M{B}_{\pi }^R$ 。

$B^{+}\left(\pi \right)=\left[\begin{array}{ccc}{m}_{11}-\frac{r_1^{+}}{n{\pi }_{j_1}}& \cdots & m_{1n}-\frac{r_1^{+}}{n{\pi }_{j_1}}\\ ⋮& \ddots & ⋮\\ m_{n1}-\frac{r_n^{+}}{n{\pi }_{j_n}}& \cdots & m_{nn}-\frac{r_n^{+}}{n{\pi }_{j_n}}\end{array}\right],$

$C^{+}\left(\pi \right)=\left[\begin{array}{ccc}\frac{r_1^{+}}{n{\pi }_{j_1}}& \cdots & \frac{r_1^{+}}{n{\pi }_{j_1}}\\ ⋮& \ddots & ⋮\\ \frac{r_n^{+}}{n{\pi }_{j_n}}& \cdots & \frac{r_n^{+}}{n{\pi }_{j_n}}\end{array}\right],$ (2)

其中$r_i^{+}=\underset{k\ne i}{\max }\left\{0,m_{ik}\right\}$ 。

下面介绍几个与本文相关的引理。

引理1 [17]若$M=\left(m_{ij}\right)\in R^{n\times n},i,j\in N$ 是严格对角占优或双严格对角占优Z-阵，则M是非奇异M-阵。

引理2 [18]若$M=\left(m_{ij}\right)\in R^{n\times n},i,j\in N$ 为$M{B}_{\pi }^R$ -矩阵，则M是P-阵。

引理3 [19]矩阵A是一个M-矩阵当且仅当A的对角元素为正，并且存在正对角矩阵X，AX是行SDD。

引理4 [20]单位矩阵I的Sherman-Morrison公式是：

${\left(I+u{v}^{\text{T}}\right)}^{-1}=I-\frac{u{v}^{\text{T}}}{1+v^{\text{T}}u},$

u和v是两个给定的向量且$1+v^{\text{T}}u\ne 0$ 。

引理5 [21]如果A是一个SDD矩阵，那么对于任意矩阵B：

${\Vert A^{-1}B\Vert }_{\infty }\le \underset{i}{\max }\frac{{\left(\left|B\right|e\right)}_i}{{\left(\langle A\rangle e\right)}_i},$ (3)

其中$\langle A\rangle$ 是A的比较矩阵，$\left({\left|B\right|}_{ij}\right)=\left|b_{ij}\right|$ ，e是一个列向量，其元素都是1。

引理6 [22]设A为M-矩阵，$D_A$ 为A的对角部分，则对于任意非负对角矩阵$D\le I$ 和正对角矩阵$\Omega$ ，

${\Vert {\left[\left(I-D\right)\Omega +DA\right]}^{-1}\Vert }_{\infty }\le {\Vert {\left(\Omega A\right)}^{-1}\max \left(D_A,\Omega \right)\Vert }_{\infty },$ (4)

其中$\max \left(D_A,\Omega \right)$ 为对角矩阵，其对角线元${\left(\max \left(D_A,\Omega \right)\right)}_{ii}=\max \left({\left(D_A\right)}_{ii},{\Omega }_{ii}\right),i=1,2,\cdots ,n$ 。

3. 主要结果

在本文中，引入以下等价的LCP [8]：

$\tilde{\Omega }M\Omega z+\tilde{\Omega }q\ge 0,z\ge 0,z^{\text{T}}\left(\tilde{\Omega }M\Omega z+\tilde{\Omega }q\right)=0$(5)

此处$\Omega =\text{diag}\left({\omega }_1,\cdots ,{\omega }_n\right),\tilde{\Omega }=\text{diag}\left({\tilde{\omega }}_1,\cdots ,{\tilde{\omega }}_n\right)$为正对角矩阵，则$x^{*}$ 是LCP(1)的解当且仅当${\tilde{\Omega }}^{-1}{x}^{*}$ 是LCP(5)的解。易见，如果取$\Omega =\tilde{\Omega }=I$ ，则LCP(5)可约化为LCP(1)。通过选择适当特定的正对角矩阵$\Omega$ 和$\tilde{\Omega }$ ，可以得到一些更清晰的误差界限。

接下来，给出该等价线性互补问题解的误差范围。设$x^{*}$ 是LCP(1)的解。根据[8]中的定理2.3，有：

${\Vert x-x^{*}\Vert }_{\infty }\le {\max }_{{\omega }_i>0,{\tilde{\omega }}_i>0}\left\{\left[\underset{d_i\in \left[0,1\right]}{\max }{\Vert \Omega {\left(I-D+D\tilde{\Omega }M\Omega \right)}^{-1}\Vert }_{\infty }\right]{\Vert r_{\tilde{\Omega }}\left({\Omega }^{-1}x\right)\Vert }_{\infty }\right\},$ (6)

此处

$r_{\tilde{\Omega }}\left({\Omega }^{-1}x\right)=\min \left(\tilde{\Omega }Mx+\tilde{\Omega }q,{\Omega }^{-1}x\right),$ (7)

$\Omega$ 和$\tilde{\Omega }$ 为正对角矩阵，且$D=\text{diag}\left(d_i\right)$ ，且$0\le d_i\le 1$ ，显而易见，当$\Omega =\tilde{\Omega }=I$ ，可表示为：

$r\left(x\right)=r_I\left(I^{-1}x\right)=\min \left(Mx+q\right).$ (8)

定理1：设$M=B^{+}\left(\pi \right)+C^{+}\left(\pi \right)$ 是一个$M{B}_{\pi }^R$ -矩阵，其中$B^{+}\left(\pi \right)$ 和$C^{+}\left(\pi \right)$ 由(2)给出，且设$x^{*}$ 是LCP(1)的一个解。则存在一个正对角矩阵$H=\text{diag}\left(h_1,\cdots ,h_n\right)$ ，使得对于任意$x\in R^n$ ，有：

${\Vert x-x^{*}\Vert }_{\infty }\le \underset{{\omega }_i>0,{\tilde{\omega }}_i>0}{\min }\left\{\mu {\Vert H\Vert }_{\infty }\underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right){\Vert r_{\tilde{\Omega }}\left({\Omega }^{-1}x\right)\Vert }_{\infty }\right\},$ (9)

此处

$\Omega =\text{diag}\left({\omega }_1,\cdots ,{\omega }_n\right),\tilde{\Omega }=\text{diag}\left({\tilde{\omega }}_1,\cdots ,{\tilde{\omega }}_n\right),$

另外，当M是一个Z-矩阵时，可知：

${\Vert x-x^{*}\Vert }_{\infty }\le \underset{{\omega }_i>0,{\tilde{\omega }}_i>0}{\min }\left\{\mu {\Vert H\Vert }_{\infty }{\Vert r_{\tilde{\Omega }}\left({\Omega }^{-1}x\right)\Vert }_{\infty }\right\},$ (10)

此处

$\begin{array}{l}\mu =\min \left\{{\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\max \left(D_{B^{+}\left(\pi \right)}\Omega ,{\tilde{\Omega }}^{-1}\right)\Vert }_{\infty },\max \left\{\frac{1}{\xi },\kappa \right\}\right\},\\ {\xi }_i=\left(b_{ii}{h}_i-{{\displaystyle \sum }}_{j\ne i}\left|b_{ij}\right|h_j\right){\tilde{\omega }}_i,\xi =\underset{i\in \left\{1,\cdots ,n\right\}}{\min }\left\{{\xi }_i\right\},\kappa =\underset{i\in \left\{1,\cdots ,n\right\}}{\max }\frac{{\omega }_i}{h_i}.\end{array}$(11)

证明：根据定理的假设，$B^{+}\left(\pi \right)$ 是一个M矩阵。由引理4可知，存在一个正对角矩阵H，使得$B^{+}\left(\pi \right)H$ 是按行严格对角占优的，且$C^{+}\left(\pi \right)H$ 仍然是秩为1的非负矩阵。记$\widehat{M}:=MH$ ，$\widehat{B}\left(\pi \right):=B^{+}\left(\pi \right)H$ ，$\widehat{C}\left(\pi \right):=C^{+}\left(\pi \right)H$ ，那么有$\widehat{M}=\widehat{B}\left(\pi \right)+\widehat{C}\left(\pi \right)$ 。因此，对于某个对角矩阵$D=\text{diag}\left(d_i\right)$ ，且$0\le d_i\le 1$ ，可以得到：

$\begin{array}{c}\Omega {\left(I-D+D\tilde{\Omega }M\Omega \right)}^{-1}={\left(\left(I-D\right){\Omega }^{-1}+D\tilde{\Omega }M\right)}^{-1}\\ =H{\left(\left(I-D\right){\Omega }^{-1}H+D\tilde{\Omega }MH\right)}^{-1}\\ =H{\left(\left(I-D\right){\Omega }^{-1}H+D\tilde{\Omega }B\left(\pi \right)H+D\tilde{\Omega }C\left(\pi \right)H\right)}^{-1}\\ =H{\left(\left(I-D\right){\Omega }^{-1}H+D\tilde{\Omega }\widehat{B}\left(\pi \right)+D\tilde{\Omega }\widehat{C}\left(\pi \right)\right)}^{-1},\end{array}$ (12)

令${\widehat{B}}_D=\left(I-D\right){\Omega }^{-1}H+D\tilde{\Omega }\widehat{B}\left(\pi \right)$ ，${\widehat{C}}_D=D\tilde{\Omega }\widehat{C}\left(\pi \right)$ ，不难看出，${\widehat{B}}_D$ 是一个有正对角线的严格对角占优矩阵，${\widehat{C}}_D$ 仍是一个秩为1的矩阵。由(12)得：

$\Omega {\left(I-D+D\tilde{\Omega }M\Omega \right)}^{-1}=H{\left({\widehat{B}}_D+{\widehat{C}}_D\right)}^{-1}=H{\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}{\widehat{B}}_D^{-1},$

所以

${\Vert \Omega {\left(I-D+D\tilde{\Omega }M\Omega \right)}^{-1}\Vert }_{\infty }\le {\Vert H\Vert }_{\infty }{\Vert {\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}\Vert }_{\infty }{\Vert {\widehat{B}}_D^{-1}\Vert }_{\infty }.$ (13)

先证明

${\Vert {\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}\Vert }_{\infty }\le \underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right),$ (14)

因为对角矩阵H是正的，且矩阵$B^{+}\left(\pi \right)$ 是Z-矩阵，所以$\widehat{B}\left(\pi \right)=B^{+}\left(\pi \right)H$ 和${\widehat{B}}_D$ 对角线也为正的。另外，${\widehat{B}}_D$ 是一个正对角线的严格对角占优的Z-矩阵，且由引理1知，${\widehat{B}}_D$ 也是一个M-矩阵，所以${\widehat{B}}_D^{-1}={\overline{b}}_{ij}$

是非负的。由于${\widehat{C}}_D=D\tilde{\Omega }\widehat{C}\left(\pi \right)=\left(D\tilde{\Omega }{C}^{+}\left(\pi \right)\right)H$ 是一个秩为1的非负矩阵，可以写成${\widehat{C}}_D={\left({\overline{c}}_1,\cdots ,{\overline{c}}_n\right)}^{\text{T}}\left(h_1,\cdots ,h_n\right)$，${\overline{c}}_i=d_i{\tilde{\omega }}_i\frac{r_i^{+}}{n{\pi }_{j_t}}\ge 0$ ，$i\in N$ 。所以有${\widehat{B}}_D^{-1}{\widehat{C}}_D={\left(u_1,\cdots ,u_n\right)}^{\text{T}}\left(h_1,\cdots ,h_n\right)$，其中$u_i={\displaystyle \sum _{k=1}^n{\overline{b}}_{ij}{\overline{c}}_i\ge 0}$ ，令向量$u={\left(u_1,\cdots ,u_n\right)}^{\text{T}}$ ，向量$h={\left(h_1,\cdots ,h_n\right)}^{\text{T}}$ 。则${\widehat{B}}_D^{-1}{\widehat{C}}_D=u{h}^{\text{T}}$，通过引理5

${\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}={\left(I+u{h}^{\text{T}}\right)}^{-1}=I-\frac{u{h}^{\text{T}}}{1+h^{\text{T}}u},$

对上式两边取无穷大范数，得到：

$\begin{array}{c}{\Vert {\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}\Vert }_{\infty }={\Vert I-\frac{u{h}^{\text{T}}}{1+h^{\text{T}}u}\Vert }_{\infty }\\ =\underset{i}{\max }\left(1-\frac{u_i{h}_i}{1+{{\displaystyle \sum }}_{k=1}^n{u}_k{h}_k}+\frac{u_i{\displaystyle {\sum }_{j\ne i}{h}_j}}{1+{{\displaystyle \sum }}_{k=1}^n{u}_k{h}_k}\right)\end{array}$

$\begin{array}{c}=\underset{i}{\max }\left(1+\frac{{{\displaystyle \sum }}_{j=1}^n{h}_j-2h_i}{\frac{1}{u_i}+h_i+{\displaystyle {\sum }_{j\ne i}\frac{u_j}{u_i}{h}_j}}\right)\\ \le \underset{i}{\max }\left(1+\frac{{{\displaystyle \sum }}_{j=1}^n{h}_j-2h_i}{h_i}\right)\\ \le \underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right).\end{array}$

接下来，给出了${\Vert {\widehat{B}}_D^{-1}\Vert }_{\infty }$ 的上界。根据引理7，很容易证明下列不等式成立：

${\Vert {\widehat{B}}_D^{-1}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\max \left(D_{B^{+}\left(\pi \right)}\Omega ,{\tilde{\Omega }}^{-1}\right)\Vert }_{\infty },$ (15)

另一方面，由于${\widehat{B}}_D$ 是一个具有正对角线的严格对角占优矩阵，并且$\left|b_{ii}\right|=b_{ii}$ ，那么根据引理6，对于每个矩阵D：

${\widehat{B}}_D^{-1}{}_{\infty }\le \frac{1}{\underset{i}{\min }{\alpha }_i^D}=\frac{1}{\underset{i}{\min }\frac{\left(1-d_i\right)h_i}{{\omega }_i}+d_i{\xi }_i},$

其中

${\alpha }_i^D:=\frac{\left(1-d_i\right)h_i}{{\omega }_i}+d_i{\omega }_i\left(b_{ii}{h}_i-{{\displaystyle \sum }}_{j\ne i}\left|b_{ij}\right|h_j\right),$

设$k\in \left\{1,\cdots ,n\right\}$ 使得${\alpha }_k^D=\min \left\{{\alpha }_i^D\right\}$ ，然后得到：

${\Vert {\widehat{B}}_D^{-1}\Vert }_{\infty }\le \frac{1}{\frac{\left(1-d_k\right)h_k}{{\omega }_k}+d_k{\xi }_k}\le \max \left\{\frac{1}{{\xi }_k},\frac{{\omega }_k}{h_k}\right\}\le \max \left\{\frac{1}{\xi },\kappa \right\},$ (16)

式子(11)中给出了${\xi }_i,\xi ,\kappa$ 。根据式(15)和(16)可得：

${\Vert {\widehat{B}}_D^{-1}\Vert }_{\infty }\le \min \left\{{\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\max \left(D_{B^{+}\left(\pi \right)}\Omega ,{\tilde{\Omega }}^{-1}\right)\Vert }_{\infty },\max \left\{\frac{1}{\xi },\kappa \right\}\right\},$ (17)

将公式(6)，(13)，(14)，(17)结合在一起，得到界(9)。

特别地，若M是一个Z-矩阵，那么$C^{+}\left(\pi \right)$ 和${\widehat{C}}_D$ 都为0，易得${\Vert {\left(I+{\widehat{B}}_D^{-1}{\widehat{C}}_D\right)}^{-1}\Vert }_{\infty }=1$ ，则根据式(13)，式(17)得：

${\Vert x-x^{*}\Vert }_{\infty }\le \underset{{\omega }_i>0,{\tilde{\omega }}_i>0}{\min }\left\{\mu {\Vert H\Vert }_{\infty }{\Vert r_{\tilde{\Omega }}\left({\Omega }^{-1}x\right)\Vert }_{\infty }\right\}.$ □

注：定理1中给出的正对角矩阵H可以用以下方法求得，对于给定的正向量$P>0$ (例如，$P=e:={\left(1,\cdots ,1\right)}^{\text{T}}$ )，因为$B^{+}\left(\pi \right)$ 是M-矩阵，所以${\left(B^{+}\left(\pi \right)\right)}^{-1}\ge 0$ ，通过求解系统$B^{+}\left(\pi \right)h=P$ 得到一个正解，则可以取$H=\text{diag}\left(h_1,h_2,\cdots ,h_n\right)$ 。实际上，对于给定的正向量P，也可以使用一些收敛分裂迭代方法(例如Gauss-Seidel方法)来得到这个h。

接下来，通过在界(9)中取几个特殊的对角参数矩阵，可以获得形式更简单的界。

如果在定理1中，取$\Omega =\tilde{\Omega }=I$ ，则可以得到以下推论：

推论1 设$M=B^{+}\left(\pi \right)+C^{+}\left(\pi \right)$ 是一个$M{B}_{\pi }^R$ -矩阵，其中$B^{+}\left(\pi \right)$ 和$C^{+}\left(\pi \right)$ 由给出，且设$x^{*}$ 是LCP(1)的一个解。则存在一个正对角矩阵$H=\text{diag}\left(h_1,h_2,\cdots ,h_n\right)$ ，使得对于任意$x\in R^n$ ，有：

${\Vert x-x^{*}\Vert }_{\infty }\le \mu {\Vert H\Vert }_{\infty }\underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right){\Vert r\left(x\right)\Vert }_{\infty },$ (18)

另外，当M是一个Z-矩阵时，特别地有：

${\Vert x-x^{*}\Vert }_{\infty }\le \mu {\Vert H\Vert }_{\infty }{\Vert r\left(x\right)\Vert }_{\infty },$ (19)

这里的$\mu ,{\xi }_i,\xi ,\kappa$ 由(11)给出，$r\left(x\right)$ 由(8)给出。

下面给出[13]中的例子表明本文的结果更好，

$M=\left(\begin{array}{cc}1& -4\\ 5& 7\end{array}\right),$

易知它不是H-矩阵，但却是一个P-阵，还是一个$M{B}_{\pi }^R$ -矩阵，根据定义$r_1^{+}=0,r_2^{+}=5$ ，这里分别取$\pi ={\left(\frac{26}{54},\frac{13}{54}\right)}^{\text{T}}$ ，通过(19)的简单计算得到：

${\Vert x-x^{*}\Vert }_{\infty }\le 5.592{\Vert r\left(x\right)\Vert }_{\infty },$

据[13]中的误差界计算，

${\Vert x-x^{*}\Vert }_{\infty }\le 5.741{\Vert r\left(x\right)\Vert }_{\infty },$

比较上面的误差界，容易看出本文的误差界结果更优。

推论2 根据定义，定理1可以根据选取特定对角参数矩阵$\Omega$ 和$\tilde{\Omega }$ ，从而得出形式更简单的误差界：

取定理1中的$\Omega =D_{B^{+}\left(\pi \right)}^{-1}$ ，$\tilde{\Omega }=I$ ，得到(9)和(10)对应的误差界：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\Vert }_{\infty }{\Vert H\Vert }_{\infty }\underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right){\Vert r\left(D_{B^{+}\left(\pi \right)}x\right)\Vert }_{\infty },$ (20)

当M是一个Z-矩阵时，有：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\Vert }_{\infty }{\Vert H\Vert }_{\infty }{\Vert r\left(D_{B^{+}\left(\pi \right)}x\right)\Vert }_{\infty }.$

取定理1中的$\Omega =I$ ，$\tilde{\Omega }=D_{B^{+}\left(\pi \right)}^{-1}$ ，得到(9)和(10)对应的误差界：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}{D}_{B^{+}\left(\pi \right)}\Vert }_{\infty }{\Vert H\Vert }_{\infty }\underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right){\Vert r_{D_{B^{+}\left(\pi \right)}^{-1}}\left(x\right)\Vert }_{\infty ,}$ (21)

当M是一个Z-矩阵时，有：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}{D}_{B^{+}\left(\pi \right)}\Vert }_{\infty }{\Vert H\Vert }_{\infty }{\Vert r_{D_{B^{+}\left(\pi \right)}^{-1}}\left(x\right)\Vert }_{\infty }.$

取定理1中的$\Omega =\text{diag}\left(B^{+}{\left({\pi }^{-1}\right)}^{-1}e\right)$ ，$\tilde{\Omega }=I$ ，得到(9)和(10)对应的误差界：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\Vert }_{\infty }{\Vert H\Vert }_{\infty }\underset{i}{\max }\left({{\displaystyle \sum }}_{j\ne i}^n\frac{h_j}{h_i}\right){\Vert r\left({\Omega }^{-1}x\right)\Vert }_{\infty },$ (22)

当M是一个Z-矩阵时，有：

${\Vert x-x^{*}\Vert }_{\infty }\le {\Vert {\left(B^{+}\left(\pi \right)H\right)}^{-1}\Vert }_{\infty }{\Vert H\Vert }_{\infty }{\Vert r\left({\Omega }^{-1}x\right)\Vert }_{\infty }.$

4. 数值算例

在本节中，给出了两个数值算例，将本文的误差界与原有的误差界进行比较。

算例1 考虑矩阵$M_1\in R^{n\times n}$ ，向量$q\in R^n$ ，考虑它的LCP(1)：

$M_1=\left(\begin{array}{ccc}2& -1& -0.5\\ -1& 3.05& -2\\ -0.9& -1.9& 5.15\end{array}\right)$

可知此处设$n=3$ ，由$r_i^{+}$ 的定义可知，$r_1^{+}=r_2^{+}=r_3^{+}=0$ ，取一组，${\pi }_1={\pi }_2={\pi }_3=\frac{1}{3}$ ，通过分裂(2)易知$B^{+}\left(\pi \right)$ 是一个非奇异M-矩阵，所以M是一个$M{B}_{\pi }^R$ 矩阵。

则由文献[13]中估计式的结果可得：

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

由本文推论1中估计式的结果可得：

$\underset{d\in \left[0,1\right]}{\max }{\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }\le \mathrm{4.390.}$

对比两式结果可知，本文的估计式在一定程度上大大改进了原有的结果，使得误差界更小，结果更精确。当原估计式中的$\beta \left(\pi \right)$ 趋近于0时，则显然$\underset{d\in \left[0,1\right]}{\max }{\Vert {\left(I-D+DM\right)}^{-1}\Vert }_{\infty }$ 趋近无穷大，则其误差越大。

算例2 考虑矩阵$M_2\in R^{n\times n}$ ，向量$q\in R^n$ ，考虑它的LCP(1)：

$M_2=\left[\begin{array}{cccccc}100& 0.1& 0& \cdots & 0& 0\\ -0.1& 100& 0.1& \cdots & 0& 0\\ 0& -0.1& 100& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 100& 0.1\\ 0& 0& 0& \cdots & -0.1& 100\end{array}\right]$

设$n=500$ ，由$r_i^{+}$ 的定义可知，$r_1^{+}=r_2^{+}=\cdots =r_{499}^{+}=0.1$ ，$r_{500}^{+}=0$ ，取一组${\pi }_{500}=\frac{1}{1000}$ ， ${\pi }_1={\pi }_2={\pi }_3={\pi }_4=\cdots ={\pi }_{499}=\frac{1}{500}$ ，得到以下分解，易知$B^{+}\left(\pi \right)$ 是一个非奇异M-矩阵，所以M是一个$M{B}_{\pi }^R$ 矩阵。

$B^{+}\left(\pi \right)=\left[\begin{array}{cccccc}100-0.1& 0.1-0.1& 0-0.1& \cdots & 0-0.1& 0-0.1\\ -0.1-0.1& 100-0.1& 0.1-0.1& \cdots & 0-0.1& 0-0.1\\ 0-0.1& -0.1-0.1& 100-0.1& \cdots & 0-0.1& 0-0.1\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0-0.1& 0-0.1& 0& \cdots & 100-0.1& 0.1-0.1\\ 0& 0& 0& \cdots & -0.1& 100\end{array}\right],$

$C^{+}\left(\pi \right)=\left[\begin{array}{ccc}\frac{0.1}{500{\pi }_1}& \cdots & \frac{0.1}{500{\pi }_1}\\ ⋮& \ddots & ⋮\\ \frac{0}{500{\pi }_n}& \cdots & \frac{0}{500{\pi }_n}\end{array}\right]$

用以下算法，得到图1。

然后通过将x替换为$x^{\left(k\right)}$ 来分析误差界，其中$x^{\left(k\right)}$ 是由Bai在[23]中提出的基于模的矩阵分裂迭代方法生成的。

基于模的矩阵分裂迭代算法：设$M=M_1-N_1$ 是矩阵$M\in R^{n\times n}$ 的分解，${\Omega }_1$ 是一个正对角矩阵$\gamma$ 是一个正的常数，给定初始向量$y^{\left(1\right)}\in R^n$ ，计算$y^{\left(k+1\right)}\in R^n$ 是通过求解线性系统：

$\left({\Omega }_1+M_1\right)y^{\left(k+1\right)}=N_1{y}^{\left(k\right)}+\left({\Omega }_1-M\right)\left|y^{\left(k\right)}\right|-\gamma q.$

设$x^{\left(k\right)}=\frac{1}{\gamma }\left(\left|y^{\left(k\right)}\right|+y^{\left(k\right)}\right)$ ，对于$k=1,2,\cdots$ 直到迭代序列${\left\{x^{\left(k\right)}\right\}}_{k=0}^{+\infty }\in R_{+}^n$ 收敛。

令$q=-4e$ ，此处$e={\left(1,1,\cdots ,1\right)}^{\text{T}}$ ，$M_1=D_M$ ，$y^{\left(0\right)}=e$ ，${\Omega }_1=M_1+I$ ，$\gamma =1$ 。算法通过8次迭代后收敛到$x^{\left(8\right)}$ ，精度为10⁻⁷。在图1中给出了这些界(18) (20) (21) (22)以及文献[13]的界。并将$x^{\left(i\right)}\left(i=1,\text{2,}\cdots ,8\right)$ 代入到这些界的估计式中得到下面的图1。

Figure 1. Error bound for linear complementarity problem of M₂

图1. M的线性互补问题的误差界

从图中可以看出，其中横坐标为x的迭代次数，纵坐标为误差界的自然对数。随着x迭代次数的增加，整体曲线均呈下降趋势。虽然当x只迭代了1次时，文献[13]的结果略微优于其他接结果，但是自当x2次以上时，可以观察到，界(22)和界(21)重合且大大优于文献[13]的界。不仅如此，还可以观察到，此时界(22)的结果也优于原文献[13]的计算结果稍大。通过该数值算例，通过多次迭代本文的估计结果在多数情况下优于原文献的结果，并且可通过选择不同的正对角参数矩阵$\Omega$ 和$\tilde{\Omega }$ ，得到更加有效的误差界估计结果。

5. 总结

本文深入探讨了矩阵线性互补问题(LCP)的解的误差界限，提出了一种基于特定对角参数矩阵$\Omega$ 和$\tilde{\Omega }$ 的新颖方法。通过对等价形式的LCP进行分析，我们成功推导出了$M{B}_{\pi }^R$ -矩阵的新误差界，这些界在不同的对角参数矩阵$\Omega$ 和$\tilde{\Omega }$ 的下，为$M{B}_{\pi }^R$ -矩阵的LCP提供了更优化的误差接。本研究采用了等价线性互补问题新的放缩技巧，并结合了$M{B}_{\pi }^R$ -矩阵的分裂形式，显著改进了文献[13]中的原有估计。特别是，当原估计式中的参数$\beta \left(\pi \right)$ 趋于零时，原估计结果可能趋向于无穷大，而本文提出的新界限则在很大程度上克服了这一问题。

尽管如此，本研究也存在一些局限性，例如在实际应用中如何选择最优的对角参数矩阵$\Omega$ 和$\tilde{\Omega }$ 以获得更精确的估计结果，这仍是一个值得研究的问题。未来的工作将集中于解决这一挑战，并探索本文方法在具有类似分裂形式的其他矩阵类上的适用性，拓展矩阵线性互补问题解的深度和广度。

NOTES

^*通讯作者。