# Modified SOR-Like Method for Absolute Value Equations

Authors: Cui-Xia Li; Shi-Liang Wu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, based on the work of Ke and Ma, a modified SOR-like method is presented to solve the absolute value equations (AVE), which is gained by equivalently expressing the implicit fixed-point equation form of the AVE as a two-by-two block nonlinear equation. Under certain conditions, the convergence conditions for the modified SOR-like method are presented. The computational efficiency of the modified SOR-like method is better than that of the SOR-like method by some numerical experiments.


---

## Body

## 1. Introduction

Consider the absolute value equations (AVE)(1)Ax−x=b,where A∈ℝn×n and b∈ℝn and x denotes all the components of the vector x∈ℝn by absolute value. Replacing “x” in (1) by “Bx” with B∈ℝn×n naturally generates the general AVE [1, 2]. At present, the AVE gradually attracts considerable attention because some optimization problems such as linear programming, convex quadratic programming, and linear complementarity problem [3–7] can be formulated as the AVE (1).In recent years, to efficiently find the numerical solution of the AVE (1), a great deal of effort is developing iteration methods. For example, for solving the AVE (1), a generalized Newton method was presented in [8] and is simply described as follows:(2)xk+1=A−Dxkb,k=0,1,…,where Dxk=diagsignxk; Dx=diagsignx denotes a diagonal matrix corresponding to signx. There are other forms of the generalized Newton method; one can see [9–13] for more details. Clearly, at every iteration step of the generalized Newton method (2), the inverse of the matrix A−Dxk should be computed. Noting that the matrix A−Dxk is changed with the iteration index k, the calculations of the generalized Newton method may be very costly. To overcome this changed iteration matrix, the Picard iteration method in [14] is easily considered as follows:(3)xk+1=A−1xk+b,k=0,1,….Clearly, the Picard iteration method (3) is needed to compute the inverse of the matrix A. Similarly, by reformulating the AVE (1) as a nonlinear equation with two-by-two block form, combining with the classical SOR-like iteration method, an SOR-like iteration method in [15] was proposed to solve it and it is simply described as follows:(4)xk+1=1−ωxk+ωA−1yk+b,yk+1=1−ωyk+ωxk+1,ω>0.Some convergence conditions of the SOR-like iteration method were given when the involved parameter satisfied certain conditions. Further, from the aspect of the involved iteration matrix of the SOR-like iteration method, in [16], some new convergence conditions were presented.It is noted that if the matrixA in (3) or (4) is ill-conditioned, then at every iteration step of the Picard and SOR-like methods an ill-conditioned linear system needs to be solved. In this case, the cost of the calculation of the inverse of the matrix A may be high. To overcome the inverse of the matrix A, Li [17] extended the classical AOR iteration method for solving the AVE and discussed the convergence properties for the AOR method. By using the Gauss–Seidel splitting, the generalized Gauss–Seidel (GGS) iteration method was presented in [18] to solve the AVE (1).In this paper, we fasten on the SOR-like iteration method for solving the AVE (1). By expressing equivalently the implicit fixed-point equation of the AVE as a nonlinear equation with two-by-two block form, a modified SOR-like iteration method is presented by a concrete matrix splitting of the involved coefficient matrix. A considerable advantage of the modified SOR-like iteration method is that the inverse of the matrix A can be avoided. From this point of view, the computing efficiency of the modified SOR-like iteration method may be better than the SOR-like iteration method when both are used to solve the AVE (1).For our later analysis, here some terminologies are briefly explained. Letℝn be the finite dimensional Euclidean space, whose norm is denoted by ⋅. For x∈ℝn, signx denotes a vector with elements equal to 1,0,−1 depending on whether the value of the corresponding element of x is larger than zero, equal to zero, or less than zero.The rest of the layout of this paper is divided into three sections. In the second section, the modified SOR-like iteration method is designed and its convergence conditions are presented. In the third section, some numerical experiments are reported. In the fourth section, some concluding remarks are given to end this paper.


## 2. Modified SOR-Like Iteration Method

In this section, the modified SOR-like iteration method is presented. For this purpose, by usingy=x for the AVE (1), we have(5)Ax−y=b,−x+y=0,i.e.,(6)A¯z=A−I−D^Ixy=b0=b¯,where D^=Dx=diagsignx,x∈ℝn.Let(7)A=D−L−U,where D=diagA, and L and U are strictly lower and upper triangular matrices obtained from A, respectively. If we take (8)A¯=D¯−L¯−U¯,where (9)D¯=D00I,L¯=L0D^0,U¯=UI00,then we have (10)xy=Mωxy+ωD¯−ωL¯−1b0,where Mω=D¯−ωL¯−11−ωD¯+ωU¯ and ω>0. Based on equation (10), the modified SOR-like iteration method is naturally obtained and described below.The modified SOR-like iteration method: let the initial vectorsx0∈ℝn and y0∈ℝn be given and ω>0. For k=0,1,2,… until the iteration sequence xk,ykk=0+∞ is convergent, calculate(11)xk+1=D−ωL−11−ωD+ωUxk+ωyk+b,yk+1=1−ωyk+ωxk+1.Lemma1 is quoted for the latter use.Lemma 1.
(see [19]). Let λ be any root of x2−bx+d=0 with b,d∈ℝ. Then, λ<1 if and only if d<1 and b<1+d.Let the iteration errors be(12)ekx=x∗−xk,eky=y∗−yk,where x∗,y∗ is the solution pair of equation (6) and xk,yk is generated by the iteration method (11). Then, the following convergence conditions with respect to the modified SOR-like iteration method (11) can be given (see Theorem 1).Theorem 1.
LetA∈ℝn×n be nonsingular and b∈ℝn. Denote(13)s=D−ωL−11−ωD+ωU,ν=D−ωL−1,α=1−ω,β=ω2ν.
If(14)sα<1,β<1−α1−s,then (15)ek+1x,ek+1y<ekx,eky,k=0,1,…,where (16)ekx,eky=ekx2+eky2.Proof.
Let us subtract equation (11) from (17)x∗=D−ωL−11−ωD+ωUx∗+ωy∗+b,y∗=1−ωy∗+ωx∗,with x∗,y∗ being the solution pair of equation (6). Then (18)ek+1x=D−ωL−11−ωD+ωUekx+ωD−ωL−1eky,ek+1y=1−ωeky+ωx∗−xk+1.
From (18), we can get (19)ek+1x≤D−ωL−11−ωD+ωU⋅ekx+ωD−ωL−1⋅eky=sekx+ωνeky,ek+1y≤1−ωeky+ωx∗−xk+1≤1−ωeky+ωx∗−xk+1=1−ωeky+ωek+1x.
It holds that(20)−ω110ek+1xek+1y≤01−ωsωνekxeky.
By left-multiplying (20) by the nonnegative matrix (21)011ω>0,we have (22)ek+1xek+1y≤sωνωs1−ω+ω2νekxeky≤sωνωs1−ω+ω2ν2ek−1xek−1y…≤sωνωs1−ω+ω2νke0xe0y.
Let(23)T=sωνωs1−ω+ω2ν.
Clearly, ifρT<1, then limk⟶∞Tk=0. This implies (24)limk⟶∞ekx=0,limk⟶∞eky=0.
In this way, the iteration sequencexk,yk produced by the modified SOR-like method (11) can converge to the solution of equation (6).
Next, we just need to get sufficient conditions such thatρT<1. Assumed that λ denotes an eigenvalue of the matrix T. Then (25)λ−sλ−1−ω−ω2ν−ω2sν=0,which is equal to (26)λ2−1−ω+ω2ν+sλ+s1−ω=0.
Using Lemma1 for equation (26), λ<1 is equal to (27)s1−ω<1,1−ω+ω2ν+s<1+s1−ω.
Therefore, if condition (14) holds, then ρT<1.
If the idea of this proof for the modified SOR-like method (11) is extended to the SOR-like method (4), then the corresponding matrix T is as follows: (28)T=1−ωωνω1−ω1−ω+ω2ν,where ν=A−1 (see [15]). By simple computations, we can get that if (29)0<ω<2,α+ω2ν<1,then the SOR-like method (4) is convergent. Therefore, we obtain a new convergence condition for the SOR-like method (4) and see the following result.Theorem 2.
Let the conditions of Theorem1 be satisfied. Denote (30)ν=A−1,α=1−ω,β=ω2ν.
If(31)0<ω<2,α+β<1,then (32)ek+1x,ek+1y<ekx,eky,k=0,1,…,where (33)ekx,eky=ekx2+eky2.Comparing Theorem2 with Theorem 3.1 in [15], it is easy to see that the region of the parameter w in Theorem 2 is the same as that in Theorem 3.1 in [15]. Both demand 0<ω<2 in Theorem 2 and Theorem 3.1 in [15]. The difference between Theorem 2 and Theorem 3.1 in [15] is on α and β. The former is α+β<1 and the latter is (34)α4−3α2−2αβ−2β2+1>0.See Theorem 3.1 in [15]. In form, the latter is more complicated than the former.From Theorem1, Corollary 1 is obtained.Corollary 1.
Let the conditions of Theorem1 be satisfied. Denote(35)s=D−ωL−11−ωD+ωU,ν=D−ωL−1,α=1−ω,β=ω2ν.If(36)max0,s−1s<ω<1+ss,β<1−α1−s,then (37)ek+1x,ek+1y<ekx,eky,k=0,1,…,where(38)ekx,eky=ekx2+eky2.


## 3. Numerical Examples

In this section, two numerical examples are provided to show the effectiveness of the modified SOR-like method from two aspects: the iteration step (denoted by “IT”) and the computing time (denoted by “CPU”). We compared the modified SOR-like method with the SOR-like method [15]. Here, all initial vector for these two testing methods are set to be zero vector, and both are terminated if the relative residual error (RES) satisfies(39)RES≔Axk−xk−b2b2≤10−6,or if the iteration step is larger than 500. All the tests are performed in MATLAB 7.0.In the following tables, “MSOR” and “SOR” denote the modified SOR-like method and the SOR-like method [15], respectively. “−” denotes the iteration steps larger than 500 or the CPU times (second) larger than 500 seconds.To get fast convergence rate of the modified SOR-like method and the SOR-like method [15], the experimentally optimal parameter ωexp is adopted, which results in the smallest iteration step.Example 1.
(see [6, 7, 17]). Let the AVE in (1) be composed with(40)A=A^+4I∈ℝn×n,A^=tridiag−1.5I,S,−0.5I∈ℝn×n,with(41)S=tridiag−1.5,4,−0.5∈ℝn×n,b=Ax∗−x∗,where (42)x∗=−1,1,−1,1,…,−1,1T∈ℝn.
In Table1, we list some numerical results of the modified SOR-like method and the SOR-like method for Example 1. From Table 1, it is easy to see that both methods can quickly converge to the unique solution x∗ for different dimensions n when the experimentally optimal parameters ωexp are used. An interesting fact is that the experimentally optimal parameters ωexp of both methods are the same. Furthermore, the value of the experimentally optimal parameter is stable and unchanged as the different dimension increases. Further, we find that the iteration steps of both methods are also the same. Moreover, the iteration steps of both methods are also stable and unchanged as the different dimension increases. These numerical results show that both methods are suitable to solve the AVE (1).
It is noted that, from the view of the elapsed CPU time, the consumption of the CPU time of the modified SOR-like method is less than that of the SOR-like method. That is to say, the modified SOR-like method has better computational efficiency because it costs much cheaper than the SOR-like method.
In brief, the numerical results in Table1 show that under certain conditions, the computational efficiency of the modified SOR-like method overmatches the SOR-like method.Table 1
Numerical comparisons of MSOR and SOR for Example1.
n360049006400810010000MSORωexp1.011.011.011.011.01IT88888CPU0.0150.0160.0310.0310.032RES4.91e − 74.93e − 74.94e − 0074.95e − 74.96e − 7SORωexp1.011.011.011.011.01IT88888CPU0.110.1560.2350.2820.36RES9.05e − 79.09e − 79.12e − 79.15e − 0079.17e − 007Example 2.
For the AVE in (1), we chose a random A by the following structure:(43)A=100∗eyen−0.02∗2∗randn,n−1,and its all singular values exceed 1. The right-hand side b is set to be b=Ax∗−x∗, where(44)x∗=−1,1,−1,1,…,−1,1T∈ℝn.
For Example2, we also compare the modified SOR-like method with the SOR-like method in [15] and see Table 2 for the concrete numerical results. Table 2 shows that both methods quickly converge to the unique solution x∗ when the experimentally optimal parameters ωexp are applied. These numerical results further ensure the observations results of Table 1, i.e., the modified SOR-like method overmatches the SOR-like method in terms of the computational efficiency under certain conditions.Table 2
Numerical comparisons of MSOR and SOR for Example2.
n1000200030004000MSORωexp0.99111IT4444CPU0.2650.9062.1563.36RES2.35e − 71.52e − 84.94e − 0071.98e − 8SORωexp0.99111IT4343CPU0.865.14122.9235.094RES2.30e − 71.00e − 61.00e − 81.00e − 6


## 4. Conclusion

In this paper, by equivalently expressing the absolute value equations (AVE) as a nonlinear equation with two-by-two block form, we have presented a modified SOR-like method to solve the AVE and discussed its convergence properties under certain conditions. The computational efficiency of the modified SOR-like method overmatches the SOR-like method in [15] by some numerical experiments under certain conditions.In addition, it is worth thinking about that it is necessary to find the theoretical optimal parameterω to obtain the least iteration step of the modified SOR-like method in the future, although it is a very difficult task.



---

*Source: 9231639-2020-11-24.xml*