Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems

doi:10.1007/s42967-023-00354-x

Communications on Applied Mathematics and Computation ›› 2025, Vol. 7 ›› Issue (5): 1617-1638.doi: 10.1007/s42967-023-00354-x

• ORIGINAL PAPERS • 上一篇

Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems

Qin-Qin Shen¹, Geng-Chen Yang², Chen-Can Zhou¹

1. School of Transportation and Civil Engineering, Nantong University, Nantong, 226019, Jiangsu, China;
2. School of Science, Nantong University, Nantong, 226019, Jiangsu, China

收稿日期:2023-08-18 修回日期:2023-11-21 接受日期:2023-11-24 出版日期:2024-05-07 发布日期:2024-05-07
通讯作者: Chen-Can Zhou,E-mail:zhouchencan@ntu.edu.cn E-mail:zhouchencan@ntu.edu.cn
基金资助:
This work was supported by the National Natural Science Foundation of China (No. 11771225) and the Qinglan Project of Jiangsu Province of China.

Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems

Qin-Qin Shen¹, Geng-Chen Yang², Chen-Can Zhou¹

1. School of Transportation and Civil Engineering, Nantong University, Nantong, 226019, Jiangsu, China;
2. School of Science, Nantong University, Nantong, 226019, Jiangsu, China

Received:2023-08-18 Revised:2023-11-21 Accepted:2023-11-24 Online:2024-05-07 Published:2024-05-07
Contact: Chen-Can Zhou,E-mail:zhouchencan@ntu.edu.cn E-mail:zhouchencan@ntu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (No. 11771225) and the Qinglan Project of Jiangsu Province of China.

摘要/Abstract

摘要： Recently, the projected Jacobi (PJ) and projected Gauss-Seidel (PGS) iteration methods have been studied for solving the horizontal linear complementarity problems (HLCPs). To further improve the convergence rates of the PJ and PGS iteration methods, by using the successive overrelaxation (SOR) matrix splitting technique, a projected SOR iteration method is introduced in this paper to solve the HLCP. Convergence analyses are carefully studied when the system matrices are strictly diagonally dominant and irreducibly diagonally dominant. The newly obtained convergence results greatly extend the current convergence theory. Finally, two numerical examples are given to show the effectiveness of the proposed PSOR iteration method and its advantages over the recently proposed PJ and PGS iteration methods.

关键词: Horizontal linear complementarity problem (HLCP), Matrix splitting, Projected method, Successive overrelaxation (SOR) iteration, Convergence

Abstract: Recently, the projected Jacobi (PJ) and projected Gauss-Seidel (PGS) iteration methods have been studied for solving the horizontal linear complementarity problems (HLCPs). To further improve the convergence rates of the PJ and PGS iteration methods, by using the successive overrelaxation (SOR) matrix splitting technique, a projected SOR iteration method is introduced in this paper to solve the HLCP. Convergence analyses are carefully studied when the system matrices are strictly diagonally dominant and irreducibly diagonally dominant. The newly obtained convergence results greatly extend the current convergence theory. Finally, two numerical examples are given to show the effectiveness of the proposed PSOR iteration method and its advantages over the recently proposed PJ and PGS iteration methods.

Key words: Horizontal linear complementarity problem (HLCP), Matrix splitting, Projected method, Successive overrelaxation (SOR) iteration, Convergence

Qin-Qin Shen, Geng-Chen Yang, Chen-Can Zhou. Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(5): 1617-1638.

参考文献

[1] Bai, Z.-Z.: On the monotone convergence of the projected iteration methods for linear complementarity problem. Numer. Math. J. Chin. Univ. (Engl. Ser.) 5(2), 228-233 (1996)
[2] Bai, Z.-Z.: On the convergence of the multisplitting methods for the linear complementarity problem. SIAM J. Matrix Anal. Appl. 21(1), 67-78 (1999)
[3] Bai, Z.-Z.: Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl. 17(6), 917-933 (2010)
[4] Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24(3), 603-626 (2003)
[5] Bai, Z.-Z., Pan, J.-Y.: Matrix Analysis and Computations. SIAM, Philadelphia (2021)
[6] Bai, Z.-Z., Parlett, B.N., Wang, Z.-Q.: On generalized successive overrelaxation methods for augmented linear systems. Numer. Math. 102(1), 1-38 (2005)
[7] Bai, Z.-Z., Yin, J.-F., Su, Y.-F.: A shift-splitting preconditioner for non-Hermitian positive definite matrices. J. Comput. Math. 24(4), 539-552 (2006)
[8] Cao, Y., Du, J., Niu, Q.: Shift-splitting preconditioners for saddle point problems. J. Comput. Appl. Math. 272, 239-250 (2014)
[9] Cao, Y., Yang, G.-C., Shen, Q.-Q.: Convergence analysis of projected SOR iteration method for a class of vertical linear complementarity problems. Comput. Appl. Math. 42(4), 191 (2023)
[10] Cottle, R.W., Dantzig, G.B.: A generalization of the linear complementarity problem. J. Comb. Theory A. 8(1), 79-90 (1970)
[11] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, San Diego (1992)
[12] Fujisawa, T., Kuh, E.S.: Piecewise-linear theory of nonlinear networks. SIAM J. Appl. Math. 22(2), 307-328 (1972)
[13] Fujisawa, T., Kuh, E.S.: A sparse matrix method for analysis of piecewise-linear resistive networks. IEEE Trans. Circ. Theory 19(6), 571-584 (1972)
[14] Gao, X.-B., Wang, J.: Analysis and application of a one-layer neural network for solving horizontal linear complementarity problems. Int. J. Comput. Intell. Syst. 7(4), 724-732 (2014)
[15] Gowda, M.S.: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8(1), 97-100 (1995)
[16] Huang, B.-H., Li, W.: A modified SOR-like method for absolute value equations associated with second order cones. J. Comput. Appl. Math. 400, 113745 (2022)
[17] Koulisianis, M.D., Papatheodorou, T.S.: Improving projected successive overrelaxation method for linear complementarity problems. Appl. Numer. Math. 45(1), 29-40 (2003)
[18] Mezzadri, F., Galligani, E.: An inexact Newton method for solving complementarity problems in hydrodynamic lubrication. Calcolo 55, 1 (2018)
[19] Mezzadri, F., Galligani, E.: Splitting methods for a class of horizontal linear complementarity problems. J. Optim. Theory Appl. 180, 500-517 (2019)
[20] Mezzadri, F., Galligani, E.: Modulus-based matrix splitting methods for horizontal linear complementarity problems. Numer. Algorithms 83(1), 201-219 (2020)
[21] Mezzadri, F., Galligani, E.: On the convergence of modulus-based matrix splitting methods for horizontal linear complementarity problems in hydrodynamic lubrication. Math. Comput. Simul. 176, 226-242 (2020)
[22] Mezzadri, F., Galligani, E.: A generalization of irreducibility and diagonal dominance with applications to horizontal and vertical linear complementarity problems. Linear Algebra Appl. 621, 214-234 (2021)
[23] Ralph, D.: A stable homotopy approach to horizontal linear complementarity problems. Control Cybern. 31(3), 575-600 (2002)
[24] Sznajder, R., Gowda, M.S.: Generalizations of P₀-properties; extended vertical and horizontal linear complementarity problems. Linear Algebra Appl. 223/224, 695-715 (1995)
[25] Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Opt. 4(1), 208-227 (1994)
[26] Zheng, H., Vong, S.: On the modulus-based successive overrelaxation iteration method for horizontal linear complementarity problems arising from hydrodynamic lubrication. Appl. Math. Comput. 402, 126165 (2021)

Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems

Convergence Analysis of the Projected SOR Iteration Method for Horizontal Linear Complementarity Problems

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Zhao-Zheng Liang, Jun-Lin Tian, Hong-Yi Wan. A Note on Chebyshev Accelerated PMHSS Iteration Method for Block Two-by-Two Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1242-1263.
[2]	Huaijun Yang. Unconditionally Superconvergence Error Analysis of an Energy-Stable and Linearized Galerkin Finite Element Method for Nonlinear Wave Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1264-1281.
[3]	Lu-Xin Wang, Qin-Qin Shen, Yang Cao. Modulus-Based Matrix Splitting Iteration Method for Horizontal Quasi-complementarity Problem[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1308-1332.
[4]	Xing Liu. An Accelerated Convergence Scheme for Solving Stochastic Fractional Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1444-1461.
[5]	Jing Chen, Qi Wang. Numerical Stability and Convergence for Delay Space-Fractional Fisher Equations with Mixed Boundary Conditions in Two Dimensions[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1462-1488.
[6]	Xuan Zhao, Zhongqin Xue. Efficient Variable Steps BDF2 Scheme for the Two-Dimensional Space Fractional Cahn-Hilliard Model[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1489-1515.
[7]	Long-Ze Tan, Ming-Yu Deng, Xue-Ping Guo. On Multi-step Greedy Kaczmarz Method for Solving Large Sparse Consistent Linear Systems[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1580-1597.
[8]	Yujian Cao, Jianguo Huang, Haoqin Wang. A Hybrid Iterative Method for Elliptic Variational Inequalities of the Second Kind[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 910-928.
[9]	Yun-Xia Tan, Zheng-Da Huang. On a Nonlinear Fast Deterministic Block Kaczmarz Method for Solving Nonlinear Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 954-969.
[10]	Gang Bao, Peijun Li, Xiaokai Yuan. Convergence of the PML Method for the Biharmonic Wave Scattering Problem in Periodic Structures[J]. Communications on Applied Mathematics and Computation, 2025, 7(3): 1122-1145.
[11]	Shipeng Mao, Jiaao Sun. Error Estimates of Finite Element Method for the Incompressible Ferrohydrodynamics Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 485-535.
[12]	Gui-Lin Yan, Yu-Jiang Wu, Bo Deng. Improvement of Convergence of One- and Two-Step MSM Iteration Methods for Nondifferentiable Nonlinear Complementarity Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 733-758.
[13]	Mengfei Wang, Yan Xu. Superconvergence of UWLDG Method for One-Dimensional Linear Sixth-Order Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 771-795.
[14]	Ren Liu, Lifei Wu. Numerical Approach for Solving Two-Dimensional Time-Fractional Fisher Equation via HABC-N Method[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 315-346.
[15]	Pavel Bakhvalov, Mikhail Surnachev. On the Order of Accuracy of Edge-Based Schemes: a Peterson-Type Counter-Example[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 372-391.