邓永坤， 张 萍

(中国矿业大学 理学院，江苏 徐州 221116)

绝对值方程的光滑牛顿算法

邓永坤， 张 萍

(中国矿业大学 理学院，江苏 徐州 221116)

针对绝对值方程Ax+=b的求解问题，给出了光滑牛顿法。通过引进极大熵函数将绝对值方程进行光滑化处理，进而转化为非线性光滑方程组，利用光滑牛顿算法对其进行求解，并对算法的收敛性和收敛速度进行了验证。数值实验结果表明该算法是有效的。

绝对值方程;极大熵方法;光滑牛顿算法

0 引言

考虑绝对值方程:其中A、B∈n×n，b∈n，绝对值依分量形式而取。绝对值方程首次由Rohn在文献［1］中提出，此后许多学者对其进行了广泛研究。文献［2］给出了该方程存在唯一解或者存在非平凡解的择一定理及几个等价形式，文献［3］证明了该方程的求解是NP－hard问题，文献［4］给出了该方程唯一可解性的条件，文献［5］给出了求解该方程的广义牛顿法，并证明了该方程与二阶锥互补问题的等价性，进而延伸到求解二阶锥互补问题。

1 光滑化处理

引理1［4］若矩阵A的最小奇异值大于矩阵B的最大奇异值，则对任意的b∈n，绝对值方程(1)存在唯一解。

引理1给出了方程(1)存在唯一解的条件，为保证存在唯一解，文中总是假设该条件成立，下面考虑如何求解该类绝对值方程。

然后对绝对值方程(1)的每一行都进行相应的光滑化处理，得到非线性光滑方程组:

将方程(2)简记为

定理1 当p→0时，非线性光滑方程组(3)的解即为绝对值方程(1)的解。令f(x)=Ax+－b，则误差限:

当p→0时，‖F(x)－f(x)‖→0，所以p→0时方程(3)的解即为方程(1)的解。得证。

2 算法及收敛性分析

算法1 (1)给定一个初始向量x0，容许误差ε，k:=0，构造非线性方程组F(x)。

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

(3)若‖xk+1－xk‖≤ε，则停止，得到解x*= xk;否则转入步骤(2)。

记非线性光滑方程组(3)中矩阵A、B及相关等式的具体表达式为

则F'(x)可以化为

引理2［11］若F:D⊂n→n在x*处F可导，x*是非线性方程组F(x)=0的解，S0⊂D是x*的邻域，又设M:S0⊂D→L(n)在x*处连续，M(x*)非奇异，则存在闭球S=¯S(x*，δ)⊂S0，使映象G(x)=x－［M(x)］－1F(x)在x∈S上有定义，且在x*处有F导数:

若还有ρ(I－［M(x*)］－1F'(x*))＜1，则x*是迭代序列xk+1=xk－［M(xk)］－1F(xk)的吸引点。

引理3［11］假定映象F:D⊂n→n及D0⊂D，若存在常数c≥0及p∈［0，1］，对所有的x、y∈D0有‖F'(x)－F'(y)‖≤c‖x－y‖p成立，则有以下不等式成立:

引理2和3的证明在文献［11］中有详细描述，文中从略。

定理2 假定x*是非线性光滑方程组(3)的解，则存在闭球S=¯S(x*，δ)⊂S0(δ＞0)，使映象G(x)=x－［F'(x)］－1F(x)对所有x∈S有定义，且算法1生成的迭代序列{xk}超线性收敛到x*，如果还假定:

其中α＞0为常数，则迭代序列{xk}至少2阶收敛。

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

3 数值实验

运用MATLAB7.0进行编程计算，参数设为:计算精度ε=1.0e－4;p为极大熵因子;n为迭代次数;t为算法运行的CPU时间，s。

为保证方程有唯一解，利用矩阵的奇异值分解构造矩阵

(此矩阵A的最小奇异值大于矩阵B的最大奇异值)，

计算结果见表1。

表1 计算结果Table 1 Results of calculation

算例2 求解绝对值方程:Ax+B|x|=b，其中

为保证方程有唯一解，同上例构造矩阵

计算结果见表2。

表2 计算结果Table 2 Results of calculation

通过表1和2可以看出，光滑牛顿法在求解绝对值问题(1)时，不仅得出了方程的解，而且具有较快的收敛速度，从而进一步验证了算法的有效性。

4 结束语

［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］王爱祥，王海军.绝对值方程的区间算法［J］.贵州大学学报:自然科学版，2010，27(2):7－10.

［9］雍龙泉，孙培民，高 凯.极大熵自适应微粒子群混合算法求解绝对值方程［J］.计算机应用研究，2011，28(7):2479－2481.

［10］李兴斯.一类不可微优化问题的有效解法［J］.中国科学:A辑，1994，24(4):371－377.

［11］李庆扬，莫孜中，祁力群.非线性方程组的数值解法［M］.北京:科学出版社，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－)，男，山东省青州人，硕士，研究方向:计算数学，E-mail:dengyongkun@126.com。

(编辑王 冬)