首页资源分类DSP > 一类特殊的非对称线性互补问题的两步迭代法

一类特殊的非对称线性互补问题的两步迭代法

已有 445122个资源

下载专区

上传者其他资源

    文档信息举报收藏

    标    签:两步迭代TwIST

    分    享:

    文档简介

    一类特殊的非对称线性互补问题的两步迭代法

    文档预览

    第25卷第1期 2005年2月 桂林电子工业学院学报 JoURNAL 0F GUILIN UNIVERSITY oF ELECTRoNIC TECHNoLoGY V01.25,No.1 Feb.2005 一类特殊的非对称线性互补问题的两步迭代法 单美静,李郴良,唐清干 (桂林电子工业学院计算科学与数学系,广西桂林541004) 摘要:线性互补问题的高效能算法在大规模科学计算与工程中至关重要。而两步迭代法是一个适合 求解大规模问题的有效算法。基于非对称逐次超松弛迭代法和投影共轭梯度迭代法的思想,文中提出了 一类求解系数矩阵为三对角非对称M矩阵的线性互补问题的uss0RP—PcG算法——两步迭代法。在 建立算法收敛性定理之后,证明了算法的收敛性。数值例子通过扩大系数矩阵的规模,并与逐次超松弛 迭代法比较来验证算法对于大规模问题具有高效性和良好的收敛性。 关键词:线性互补问题;USs0RP—PcG算法;两步迭代法;收敛性 中图分类号:0241 文献标识码;A 文章编号:1001—7437(2005)01—62一04 引言 1预备知识 线性互补问题[1]在大型科学与工程计算中的广 泛应用,使得人们将研究方面逐渐转向互补问题的高 效解法。考虑到以往出现的迭代法,如Jacobi迭代 法,Gauss—Seidel迭代法,SOR法,SSOR法以及这些 方法的改进和加速形式[2]对于大规模矩阵均有其各 自的局限性,于是充分利用已有的各迭代法之优点取 长补短。此时,两步法自然就应运而生。早先类似两 步法的思想由Mo托和Toraldo在文献[3]中提出, 后来M.ko占vara和J.Zowe在文献[4]中加以改进并 运用到系数矩阵为对称正定的线性互补问题中,同时 进行了收敛性的分析。此算法拥有一些好的特性,可 以通过离散逼近问题的近似解来有效地削减误差,在 具体实施中具有很好的实际计算效果。本文将两步 法推广到求解非对称线性互补问题。 以R”表示咒维欧氏空间,对于向量 z一(z1,z2,…,z。)1,y(y1,y2,…,y。)1∈R”, 规定z≥y,当且仅当 zi≥M,i=1,2,…,咒. 定义1[1] (线性互补问题)对于任意给定的6∈ 彤,A∈R以“,线性互补问题(LCP)是指:求z∈R”使 得 z≥O,Az一6≥0,zT(Az一6)一0 (1) 定义2[5](上解集)称5一{z∈彤:z≥o,Az一6≥ o)为问题(1)的上解集。 在实际应用当中,经常遇到以大型稀疏矩阵为系 数矩阵的线性互补问题。因此,很多求解此类问题的 有效算法已经被提出。这里讨论其中三种较为典型的 算法: (1)SORP法(投影逐次超松驰迭代法),这种算 法以其理论简单而著称。 (2)PcGA法(带有效集族的投影共轭梯度法), 在给定有效集时,这种算法比SOR尸法收敛速度快。 (3)MG法(多重网格法),这是三种算法中收敛 速度最快的。但是需要构造辅助问题来解决。 本文研究给出的算法比(1),(2)中提到了sORP 法、PcGA法更有效,并且借鉴了(3)中MG算法的 思想,在每一步迭代中都包括对辅助问题的近似解的 收稿日期:2004—11—24 基金项目:国家自然科学基金(10371035)I桂林电子工业学院软科学项目(D20348) 作者简介:单美静(1979一),女,辽宁大连人,桂林电子工业学院计算科学与数学系硕士研究生,研究方向为互补问题的算法、微分差分方程 的数值解.  万方数据 第1期 单美静等:一类特殊的非对称线性互补问题的两步迭代法 63 松驰逼近。 假设对于问题(1)的解z。找到一个近似序列 {z),定义指标集J(z).考虑问题的条件z≥o, 贝Ⅱ Jr(z)一{i fzt=O}. 令户(z)为J(z)的基数集, PJ(。):R“—}R”一“种. 这里如不引起混乱将省略z,并记J’一J(z。)。 2算法 3收敛性定理 针对系数矩阵A为对称正定矩阵,文献[4]中已 经分析了算法的收敛性。本文尝试将该算法的收敛性 推广到系数矩阵A为三对角M阵的情况,建立并证 明收敛性定理。 定义3[幻 (三对角M矩阵)咒×行实三对角矩 阵, 2.1 USSoRP算法 扩l:ma出;+薏@一善硎+1一 ∑口捌),o) (2) j≥i 2.2基本算法(算法1) 令zo∈S,优∈N,s∈Ⅳ,志一0,1,2,…: 第1步:实施m步USSoRP算法,并令 ∥+%=USSoRP“(∥;A,6,0); 第2步:定义P,,其中J—J(zH坛),并计算 ,=6一A∥+K. 矿=(PJAP})一1P,一, z‘+1一z‘+蚝+yP丁2‘, 其中y是7≤1的最小实数,∥+1∈S. 我们注意到.如果j(z蚪地)=,(z。),那么就有 z蚪1=z。.算法lI门第2步在修正残量∥时,最主要 的工作是解线性方程组(P,AP于)∥一P,∥.这里使用 PCG迭代算法。考虑诸多因素,将该算法改进推广, 得到一类求解非对称线性互补问题的UsSORP— PcG算法(两步迭代法)。 2.3 UssoRP—PCG算法(算法2) 令zo∈5,m∈Ⅳ,s∈Ⅳ,愚一0,1,2,… 第1步:实施优步usSORP算法,并令 z蚪%一USSORP”(∥;A,6,O); 第2步:定义P,,其中J=J(z蚪圮),并计算 ∥一6一Az蚪坯.实旋s步PCG并定义. ∥一PCG5(o,P,AP7,P,,). 下一步迭代为 z‘十1一z‘+%+,iP7z‘, 其中),是y≤1的最小实数,∥+1∈S.  万方数据 A一 ’. 口H一1” 口M—l 口^“ 如果A元素满足鼬>o,(i一1,…,,z); 口f』<0,(J=i一1,i一2,…,咒; _『一i+1,i一1,…,,z一1) 而且各行元素之和满足口11+口12>o,口。。一1+口。。>o; %+∑口玎>o. 则A为三对角M阵。 由算法2知,系数阵P,AP歹仍是M阵,剩余, 非正,易证引理1. 引理1 z‘一PCG5(o,PJAP7,PJ,)存在排列矩 阵P,,使得以20—o为初始点经过s步PCG算法迭 代产生的结果z‘≤o. 弓I理2[63 若z‘∈S,贝0 z‘+1∈S. 定理1设矩阵A为三对角M矩阵,则对于 o<叫<订薪, USSORP—PcG算法产生的迭代序列{z‘)t∈Ⅳ收敛于 问题(1)的解z’.这里 ㈣一m?x善…以,一薏 证明:由三对角M矩阵定义知: ∑‰I<%,江1,…㈣ 即II B|I<1. 首先,讨论算法2的第1步:z抖坛=UsSORP” (z‘;A,6)为不引起混乱,这里用y抖1来表示z蚪兄, y,。y;+私一争,y;一善叫+1) 由(2)式得到: 1)当∥十1>o,∥>o时,当i一1时, 64 桂林电子工业学院学报 2005年2月 y{+1一y{一豢(6·一口,ty{一 口12yl…·一口hy:)<o; 依此类推,当i一,z一户时, 业±;一y:一,= ::二:}=二:‘6一一一一口n一一,·yi+1一 …· 口。一声,2yl+1 一口。一声,。一声一ly:±;一1 一 口。一声,H一声y:一户一口。一声,。一声+ly:一声+1一 …一缸"y:)_若三× [(6一Aj,‘)。一p一口。一川(y{+1一yi)一 …一口。一p,。一p—l(y:±;一1一y:一p一1)] 而(6一句‘)。一p<o,(y{+1一y{)<o,…, (y:±;一l—y:一p一1)<o 所以可知y:±;<露一,,即{y‘)是递减序列。 2)当y;+1一O,y;≥O时,显然y;+1≤y?,即{y”) 是递减序列。 3)当y;+1>o,y;=o时,此种情况不存在,具体 证明如下: 假设了;+1>o,y净。这种情况存在,当i一1时, y{+1一y{= 豢(6·一口,ty:一口·zyl一…一口,”y:)= 暑(卜∥)-<o, 而(2)式可知,可得y{+1一o. 当i一2时, j,i+1一yl= 三(6z一乜z-yi一口zz业一…一nz。y:)一 薏(6z一日z,yi一口zzyl一…一日z”y:)+ 警(yi一斫+1)一 罴(6一∥)z<o 仍由(2)式,可得奠+1一o. 依此类推,同理可证当v;一。时,必有y;+1一o. 即情况3)不存在。 综上所述,可见算法2第1步是下降的,即经过 m步USSORP算法迭代得z蚪坛<z2. 由(1)式可知残量r‘=6一Az¨蚝≤o.根据引理1 的结论z‘≤o,可知y尸&‘≤o,结合z抖1一∥+yP&‘, 得到{∥)减序列。而依题意∥≥o,得到{∥)是单调递 减有下界。根据单调有界数列是收敛的,可知算法2 产生的迭代序列{z‘)。∈Ⅳ收敛。 设{z‘)t∈Ⅳ收敛于z。,现证z。是原问题的解。对 z‘+1一z‘+玩+yP,2‘ 两边取极限得到 z’一z。+yP矗+, 其中z。是序列{z‘)的极限,整理得到2’=o.又有, ∥=PCG5(o,PJAP丁,PJ,)∈尺”一p。’, 所以得知当i∈ⅣV(z)时,z,>o且(6一Az。),一。 当i∈,(z)时,z,一0且(6一Az+)i>0.结合以上两 种情况,得知z。≥o,Az。一6≥o, (z。)丁(Az。一6)一o,即z。是原问题的解。证毕。 4数值实验 在这一节中我们在PⅣ1.7G、256M内存兼容机 上针对算法2编制一个C语言程序,以验证其有效 性。考虑如下线性互补问题Ⅲ: z≥0,Az一6≥O,zT(Az一6)一0, 其中6一(1,一1,1,一1,…,一1)T为以×1列向量, 4 一2 O ●●● O O 一1 4 一2 ●●● 0 0 A一 一 0;0 1;0 ●●● ● ● ● 4;O ●●● O;4 一 O;2 O O O ●●● 一1 4 运行算法时选取zo一(1,1,…,1)T∈S,参数7—1, cc,一1.84,迭代终止准则为 I|∥“一∥||<10~. 数值实验结果见表1.  万方数据 第1期 单美静等:一类特殊的非对称线性互补问题的两步迭代法 65 阶数 表1不同算法的数值实验结果比较 算法 迭代次数 m一5,s=1 运行时间 (s) 运行结果 0∥+1一≯ 注:(1)表1中,m表示两步法中ussORP算法的迭代次数,s表示两步法中PcG算法的迭代次数。在计算过程中,考虑 到≯+M的零元个数及运算效率,故选择m=5,s=1是比较合理的。 (2)从表1可以看出,本文提出的两步迭代法比soRP方法的数值效果要好。通过数值例子验证,这种优势还可以 推广到系数矩阵规模更大的情况。 参考文献: [1] Pang J s,stone R E.The 1inear complementarity problem[M]. San Diego:Academic Press,1 992. [2]陈景良,陈向举特殊矩阵[M].北京:清华大学出版社,2001. [3] Mor邑J,Toraldo G.on the s01ution of 1arge quadratic progra— mming problems with bound constraints.SIAM J.0ptimization 1991.1。93—113. [4] Michal KoEvara,Jochem zowe.An iterative two—step algorithm for linear complementarity problem口].Numerische Mathematik 86 1994,95—106. [5] Hoppe R H W:Multigrid algorithms for variationalinequalities 口].sIAM J.Numer.Anal-1987,1046—1065. [6] Pasi Tarvainen.B10ck relaxation methods for algebraic obstacle problems with M—matrices:theory and applications[M]. JYVAASKYLA:University JyvAskylA,1 994. Two—step IteratiVe Method for a C lass of Special UUnnsSvVmmmmeettrrilcCal Lilnear CU0mplementarity Problem sHAN M以一j汲g,LI Chen—liang,TANG Q讽g—gan (Dept.of Computing Science and Mathematics,Guilin 541 004,China) Abstract: It is significant to study the high efficiency methods for solving the linear complementarity problems commonly confronted in science and engineering. Two—step iterative method is an efficient method suitable for numerical computing. MotiVated on the idea of USSORP method and PCG method,a two~step method for s01Ving an unsymmetricallinear complementarity problem with tridiagonal matrix is proposed. A conVergence theorem of the method is established and proved.Numerical experiment results demonstrate that the algorithm is efficient and reliable. Key words: linear complementary problem, USSORP—PCG algorithm, two—step iteration method, conVergence (责任编辑梁王欢)  万方数据 一类特殊的非对称线性互补问题的两步迭代法 作者: 作者单位: 刊名: 英文刊名: 年,卷(期): 单美静, 李郴良, 唐清干, SHAN Mei-jing, LI Chen-liang, TANG Qing-gan 桂林电子工业学院,计算科学与数学系,广西,桂林,541004 桂林电子工业学院学报 JOURNAL OF GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY 2005,25(1) 参考文献(6条) 1.Pang J S;Stone R E The linear complementarity problem 1992 2.陈景良;陈向晖 特殊矩阵 2001 3.MoreJ;Toraldo G On the solution of large quadratic programming problems with bound constraints[外 文期刊] 1991 4.Michal Kocvara;Jochem Zowe An iterative two-step algorithm for linear complementarity problem 1994 5.Hoppe R H W Multigrid algorithms for variational inequalities 1987 6.Pasi Tarvainen Block relaxation methods for algebraic obstacle problems with M-matrices: theory and applications 1994 引用本文格式:单美静.李郴良.唐清干.SHAN Mei-jing.LI Chen-liang.TANG Qing-gan 一类特殊的非对称线性互 补问题的两步迭代法[期刊论文]-桂林电子工业学院学报 2005(1)

    Top_arrow
    回到顶部
    EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。