絕對(duì)值方程的光滑牛頓算法

鄧永坤， 張 萍

(中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221116)

絕對(duì)值方程的光滑牛頓算法

鄧永坤， 張 萍

(中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221116)

針對(duì)絕對(duì)值方程Ax+=b的求解問題，給出了光滑牛頓法。通過引進(jìn)極大熵函數(shù)將絕對(duì)值方程進(jìn)行光滑化處理，進(jìn)而轉(zhuǎn)化為非線性光滑方程組，利用光滑牛頓算法對(duì)其進(jìn)行求解，并對(duì)算法的收斂性和收斂速度進(jìn)行了驗(yàn)證。數(shù)值實(shí)驗(yàn)結(jié)果表明該算法是有效的。

絕對(duì)值方程;極大熵方法;光滑牛頓算法

0 引言

考慮絕對(duì)值方程:其中A、B∈n×n，b∈n，絕對(duì)值依分量形式而取。絕對(duì)值方程首次由Rohn在文獻(xiàn)［1］中提出，此后許多學(xué)者對(duì)其進(jìn)行了廣泛研究。文獻(xiàn)［2］給出了該方程存在唯一解或者存在非平凡解的擇一定理及幾個(gè)等價(jià)形式，文獻(xiàn)［3］證明了該方程的求解是NP－h(huán)ard問題，文獻(xiàn)［4］給出了該方程唯一可解性的條件，文獻(xiàn)［5］給出了求解該方程的廣義牛頓法，并證明了該方程與二階錐互補(bǔ)問題的等價(jià)性，進(jìn)而延伸到求解二階錐互補(bǔ)問題。

1 光滑化處理

引理1［4］若矩陣A的最小奇異值大于矩陣B的最大奇異值，則對(duì)任意的b∈n，絕對(duì)值方程(1)存在唯一解。

引理1給出了方程(1)存在唯一解的條件，為保證存在唯一解，文中總是假設(shè)該條件成立，下面考慮如何求解該類絕對(duì)值方程。

然后對(duì)絕對(duì)值方程(1)的每一行都進(jìn)行相應(yīng)的光滑化處理，得到非線性光滑方程組:

將方程(2)簡(jiǎn)記為

定理1 當(dāng)p→0時(shí)，非線性光滑方程組(3)的解即為絕對(duì)值方程(1)的解。令f(x)=Ax+－b，則誤差限:

當(dāng)p→0時(shí)，‖F(xiàn)(x)－f(x)‖→0，所以p→0時(shí)方程(3)的解即為方程(1)的解。得證。

2 算法及收斂性分析

算法1 (1)給定一個(gè)初始向量x0，容許誤差ε，k:=0，構(gòu)造非線性方程組F(x)。

(2)計(jì)算xk+1，xk+1=xk－［F'(xk)］－1F(xk)，k=k+1。

(3)若‖xk+1－xk‖≤ε，則停止，得到解x*= xk;否則轉(zhuǎn)入步驟(2)。

記非線性光滑方程組(3)中矩陣A、B及相關(guān)等式的具體表達(dá)式為

則F'(x)可以化為

引理2［11］若F:D?n→n在x*處F可導(dǎo)，x*是非線性方程組F(x)=0的解，S0?D是x*的鄰域，又設(shè)M:S0?D→L(n)在x*處連續(xù)，M(x*)非奇異，則存在閉球S=ˉS(x*，δ)?S0，使映象G(x)=x－［M(x)］－1F(x)在x∈S上有定義，且在x*處有F導(dǎo)數(shù):

若還有ρ(I－［M(x*)］－1F'(x*))＜1，則x*是迭代序列xk+1=xk－［M(xk)］－1F(xk)的吸引點(diǎn)。

引理3［11］假定映象F:D?n→n及D0?D，若存在常數(shù)c≥0及p∈［0，1］，對(duì)所有的x、y∈D0有‖F(xiàn)'(x)－F'(y)‖≤c‖x－y‖p成立，則有以下不等式成立:

引理2和3的證明在文獻(xiàn)［11］中有詳細(xì)描述，文中從略。

定理2 假定x*是非線性光滑方程組(3)的解，則存在閉球S=ˉS(x*，δ)?S0(δ＞0)，使映象G(x)=x－［F'(x)］－1F(x)對(duì)所有x∈S有定義，且算法1生成的迭代序列{xk}超線性收斂到x*，如果還假定:

其中α＞0為常數(shù)，則迭代序列{xk}至少2階收斂。

假定式(4)成立，則由引理3［11］可知:

3 數(shù)值實(shí)驗(yàn)

運(yùn)用MATLAB7.0進(jìn)行編程計(jì)算，參數(shù)設(shè)為:計(jì)算精度ε=1.0e－4;p為極大熵因子;n為迭代次數(shù);t為算法運(yùn)行的CPU時(shí)間，s。

為保證方程有唯一解，利用矩陣的奇異值分解構(gòu)造矩陣

(此矩陣A的最小奇異值大于矩陣B的最大奇異值)，

計(jì)算結(jié)果見表1。

表1 計(jì)算結(jié)果Table 1 Results of calculation

算例2 求解絕對(duì)值方程:Ax+B|x|=b，其中

為保證方程有唯一解，同上例構(gòu)造矩陣

計(jì)算結(jié)果見表2。

表2 計(jì)算結(jié)果Table 2 Results of calculation

通過表1和2可以看出，光滑牛頓法在求解絕對(duì)值問題(1)時(shí)，不僅得出了方程的解，而且具有較快的收斂速度，從而進(jìn)一步驗(yàn)證了算法的有效性。

4 結(jié)束語

［1］ROHN J.Systems of linear interval equations［J］.Linear Algebra and its Application，1989，126:39－78.

［2］ROHN J.A theorem of the alternatives for the equation Ax+= b［J］.Linear and Multilinear Algebra，2004，52(6):421－426.

［3］MANGASARIAN O L.Absolute value programming［J］.Computational Optimization and Applications，2007，36(1):43－53.

［4］ROHN J.On unique solvability of the absolute value equation［J］.Optimization Letters，2009，3(4):603－606.

［5］HU S L，HUANG Z H，ZHANG Q.A generalized Newton method for absolute value equations associated with second order cones［J］.Computational Optimization and Applications，2011，235: 1490－1501.

［6］MANGASARIAN O L，MEYER R R.Absolute value equations［J］.Linear Algebra and Its Application，2006，419(2/3):359－367.

［7］MANGASARIAN O L.A generalized Newton method for absolute value equations［J］.Optimization Letters，2009，3(1):101－108.

［8］王愛祥，王海軍.絕對(duì)值方程的區(qū)間算法［J］.貴州大學(xué)學(xué)報(bào):自然科學(xué)版，2010，27(2):7－10.

［9］雍龍泉，孫培民，高 凱.極大熵自適應(yīng)微粒子群混合算法求解絕對(duì)值方程［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(7):2479－2481.

［10］李興斯.一類不可微優(yōu)化問題的有效解法［J］.中國(guó)科學(xué):A輯，1994，24(4):371－377.

［11］李慶揚(yáng)，莫孜中，祁力群.非線性方程組的數(shù)值解法［M］.北京:科學(xué)出版社，1987:8－50.

Smooth Newton method for absolute value equations

DENG Yongkun， ZHANG Ping
(College of Sciences，China University of Mining＆Technology，Xuzhou 221116，China)

Aimed at the solution to the absolute value equation Ax+B x =b，this paper presents a smooth Newton method.By using the maximum entropy function，absolute value equations problem could be transformed into the nonlinear smooth equations.Then the smooth Newton method is proposed for solving the absolute value equations and its convergence and convergent rate are proved.Numerical results indicate that the method is effective.

absolute value equation;maximum entropy method;smooth Newton method

O242.2

A

1671－0118(2011)06－0499－04

2011－10－26

鄧永坤(1988－)，男，山東省青州人，碩士，研究方向:計(jì)算數(shù)學(xué)，E-mail:dengyongkun@126.com。

(編輯王 冬)