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

doi:10.12286/jssx.j2021-0774

计算数学 ›› 2021, Vol. 43 ›› Issue (3): 401-412.DOI: 10.12286/jssx.j2021-0774

• 论文 • 上一篇

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

张丽丽¹, 任志茹²

1. 河南财经政法大学数学与信息科学学院, 郑州 450046;
2. 中央财经大学统计与数学学院, 北京 100081

收稿日期:2021-01-26 出版日期:2021-08-15 发布日期:2021-08-20
通讯作者: 任志茹,renzr@cufe.edu.cn.
基金资助:
河南省高等学校重点科研项目（21A110003），河南财经政法大学信和·黄廷方青年学者资助计划，国家自然科学基金（11771467），中央财经大学学科建设经费和中央高校基本科研业务费专项资金资助.

PDF ( 151 ) 引用

张丽丽, 任志茹. 改进的分块模方法求解对角占优线性互补问题[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 Lili¹, Ren Zhiru²

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.

Key words: linear complementarity problem, block modulus method, diagonally dominant matrix, convergence

MR(2010)主题分类:

65F10

分享此文:

[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]	余妍妍, 代新杰, 肖爱国. 非自治刚性随机微分方程正则EM分裂方法的收敛性和稳定性[J]. 计算数学, 2022, 44(1): 19-33.
[2]	邵新慧, 亢重博. 基于分数阶扩散方程的离散线性代数方程组迭代方法研究[J]. 计算数学, 2022, 44(1): 107-118.
[3]	古振东. 非线性弱奇性Volterra积分方程的谱配置法[J]. 计算数学, 2021, 43(4): 426-443.
[4]	包学忠, 胡琳. 随机变延迟微分方程平衡方法的均方收敛性与稳定性[J]. 计算数学, 2021, 43(3): 301-321.
[5]	胡雅伶, 彭拯, 章旭, 曾玉华. 一种求解非线性互补问题的多步自适应Levenberg-Marquardt算法[J]. 计算数学, 2021, 43(3): 322-336.
[6]	李旭, 李明翔. 连续Sylvester方程的广义正定和反Hermitian分裂迭代法及其超松弛加速[J]. 计算数学, 2021, 43(3): 354-366.
[7]	邱泽山, 曹学年. 带漂移的单侧正规化回火分数阶扩散方程的Crank-Nicolson拟紧格式[J]. 计算数学, 2021, 43(2): 210-226.
[8]	袁光伟. 非正交网格上满足极值原理的扩散格式[J]. 计算数学, 2021, 43(1): 1-16.
[9]	朱梦姣, 王文强. 非线性随机分数阶微分方程Euler方法的弱收敛性[J]. 计算数学, 2021, 43(1): 87-109.
[10]	李天怡, 陈芳. 求解一类分块二阶线性方程组的QHSS迭代方法[J]. 计算数学, 2021, 43(1): 110-117.
[11]	丁戬, 殷俊锋. 求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法[J]. 计算数学, 2021, 43(1): 118-132.
[12]	尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[13]	古振东, 孙丽英. 非线性第二类Volterra积分方程的Chebyshev谱配置法[J]. 计算数学, 2020, 42(4): 445-456.
[14]	吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[15]	张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.

阅读次数

全文

摘要

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

AN IMPROVED BLOCK MODULUS METHOD FOR DIAGONALLY DOMINANT LINEAR COMPLEMENTARITY PROBLEMS

扫码分享