• 论文 • 上一篇    

改进的分块模方法求解对角占优线性互补问题

张丽丽1, 任志茹2   

  1. 1. 河南财经政法大学数学与信息科学学院, 郑州 450046;
    2. 中央财经大学统计与数学学院, 北京 100081
  • 收稿日期:2021-01-26 出版日期:2021-08-15 发布日期:2021-08-20
  • 通讯作者: 任志茹,renzr@cufe.edu.cn.
  • 基金资助:
    河南省高等学校重点科研项目(21A110003),河南财经政法大学信和·黄廷方青年学者资助计划,国家自然科学基金(11771467),中央财经大学学科建设经费和中央高校基本科研业务费专项资金资助.

张丽丽, 任志茹. 改进的分块模方法求解对角占优线性互补问题[J]. 计算数学, 2021, 43(3): 401-412.

Zhang Lili, Ren Zhiru. AN IMPROVED BLOCK MODULUS METHOD FOR DIAGONALLY DOMINANT LINEAR COMPLEMENTARITY PROBLEMS[J]. Mathematica Numerica Sinica, 2021, 43(3): 401-412.

AN IMPROVED BLOCK MODULUS METHOD FOR DIAGONALLY DOMINANT LINEAR COMPLEMENTARITY PROBLEMS

Zhang Lili1, Ren Zhiru2   

  1. 1. School of Mathematics and Information Science, Henan University of Economics and Law, Zhengzhou 450046, China;
    2. School of Statistics and Mathematics, Central University of Finance and Economics, Beijing 100081, China
  • Received:2021-01-26 Online:2021-08-15 Published:2021-08-20
为了高效求解中小型线性互补问题,本文提出了改进的分块模方法,并证明了关于严格对角占优(对角元素均为正数)线性互补问题的收敛性.对于广义对角占优线性互补问题,先将其转化为严格对角占优线性互补问题,再采用改进的分块模方法求解.数值结果表明,改进的分块模方法在求解广义对角占优线性互补问题时在内迭代次数和计算时间上均明显优于分块模方法.
To solve the small and medium-sized linear complementarity problems efficiently, we present an improved block modulus method and prove its convergence for the strictly diagonally dominant (with positive diagonal entries) linear complementarity problem. For the generalized diagonally dominant linear complementarity problem, it is first turned into a strictly diagonally dominant one and then solved by the improved block modulus method. Numerical results show that the improved block modulus method is obviously superior to the block modulus method in terms of the number of inner iterations and the computing time for solving the generalized diagonally dominant linear complementarity problems.

MR(2010)主题分类: 

()
[1] Murty K G. Linear Complementarity, Linear and Nonlinear Programming[M]. Berlin:Heldermann-Verlag, 1988.
[2] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem[M]. San Diego:Academic Press, 1992.
[3] Ferris M C, Pang J S. Engineering and economic applications of complementarity problems[J]. SIAM Rev., 1997, 39(4):669-713.
[4] van Bokhoven W M G. Piecewise-Linear Modelling and Analysis[M]. Eindhoven:Proefschrift, 1981.
[5] Kappel N W, Watson L T. Iterative algorithms for the linear complementarity problem[J]. Int. J. Comput. Math., 1986, 19(3-4):273-297.
[6] Dong J L, Jiang M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numer. Linear Algebra Appl., 2009, 16(2):129-143.
[7] Hadjidimos A, Tzoumas M. Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem[J]. Linear Algebra Appl., 2009, 431(1-2):197-210.
[8] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2010, 17(6):917-933.
[9] Zhang L L. Two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Numer. Algorithms, 2011, 57(1):83-99.
[10] 张丽丽. 关于线性互补问题的模系矩阵分裂迭代方法[J]. 计算数学, 2012, 34(4):373-386.
[11] Bai Z Z, Zhang L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2013, 20(3):425-439.
[12] Li W. A general modulus-based matrix splitting method for linear complementarity problems of H-matrices[J]. Appl. Math. Lett., 2013, 26(12):1159-1164.
[13] Zheng N, Yin J F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem[J]. Numer. Algorithms, 2013, 64(2):245-262.
[14] Zheng N, Yin J F. Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an H+-matrix[J]. J. Comput. Appl. Math., 2014, 260:281-293.
[15] Xu W W, Liu H. A modified general modulus-based matrix splitting method for linear complementarity problems of H-matrices[J]. Linear Algebra Appl., 2014, 458:626-637.
[16] Dong J L, Gao J B, Ju F J, Shen J H. Modulus methods for nonnegatively constrained image restoration[J]. SIAM J. Imaging Sciences, 2016, 9(3):1226-1246.
[17] Li W, Zheng H. A preconditioned modulus-based iteration method for solving linear complementarity problems of H-matrices[J]. Linear Multilinear Algebra, 2016, 64(7):1390-1403.
[18] Wu S L, Li C X. Two-sweep modulus-based matrix splitting iteration methods for linear complementarity problems[J]. J. Comput. Appl. Math., 2016, 302:327-339.
[19] Bai Z Z, Zhang L L. Modulus-based multigrid methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2017, 24(6):e2105.
[20] Yang X, Huang Y M, Sun L. A modulus iteration method for retinex problem[J]. Numer. Linear Algebra Appl., 2018, 25(6):e2207.
[21] Zhang L T, Jiang D D, Zuo X Y, Zhao Y C, Zhang Y F. Relaxed modulus-based synchronous multisplitting multi-parameter methods for linear complementarity problems[J]. Mobile Netw. Appl., 202126(2):745-754.
[22] Hadjidimos A, Zhang L L. Comparison of three classes of algorithms for the solution of the linear complementarity problem with an H+-matrix[J]. J. Comput. Appl. Math., 2018, 336:175-191.
[23] Berman A, Plemmons R J. Nonnegative Matrices in the Mathematical Sciences[M]. New York:Academic Press, 1979.
[24] Bai Z Z. On the convergence of the multisplitting methods for the linear complementarity problem[J]. SIAM J. Matrix Anal. Appl., 1999, 21(1):67-78.
[25] Frommer A, Szyld D B. H-splittings and two-stage iterative methods[J]. Numer. Math., 1992, 63(1):345-356.
[26] Varga R S. Matrix Iterative Analysis[M]. Berlin and Heidelberg:Springer-Verlag, 2000.
[27] Frommer A, Mayer G. Convergence of relaxed parallel multisplitting methods[J]. Linear Algebra Appl., 1989, 119:141-152.
[28] 胡家赣.||B-1A||的估计及其应用[J]. 计算数学, 1982, 4(3):272-282.
[29] 胡家赣.尺度变换和矩阵分解的收敛性[J]. 计算数学, 1983, 5(1):72-78.
[30] Hadjidimos A, Lapidakis M, Tzoumas M. On iterative solution for linear complementarity problem with an H+-matrix[J]. SIAM J. Matrix Anal. Appl., 2012, 33(1):97-110.
[31] Wang A, Cao Y, Chen J X. Modified Newton-type iteration methods for generalized absolute value equations[J]. J. Optim. Theory Appl., 2019, 181(1):216-230.
[32] Alanelli M, Hadjidimos A. A new iterative criterion for H-matrices[J]. SIAM J. Matrix Anal. Appl., 2006, 29(1):160-176.
[33] Carlson D, Markham T L. Schur complements of diagonally dominant matrices[J]. Czech. Math. J., 1979, 29(2):246-251.
[1] 包学忠, 胡琳. 随机变延迟微分方程平衡方法的均方收敛性与稳定性[J]. 计算数学, 2021, 43(3): 301-321.
[2] 胡雅伶, 彭拯, 章旭, 曾玉华. 一种求解非线性互补问题的多步自适应Levenberg-Marquardt算法[J]. 计算数学, 2021, 43(3): 322-336.
[3] 李旭, 李明翔. 连续Sylvester方程的广义正定和反Hermitian分裂迭代法及其超松弛加速[J]. 计算数学, 2021, 43(3): 354-366.
[4] 邱泽山, 曹学年. 带漂移的单侧正规化回火分数阶扩散方程的Crank-Nicolson拟紧格式[J]. 计算数学, 2021, 43(2): 210-226.
[5] 袁光伟. 非正交网格上满足极值原理的扩散格式[J]. 计算数学, 2021, 43(1): 1-16.
[6] 朱梦姣, 王文强. 非线性随机分数阶微分方程Euler方法的弱收敛性[J]. 计算数学, 2021, 43(1): 87-109.
[7] 李天怡, 陈芳. 求解一类分块二阶线性方程组的QHSS迭代方法[J]. 计算数学, 2021, 43(1): 110-117.
[8] 丁戬, 殷俊锋. 求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法[J]. 计算数学, 2021, 43(1): 118-132.
[9] 尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[10] 古振东, 孙丽英. 非线性第二类Volterra积分方程的Chebyshev谱配置法[J]. 计算数学, 2020, 42(4): 445-456.
[11] 吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[12] 张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[13] 李枝枝, 柯艺芬, 储日升, 张怀. 二阶锥线性互补问题的广义模系矩阵分裂迭代算法[J]. 计算数学, 2019, 41(4): 395-405.
[14] 戴平凡, 李继成, 白建超. 解线性互补问题的预处理加速模Gauss-Seidel迭代方法[J]. 计算数学, 2019, 41(3): 308-319.
[15] 胡冬冬, 曹学年, 蒋慧灵. 带非线性源项的双侧空间分数阶扩散方程的隐式中点方法[J]. 计算数学, 2019, 41(3): 295-307.
阅读次数
全文


摘要