求解线性互补问题的改进加速迭代方法

沈海龙, 魏 彤

(东北大学 理学院, 辽宁 沈阳 110819)



求解线性互补问题的改进加速迭代方法

沈海龙, 魏 彤

(东北大学 理学院, 辽宁 沈阳 110819)

从基于模系数矩阵分裂迭代方法的演变方法出发,将收敛所需满足的条件一般化,提出了一种改进的加速分裂迭代方法.理论分析表明新方法可以和线性互补问题等价转换,将新方法与其他几种方法进行比较分析,给出了系数矩阵是H+-矩阵的收敛定理.最后,通过数值算例证明了提出的新方法在运算过程中需要更少的迭代步数和更短的运行时间.

线性互补问题; 矩阵分裂; 迭代方法; H-矩阵; 收敛

线性互补问题LCP(q,A)就是找到向量r,z∈C满足如下条件[1-3]:

式中,A=(aij)∈Cn×n是给定的大型稀疏实数矩阵,q=(q1,q2,…,qn)T∈C是一个给定实向量.

线性互补问题LCP(q,A)在20世纪60年代被首次提出,由于其在数学规划方面是一类非常重要的分支,同时又是一个交叉的研究领域,因此,引起了很多数学研究者的高度重视[4-16].随着线性互补问题LCP(q,A)在算法和理论上的不断发展和完善,其实际应用的范围也逐步扩大,现已经拓展到了金融,交通和经济的问题中.自从线性互补问题LCP(q,A)被提出以来,在其算法方面和理论方面的研究都已取得了非常丰富的研究成果.主要的数值解算法分为直接算法和迭代算法,本文主要讨论迭代算法.迭代算法有多重分裂法[6-9],投影迭代法[10-12]等.很多学者利用多重分裂法的多分裂思想构造可行有效的算法将其应用到并行计算中来解决大型线性互补问题LCP(q,A)[13-16],虽然在求解线性互补问题LCP(q,A)方面已经有了许多算法,但是这些算法大都存在着限制条件.

1 改进的加速分裂迭代方法

1.1 迭代格式的建立

对于任意向量x∈Cn,向量|x|+x和向量|x|-x都是非负向量而且各个分量之间乘积为零.Van Bokhoven利用了这个性质,在线性互补问题LCP(q,A) 中,令z:=|x|+x,r:=|x|-x,巧妙地将线性互补问题LCP(q,A)转化成为一个不动点方程,

(1)

此方法为求解线性互补问题LCP(q,A)的模迭代方法[7].

为了使模迭代方法的收敛速度能够提高,Dong和Jiang在模迭代方法的基础上引入了一个移位因子α>0,提出了改进型的模迭代方法[8],其格式为

(2)

接着,Zhong-Zhi Bai在线性互补问题LCP(q,A) 中令z:=γ-1(|x|+x),r:=γ-1Ω(|x|-x).其中,γ>0,Ω是一个正对角矩阵,得到如下不动点方程

(3)

因此,线性互补问题LCP(q,A)就转化为了求解不动点方程式(3)[9].为了更容易的求解式(3),将不动点方程左边的矩阵A∈Cn×n分裂成A=M-N,得到了基于模系数矩阵分裂迭代方法:

(4)

(5)

(6)

其中Ω=diag(ωi)是一个正对角矩阵,Φ=(κij)是一个非负矩阵.

下面引理将证明线性互补问题LCP(q,A)可以和扩展之后得到的新方程等价转换.

(ⅱ) 若x满足不动点方程(6),则r=Φ(|x|-x),z=Ω(|x|+x)是线性互补问题LCP(q,A)的解.

证明 首先证明(ⅰ):假设向量(z,r)是线性互补问题LCP(q,A)的一个解,向量(z,r)是一组非负的向量,可以表示为z=Ω(|x|+x),r=Φ(|x|-x).根据线性互补问题LCP(q,A)的定义,可知,zTr=0,r=Az+q,因此,可以得到表示形式Φ(|x|-x)=AΩ(|x|+x)+q.

这样就验证了(ⅰ)的结论.

线性互补问题LCP(q,A)的表达形式为r=Az+q,设r=Φ(|x|-x)和z=Ω(|x|+x),易知

(a) 如果xi>0,那么zi>0,ri=0; (b) 如果xi=0,那么zi=0,ri=0; (c) 如果xi<0,那么zi=0,ri>0.

因此,可知zTr=0恒成立,它满足线性互补问题LCP(q,A)的条件,所以r=Φ(|x|-x)和z=Ω(|x|+x)是线性互补问题LCP(q,A)的一个解.这就验证了(ⅱ)的结论.

注:引理1说明了可以通过求解不动点方程(6)得到了线性互补问题LCP(q,A)的解.

迭代方程(6)只提供了求解线性互补问题LCP(q,A)的一个方程模型,为了能够在实际运算的时候更加快速的求解线性互补问题LCP(q,A),可以基于AOR,SOR,GS,J分裂迭代方法,提出了相应的分裂迭代方法,本文仅介绍基于模系数矩阵分裂形式的改进加速快速松弛方法.

在还原环境中，当有机质存在时，脱硫酸细菌能使SO42-还原为H2S，结果使得地下水中SO42-减少，pH值变大。

在实际运算中选取了合适的松弛参数α和β,会使方程的收敛性大大提高,加快运算速度.

1.2 收敛性分析

(7)

证明 由式(6)～式(7)可知,误差向量满足如下方程:

整理可得

(8)

对角部分元素:

非对角部分元素:

2 数值算例

例1 在线性互补问题LCP(q,A)中,令矩阵A为

在式(6)中,令Ω=I,κij=0(i≠j),则式(6)将变为如下形式,

表1是迭代方程(5)(κij=0(i≠j))的数值算例结果,表2是迭代方程(6)(κij≠0(i≠j))的数值算例结果,从迭代步数和迭代时间两方面进行比较.矩阵的阶数分为三种情况考虑.

表1 文献[16]中的迭代结果

表2 本文方法的迭代结果

在迭代方程(6)中,令Ω=5I,下面表3是迭代方程(5)(κij=0(i≠j))的数值算例结果,表4是迭代方程(6)(κij≠0(i≠j))的数值算例结果，从迭代步数和迭代时间两方面进行比较。矩阵的阶数分为三种情况考虑。

表3 文献[16]中的迭代结果

表4 本文方法的迭代结果

从表1～表4可以看出,相比迭代方程(5),迭代方程(6)需要更少的迭代步数和更短的迭代时间,因此,本文给出的方法需要更少的迭代步数和更短的迭代时间,对于求解线性互补问题是可行和有效的.

3 结 语

本文是从一般加速的基于模系数矩阵分裂迭代方法出发,将收敛所需满足的条件一般化,提出了一种改进加速分裂迭代方法,且给出了系数矩阵是 矩阵的收敛定理,通过数值算例说明了在选择了合适的参数矩阵的条件下提出的改进加速分裂迭代方法是可行和有效的.

[ 1 ] YANG H J, LI Q. A multiplicative multisplitting method for solving the linear complementarity problem[J]. Computers and Mathematics with Applications, 2009,58(10):1970-1978.

[ 2 ] MEHDI D, MASOUD H. Two class of synchronous matrix multisplitting schemes for solving linear complementarity problems[J]. Journal of Computational and Applied Mathematics, 2011, 235(15):4325-4336.

[ 3 ] ZHENG N, YIN J F. On the convergence of projected triangular decomposition methods for pricing American options with stochastic volatility[J]. Applied Mathematics and Computation, 2013,223(3):411-422.

[ 4 ] ZHANG L T, ZUO X Y, GU T X, et al. Improved convergence theorems of multisplitting methods for the linear complementarity problem[J]. Applied Mathematics and Computation, 2014,243(4):982-987.

[ 5 ] ZHANG L T, LI J L. The weaker convergence of modulus-based synchronous multisplitting multi-parameters methods for linear complementarity problems[J]. Computers and Mathematics with Applications, 2014,67(10):1954-1959.

[ 6 ] ZHANG L L. Two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Numerical Algorithms, 2011,57(1):83-99.

[ 7 ] KE Y F, MA C F. On the convergence analysis of two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Applied Mathematics and Computation, 2014,243:413-418.

[ 8 ] DONG J L, JIANG M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2009,16(2):129-143.

[ 9 ] BAI Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2010,17(6):917-933.

[10] ZHANG L L, REN Z R. Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Applied Mathematics Letters, 2013,26(6): 638-642.

[11] ZHANG L L , ZHANG Y P , REN Z R. New convergence proofs of modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Linear Algebra and its Application, 2015,481:83-93.

[12] ZHONG Z B, ZHANG L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2013,20(3):425-429.

[13] BAI Z Z , ZHANG L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013,62(1):59-77.

[14] Zhang L L. Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems[J]. Journal of Optimization Theory and Applications, 2014,160(1):189-203.

[15] ZHENG N, YIN J F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem[J]. Numerical Algorithms, 2013,64(2):245-262.

[16] LI W. A general modulus-based matrix splitting method for linear complementarity problems of matrices[J]. Applied Mathematics Letters, 2013,26(12):1159-1164.

【责任编辑: 肖景魁】

Modified Accelerated Splitting Iteration Method for Linear Complementarity Problem

ShenHailong,WeiTong

(Department of Mathematics, Northeastern University, Shenyang 110819, China)

Based on evolution method of modulus-based matrix splitting iteration method, the convergence condition was generalized; a modified accelerated splitting iteration method was proposed. The new method can be proved to be equivalent to the linear complementarity problem theoretically and compared to other methods; a new convergence theorem with matrix was put forward. With numerical examples, the new method was proved to need less iteration step numbers and shorter running time.

linear complementarity problem; matrix splitting; iteration method; matrix; convergence

2016-04-29

国家自然科学基金资助项目(11071033).

沈海龙(1971-),男,吉林延吉人,东北大学讲师,博士.

2095-5456(2016)05-0420-05

O 241 6

A