New modulus-based synchronous multisplitting methods based on block splitting for linear complementarity problems

ZHANG Litao , ZHANG Guohui, ZHAO Yinchao

(1. College of Science, Zhengzhou University of Aeronautics, Zhengzhou 450015, China; 2. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, Henan Province, China; 3. Henan Province Synergy Innovation Center of Aviation Economic Development, Zhengzhou 450015, China; 4. School of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China; 5. Public Art Teaching, Zhengzhon University of Aeronautics, Zhengzhou 450015, China)

Abstract： Based on the existing algorithms, we further study relaxed modulus-based synchronous block multisplitting multi-parameters methods for linear complementarity problem. Furthermore, we give the weaker convergence results of our new method in this paper when the system matrix is a block H+-matrix. Therefore, our results provide a guarantee for the optimal relaxation parameters.

Key Words： relaxed modulus-based method; linear complementarity problem; block splitting; block H+-matrix; synchronous multisplitting

0 Introduction

Consider the linear complementarity problem abbreviated as LCP(q,A), for finding a pair of real vectorsrandz∈Rnsuch that

r： =Az+q≥0,z≥0 andzT(Az+q)=0,

(1)

whereA=(aij)Rn×nis a given large, sparse and real matrix andq=(q1,q2,…,qn)T∈Rnis a given real vector. Here,zTand ≥ denote the transpose of the vectorzand the componentwise defined partial ordering between two vectors, respectively.

Many problems in scientific computing and engineering applications may lead to solutions of LCPs of the form (1). For example, the linear complementarity problem may arise from application problems such as the convex quadratic programming, the Nash equilibrium point of the bimatrix game, the free boundary problems of fiuid dynamics etc[1-2]. Some solvers for LCP(q,A) with a special matrixAwere proposed[3-12]. Recently, many researches have focused on the solver of LCP(q,A) with an algebra equation[8-22]. In particular, BAI et al[8-9]proposed a modulus-based matrix multisplitting iterative method for solving LCP(q,A) and presented convergence analysis for the proposed methods . ZHANG et al[13]extended the condition of a compatibleHsplitting to that of anH-splitting. LI[23]extended the modulus-based matrix splitting iteration method to more general cases. BAI[24]presented parallel matrix block multisplitting relaxation iterative methods, and established the convergence theory of these new methods in a thorough manner. LI et al[25]studied synchronous block multisplitting iterative methods. ZHANG et al[15]generalized the methods of BAI et al[26]and studied modulus-based synchronous multisplitting multi-parameters methods for linear complemen-tarity problem.

In this paper, we generalize the corresponding methods of BAI et al[26]and ZHANG et al[15]from point form to block form according to the modulus-based synchronous multisplitting iteration methods and consider relaxed modulus-based synchronous multisplitting multi-parameter method based on block splitting for solving LCP(q,A). Moreover, we give some theoretical analysis and improve some existing convergence results in [25-26].

The rest of this paper is organized as follows： In section 1, we give some notations and lemmas. In section 2, we propose relaxed modulus-based synchronous block multisplitting multi-parameters method for solving LCP(q,A). In section 3, we give the convergence analysis for the proposed method.

1 Notations and lemmas

In order to study mudulus-based synchronous block multisplitting iteration methods for solving LCP(q,A), let us introduce some definitions and lemmas.

Definition1[24]Define the set：

(1)Ln,I(n1,n2,…,np)={A=Aij∈Ln(n1,n2,…,np)|Aii∈L(Rni) is nonsingular (i=1,2,…,p)};

Definition2[27]LetA∈Ln,I(n1,n2,…,np), and (I)-type block comparison matrix 〈M〉=(〈M〉ij)∈L(Rn) and (II)-type block comparison matrix 〈〈M〉〉=(〈〈M〉〉ij)∈L(Rn) are defined as

respectively.

Moreover, based on block matrixA∈Ln,I(n1,n2,…,np), andL∈Ln,I(n1,n2,…,np), letD(L)=diag (L11,L22,…,Lpp),B(L)=D(L)-L,J(A)=D(A)-1B(A),μ1(A)=ρ(J〈A 〉),μ2(A)=ρ(I-〈〈A〉〉), using definition 2, we easily verify

〈I-J(A)〉=〈〈I-J(A)〉〉=〈〈A〉〉,
μ2(A)≤μ1(A).

Definition4[27]LetA∈Ln,I(n1,n2,…,np), then [A]=(‖Mij‖)∈L(Rn) is called block absolute value of block matrixA. Similarly, we may define block absolute value of block vectorx∈Vn(n1,n2,…,np) as [x]∈Rn.

Lemma1[24]LetA,B∈Ln,I(n1,n2,…,np),x,y∈Vn(n1,n2,…,np),γ∈R1, then

(1) |[A]-[B]|≤[A+B]≤[A]+[B](|[x]-[y]|)≤[x+y]≤[x]+[y];

(2) [AB]≤[A][B]([Ax]≤[A][x]);

(3) [γA]≤|γ|[A]([γx]≤|γ|[x]),q∈Rn;

(4)ρ(A)≤ρ(|A|)≤ρ([A]).

(1)Ais nonsingular;

(2) [(PAQ)-1]≤〈PAQ〉-1;

(3) μ1(PAQ)<1.

(1)Ais nonsingular;

(2) [(PAQ)-1]≤〈〈PAQ〉〉-1[D(PAQ)-1];

(3)μ2(PAQ)<1.

Definition5[24]Define the set：

Express the same mode set of (I)-type and (II)-type associated with the matrixM=(Mij)∈Ln,I(n1,n2,…,np), respectively.

Lemma4[28]LetAbe anH-matrix. ThenAis nonsingular, and |A-1|≤〈A〉-1.

Lemma5[29]LetA=(aij)∈Zn×nwhich has all positive diagonal entries.Ais anM-matrix if and only ifρ(B)<1, whereB=D-1C,D=diag(A),A=D-C.

Lemma6[5]LetA∈Rn×nbe anH+-matrix. Then LCP(q,A) has a unique solution for anyq∈Rn.

Lemma7[8]LetA=M-Nbe a splitting of the matrixA∈Rn×n,Ωbe a positive diagonal matrix, andγbe a positive constant. Then, for the LCP(q,A), the following statements hold true：

(Ω+M)x=Nx+(Ω-A)|x|-γq;

(2)

(ii) Ifxsatisfies the implicit fixed-point equation (2), then

z=γ-1(|x|+x) ,r=γ-1Ω(|x|-x)

(3)

is a solution of the LCP(q,A).

2 RMS-BMMTOR methods

Firstly, we introduce the concept of multisplitting method and the detailed process of parallel iterative method.

1)A=Mk-NK,det(Mk)≠0 is a splitting fork=1,2,…,l;

Given a positive diagonal matrixΩand a positive constantγ, form lemma 7, we know that ifxsatisfies either of the implicit fixed-point equations

(Ω+Mk)x=Nkx+ (Ω-A)|x-γq,

k= 1, 2,…,l,

(4)

then

z=γ-1(|x| +x),r= γ-1Ω(|x|-x)

(5)

is a solution of the LCP(q,A).

Based on block matrixA∈Rm×m, the corresponding block diagonal matrix isD= diag(A11,A22,…,App), andLk,Fkis block strictly triangular matrices,Uk=D-Lk-FkA, then (D-Lk-Fk,Uk,Ek) is a multisplitting of block matrixA∈Rm×m. With the equivalent reformulations (4), (5) and TOR method[16]of the LCP(q,A), we can establish the following relaxed modulus-based synchronous block multisplitting multi-parameters TOR method (RMSBMMTOR), which is similar to method 3.1 in [2] and method 3.1 in [15].

Method1(The RMS-BMMTOR method for LCP(q,A))

andx(m,k)∈Rnaccording to

wherex(m,k),k=1,2,…,lare obtained by solving the linear systems

(αkΩ+D-(βkLk+γkFk))x(m,k)=[(1-αk)D+

(αk-βk)Lk+(αk-γk)Fk+αkUk]x(m)+

αk[(Ω-A)|x(m)|-γq],k=1,2,…,l,

(6)

respectively.

Remark1In method 1, when the coefficient matrixAis point form andαk=α,βk=β,γk=γ,ω=1, the RMS-BMMTOR method reduces to the MSMTOR method; When the coefficient matrixAis point form andαk=α,βk=β=γk,ω= 1, the RMS-BMMTOR method reduces to the MSMAOR method[26]; When the coefficient matrixAis point form andω=1, the RMS-BMMTOR method reduces to the MSMMTOR method; When the coefficient matrixAis point form andγk=βk,ω=1, the RMS-BMMTOR method reduces to the MSMMAOR method[15]; Whenω= 1, the RMS-BMMTOR method reduces to the MSBMMTOR method; Whenγk=βk,ω=1, the RMS-BMMTOR method reduces to the MSBMMAOR method[25]; When the parameters (αk,βk,γk,ω) = (αk,αk,αk, 1), (1, 1, 1, 1) and (1, 0, 0, 1), the RMS-BMMTOR method reduces to the MSBMMSOR, MSBMGS and MSBMJ methods, respectively; When the parameters (αk,βk,ω) = (αk,αk,αk,ω), (1, 1, 1,ω) and (1, 0, 0,ω), the RMS-BMMTOR method reduces to the RMS-BMMSOR, RMSBMGS and RMSBMJ methods, respectively.

3 Convergence analysis

Based on the modulus-based synchronous multisplitting AOR method, BAI et al[26]obtained the following results in 2013 .

Based on the modulus-based synchronous block multisplitting AOR method, LI et al[25]analyzed the following results in 2013.

Based on the modulus-based synchronous multisplitting multi-parameters AOR method, ZHANG et al[15]gave the following results in 2014.

Based on the global relaxed non-stationary multisplitting multi-parameter TOR method (GRNMMTOR) for the large sparse linear systems, ZHANG et al[16]obtained the following convergence theorem in 2008.

Theorem4[16]LetA∈Rn×nbe anH-matrix, and fork=1,2,…,l,LkandFkbe strictly lower triangular matrices. Define the matrixUk,k=1,2,…,l, such thatA=D-Lk-Fk-Uk. Assume that we have 〈A〉=|D|-|Lk|-|Fk|-|Uk|=|D|-|B|. If

Based on relaxed modulus-based synchronous block multisplitting multi-parameters TOR method, we will present a convergence results of the multisplitting methods for the linear complementarity problem when the system matrix is a blockH+-matrix, which is as follows：

(7)

max{βk,γk}. Moreover,βk,γkshould be greater or less thanαkat once.

ProofFrom lemma 6 and (6), for the RMS-BMMTOR method, it holds that

αk[(Ω-H)|x*|-γq],k=1,2,…,l.

(8)

By subtracting (8) and (6), we have

(1-ω)(x(m)-x*).

(9)

By taking absolute values on both sides of the equality (9), estimating |[x(m)]-[x*]|≤[x(m)-x*] and amplifying, we may obtain

αk[Ω-H][x(m)-x*]+|1-ω|[x(m)-x*].

αk[Ω-H]][x(m)-x*]+(1-ω)[x(m)-x*]≤

αk〈Ω〉][x(m)-x*]+(1-ω)[x(m)-x*]=

(10)

where

HRMSBMMTOR=αk〈Ω〉+D〈H〉-(βk[Lk]+

γk[Fk]))-1[(|1-αk|-αk)D〈H〉+(|αk-βk|+

(11)

The error relationship (10) is the base for proving the convergence of RMS-BMMTOR method. By making use of lemmas 1 and 2, definingε(m)=x(m)-x*and arranging similar terms together, we can obtain

Mk=αk〈Ω〉+D〈H〉-(βk[Lk]+γk[Fk]),

Mk-2αkD〈H〉+2αkB〈H〉.

So, we have

Through further analysis, we have

(J〈H〉+εeeT)xε=ρεxε,

whereρε=ρ(J〈H〉+εeeT)=ρ(Jε). Moreover, ifε>0 is small enough, we haveρε<1 by continuity of the spectral radius. Because of 0<αk≤1, we also have 1-2αk+2αkρ<1, and 1-2αk+2αkρε<1. So

(1-2αk+2αkρ(Jε))xε.

|1-ω|xε≤ω(1-2αk+2αkρε)xε+

|1-ω|xε≤(ωρ′+|1-ω|)xε=θ1xε(ε→0+),

whereθ1=ωρ′+|1-ω|<1.

Subcase1αk≥βkandαk≥γk. Define

Mk-2D〈H〉+2αkB〈H〉.

So

2αkρ-1<1 and 2αkρε-1<1.

So

|1-ω|xε≤ω(2αkρε-1)xε+|1-ω|xε≤

(ωρ′+|1-ω|)xε=θ2xε(ε→0+),

where

θ2=ωρ′+|1-ω|<1.

Subcase2αk≤βkandαk≤γk. Define

Mk-2D〈H〉+2δkB〈H〉,

whereδk=max{βk,γk}. So

2δkρ-1<1 and 2δkρε-1<1.

So

[HRMS-BMMTOR]xε≤xε-2[1-δkρ(Jε)]xε=

(2δkρ(Jε)-1)xε.

|1-ω|xε≤ω(2δkρε-1)xε+|1-ω|xε≤

(ωρ′+|1-ω|)xε=θ3xε(ε→0+),

whereθ3=ωρ′+|1-ω|<1.

Remark2In the fact application, the parameters can be adjusted suitably so that the convergence property of method can be substantially improved. That is to say, we have more choices for the splittingA=B-Cwhich makes the multisplitting iteration methods converge.Therefore, our convergence theories extend the scope of multisplitting iterative methods in applications.

Through the similar proving process of theorem 4, we can obtain the following con-vergence results.

(7)

Remark3From table 1, we obviously see that the MSMMAOR method in [30] and the MSBMAOR method in [23] use the same parametersα,βin different processors, but the RMS-BMMTOR method in this paper uses different parametersαk,βk,γk(k=1,2,…,l)in different processors. Moreover, when computingx(m+1)in method 2, we utilize relaxation extrapolation technique and add a relaxation parameter. Therefore, we may choose proper relaxation parameters to increase convergence speed and reduce the computation time when doing numerical experiments. In RMS-BMMTOR method, we may choose properEkto balance the load of each processor and avoid synchronization.

4 Conclusions

The manuscript discusses relaxed modulus-based synchronous block multisplitting multi-parameters methods for linear complementarity problems. We have analyzed and got the new convergence theorem under certain conditions. However, table 1 shows some existing methods for linear complementarity problems are special cases of new methods with appropriate parameters. Moreover, new convergence theorems are more general and practical.

Table 1 The modulus-based synchronous (blokc) multisplitting multi-parameters method and the corresponding convergence results