×

Generalized AOR methods for linear complementarity problem. (English) Zbl 1121.65068

The authors propose a class of generalized accelerated overrelaxation (GAOR) methods for the linear complementarity problem, whose special case reduces to generalized successive overrelaxation (GSOR) methods. Some sufficient conditions for convergence of the GAOR and GSOR methods are presented when the system matrix \(M\) is an \(H\)-matrix, \(M\)-matrix and a strictly or irreducible diagonally dominant matrix. The monotone convergence of the new methods are discussed when \(M\) is an \(L\)-matrix. The numerical results show that the proposed methods are effective for large and sparse linear complementarity problems when \(M\) is an \(H\)-matrix with positive diagonals.

MSC:

65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berman, A.; Plemmons, R. J., Nonnegative Matrix in the Mathematical Sciences (1979), Academic Press: Academic Press New York · Zbl 0484.15016
[2] Bai, Z. Z., On the monotone convergence of matrix multisplitting relaxation methods for the linear complementarity problem, IMA J. Numer. Anal., 18, 509-518 (1998) · Zbl 0914.65072
[3] Bai, Z. Z., On the convergence of the multisplitting methods for the linear complementarity problem, SIAM J. Matrix Anal. Appl., 21, 67-78 (1999) · Zbl 0942.65059
[4] Bai, Z. Z.; Evans, D. J., Chaotic iterative methods for linear complementarity problems, J. Comput. Appl. Math., 96, 127-138 (1998) · Zbl 0927.65079
[5] Bai, Z. Z.; Evans, D. J., Matrix multisplitting relaxation methods for linear complementarity problems, Int. J. Comput. Math., 63, 309-326 (1997) · Zbl 0876.90086
[6] James, K. R., Convergence of matrix iterations subject to diagonal dominance, SIAM J. Numer. Anal., 12, 478-484 (1973) · Zbl 0255.65019
[7] Yuan, D.; Song, Y., Modified AOR methods for linear complementarity problem, Appl. Math. Comput., 140, 53-67 (2003) · Zbl 1030.65065
[8] Song, Y., On the convergence of the generalized AOR method, Linear Algebra Appl., 256, 199-218 (1997) · Zbl 0872.65028
[9] Song, Y., Konvergenzkriterien fur das verallgemeinerte AOR-Verfahren, Z. Angew. Math. Mech., 72, 445-447 (1992) · Zbl 0767.65023
[10] Mangasarian, O. L., Solution of symmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 22, 465-485 (1977) · Zbl 0341.65049
[11] Pang, J. S., Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem, J. Optim. Theory Appl., 42, 1-17 (1984) · Zbl 0506.90082
[12] Ahn, B. H., Solution of nonsymmetric linear complementarity problems by iterative methods, J. Optim. Theory Appl., 33, 185-197 (1981) · Zbl 0422.90079
[13] Rheinholdt, W. C.; Vandergraft, J. S., A simple approach to the Perron-Frobenius theory for positive operators on general partially-ordered finite-dimension linear spaces, Math. Comput., 27, 139-145 (1973) · Zbl 0255.15017
[14] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press San Diego · Zbl 0757.90078
[15] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102
[16] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602
[17] Elliott, C. M.; Ockenden, J. R., Weak Variational Methods for Moving Boundary Value Problems (1982), Pitmam: Pitmam London · Zbl 0476.35080
[18] Jiang, M. Q.; Dong, J. L., On convergence of two-stage splitting methods for linear complementarity problems, J. Comput. Appl. Math., 181, 58-69 (2005) · Zbl 1078.65052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.