M 矩阵的线性互补问题的误差界

房喜明

(肇庆学院数学与统计学院，肇庆 526000)

0 引言

线性互补问题产生于一些科学计算，以及工程和经济领域的应用，包括线性和二次规划问题、弹性接触问题、滑动轴承的自由边界问题以及市场平衡问题等[1–4]。线性互补问题的数学模型为：寻找x ∈Rn，满足条件

其中A ∈Rn×n,q ∈Rn为已知。线性互补问题通常简记为LCP(A,q)。

对于线性互补问题LCP(A,q)，近几十年来，无论是在理论方面还是在数值求解方面，许多学者一直在研究，取得了丰富的理论成果。理论研究包括解的存在性、唯一性、稳定性，以及线性互补问题LCP(A,q)与其他问题的联系[5–10]。线性互补问题的一个著名的结论是：线性互补问题LCP(A,q)对于任意q ∈Rn存在唯一解的充分必要条件是A为P矩阵。关于P矩阵，它包括许多特殊类型，如正定矩阵和H+矩阵等[2,11–12]。Mathias 和Pang 在文献[5]中引入一个关于P矩阵的函数c(A)，并对c(A)的值给出一些估计。Cottle 等在文献[6]中，使用函数c(A)提出关于线性互补问题扰动的一些结论。由于函数c(A)不容易计算，许多学者探讨使用其他函数来估计误差界，处理系数矩阵为特殊矩阵，如H+矩阵和B矩阵等的线性互补问题[9,12–17]。Chen 和Xiang 在文献[7]中基于矩阵函数αp(A)讨论了线性互补问题的误差界。函数αp(A)后来被一些学者使用，且在估计误差界等方面表现比较好。αp(A)也存在不容易计算问题。因此，它的估计值常被使用[12–13,16]。有关线性互补问题LCP(A,q)的其他理论和数值解法，参见文献[2,8,11]。

本文使用函数αp(A)进一步研究线性互补问题LCP(A,q)的误差界。首先，给出函数αp(A)的准确值，其中A是一个主对角元为1 的M矩阵。之后，给出该类M矩阵的线性互补问题LCP(A,q)的绝对误差界和相对误差界。接下来，通过等价转化将误差界理论推广到一般情形，即给出系数矩阵为一般M矩阵的线性互补问题的误差界。最后，给出一些与误差界有关的数值试验。本文给出函数αp(A)的准确值，并将该函数应用到估计线性互补问题LCP(A,q)的误差界。主要结论见定理1 至定理6。数值结果表明，由αp(A)的准确值得出的误差界理论比现有一些理论好。

本文结构安排如下：第1 部分简要介绍一些定义和基本结论等；第2 部分给出本文的主要结果；第3 部分给出一些数值例子；第4 部分是结束语。

1 准备知识

在这部分，我们简要介绍本文中所涉及的一些概念、符号和基本结论等。

定义1[7]矩阵A=(aij)∈Rn×n称为M矩阵(在一些文章中称为非奇异M矩阵)，如果A满足

定义2[2]矩阵A=(aij)∈Rn×n称为H+矩阵，如果A满足aii>0(i=1,2,···,n)，且其比较矩阵〈A〉=(〈aij〉) 为M矩阵，其中〈aij〉定义为

其中“|·|”表示绝对值函数。

对于P矩阵A，函数c(A)定义为

详细资料可参考文献[5]。对于任意向量x,y,x∗,y∗∈Rn，根据文献[7]，有如下关系式

其中di ∈[0,1](i=1,2,···,n)。基于式(2)，Chen 和Xiang 在文献[7]中给出线性互补问题的绝对误差界，即

其中p ≥1 或p=∞，x∗,x ∈Rn分别表示线性互补问题LCP(A,q)的解和任意实向量。D= diag(d) = diag([d1d2··· dn])是一个对角矩阵，其对角元di满足di ∈[0,1](i=1,2,···,n)。线性互补问题LCP(A,q)的自然余量函数r(x)定义为

其中min 表示两实向量依分量取最小。

引理1[7]假定A ∈Rn×n是一个H+矩阵，则

其中〈A〉和Λ分别表示矩阵A的比较矩阵和主对角矩阵，矩阵max(Λ,I)定义为

引理2[13]假定A ∈Rn×n是一个M矩阵，则

2 主要结果

在这部分，我们首先给出主对角元满足aii= 1(i= 1,2,···,n)的M矩阵A的矩阵函数αp(A)的准确值，之后，使用该函数估计线性互补问题LCP(A,q)的误差界，并给出一些结论。

定理1如果A ∈Rn×n是一个M矩阵，且满足aii=1(i=1,2,···,n)，则

证明 因为A是一个M矩阵，所以A是一个H+矩阵，且满足〈A〉=A。结合引理1 和已知条件aii=1(i=1,2,···,n)，有

与此同时，由引理2，可得

因此，根据式(9)和式(10)，可知等式(8)成立。

注1在文献[7]中，作者讨论函数α1(A)，并给出一个计算公式，即α1(A) =maxv∈V f(v)，其中容易看出，该公式不便于实际使用。定理1 给出函数αp(A)，当p=1,2,···,∞时的准确值，改进了文献[7]的结果。

引理3如果A ∈Rn×n是一个M矩阵，并且满足aii=1(i=1,2,···,n)，则

其中e=(1,1,···,1)T，|A|=(|aij|)表示矩阵A的绝对值矩阵。

证明 因为

其中di ∈[0,1](i= 1,2,···,n)。根据矩阵范数//· //1和//· //∞的定义，容易证得公式(11)中的两个等式成立。

根据定理1 和引理3，不等式(3)中的绝对误差界可以表示成更精确形式，即下面的定理。

定理2如果A ∈Rn×n是一个M矩阵，且满足aii= 1(i= 1,2,···,n)，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则对于任意向量x ∈Rn，不等式

成立，其中r(x)由式(4)给出。

证明 根据定理1 和引理3，可知

分别满足

因此，在不等式(3)中使用式(13)和式(14)进行替换，易得式(12)成立。

推论1如果A ∈Rn×n是一个M矩阵，且满足aii= 1(i= 1,2,···,n)，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则不等式

成立，其中(−q)+=max(0,−q)。

证明 由式(4)，可得

在式(12)中取x=0，结合式(16)，易证不等式(15)成立。

一方面，我们得到//x −x∗//p的界，即定理2 中的式(12)。另一方面，我们得到//x∗//p的界，即推论1 中的式(15)。因此，易得下关于相对误差界的结论。

定理3如果A ∈Rn×n是一个M矩阵，且满足aii= 1(i= 1,2,···,n)，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则对于任意x ∈Rn，如果(−q)+̸=0，不等式

成立，其中r(x)由式(4)给出，(−q)+=max(0,−q)。

注2定理2、推论1 和定理3 显示，如果A ∈Rn×n是一个M矩阵，且满足aii=1(i=1,2,···,n)，则：

接下来，我们考虑一般情形，即线性互补问题LCP(A,q)的系数矩阵A为普通的M矩阵，也即A的主对角矩阵不一定是单位矩阵。首先，给出一个基本结论，即对于任意的正对角矩阵Λ，有等价关系

根据M矩阵的理论，线性互补问题LCP(A,q)的定义以及上面的等价关系，容易证得下面的引理。

引理4如果A ∈Rn×n是一个M矩阵，则对于任意的正对角矩阵Λ，矩阵ΛA也是M矩阵。

引理5如果A ∈Rn×n是一个M矩阵，则对于任意的正对角矩阵Λ，线性互补问题LCP(A,q)等价于线性互补问题

引理4和引理5 的证明过程省略。如果记线性互补问题(18)为LCP(ΛA,Λq)，则引理5 可以概况为：对于任意的正对角矩阵Λ，线性互补问题LCP(A,q)等价于线性互补问题LCP(ΛA,Λq)。因为M矩阵的主对角矩阵是正对角矩阵，结合引理4、引理5 以及定理1 至定理3，可得下面一些结论。

定理4如果A ∈Rn×n是一个M矩阵，其主对角矩阵为Λ，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则对于任意的x ∈Rn，不等式

成立，其中rΛ−1(x)=min(x,Λ−1Ax+Λ−1q)。

证明x∗是系数矩阵为M矩阵的线性互补问题LCP(A,q)的解，也是线性互补问题LCP(Λ−1A,Λ−1q)的解。由于系数矩阵Λ−1A是一个M矩阵，且其主对角矩阵为单位阵，由定理2 可知，x和x∗满足式(12)，即

其中rΛ−1(x)由式(4)给出，即rΛ−1(x)=min(x,Λ−1Ax+Λ−1q)。因此，式(19)得证。

定理5如果A ∈Rn×n是一个M矩阵，其主对角矩阵为Λ，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则不等式

成立，其中(−Λ−1q)+=max(0,−Λ−1q)。

不等式(20)容易证明，只需在式(19)中取x= 0 即可。基于定理4 和定理5，与定理3 类似，可以得到系数矩阵为一般M矩阵的线性互补问题的相对误差界。

定理6如果A ∈Rn×n是一个M矩阵，其主对角矩阵为Λ，向量x∗∈Rn是线性互补问题LCP(A,q)的解，则对于任意x ∈Rn，如果(−q)+̸=0，不等式

成立，其中

对于系数矩阵为M矩阵的线性互补问题LCP(A,q)，根据文献[5]，有

同时，根据推论1，有

因此，有

结合式(22)和定理5，可得x∗新的界

因此，如果记式(23)的左侧和右侧分别为Ul和Ur，可得新的相对误差界

因为式(24)比式(21)更复杂，并且涉及不易计算的函数c(A)，本文不讨论。

3 数值例子

在这部分，我们给出一些数值例子，并与已有结论进行比较。前3 个例子是低阶线性互补问题，第4 个例子是高阶线性互补问题。在第1 个例子中，我们将定理4 与文献[7,12,16]中的结论进行数值比较。第2 个和第3 个例子分别关于准确解的界和数值解的误差界。在最后的一个例子中，我们使用迭代法求解线性互补问题LCP(A,q)，并用定理4 估计每步所得数值解的误差界。

例1在这个例子中，考虑数值解的绝对误差界。选取线性互补问题LCP(A,q)中的系数矩阵A为

该矩阵是一个非对称M矩阵，曾出现在文献[12,16]中，其中k>1，则

其中

令q=(0,−ε)T,x=ε(1,2)T，则

根据定理4，关于数值解x的误差界，有

根据文献[7]中的式(2.4)，有

根据文献[16]中的式(2.3)，有

根据文献[12]中的式(3.5)，有

例2在这个例子中，我们考虑线性互补问题真实解的界。在线性互补问题LCP(A,q)中，选取A和q分别为

因此，可得线性互补问题LCP(A,q)的真实解x∗的上界为

第一个不等式是根据定理5，第二个不等式是根据文献[7]中的定理2.4。可以看出，两个上界相等的一个条件是矩阵A为正对角矩阵，即t= 0，并且p=∞。因此，这个例子显示，定理5 给出的上界比文献[7]给出的上界好。

例3在这个例子中，我们考虑一个具体的线性互补问题，在LCP(A,q)中选取A和q分别为

则A是一个非对称的M矩阵，线性互补问题LCP(A,q)的准确解为x∗=(2,1,0)T。假定数值解为x=(2.1,0.9,−0.1)T，则

通过计算，可得表1 和表2。

表1 误差界涉及的一些量

表2 绝对误差界和相对误差界

表1 给出误差界涉及的一些量，表2 给出根据定理4 和定理6 计算得到的误差界。从表2 可以看出，定理4 和定理6 给出的误差界可以用来估计数值解与准确解之间的近似程度。从这个例子中也可以看出绝对误差界比相对误差界更接近真实情况。

例4在这个例子中，我们考虑一个高阶的线性互补问题。数值解由Modulus-based Gauss-Seidel(MGS)迭代法计算得到，该方法是求解线性互补问题LCP(A,q)数值解的有效方法之一，详细资料可参见文献[2]。在LCP(A,q)中，选取A为一个块三对角M矩阵，即A=Tridiag(−I,S,−I)+D ∈Rn×n，其中

I是一个m阶单位矩阵，其中n=m2。取准确解x∗和q分别为x∗= (1,2,1,2,···)T∈Rn,q=−Ax∗。在MGS 迭代法中，选取参数矩阵Ω= diag(diag(A))，初始迭代向量x(0)为x(0)= (1,0,1,0,···)T∈Rn。设置停止迭代条件为norm(r(x(k)))＜ 10−5，其中x(k)表示k次迭代得到的数值解，符号“diag”和“norm”是数学软件Matlab 中的两个函数。考虑误差//x(k)−x∗//p的下界、上界和准确值，其中p= 1,2,···,∞。令n=900，得到下图1 和图2。

图1 x(k)关于范数//·//1 的误差界

图2 x(k)关于范数//·//∞的误差界

在图1 和图2 中，水平轴表示迭代步数，图中直线、点线和星线分别表示函数

其中p=1,2,···,∞。数值结果表明，定理4 可以用来估计数值解的绝对误差。

4 结束语

在本文中，基于矩阵函数αp(A)的准确值和线性互补问题LCP(A,q)的等价转化，我们给出系数矩阵为M矩阵的线性互补问题的误差界。数值结果表明，所给的误差界是有效的和实用的。与相对误差界比较，绝对误差界与实际情况更接近一些。要更好地估计相对误差界，需要探寻其他的理论和方法。同时，有关线性互补问题LCP(A,q)的扰动和求解方法等，也值得后续进一步探讨。