Generalized Accelerated Overrelaxation Method For Solving Linear Complementarity Problems

Linear complementarity problems have been developed very quickly since they appeared in the 60s last century, especially the recent two decades. And they were widely used in engineering, economics and operations research. Roughly speaking, the study of the linear complementarity problems can be classified into two classes: theories and algorithms. The former is devoted to the existence, uniqueness, stability and sensitivity analysis of the solutions, while the latter is intended to solve the problems efficiently, together with the theoretical analysis of the algorithms. We will consider a class of method for solving the linear complementarity problem: generalized accelerated overrelaxation methods.In this paper, we will consider the generalized accelerated overrelaxation (GAOR ) methods for solving the linear complementarity problem LCP ( M,q), where M is an n×n nonsingular matrix, q∈Rn. In section one, a class of GAOR methods, in which one special case reduces to GSOR methods, for solving the linear complementarity problems are firstly proposed.In section two, we discuss the convergence of the GAOR and the GSOR methods, for the GAOR methods, we describe its convergence: when the system matrix M = ( mkj )∈R×is an H ?matrix with positive diagonal elements and let the splitting M = D+L+U satisfy M = D?L?U. If 0 <ωi <1 +ρ2(J), i = 1,2,n, andα∈R+,then for any initial guess z 0∈Rn, the iterative sequence { z p} generated by the GAOR methods converges to the unique solution z * of the LCP ( M,q) and As the special case, for the GSOR methods, we also have the convergence results. It is clearly that an M ?matrix is also an H ?matrix, hence, the statements are valid for the M ?matrix, since a strictly or irreducible diagonally dominant matrix with positive diagonal elements is also satisfying the condition of the theorem, then the results are also valid for these matrices.In section three, we consider the monotone convergence of the two methods, we get the result of the monotone convergence of the two methods: assume that M∈Rn×n is an L ?matrix. Also, assume that 0 <ωi≤1,i=1,2,n,0<α≤1. Then for any initial vector z 0∈? , the iterative sequence { z p },p=0,1,2,, generated by the GAOR methods or the GSOR methods has the following properties:(1) 0≤z p +1≤zp≤z0, p =0,1,2,;(2) lim zpz*p→∞= is the unique solution of the LCP ( M,q).In this section, we also discuss the influence of the parametersωi, i = 1,2,n andαupon the convergence rate of the GAOR and GSOR methods. We can get the result that the parameter collectionsω1 =ω2==ωn =α=1 can result in faster convergence rate of the GAOR and GSOR methods under the assumptions. This also implies that the optimum parameters, in general, should beα*ω1*,ω2*,ωn*∈[1 ,∞).Finally, a numerical example is used to validate the results proved in section three, that is, the larger the parameters are, the smaller the number of iterations are needed by the sequence to converge to the required accurate solution. In other words, the converg- ence rate is much quicker.