# Numerical Solution of the Absolute Value Equations Using Two Matrix Splitting Fixed Point Iteration Methods

Authors: Rashid Ali; Asad Ali; Mohammad Mahtab Alam; Abdullah Mohamed
Journal: Journal of Function Spaces
 (2022)

---

## Abstract

The absolute value equations (AVEs) are significantnonlinear and non-differentiable problems that arise in the optimization community. In this article, we provide two new iteration methods for determining AVEs. These two approaches are based on the fixed point principle and splitting of the coefficient matrix with three extra parameters. The convergence of these procedures is also presented using some theorems. The validity of our methodologies is demonstrated via numerical examples.


---

## Body

## 1. Introduction

In the last few decades, the AVE has been identified as a type of NP-hard and non-differentiable problem, which can be equivalent to numerous mathematical problems, such as bimatrix games, linear and quadratic programming, contact problems, network prices, and network equilibrium problems; see [1–6] for more details.We consider the AVE problem of finding anx∈Rn such that
(1)Ax−x=b.Hereb∈Rn, A∈Rn×n and x signifies the absolute values of the components of x∈Rn. Note that Eq. (1) is a special case of the following generalized AVE:
(2)Ax+Bx=b,where B∈Rn×n was familiarized by Rohn [1] and more studied in [7–11].Furthermore, AVEs are equivalently reformulated into linear complementarity problems (LCPs). These formulations are discussed in [12–14] and the references therein. Taking the well-known LCP as an example: Let us assume that the LCP f,M consists of determining y∈Rn such that
(3)y≥0,Γ=M¯y+f≥0,yTΓ=0,where f∈Rn and M¯∈Rn×n. The system (3) can be expressed as AVE
(4)Ax−Bx=f,with
(5)x=12By+f,where B=M¯−I and A=M¯+I. Meszzadri [15] established the equivalence among horizontal LCPs and AVEs. Furthermore, the unique solvability of system (1) and its relation to mixed-integer programming and LCP have been discussed by Prokopyev [16].Recently, the problem of determining the AVEs has enticed much consideration and has been studied in the literature. For instance, Ali et al. [17] introduced the generalized successive overrelaxation (GSOR) methods to determine AVE (1) and provided the necessary conditions for the convergence of the methods. Zhang and Wei [18] introduced a generalized Newton approach for obtaining (1) and designated the global and finite convergence with the condition that A+I,A−I is regular. Cruz et al. [19] established an inexact semi-smooth Newton approach for the AVE (1) and showed that the approach is globally convergent with the condition if A−1<1/3. Ke [20] presented the new iteration algorithm for determining (1) and proved the new convergence conditions under suitable assumptions. Moosaei et al. [21] presented two approaches for determining the NP-hard AVEs when the singular values of A exceed 1. Cacceta et al. [22] investigated the smoothing Newton method for obtaining (1) and discussed that this method is globally convergent with condition that A−1<1. Chen et al. [23] discussed the optimal parameter SOR-like iteration technique for Eq. (1). Wu as well as Li [24] used the shift splitting (SS) technique to develop an iterative shift splitting technique to find the AVE (1), and others; see [25–27] and the references therein.Recent studies have revealed that Li and Dai [28] as well as Najafi and Edalatpanah [29] provide methods for determining LCPs utilizing the fixed point principle. The objective of this study is to apply this approach to AVEs based on the fixed point principle, and to suggest efficient approaches for calculating AVE (1). We have made the following contributions in our study:
(i)
We divide theA matrix into various parts and then connect this splitting with the fixed point formula, which can accelerate the convergence of the proposed iterative procedures.(ii)
We consider the convergent conditions of newly designed approaches under various new situations.The analysis is structured as follows. The offered strategies for defining AVE (1) are examined in Section 2. In addition, the numerical tests are discussed in Section 3, while the conclusion is presented in Section 4.


## 2. Suggested Methods

In this part, we propose strategies to determine AVE (1). We begin by discussing some symbols and auxiliary outcomes.We illustrate the spectral radius, infinity norm, and tridiagonal matrix ofA, respectively, as ρA, A∞ and TdiagA.Lemma 1 (see [30]).
Supposeu,v be the two vectors ∈Rn. Then u−v≥u−v.
In order to propose and examine the new iteration methods, the matrixA is divided as follows:
(6)A=NA−MA,with
(7)NA=1ααDA−αUA+βUA⋆andMA=1ααLA+βUA⋆,where 0<α,β≤1. Furthermore, DA, UA, UA⋆ and LA, are the diagonal, the strictly upper, the transpose of strictly upper and the strictly lower triangular parts of A, respectively. The AVE (1) is equivalent to the fixed point problem of solving
(8)x=Hx,such that
(9)Hx=x−λEAx−x−b,where 0<λ≤1 and E∈Rn×n is a positive diagonal matrix (then by choice of E=DA−1, see [31, 32] for more details). By utilizing splitting (6), we offer the following two new schemes to obtain AVEs (see Appendix A):


### 2.1. Method I

(10)xm+1=xm−λE−MAxm+1+NAxm−xm+b.m=0,1,2,⋯,


### 2.2. Method II

(11)xm+1=xm+DA−1MAxm+1−λEAxm−xm−b−DA−1MAxm.m=0,1,2,⋯,Now, we study the convergence investigation of the presented iteration methods.Theorem 2.
Assume that the system (1) is solvable and A=NA−MA be a splitting of A, then
(12)xm+1−x⋆≤R−1Qxm−x⋆,where
(13)R=I−λEMAandQ=λE+I−λENA.
Moreover, ifρR−1Q<1, the sequence xm designed by method I will lead to the unique solution x⋆ of the system (1).Proof.
Supposex⋆ be a solution of system (1). Therefore,
(14)x⋆=x⋆−λE−MAx⋆+NAx⋆−x⋆+b.
After subtracting (14) from (10), we obtain
(15)xm+1−whitex⋆=xm−x⋆−λE−MAxm+1−x⋆+NAxm−x⋆−xm+x⋆,xm+1−x⋆=xm−x⋆+λEMAxm+1−x⋆−λENAxm−x⋆+λExm−x⋆,xm+1−x⋆=I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆.
Considering the absolute values on each side, we have(16)xm+1−x⋆=I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆,xm+1−x⋆≤I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆.
Using Lemma1, we get
(17)xm+1−x⋆≤I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆,xm+1−x⋆−λEMAxm+1−x⋆≤I−λENAxm−x⋆+λExm−x⋆,I−λEMAxm+1−x⋆≤λE+I−λENAxm−x⋆.
SinceI−λEMA is invertible. Therefore, I−λEMA−1 exists as well as non-negative, we have
(18)xm+1−x⋆≤R−1Qxm−x⋆,where
(19)R=I−λEMAandQ=λE+I−λENA.
Note that the matrixR−1Q is non-negative. Based on [31, 32], if ρR−1Q<1, then the sequence xm designed by Method I converges to the x⋆ solution of system (1).
Uniqueness: suppose thatx¯¯ represents another AVE solution. Based on the equations
(20)Ax⋆−x⋆=b,Ax¯¯−x¯¯=b,presented as
(21)x⋆=x⋆−λE−MAx⋆+NAx⋆−x⋆+b,x¯¯=x¯¯−λE−MAx¯¯+NAx¯¯−x¯¯+b,we obtain
(22)x⋆−x¯¯≤R−1Qx⋆−x¯¯.
And sinceρR−1Q<1, we get
(23)x⋆=x¯¯.
The proof has been completed.Theorem 3.
Letxm+1 and xm are the sequences generated by Method II, then
(24)xm+1−xm≤G−1Jxm−xm−1,where
(25)G=I−DA−1MAandJ=I+λE−λEA+DA−1MA.
Moreover, ifρG−1J<1, the sequence xm designed by method II will lead to the unique solution x⋆ of the system (1).Proof.
Supposex⋆ be a solution of system (1). Then
(26)x⋆=x⋆+DA−1MAx⋆−λEAx⋆−x⋆−b−DA−1MAx⋆.
After subtracting (26) from (11), we obtain
(27)xm+1−x⋆=xm−x⋆+DA−1MAxm+1−x⋆−λEAxm−x⋆+λExm−x⋆−DA−1MAxm−x⋆,
Taking absolute values on both sides and using Lemma1, we have
(28)xm+1−x⋆≤xm−x⋆+DA−1MAxm+1−x⋆−λEA+DA−1MAxm−x⋆+λExm−x⋆,≤xm−x⋆+DA−1MAxm+1−x⋆−λEA+DA−1MAxm−x⋆+λExm−x⋆,xm+1−x⋆≤I+λE−λEA+DA−1MAxm−x⋆+DA−1MAxm+1−x⋆,I−DA−1MAxm+1−x⋆≤I+λE−λEA+DA−1MAxm−x⋆.
So,(29)xm+1−x⋆≤G−1Jxm−x⋆.
Based on theorem 4.1 of [31] and theorem 3.1 of [28, 29], if ρG−1J<1, the iteration sequence xmm=0∞ created by Method II is convergent.
The proof of the uniqueness is similar as the proof in Theorem2 and is omitted here.


## 2.1. Method I

(10)xm+1=xm−λE−MAxm+1+NAxm−xm+b.m=0,1,2,⋯,


## 2.2. Method II

(11)xm+1=xm+DA−1MAxm+1−λEAxm−xm−b−DA−1MAxm.m=0,1,2,⋯,Now, we study the convergence investigation of the presented iteration methods.Theorem 2.
Assume that the system (1) is solvable and A=NA−MA be a splitting of A, then
(12)xm+1−x⋆≤R−1Qxm−x⋆,where
(13)R=I−λEMAandQ=λE+I−λENA.
Moreover, ifρR−1Q<1, the sequence xm designed by method I will lead to the unique solution x⋆ of the system (1).Proof.
Supposex⋆ be a solution of system (1). Therefore,
(14)x⋆=x⋆−λE−MAx⋆+NAx⋆−x⋆+b.
After subtracting (14) from (10), we obtain
(15)xm+1−whitex⋆=xm−x⋆−λE−MAxm+1−x⋆+NAxm−x⋆−xm+x⋆,xm+1−x⋆=xm−x⋆+λEMAxm+1−x⋆−λENAxm−x⋆+λExm−x⋆,xm+1−x⋆=I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆.
Considering the absolute values on each side, we have(16)xm+1−x⋆=I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆,xm+1−x⋆≤I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆.
Using Lemma1, we get
(17)xm+1−x⋆≤I−λENAxm−x⋆+λEMAxm+1−x⋆+λExm−x⋆,xm+1−x⋆−λEMAxm+1−x⋆≤I−λENAxm−x⋆+λExm−x⋆,I−λEMAxm+1−x⋆≤λE+I−λENAxm−x⋆.
SinceI−λEMA is invertible. Therefore, I−λEMA−1 exists as well as non-negative, we have
(18)xm+1−x⋆≤R−1Qxm−x⋆,where
(19)R=I−λEMAandQ=λE+I−λENA.
Note that the matrixR−1Q is non-negative. Based on [31, 32], if ρR−1Q<1, then the sequence xm designed by Method I converges to the x⋆ solution of system (1).
Uniqueness: suppose thatx¯¯ represents another AVE solution. Based on the equations
(20)Ax⋆−x⋆=b,Ax¯¯−x¯¯=b,presented as
(21)x⋆=x⋆−λE−MAx⋆+NAx⋆−x⋆+b,x¯¯=x¯¯−λE−MAx¯¯+NAx¯¯−x¯¯+b,we obtain
(22)x⋆−x¯¯≤R−1Qx⋆−x¯¯.
And sinceρR−1Q<1, we get
(23)x⋆=x¯¯.
The proof has been completed.Theorem 3.
Letxm+1 and xm are the sequences generated by Method II, then
(24)xm+1−xm≤G−1Jxm−xm−1,where
(25)G=I−DA−1MAandJ=I+λE−λEA+DA−1MA.
Moreover, ifρG−1J<1, the sequence xm designed by method II will lead to the unique solution x⋆ of the system (1).Proof.
Supposex⋆ be a solution of system (1). Then
(26)x⋆=x⋆+DA−1MAx⋆−λEAx⋆−x⋆−b−DA−1MAx⋆.
After subtracting (26) from (11), we obtain
(27)xm+1−x⋆=xm−x⋆+DA−1MAxm+1−x⋆−λEAxm−x⋆+λExm−x⋆−DA−1MAxm−x⋆,
Taking absolute values on both sides and using Lemma1, we have
(28)xm+1−x⋆≤xm−x⋆+DA−1MAxm+1−x⋆−λEA+DA−1MAxm−x⋆+λExm−x⋆,≤xm−x⋆+DA−1MAxm+1−x⋆−λEA+DA−1MAxm−x⋆+λExm−x⋆,xm+1−x⋆≤I+λE−λEA+DA−1MAxm−x⋆+DA−1MAxm+1−x⋆,I−DA−1MAxm+1−x⋆≤I+λE−λEA+DA−1MAxm−x⋆.
So,(29)xm+1−x⋆≤G−1Jxm−x⋆.
Based on theorem 4.1 of [31] and theorem 3.1 of [28, 29], if ρG−1J<1, the iteration sequence xmm=0∞ created by Method II is convergent.
The proof of the uniqueness is similar as the proof in Theorem2 and is omitted here.


## 3. Numerical Examples

In this unit, five examples are provided to analyze the performance of the proposed methods from three stances:(i)
‘Iter’ indicates the iteration steps.(ii)
‘Time’ implies the CPU time (s).(iii)
‘RES’ signifies the 2-norm of residual vectors.Here, ‘RES’ is determined by(30)RES≔b+xm−Axm2≤10−6.All calculations were done on a computer with an Intel(R) Core(TM) i5-3337U CPU@ 1.80 GHz processor and Memory 4GB using MATLAB R2016a. In Examples 4 and 5, the starting guess is supposed to be x0=0,0,0,⋯,0T∈Rn.First, we use numerical experiments to satisfy the convergence conditionsρR−1Q<1 and ρG−1J<1. Table 1 delivers the outcomes.Table 1
Convergence conditions of Theorem2 and Theorem 3.
ExamplesnMethod IMethod IIρR−1QρG−1J3.11000.82500.89294000.82500.89393.21000.81670.84424000.81670.84483.310000.50240.507630000.50740.51243.42560.40270.403840960.40330.35383.510000.31270.317330000.31520.3195In Table1, we performed the convergence conditions of both theorems using numerical experiments. Obviously, these two methods meet these conditions. To examine the implementation of our novel methods, we consider the following tests.Example 4.
Assume thatA=M+φI∈Rn×n and b=Ax⋆−x⋆∈Rn, such that.
(31)M=Tdiag−I,S,−I∈Rn×n,andx⋆=1,2,1,2,⋯,T∈Rn.
Here,S=Tdiag−1,4,−1∈RΔ×Δ, I∈RΔ×Δ and n=Δ2. The outcomes are shown in Table 2, and the graphs are displayed in Figures 1 and 2, respectively.Table 2
The outcomes of Example4 with α=0.5,β=0.9 and φ=4.
nλ0.20.40.60.81100Method IIter10247292416Time0.5770.3920.3380.3230.315RES9.861e–079.234e–079.166e–075.999e–077.548e–07Method IIIter214102654735Time0.9060.5170.42470.3980.354RES9.264e–079.927e–079.523e–077.276e–079.448e–07400Method IIter10548302415Time2.9291.6771.1531.0500.851RES9.617e–079.974e–076.6810e–075.568e–079.702e–07Method IIIter230111715138Time13.1156.4264.2913.1532.476RES9.700e–078.567e–077.950e–077.096e–079.720e–07Figure 1
Graphs showing the convergence rates of the suggested approaches for various values ofλ.
(a)
Method I forn=100(b)
Method II forn=100Figure 2
Graphs showing the convergence rates of the suggested approaches for various values ofλ.
(a)
Method I forn=400(b)
Method II forn=400In Table2, the given methods calculate the AVE solution for different α,β and λ values. We notice that if we increase λ, the convergence of the given strategies becomes quicker. The curves in Figures 1 and 2 display the effectiveness of the given procedures. Graphically sketch demonstrates that the convergence of the presented approaches is faster when the value of λ is bigger.Example 5.
Assume thatA=M+φI∈Rn×n and b=Ax⋆−x⋆∈Rn, such that
(32)M=Tdiag−1.5I,S,−0.5I∈Rn×n∈Rn×n,x⋆=−1l,l=1,2,⋯,nT∈Rn,where S=Tdiag−1.5,8,−0.5∈RΔ×Δ, I∈RΔ×Δ as well as n=Δ2. The outcomes are presented in Table 3, and the graphical representations are shown in Figures 3 and 4, respectively.Table 3
The outcomes for Example5 using α=0.5,β=0.9 and φ=4.
nλ0.20.40.60.81100Method IIter9040231410Time0.6450.3700.34280.3350.330RES9.921e–079.6888e–079.284e–079.691e–071.650e–07Method IIIter11754332216Time0.7170.4470.3910.3640.351RES9.392e–079.318e–078.321e–079.038e–074.232e–07400Method IIter9442241510Time2.4551.41931.01880.8540.747RES8.401e–077.318e–077.691e–074.637e–074.201e–07Method IIIter12458352417Time6.7853.3032.2401.6971.334RES9.592e–077.878e–079.050e–076.450e–075.055e–07Figure 3
Graphs showing the convergence rates of the suggested approaches for various values ofλ.
(a)
Method I forn=100(b)
Method II forn=100Figure 4
Graphs showing the convergence rates of the suggested approaches for various values ofλ.
(a)
Method I forn=400(b)
Method II forn=400In Table3, we presented the convergence behavior of the given methods using the values of α,β and λ. Obviously, if the value of λ is larger, the convergence of the given approaches grows faster. The graphical representation is illustrated in Figures 3 and 4. These curves explain the efficiency of the suggested approaches at various λ values.Example 6.
Assume that(33)A=4,forj=i−1,forj=i+1,i=1,2,⋯,n−1,j=i−1,i=2,⋯,n,0,otherwise.and b=Ax⋆−x⋆∈Rn, such that x⋆=−1w,w=1,2,⋯,nT∈Rn. This example uses the same stopping criteria and starting guess as shown in [24]. Moreover, we compare the new techniques with the procedure described in [20] (symbolized by AM) as well as the shift splitting iteration method reported in [24] (represented by SS). These outcomes are presented in Table 4.Table 4
The outcomes for Example6 using α=β=1 and λ=0.97.
Techniquesn1000200030004000AMIter19191919Time3.159014.207936.573974.4664RES7.880e-077.884e-077.896e-077.896e-07SSIter14141414Time2.75019.513119.293533.4672RES8.913e-078.924e-078.928e-078.930e-07Method IIter11111111Time1.7395.572813.384625.4884RES9.531e-079.537e-079.539e-079.540e-07Method IIIter12121212Time2.10027.499116.894431.8679RES3.688e-073.667e-073.661e-073.657e-07The results of Table4 show that all methods are capable of determining the problem efficiently and precisely. Our techniques are more valuable than existing strategies, such as the AM and SS methods, in terms of iterations (Iter) and solving time (Time).Example 7.
Consider(34)A=I⊗T+χ⊗I∈RΘ×Θ.
Here,I∈RΘ×Θ is a unit matrix, and ⊗ indicates the Kronecker product. In addition, T and χ∈Rn×n, as shown below.
(35)T=Tdiag2+ϕ8,8,2−ϕ8,χ=Tdiag1+ϕ4,4,1−ϕ4,ϕ=1/n;Θ=n2.
Here,b=Ax⋆−x⋆∈RΘ, where x⋆=onesΘ,1∈RΘ. In Examples 7 and 8, using the same starting guess as well as the stopping criterion as given in [23]. Moreover, we compare the recommended techniques with the process shown in [23] (exposed by SRM) and the iteration scheme introduced in [17] (represented by GSOR). These data are explained in Table 5.Table 5
The results for Example7 using α=β=1 and λ=0.97.
MethodsV256129624014096SRMIter17181818Time0.36074.583422.8075117.7810RES6.804e–093.735e–095.072e–096.619e–09GSORIter14151515Time0.474416.724288.963658.7786RES3.269e–091.805e–092.712e–093.808e–09Method IIter11111212Time0.34234.686924.6612125.0572RES3.548e–097.540e–091.070e–091.383e–09Method IIIter11111212Time0.530711.043611.931757.3148RES4.297e–099.345e–091.357e–091.760e–09All techniques in Table5 consider the solution x⋆ for various numbers of V. Based on the data in Table 5, we can identify that our recommended procedures provide better results than both SRM and GSOR procedures.Example 8.
We consider the AVE (1) with
(36)A=Tdiag−1,8,−1∈Rn×n,x⋆=−1l,l=1,2,⋯,nT∈Rn,and b=Ax⋆−x⋆. The data are reported in Table 6.Table 6
The outcomes for Example8 using α=β=1 and λ=0.97.
Methodsn1000200030004000SRMIter20202020Time2.861912.819537.290575.2874RES4.125e-095.834e-097.146e-098.252e-09GSORIter17171818Time2.68417.574611.311617.7786RES6.846e–099.711e–092.808e–093.244e–09Method IIter13131313Time1.55013.17907.950912.6772RES5.343e–097.518e–099.191e–091.652e–09Method IIIter13131313Time2.47685.303811.720316.3148RES5.766e–098.047e–099.812e–091.760e–09Based on Table6, we perceive that all procedures can determine the problem efficiently and precisely. We can clearly distinguish that our techniques are more beneficial than existing processes, such as SRM and GSOR, with respect to the iteration steps (Iter) and the solving time (Time).


## 4. Conclusion

We have introduced two novel iterative techniques for obtaining the AVE (1) and demonstrated that the offered approaches converge to the system (1) under proper selections of the involved parameters. The effectiveness of the recommended methods has also been evaluated numerically. The numerical outcomes indicate that the suggested strategies are effective for large and sparse AVEs. For future research, the theoretical comparison and analysis of these iteration methods are of great interest.



---

*Source: 7934796-2022-05-26.xml*