解线性互补问题的预处理加速模Gauss-Seidel迭代方法

doi:10.12286/jssx.2019.3.308

计算数学 ›› 2019, Vol. 41 ›› Issue (3): 308-319.DOI: 10.12286/jssx.2019.3.308

解线性互补问题的预处理加速模Gauss-Seidel迭代方法

戴平凡¹, 李继成², 白建超³

1. 三明学院信息工程学院, 三明 365004;
2. 西安交通大学数学与统计学院, 西安 710049;
3. 西北工业大学应用数学系, 西安 710129

收稿日期:2017-12-16 出版日期:2019-09-15 发布日期:2019-08-21
基金资助:
国家自然科学基金（11671318）；福建省自然科学基金（2016J01028）；福建省教育厅科技项目（JA15469）资助.

PDF ( 377 ) 引用

戴平凡, 李继成, 白建超. 解线性互补问题的预处理加速模Gauss-Seidel迭代方法[J]. 计算数学, 2019, 41(3): 308-319.

Dai Pingfan, Li Jicheng, Bai Jianchao. A PRECONDITIONED ACCELERATED MODULUS-BASED GAUSS-SEIDEL ITERATION METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEM[J]. Mathematica Numerica Sinica, 2019, 41(3): 308-319.

A PRECONDITIONED ACCELERATED MODULUS-BASED GAUSS-SEIDEL ITERATION METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEM

Dai Pingfan¹, Li Jicheng², Bai Jianchao³

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

Received:2017-12-16 Online:2019-09-15 Published:2019-08-21

本文提出了解线性互补问题的预处理加速模系Gauss-Seidel迭代方法，当线性互补问题的系统矩阵是M-矩阵时证明了方法的收敛性，并给出了该预处理方法关于原方法的一个比较定理.数值实验显示该预处理迭代方法明显加速了原方法的收敛.

关键词： 线性互补问题, 预处理, 模系Gauss-Seidel迭代方法, 比较定理

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 words: Linear complementarity problems, Preconditioning, Modulus-based GaussSeidel iterative method, Comparison theorem

MR(2010)主题分类:

65F10

分享此文:

[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]	缪树鑫. 关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记[J]. 计算数学, 2022, 44(1): 89-96.
[2]	胡雅伶, 彭拯, 章旭, 曾玉华. 一种求解非线性互补问题的多步自适应Levenberg-Marquardt算法[J]. 计算数学, 2021, 43(3): 322-336.
[3]	张丽丽, 任志茹. 改进的分块模方法求解对角占优线性互补问题[J]. 计算数学, 2021, 43(3): 401-412.
[4]	何颖, 刘皞. 一类Toeplitz线性代数方程组的预处理GMRES方法[J]. 计算数学, 2021, 43(2): 177-191.
[5]	丁戬, 殷俊锋. 求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法[J]. 计算数学, 2021, 43(1): 118-132.
[6]	吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[7]	曹阳, 陈莹婷. 正则化HSS预处理鞍点矩阵的特征值估计[J]. 计算数学, 2020, 42(1): 51-62.
[8]	王丽, 罗玉花, 王广彬. 求解加权线性最小二乘问题的一类预处理GAOR方法[J]. 计算数学, 2020, 42(1): 63-79.
[9]	李枝枝, 柯艺芬, 储日升, 张怀. 二阶锥线性互补问题的广义模系矩阵分裂迭代算法[J]. 计算数学, 2019, 41(4): 395-405.
[10]	李郴良, 田兆鹤, 胡小媚. 一类弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法[J]. 计算数学, 2019, 41(1): 91-103.
[11]	刘忠祥, 王翠薇, 王增琦. 求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进[J]. 计算数学, 2018, 40(3): 271-286.
[12]	郑华, 罗静. 一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J]. 计算数学, 2018, 40(1): 24-32.
[13]	骆其伦, 黎稳. 二维Helmholtz方程的联合紧致差分离散方程组的预处理方法[J]. 计算数学, 2017, 39(4): 407-420.
[14]	甘小艇, 殷俊锋. 二次有限体积法定价美式期权[J]. 计算数学, 2015, 37(1): 67-82.
[15]	曹阳, 陶怀仁, 蒋美群. 鞍点问题的广义位移分裂预条件子[J]. 计算数学, 2014, 36(1): 16-26.

阅读次数

全文

摘要

解线性互补问题的预处理加速模Gauss-Seidel迭代方法

A PRECONDITIONED ACCELERATED MODULUS-BASED GAUSS-SEIDEL ITERATION METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEM

扫码分享