计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2019, Vol. 41 Issue (3): 308-319    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
解线性互补问题的预处理加速模Gauss-Seidel迭代方法
戴平凡1, 李继成2, 白建超3
1. 三明学院信息工程学院, 三明 365004;
2. 西安交通大学数学与统计学院, 西安 710049;
3. 西北工业大学应用数学系, 西安 710129
A PRECONDITIONED ACCELERATED MODULUS-BASED GAUSS-SEIDEL ITERATION METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEM
Dai Pingfan1, Li Jicheng2, Bai Jianchao3
1. School of Information Engineering, Sanming University, Sanming 365004, China;
2. School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, 710049, China;
3. Department of Applied Mathematics, Northwestern Polytechnical University, Xi'an, 710129, China
 全文: PDF (360 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文提出了解线性互补问题的预处理加速模系Gauss-Seidel迭代方法,当线性互补问题的系统矩阵是M-矩阵时证明了方法的收敛性,并给出了该预处理方法关于原方法的一个比较定理.数值实验显示该预处理迭代方法明显加速了原方法的收敛.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词线性互补问题   预处理   模系Gauss-Seidel迭代方法   比较定理     
Abstract: In this paper, a preconditioned accelerated modulus-based Gauss-Seidel iteration method for solving linear complementarity problem is presented. The convergence analysis on the proposed method for solving the linear complementarity problem involved with an M-matrix is given, and a comparison theorem of the preconditioned method with respect to the original method is derived. Numerical examples show that the new method improves considerably convergence rate of the original accelerated modulus-based Gauss-Seidel iteration method for solving the linear complementarity problem.
Key wordsLinear complementarity problems   Preconditioning   Modulus-based GaussSeidel iterative method   Comparison theorem   
收稿日期: 2017-12-16; 出版日期: 2019-08-21
基金资助:

国家自然科学基金(11671318);福建省自然科学基金(2016J01028);福建省教育厅科技项目(JA15469)资助.

引用本文:   
. 解线性互补问题的预处理加速模Gauss-Seidel迭代方法[J]. 计算数学, 2019, 41(3): 308-319.
. A PRECONDITIONED ACCELERATED MODULUS-BASED GAUSS-SEIDEL ITERATION METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEM[J]. Mathematica Numerica Sinica, 2019, 41(3): 308-319.
 
[1] Berman A, Plemmons R. Nonnegative Matrix in the Mathematical Sciences[M]. Academic Press, New York, 1979.
[2] Cottle R, Pang J. Stone R.E. The Linear Complementarity Problem[M]. Academic Press, San Diego, 1992.
[3] Murty K. Linear Complementarity, Linear and Nonlinear Programming[M]. Haldermann Verlag, Berlin, 1988.
[4] Cryer W. The solution of a quadratic programming problem using systematic overrelaxation[J]. SIAM J. Control., 1971, 9:385-392.
[5] Mangasarian O. Solution of symmetric linear complementarity problems by iterative methods[J]. J. Optim. Theory Appl., 1977, 22:465-485.
[6] Ahn B. Solution of nonsymmetric linear complementarity problems by iterative methods[J]. J. Optim. Theory Appl., 1981, 33:185-197.
[7] Pang J. Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem[J]. J. Optim. Theory Appl., 1984, 42:1-17.
[8] Bai Z Z. On the convergence of the multisplitting methods for the linear complementarity problem[J]. SIAM J. Matrix Anal. Appl., 1999, 21:67-78.
[9] Bai Z Z, Evans D J. Matrix multisplitting relaxation methods for linear complementarity problems[J]. Int. J. Comput. Math., 1997, 63:309-326.
[10] Dehghan M, Hajarian M. Convergence of SSOR Methods for linear complementarity problems[J]. Oper. Res. lett., 2009, 37:219-223.
[11] W.M.G. Bokhoven v. A Class of Linear Complementarity Problems is Solvable in Polynomial Time. Unpublished paper, Dept.of Electrical Engineering, University of Technology, The Netherlands, 1980.
[12] Kappel N W, Watson L T. Iterative algorithms for the linear complementarity problem[J]. Int. J. Comput. Math., 1986, 19:273-296.
[13] Bai Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Linear Algebra Appl., 2010, 6:917-933.
[14] Dong J L, Jiang M Q. A modified modulus method for symmetric positive-definite linear complementarity problems[J]. Numer. Linear Algebra Appl., 2009, 16:129-143.
[15] Hadjidimos A, Tzoumas M. Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem[J]. Linear Algebra Appl., 2009, 431:197-210.
[16] Hadjidimos A, Lapidakis M, Tzoumas M. On iterative solution for linear complementarity problem with an H+-matrix[J]. SIAM J. Matrix Anal. Appl., 2011, 33:97-110.
[17] Zhang L L. Two-step modulus based matrix splitting iteration for linear complementarity problems[J]. Numer. Algor., 2011, 57:83-99.
[18] Zheng N, Yin J F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numer. Algor., 2013, 64:245-262.
[19] 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.
[20] Bai, Z Z, Zhang, L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numer. Algor., 2013, 62:59-77.
[21] Hadjidimos A, Noutsos D, Tzoumas M. More on modifications and improvements of classical iterative schemes for M-matrices[J]. Linear Algebra Appl., 2003, 364:253-279.
[22] Li W, Sun W. Modified Gauss-Seidel type methods and Jacobi type methods for Z-matrices[J]. Linear Algebra Appl., 2000, 317:227-240.
[23] Li W. The convergence of the modified Gauss-Seidel methods for consistent linear systems[J]. J. Comput. Appl. Math., 2003, 154:97-105.
[24] Li W. A note on the preconditioned Gauss-Seidel (GS) method for linear systems[J]. J. Comput. Appl. Math., 2005, 182:81-90.
[25] Wang L., Song Y. Preconditioned AOR iterative method for M-matrices[J]. J. Comput. Appl. Math., 2009, 226:114-124.
[26] Liu C.Y., Li C.L. A new preconditioned Generalised AOR methods for the linear complementarity problem based on a generalised Hadjidimos preconditioner[J]. East Asian J. Appl. Math., 2012, 2:94-107.
[27] Dai P F, Li J C, Li Y T, Bai J. A general preconditioner for linear complementarity problem with an M-matrix[J]. J. Comput. Appl. Math., 2017, 317:100-112.
[28] Varga R S. Matrix Iterative Analysis[M]. Prentice-Hall. Englewood Cliffs, NJ, 1962.
[29] Frommer A, Mayer G. Convergence of relaxed parallel multisplitting methods[J]. Linear Algebra Appl., 1989, 119:141-152.
[30] Neumann M, Plemmons R J. Convergence of parallel multisplitting iterative methods for Mmatrices[J]. Linear Algebra Appl., 1987, 88:559-573.
[31] Axelsson O. Iterative Solution methods. Cambridge University Press[M]. Cambridge, 1996.
[32] Seydel Rüdiger U. Tools for Computational Finance[M]. 4ed., Springer, 2009.
[33] Wilmott P, Dewynne J, Howison S. Option Pricing:Mathematical Models and Computation[M]. Oxford Financial Press, Oxford, UK, 1993.
[34] Ahn B H. Iterative methods for linear complementarity problems with upper-bounds on primary variables[J]. Math. Program., 1983, 26:295-315.
[1] 李枝枝, 柯艺芬, 储日升, 张怀. 二阶锥线性互补问题的广义模系矩阵分裂迭代算法[J]. 计算数学, 2019, 41(4): 395-405.
[2] 李郴良, 田兆鹤, 胡小媚. 一类弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法[J]. 计算数学, 2019, 41(1): 91-103.
[3] 刘忠祥, 王翠薇, 王增琦. 求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进[J]. 计算数学, 2018, 40(3): 271-286.
[4] 郑华, 罗静. 一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J]. 计算数学, 2018, 40(1): 24-32.
[5] 骆其伦, 黎稳. 二维Helmholtz方程的联合紧致差分离散方程组的预处理方法[J]. 计算数学, 2017, 39(4): 407-420.
[6] 李琴. Stokes方程的一种预处理方法[J]. 计算数学, 2017, 38(2): 81-90.
[7] 赵莲, 赵永华, 迟学斌. 基于计算与通信重叠的稀疏矩阵-向量乘积及其在AMG中的应用[J]. 计算数学, 2015, 36(3): 197-214.
[8] 甘小艇, 殷俊锋. 二次有限体积法定价美式期权[J]. 计算数学, 2015, 37(1): 67-82.
[9] 席钧, 曹建文. 美式期权定价的分数阶偏微分方程组及其数值离散方法[J]. 计算数学, 2014, 35(3): 229-240.
[10] 朱雪芳. 求解鞍点问题的一类广义SSOR预条件子[J]. 计算数学, 2014, 35(2): 117-124.
[11] 张秀梅, 王川龙. 求解大型非对称线性系统的一种新的预处理方法[J]. 计算数学, 2014, 35(1): 28-34.
[12] 曹阳, 陶怀仁, 蒋美群. 鞍点问题的广义位移分裂预条件子[J]. 计算数学, 2014, 36(1): 16-26.
[13] 于春肖, 苑润浩, 穆运峰. 新预处理ILUCG法求解稀疏病态线性方程组[J]. 计算数学, 2014, 35(1): 21-27.
[14] 任志茹. 三阶线性常微分方程Sinc方程组的结构预处理方法[J]. 计算数学, 2013, 35(3): 305-322.
[15] 范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10