廣義絕對值方程

龔成，戴培良

（常熟理工學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，江蘇常熟 215500）

廣義絕對值方程

龔成，戴培良

（常熟理工學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，江蘇常熟 215500）

廣義絕對值方程是絕對值方程的推廣，證明了其等價于廣義線性互補(bǔ)問題，探討了廣義絕對值方程解唯一存在的條件，這些結(jié)果也推廣了Mangasarian在文獻(xiàn)[1]中的結(jié)論，提出了廣義絕對值方程解唯一存在的幾個充要條件.最后，給出了廣義絕對值方程的一個迭代算法，理論分析和數(shù)值結(jié)果均說明該方法是有效的.

廣義絕對值方程；廣義線性互補(bǔ)問題；迭代算法；

0 引言

考慮如下形式的廣義絕對值方程

其中A,B∈Rn×n，b,c∈Rn，絕對值依分量運(yùn)算．當(dāng)B=E（單位矩陣）且c=0，絕對值方程（1）就是

絕對值方程作為有效的優(yōu)化工具，自Rohn在文獻(xiàn)[2]中提出后，學(xué)者M(jìn)angasarian，Prokopyev等深入研究了絕對值方程的理論和數(shù)值求解．文獻(xiàn)[1，3，4]證明了絕對值方程等價于線性互補(bǔ)問題且其求解是NP-難的．文獻(xiàn)[5]基于絕對值方程和背包問題的聯(lián)系，提出了求解背包問題的序列線性規(guī)劃方法．文獻(xiàn)[6]提出了一個求解絕對值方程的擬牛頓算法．文獻(xiàn)[7]提出求解絕對值方程的區(qū)間方法．

本文進(jìn)一步研究了形如（1）的廣義絕對值方程，證明了其等價于廣義線性互補(bǔ)問題：給定n×n階實(shí)方陣M，N和n維實(shí)向量p，q，求滿足如下條件的實(shí)向量x：

并且討論了其解的存在性問題，拓展了文獻(xiàn)[2]中的一些結(jié)果．最后，給出廣義絕對值方程的一個迭代算法．

1 等價問題

先考慮廣義絕對值方程與垂直線性互補(bǔ)問題的等價性．

定理1.1 廣義絕對值方程（1）等價于垂直線性互補(bǔ)問題0≤(Mx+q)⊥(Nx+p)≥0．

考慮每一個分量，根據(jù)|s-t|=s+t?s≥0,t≥0,st=0可知廣義絕對值方程（1）等價于0≤(Mx+q)⊥(Nx+p)≥0.證畢．

推論若A-B可逆，則廣義絕對值方程（1）等價于線性互補(bǔ)問題

證明若A-B可逆，則(A-B)-1存在．令z=(A-B)x-c-b，根據(jù)定理1.1，廣義絕對值方程（1）等價于0≤z⊥(A+B)(A-B)-1z+q≥0，其中q=(A+B)(A-B)-1(c+b)+c-b，z=(A-B)x-c-b．證畢．

2 可解問題

下面考慮廣義絕對值方程（1）的可解性．

記σmin(A)和σmax(A)為矩陣A的最小奇異值和最大奇異值．

定理2.1若σmax(B)＜σmin(A)，則對于任意給定的向量b,c∈Rn，廣義絕對值方程（1）有唯一解．

證明先證(A-B)-1存在．假設(shè)不存在，則存在向量x≠0，使得(A-B)x=0．故

在霸座視頻瘋傳的同時，一些“如果霸座這事發(fā)生在國外”的視頻，也引起網(wǎng)友熱議。例如今年1月，美國一名18歲的女生乘坐地鐵時，把腳放在座位上，警察警告無效后，直接將她強(qiáng)行拉下車并拘捕。據(jù)悉，美國地鐵規(guī)定“若將腳或鞋放在座位上，輕則被警告，重則會被趕下地鐵”。哪怕是再微小的違法行為，執(zhí)法者也必須說不。這，正是法治社會的應(yīng)有之義。

有唯一解可知定理成立．證畢．

定義2.1如果矩陣Q的第i行是矩陣M的第i行或者矩陣N的第i行，那么稱矩陣Q為矩陣集合{M,N}的行表示矩陣，其中i=1,2,…n．

引理[8]對于任意向量p,q∈Rn，垂直線性互補(bǔ)問題0≤(Mx+q)⊥(Nx+p)≥0有唯一解等價于以下任一命題：

（1）矩陣集合{M,N}的所有行表示矩陣有相同的非零行列式符號．

（2）對于任意非負(fù)對角矩陣Λ1,Λ2∈Rn×n且Λ1+Λ2的對角元都大于零，那么行列式|Λ1M+Λ2N|不為零．

定理2.2對于任意向量b,c∈Rn，廣義絕對值方程（1）有唯一解等價于以下任一命題：

（1）矩陣集合{A+B,A-B}的所有行表示矩陣有相同的非零行列式符號．

（3）A+B可逆，且矩陣集合{E,(A-B)(A+B)-1}的所有行表示矩陣的行列式大于零．

證明由廣義絕對值方程與垂直線性互補(bǔ)問題的等價性和引理易知（1）和（2）成立．下面，只需證（1）?（3）．

（1）?（3）：對任意的b,c∈Rn，廣義絕對值方程（1）有唯一解，則{A+B,A-B}的行表示矩陣有相同的非零行列式符號，故A+B行列式不為零從而可逆．現(xiàn)在矩陣集合{E,(A-B)(A+B)-1}的任何行表示矩陣可以表示為K(A+B)-1的形式，其中K是矩陣集合{A+B,A-B}的行表示矩陣．因此矩陣組{E,(A-B)(A+B)-1}的行表示矩陣有相同的行列式符號．從而矩陣集合{E,(A-B)(A+B)-1}的所有行表示矩陣的行列式大于零．

（3）?（1）：由于矩陣集合{E,(A-B)(A+B)-1}的任何行表示矩陣可以表示為K(A+B)-1的形式，其中K是矩陣集合{A+B,A-B}的行表示矩陣．因此矩陣K的行列式|K|不為零，且|K|恒正或者恒負(fù)．從而矩陣集合{A+B,A-B}的所有行表示矩陣有相同的非零行列式符號．證畢．

當(dāng)B=E（單位矩陣）且c=0時，得到下面的推論．

推論[8]對于任意向量b∈Rn，絕對值方程（1）有唯一解等價于以下任一命題：

（1）矩陣A+diag(y1,y2,…,yn)的行列式有相同的非零行列式符號，其中|yi|=1，i=1,2,…n．

（2）對于任意非負(fù)對角矩陣Λ1,Λ2∈Rn×n且Λ1+Λ2的對角元都大于零，那么行列式|(Λ1+Λ2)A+(Λ1-Λ2)|不為零．

（3）A+E可逆，且矩陣集合{E,(A-E)(A+E)-1}的所有行表示矩陣的行列式大于零．

以上的定理與推論，討論了絕對值方程有解的情形，這有助于我們更深地理解絕對值方程及其相關(guān)的數(shù)學(xué)模型．

3 迭代算法

若A可逆，Ax-|Bx+c|=b可化為x=A-1|Bx+c|+A-1b=f(x)．

對任意x,y∈Rn，有

若‖A-1‖‖B‖＜1，則對任意b,c∈Rn，廣義絕對值方程（1）有唯一解．此時

故f(x)是壓縮映射．根據(jù)Banach壓縮映射原理，f(x)有唯一不動點(diǎn)．所以序列xk+1=f(xk)是收斂到廣義絕對值方程的唯一解．

在Matlab7.0上編程計算例題．

例1.（隨機(jī)測試）Ax-|Bx+c|=b，其中

隨機(jī)取初始點(diǎn)

記ω：計算精度；T:CPU時間；k:求解迭代次數(shù)．得到近似解為

表1 計算結(jié)果

數(shù)值結(jié)果表明了算法是有效的．但算法涉及到求逆，因此一旦規(guī)模變大，算法將不適合．如何求解大規(guī)模的絕對值方程，也是我們將來的工作之一．

[1]Mangasarian O，Meyer R.Absolute value equations[J].Linear Algebra Appl，2006，419:359-367.

[2]Rohn J.A theorem of the alternatives for the equation Ax+B|x|=b[J].Linear and Multilinear Algebra，2004，52（6）:421-426.

[3]Prokopyev O.On equivalent reformulations f-or absolute value equations[J].Comput Optim Appl，2009，44:363-372.

[4]Mangasarian O.Absolute value programming[J].Comput Optim Appl，2007，36（1）:43-53.

[5]Mangasarian O.Knapsack feasibility as an ab-solute value equation solvable by successive linear programming[J].Optim Lett，2009 （3）:161-170.

[6]Mangasarian O.A generalized Newton metho-d for absolute value equations[J].Optim Lett，2009（3）:101-108.

[7]王愛祥，王海軍.絕對值方程的區(qū)間算法[J].貴州大學(xué)學(xué)報，2010，27（2）：7-10．

[8]王愛祥，王海軍，龔成.絕對值方程的唯一可解性[J].科學(xué)技術(shù)與工程，2010，10（34）：8501-8502．

Generalized Absolute Value Equations

GONG Cheng，DAI Pei-liang
（School of Mathematics and Statistics,Changshu Institute of Technology,Changshu 215500,China)

This paper is concerned with the generalized absolute value equations.It shows that the generalized absolute value equations are equivalent to the generalized linear complementarity problem and a bilinear pro?gram.Existence results of the generalized absolute value equations solution are obtained and the results of Man?gasarian in[2]are improved.Some necessary and sufficient conditions are given.An iterative algorithm is pro?posed for the generalized absolute value equations.Theoretic analysis and numerical results show that the meth?od is effective.

generalized absolute value equations;generalized linear complementarity problem;iterative algorithm

O242.2

A

1008-2794（2011）08-0027-04

2011-06-01

龔成（1989—），男，江蘇興化人，常熟理工學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院2011屆畢業(yè)生.

戴培良（1965—），男，江蘇常熟人，常熟理工學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院教授，博士，研究方向：計算數(shù)學(xué)，E-mail: dpl@cslg.edu.cn．