下载文档原格式
求解线性互补问题的改进加速迭代方法沈海龙;魏彤【摘要】从基于模系数矩阵分裂迭代方法的演变方法出发，将收敛所需满足的条件一般化，提出了一种改进的加速分裂迭代方法。
理论分析表明新方法可以和线性互补问题等价转换，将新方法与其他几种方法进行比较分析，给出了系数矩阵是H+矩阵的收敛定理。
最后，通过数值算例证明了提出的新方法在运算过程中需要更少的迭代步数和更短的运行时间。
%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.【期刊名称】《沈阳大学学报》【年(卷),期】2016(028)005【总页数】5页(P420-424)【关键词】线性互补问题;矩阵分裂;迭代方法;H 矩阵;收敛【作者】沈海龙;魏彤【作者单位】东北大学理学院，辽宁沈阳 110819;东北大学理学院，辽宁沈阳110819【正文语种】中文【中图分类】O2416线性互补问题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)方面已经有了许多算法,但是这些算法大都存在着限制条件.对于任意向量x∈Cn,向量|x|+x和向量|x|-x都是非负向量而且各个分量之间乘积为零.Van Bokhoven利用了这个性质,在线性互补问题LCP(q,A) 中,令z:=|x|+x,r:=|x|-x,巧妙地将线性互补问题LCP(q,A)转化成为一个不动点方程,此方法为求解线性互补问题LCP(q,A)的模迭代方法[7].为了使模迭代方法的收敛速度能够提高,Dong和Jiang在模迭代方法的基础上引入了一个移位因子α>0,提出了改进型的模迭代方法[8],其格式为接着,Zhong-Zhi Bai在线性互补问题LCP(q,A) 中令z:=γ-1(|x|+x),r:=γ-1Ω(|x|-x).其中,γ>0,Ω是一个正对角矩阵,得到如下不动点方程因此,线性互补问题LCP(q,A)就转化为了求解不动点方程式(3)[9].为了更容易的求解式(3),将不动点方程左边的矩阵A∈Cn×n分裂成A=M-N,得到了基于模系数矩阵分裂迭代方法:令,直到迭代序列收敛,其中Ω1和Ω2是两个正对角矩阵.本文将方程(5)推广到更一般的情况,将正对角矩阵Ω2扩展为一个非负矩阵Φ.令是矩阵AΩ的两个分裂,方程(5)变为其中Ω=diag(ωi)是一个正对角矩阵,Φ=(κij)是一个非负矩阵.下面引理将证明线性互补问题LCP(q,A)可以和扩展之后得到的新方程等价转换. 引理是矩阵AΩ的两个分裂,Ω=diag(ωi)是一个正对角矩阵,Φ=(κij)是一个非负矩阵.对于线性互补问题LCP(q,A,则有:(ⅰ) 若(z,r)是线性互补问题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.由已知条件可知,,因此,这样就验证了(ⅰ)的结论.再证明(ⅱ)的正确性.由已知条件可知, ,因此,可以将不动点方程(6)写成如下形式: 线性互补问题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分裂迭代方法,提出了相应的分裂迭代方法,本文仅介绍基于模系数矩阵分裂形式的改进加速快速松弛方法.令.其中DAΩ是矩阵AΩ的对角矩阵,-LAΩ是矩阵的严格下三角矩阵,-UAΩ是矩阵AΩ的严格上三角矩阵,α和β为松弛参数.则改进加速快速松弛方法的迭代格式为在实际运算中选取了合适的松弛参数α和β,会使方程的收敛性大大提高,加快运算速度.由文献[7-9,16]可知,当线性互补问题LCP(q,A)的矩阵A是一个H+-矩阵时,线性互补问题LCP(q,A)有唯一解.如果假设是线性互补问题LCP(q,A)的精确解,由引理1可知其满足不动点方程:定理1 设矩阵A∈Cn×n是一个H+-矩阵,是AΩ的两个H-分裂,是一个M-矩阵,和是非负对角元素矩阵.Ω是一个正对角矩阵(Ω=(ωi)>0),Φ是一个非负矩阵(Φ=(κij)≥0).若参数矩阵是一个M-矩阵且是一个M-矩阵,对于任意的初始向量x(0)∈Cn迭代方程(6)所构造的迭代序列都收敛到线性互补问题LCP(q,A)的唯一解z*, 其中Φ=Φ′+Φ″ ,证明由式(6)～式(7)可知,误差向量满足如下方程:由已知是一个M-矩阵,是一个非负矩阵,〉是一个Z-矩阵,,易知是一个M-矩阵,是一个H-矩阵,因此.于是有整理可得由于〉是一个M-矩阵,是一个非负矩阵,是一个M-矩阵,则是一个M-分裂,且有<1,故是一个M-矩阵,它的逆矩阵是一个正矩阵.于是,式(8)可写成如下形式:设 .根据已知条件是一个M-矩阵,是一个非负矩阵,因此是一个M-分裂.只需证明是一个M-矩阵即可.将分成对角部分元素和非对角部分元素讨论.对角部分元素:非对角部分元素:|的对角部分元素可以表示为|,非对角部分元素可以表示为|.|的对角部分元素可以表示为|,非对角部分元素可以表示为|.通过上述对角部分与非对角部分讨论可知:根据已知条件可得,Ω-Φ是一个M-矩阵,于是有是一个M-矩阵,是一个M-分裂,则. 例1 在线性互补问题LCP(q,A)中,令矩阵A为且T,可知矩阵A是一个H+-矩阵,易知线性互补问题LCP(q,A)有唯一解.设初始向量,令Ω=I,I是一个单位矩阵,迭代误差为‖RES‖≤10-5 .在式(6)中,令Ω=I,κij=0(i≠j),则式(6)将变为如下形式,其中是一个正对角矩阵.表1是迭代方程(5)(κij=0(i≠j))的数值算例结果,表2是迭代方程(6)(κij≠0(i≠j))的数值算例结果,从迭代步数和迭代时间两方面进行比较.矩阵的阶数分为三种情况考虑.从表1～表4可以看出,相比迭代方程(5),迭代方程(6)需要更少的迭代步数和更短的迭代时间,因此,本文给出的方法需要更少的迭代步数和更短的迭代时间,对于求解线性互补问题是可行和有效的.本文是从一般加速的基于模系数矩阵分裂迭代方法出发,将收敛所需满足的条件一般化,提出了一种改进加速分裂迭代方法,且给出了系数矩阵是矩阵的收敛定理,通过数值算例说明了在选择了合适的参数矩阵的条件下提出的改进加速分裂迭代方法是可行和有效的.。
