房喜明

(肇慶學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，肇慶 526000)

0 引言

線性互補(bǔ)問題產(chǎn)生于一些科學(xué)計(jì)算，以及工程和經(jīng)濟(jì)領(lǐng)域的應(yīng)用，包括線性和二次規(guī)劃問題、彈性接觸問題、滑動(dòng)軸承的自由邊界問題以及市場平衡問題等[1–4]。線性互補(bǔ)問題的數(shù)學(xué)模型為：尋找x ∈Rn，滿足條件

其中A ∈Rn×n,q ∈Rn為已知。線性互補(bǔ)問題通常簡記為LCP(A,q)。

對(duì)于線性互補(bǔ)問題LCP(A,q)，近幾十年來，無論是在理論方面還是在數(shù)值求解方面，許多學(xué)者一直在研究，取得了豐富的理論成果。理論研究包括解的存在性、唯一性、穩(wěn)定性，以及線性互補(bǔ)問題LCP(A,q)與其他問題的聯(lián)系[5–10]。線性互補(bǔ)問題的一個(gè)著名的結(jié)論是：線性互補(bǔ)問題LCP(A,q)對(duì)于任意q ∈Rn存在唯一解的充分必要條件是A為P矩陣。關(guān)于P矩陣，它包括許多特殊類型，如正定矩陣和H+矩陣等[2,11–12]。Mathias 和Pang 在文獻(xiàn)[5]中引入一個(gè)關(guān)于P矩陣的函數(shù)c(A)，并對(duì)c(A)的值給出一些估計(jì)。Cottle 等在文獻(xiàn)[6]中，使用函數(shù)c(A)提出關(guān)于線性互補(bǔ)問題擾動(dòng)的一些結(jié)論。由于函數(shù)c(A)不容易計(jì)算，許多學(xué)者探討使用其他函數(shù)來估計(jì)誤差界，處理系數(shù)矩陣為特殊矩陣，如H+矩陣和B矩陣等的線性互補(bǔ)問題[9,12–17]。Chen 和Xiang 在文獻(xiàn)[7]中基于矩陣函數(shù)αp(A)討論了線性互補(bǔ)問題的誤差界。函數(shù)αp(A)后來被一些學(xué)者使用，且在估計(jì)誤差界等方面表現(xiàn)比較好。αp(A)也存在不容易計(jì)算問題。因此，它的估計(jì)值常被使用[12–13,16]。有關(guān)線性互補(bǔ)問題LCP(A,q)的其他理論和數(shù)值解法，參見文獻(xiàn)[2,8,11]。

本文使用函數(shù)αp(A)進(jìn)一步研究線性互補(bǔ)問題LCP(A,q)的誤差界。首先，給出函數(shù)αp(A)的準(zhǔn)確值，其中A是一個(gè)主對(duì)角元為1 的M矩陣。之后，給出該類M矩陣的線性互補(bǔ)問題LCP(A,q)的絕對(duì)誤差界和相對(duì)誤差界。接下來，通過等價(jià)轉(zhuǎn)化將誤差界理論推廣到一般情形，即給出系數(shù)矩陣為一般M矩陣的線性互補(bǔ)問題的誤差界。最后，給出一些與誤差界有關(guān)的數(shù)值試驗(yàn)。本文給出函數(shù)αp(A)的準(zhǔn)確值，并將該函數(shù)應(yīng)用到估計(jì)線性互補(bǔ)問題LCP(A,q)的誤差界。主要結(jié)論見定理1 至定理6。數(shù)值結(jié)果表明，由αp(A)的準(zhǔn)確值得出的誤差界理論比現(xiàn)有一些理論好。

本文結(jié)構(gòu)安排如下：第1 部分簡要介紹一些定義和基本結(jié)論等；第2 部分給出本文的主要結(jié)果；第3 部分給出一些數(shù)值例子；第4 部分是結(jié)束語。

1 準(zhǔn)備知識(shí)

在這部分，我們簡要介紹本文中所涉及的一些概念、符號(hào)和基本結(jié)論等。

定義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〉定義為

其中“|·|”表示絕對(duì)值函數(shù)。

對(duì)于P矩陣A，函數(shù)c(A)定義為

詳細(xì)資料可參考文獻(xiàn)[5]。對(duì)于任意向量x,y,x?,y?∈Rn，根據(jù)文獻(xiàn)[7]，有如下關(guān)系式

其中di ∈[0,1](i=1,2,···,n)?；谑?2)，Chen 和Xiang 在文獻(xiàn)[7]中給出線性互補(bǔ)問題的絕對(duì)誤差界，即

其中p ≥1 或p=∞，x?,x ∈Rn分別表示線性互補(bǔ)問題LCP(A,q)的解和任意實(shí)向量。D= diag(d) = diag([d1d2··· dn])是一個(gè)對(duì)角矩陣，其對(duì)角元di滿足di ∈[0,1](i=1,2,···,n)。線性互補(bǔ)問題LCP(A,q)的自然余量函數(shù)r(x)定義為

其中min 表示兩實(shí)向量依分量取最小。

引理1[7]假定A ∈Rn×n是一個(gè)H+矩陣，則

其中〈A〉和Λ分別表示矩陣A的比較矩陣和主對(duì)角矩陣，矩陣max(Λ,I)定義為

引理2[13]假定A ∈Rn×n是一個(gè)M矩陣，則

2 主要結(jié)果

在這部分，我們首先給出主對(duì)角元滿足aii= 1(i= 1,2,···,n)的M矩陣A的矩陣函數(shù)αp(A)的準(zhǔn)確值，之后，使用該函數(shù)估計(jì)線性互補(bǔ)問題LCP(A,q)的誤差界，并給出一些結(jié)論。

定理1如果A ∈Rn×n是一個(gè)M矩陣，且滿足aii=1(i=1,2,···,n)，則

證明 因?yàn)锳是一個(gè)M矩陣，所以A是一個(gè)H+矩陣，且滿足〈A〉=A。結(jié)合引理1 和已知條件aii=1(i=1,2,···,n)，有

與此同時(shí)，由引理2，可得

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

注1在文獻(xiàn)[7]中，作者討論函數(shù)α1(A)，并給出一個(gè)計(jì)算公式，即α1(A) =maxv∈V f(v)，其中容易看出，該公式不便于實(shí)際使用。定理1 給出函數(shù)αp(A)，當(dāng)p=1,2,···,∞時(shí)的準(zhǔn)確值，改進(jìn)了文獻(xiàn)[7]的結(jié)果。

引理3如果A ∈Rn×n是一個(gè)M矩陣，并且滿足aii=1(i=1,2,···,n)，則

其中e=(1,1,···,1)T，|A|=(|aij|)表示矩陣A的絕對(duì)值矩陣。

證明 因?yàn)?/p>

其中di ∈[0,1](i= 1,2,···,n)。根據(jù)矩陣范數(shù)//· //1和//· //∞的定義，容易證得公式(11)中的兩個(gè)等式成立。

根據(jù)定理1 和引理3，不等式(3)中的絕對(duì)誤差界可以表示成更精確形式，即下面的定理。

定理2如果A ∈Rn×n是一個(gè)M矩陣，且滿足aii= 1(i= 1,2,···,n)，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則對(duì)于任意向量x ∈Rn，不等式

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

證明 根據(jù)定理1 和引理3，可知

分別滿足

因此，在不等式(3)中使用式(13)和式(14)進(jìn)行替換，易得式(12)成立。

推論1如果A ∈Rn×n是一個(gè)M矩陣，且滿足aii= 1(i= 1,2,···,n)，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則不等式

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

證明 由式(4)，可得

在式(12)中取x=0，結(jié)合式(16)，易證不等式(15)成立。

一方面，我們得到//x ?x?//p的界，即定理2 中的式(12)。另一方面，我們得到//x?//p的界，即推論1 中的式(15)。因此，易得下關(guān)于相對(duì)誤差界的結(jié)論。

定理3如果A ∈Rn×n是一個(gè)M矩陣，且滿足aii= 1(i= 1,2,···,n)，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則對(duì)于任意x ∈Rn，如果(?q)+?=0，不等式

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

注2定理2、推論1 和定理3 顯示，如果A ∈Rn×n是一個(gè)M矩陣，且滿足aii=1(i=1,2,···,n)，則：

接下來，我們考慮一般情形，即線性互補(bǔ)問題LCP(A,q)的系數(shù)矩陣A為普通的M矩陣，也即A的主對(duì)角矩陣不一定是單位矩陣。首先，給出一個(gè)基本結(jié)論，即對(duì)于任意的正對(duì)角矩陣Λ，有等價(jià)關(guān)系

根據(jù)M矩陣的理論，線性互補(bǔ)問題LCP(A,q)的定義以及上面的等價(jià)關(guān)系，容易證得下面的引理。

引理4如果A ∈Rn×n是一個(gè)M矩陣，則對(duì)于任意的正對(duì)角矩陣Λ，矩陣ΛA也是M矩陣。

引理5如果A ∈Rn×n是一個(gè)M矩陣，則對(duì)于任意的正對(duì)角矩陣Λ，線性互補(bǔ)問題LCP(A,q)等價(jià)于線性互補(bǔ)問題

引理4和引理5 的證明過程省略。如果記線性互補(bǔ)問題(18)為LCP(ΛA,Λq)，則引理5 可以概況為：對(duì)于任意的正對(duì)角矩陣Λ，線性互補(bǔ)問題LCP(A,q)等價(jià)于線性互補(bǔ)問題LCP(ΛA,Λq)。因?yàn)镸矩陣的主對(duì)角矩陣是正對(duì)角矩陣，結(jié)合引理4、引理5 以及定理1 至定理3，可得下面一些結(jié)論。

定理4如果A ∈Rn×n是一個(gè)M矩陣，其主對(duì)角矩陣為Λ，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則對(duì)于任意的x ∈Rn，不等式

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

證明x?是系數(shù)矩陣為M矩陣的線性互補(bǔ)問題LCP(A,q)的解，也是線性互補(bǔ)問題LCP(Λ?1A,Λ?1q)的解。由于系數(shù)矩陣Λ?1A是一個(gè)M矩陣，且其主對(duì)角矩陣為單位陣，由定理2 可知，x和x?滿足式(12)，即

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

定理5如果A ∈Rn×n是一個(gè)M矩陣，其主對(duì)角矩陣為Λ，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則不等式

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

不等式(20)容易證明，只需在式(19)中取x= 0 即可?；诙ɡ? 和定理5，與定理3 類似，可以得到系數(shù)矩陣為一般M矩陣的線性互補(bǔ)問題的相對(duì)誤差界。

定理6如果A ∈Rn×n是一個(gè)M矩陣，其主對(duì)角矩陣為Λ，向量x?∈Rn是線性互補(bǔ)問題LCP(A,q)的解，則對(duì)于任意x ∈Rn，如果(?q)+?=0，不等式

成立，其中

對(duì)于系數(shù)矩陣為M矩陣的線性互補(bǔ)問題LCP(A,q)，根據(jù)文獻(xiàn)[5]，有

同時(shí)，根據(jù)推論1，有

因此，有

結(jié)合式(22)和定理5，可得x?新的界

因此，如果記式(23)的左側(cè)和右側(cè)分別為Ul和Ur，可得新的相對(duì)誤差界

因?yàn)槭?24)比式(21)更復(fù)雜，并且涉及不易計(jì)算的函數(shù)c(A)，本文不討論。

3 數(shù)值例子

在這部分，我們給出一些數(shù)值例子，并與已有結(jié)論進(jìn)行比較。前3 個(gè)例子是低階線性互補(bǔ)問題，第4 個(gè)例子是高階線性互補(bǔ)問題。在第1 個(gè)例子中，我們將定理4 與文獻(xiàn)[7,12,16]中的結(jié)論進(jìn)行數(shù)值比較。第2 個(gè)和第3 個(gè)例子分別關(guān)于準(zhǔn)確解的界和數(shù)值解的誤差界。在最后的一個(gè)例子中，我們使用迭代法求解線性互補(bǔ)問題LCP(A,q)，并用定理4 估計(jì)每步所得數(shù)值解的誤差界。

例1在這個(gè)例子中，考慮數(shù)值解的絕對(duì)誤差界。選取線性互補(bǔ)問題LCP(A,q)中的系數(shù)矩陣A為

該矩陣是一個(gè)非對(duì)稱M矩陣，曾出現(xiàn)在文獻(xiàn)[12,16]中，其中k>1，則

其中

令q=(0,?ε)T,x=ε(1,2)T，則

根據(jù)定理4，關(guān)于數(shù)值解x的誤差界，有

根據(jù)文獻(xiàn)[7]中的式(2.4)，有

根據(jù)文獻(xiàn)[16]中的式(2.3)，有

根據(jù)文獻(xiàn)[12]中的式(3.5)，有

例2在這個(gè)例子中，我們考慮線性互補(bǔ)問題真實(shí)解的界。在線性互補(bǔ)問題LCP(A,q)中，選取A和q分別為

因此，可得線性互補(bǔ)問題LCP(A,q)的真實(shí)解x?的上界為

第一個(gè)不等式是根據(jù)定理5，第二個(gè)不等式是根據(jù)文獻(xiàn)[7]中的定理2.4?？梢钥闯?，兩個(gè)上界相等的一個(gè)條件是矩陣A為正對(duì)角矩陣，即t= 0，并且p=∞。因此，這個(gè)例子顯示，定理5 給出的上界比文獻(xiàn)[7]給出的上界好。

例3在這個(gè)例子中，我們考慮一個(gè)具體的線性互補(bǔ)問題，在LCP(A,q)中選取A和q分別為

則A是一個(gè)非對(duì)稱的M矩陣，線性互補(bǔ)問題LCP(A,q)的準(zhǔn)確解為x?=(2,1,0)T。假定數(shù)值解為x=(2.1,0.9,?0.1)T，則

通過計(jì)算，可得表1 和表2。

表1 誤差界涉及的一些量

表2 絕對(duì)誤差界和相對(duì)誤差界

表1 給出誤差界涉及的一些量，表2 給出根據(jù)定理4 和定理6 計(jì)算得到的誤差界。從表2 可以看出，定理4 和定理6 給出的誤差界可以用來估計(jì)數(shù)值解與準(zhǔn)確解之間的近似程度。從這個(gè)例子中也可以看出絕對(duì)誤差界比相對(duì)誤差界更接近真實(shí)情況。

例4在這個(gè)例子中，我們考慮一個(gè)高階的線性互補(bǔ)問題。數(shù)值解由Modulus-based Gauss-Seidel(MGS)迭代法計(jì)算得到，該方法是求解線性互補(bǔ)問題LCP(A,q)數(shù)值解的有效方法之一，詳細(xì)資料可參見文獻(xiàn)[2]。在LCP(A,q)中，選取A為一個(gè)塊三對(duì)角M矩陣，即A=Tridiag(?I,S,?I)+D ∈Rn×n，其中

I是一個(gè)m階單位矩陣，其中n=m2。取準(zhǔn)確解x?和q分別為x?= (1,2,1,2,···)T∈Rn,q=?Ax?。在MGS 迭代法中，選取參數(shù)矩陣?= diag(diag(A))，初始迭代向量x(0)為x(0)= (1,0,1,0,···)T∈Rn。設(shè)置停止迭代條件為norm(r(x(k)))＜ 10?5，其中x(k)表示k次迭代得到的數(shù)值解，符號(hào)“diag”和“norm”是數(shù)學(xué)軟件Matlab 中的兩個(gè)函數(shù)。考慮誤差//x(k)?x?//p的下界、上界和準(zhǔn)確值，其中p= 1,2,···,∞。令n=900，得到下圖1 和圖2。

圖1 x(k)關(guān)于范數(shù)//·//1 的誤差界

圖2 x(k)關(guān)于范數(shù)//·//∞的誤差界

在圖1 和圖2 中，水平軸表示迭代步數(shù)，圖中直線、點(diǎn)線和星線分別表示函數(shù)

其中p=1,2,···,∞。數(shù)值結(jié)果表明，定理4 可以用來估計(jì)數(shù)值解的絕對(duì)誤差。

4 結(jié)束語

在本文中，基于矩陣函數(shù)αp(A)的準(zhǔn)確值和線性互補(bǔ)問題LCP(A,q)的等價(jià)轉(zhuǎn)化，我們給出系數(shù)矩陣為M矩陣的線性互補(bǔ)問題的誤差界。數(shù)值結(jié)果表明，所給的誤差界是有效的和實(shí)用的。與相對(duì)誤差界比較，絕對(duì)誤差界與實(shí)際情況更接近一些。要更好地估計(jì)相對(duì)誤差界，需要探尋其他的理論和方法。同時(shí)，有關(guān)線性互補(bǔ)問題LCP(A,q)的擾動(dòng)和求解方法等，也值得后續(xù)進(jìn)一步探討。