# The Solution of Absolute Value Equations Using Two New Generalized Gauss-Seidel Iteration Methods

Authors: Rashid Ali
Journal: Computational and Mathematical Methods
 (2022)

---

## Abstract

In this paper, we provide two new generalized Gauss-Seidel (NGGS) iteration methods for solving absolute value equationsAx−∣x∣=b, where A∈Rn×n, b∈Rn, and x∈Rn are unknown solution vectors. Also, convergence results are established under mild assumptions. Eventually, numerical results prove the credibility of our approaches.


---

## Body

## 1. Introduction

Consider the absolute value equation (AVE):(1)Ax−∣x∣=b,where A∈Rn×n, ∣x∣=∣x1∣,∣x2∣,⋯,∣xn∣T, and b∈Rn. A more general structure of the AVE is
(2)Ax+B∣x∣=b,where B∈Rn×n, B≠0. When B=−I, where I denotes the identity matrix, then Eq. (2) reduces to the special form (1). The AVEs are significant nondifferentiable and nonlinear problems that appear in optimization, e.g., linear programming, journal bearings, convex quadratic programming, linear complementarity problems (LCPs), and network prices [1–13].The numerical techniques for AVEs have received a lot of attention in recent years, and several approaches have been suggested, such as Li [14] proposed the preconditioned AOR iterative technique to determine AVE (1) and established the novel convergence results of the suggested scheme. To solve the AVE (1), Ke and Ma [15] introduced an SOR-like approach. Chen et al. [16] studied the concept of [15] extensively and presented an optimal parameter SOR-like approach. Huang and Hu [17] reformulated the AVE system as a standard LCP without any premise and showed some convexity and existence outcomes for determining AVE (1). Fakharzadeh and Shams [18] recommended the mixed-type splitting (MTS) iterative scheme for determining AVE (1) and established the novel convergence properties. Zhang et al. [19] developed a novel algorithm that transformed the AVE problem into an optimization problem associated with convexity. Caccetta et al. [20] examined a smoothing Newton technique for determining (1) and showed that the technique is globally convergent when ∥A−1∥<1. Saheya et al. [11] investigated smoothing type techniques for determining (1) and showed that their techniques have global and local quadratic convergence. Gu et al. [21] proposed the nonlinear CSCS-like approach as well as the Picard-CSCS approach in order to determine (1), which concerns the Toeplitz matrix. Wu and Li [22] developed a special shift splitting technique to determine AVE (1) and demonstrated the novel convergence outcomes for the approach. Edalatpour et al. [23] established the generalized Gauss-Seidel (GGS) techniques for determining (1) and analyzed its convergence properties and others; see [24–35] and the references therein.This article describes two new iterative approaches to determine AVEs. The main contributions we made to the article are as follows:(i)
We extend the GGS technique [23] to the general case. To achieve this goal, we impose two additional parameters (λ and Ω) that can accelerate the convergence procedure.(ii)
A variety of novel conditions are used to investigate the convergence properties of the newly developed methods.The remainder of this paper is organized in the following manner. In Section2, we present some notations and a lemma that will be used throughout the remainder of this study. In Section 3, we propose the NGGS procedures and discuss their convergence. We demonstrate the efficiency of these algorithms in Section 4 by providing numerical examples. In the last section, we make concluding remarks.


## 2. Preliminaries

Here we briefly examine some of the notations and concepts used in this article.LetA=aij∈Rn×n, we indicate the norm and absolute value as A∞ and ∣A∣=∣aij∣, respectively. The matrix A∈Rn×n is called an Z-matrix if aij≤0 for i≠j and an M-matrix if it is a nonsingular Z-matrix and with A−1≥0.Lemma 1. [36].
Supposex and ∈Rn, then x−z∞≥x−z∞.


## 3. NGGS Iteration Methods

Here, we examine the suggested methods (NGGS method I and NGGS method II) for determining AVE (1).


### 3.1. NGGS Method I for AVE

Recalling that the AVE (1) has the following form,Ax−∣x∣=b.Multiplyingλ, then we get
(3)λAx−λ∣x∣=λb.Let(4)A=DA−LA−UA=Ω+DA−LA−Ω+UA,where DA=diagA,LA, and UA are strictly lower and upper triangular parts of A, respectively. Furthermore, Ω=ΨI, where 0≤Ψ≤1 and I denote the identity matrix. Using (3) and (4), the NGGS Method I is suggested as
(5)Ω+DA−λLAx−λx=1−λΩ+DA+λΩ+UAx+λb.Using the iterative scheme, so (5) can be written as
(6)Ω+DA−λLAxi+1−λxi+1=1−λΩ+DA+λΩ+UAxi+λb,wherei=0,1,2,⋯, and 0<λ≤1 (see Appendix). Note that if λ=1 and Ω=0, then Eq. (6) reduces to the GGS method [23].The next step in the analysis is to verify the convergence of NGGS method I by using the following theorem.Theorem 2.
Suppose that AVE (1) is solvable, let the diagonal values of A>1 and DA−LA−I matrix be the strictly row wise diagonally dominant. If
(7)∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞<1−λ∥Ω+DA−λLA−1∥∞,then the sequence xi of the NGGS method I converges to the unique solution x⋆ of AVE (1).Proof.
We will prove first∥Ω+DA−λLA−1∥∞<1. Clearly, if we put LA=0, then ∥Ω+DA−λLA−1∥∞=∥Ω+DA−1∥∞<1. If we assume that LA≠0, we get
0≤∣λLA∣t<Ω+DA−It,if we take
∣λLA∣t<Ω+DA−It.
Taking both side byΩ+DA−1, we get
Ω+DA−1∣λLA∣t<Ω+DA−1Ω+DA−It,
∣λΩ+DA−1LA∣t<I−Ω+DA−1t,
∣λΩ+DA−1LA∣t<t−Ω+DA−1t,
Ω+DA−1t<t−∣λΩ+DA−1LA∣t,(8)Ω+DA−1t<1−∣Q∣t,where Q=λΩ+DA−1LA and t=1,1,⋯,1T. Also, we have
0≤I−Q−1=I+Q+Q2+Q3+⋯+Qn−1,(9)≤I+∣Q∣+Q2+Q3+⋯+Qn−1=I−∣Q∣−1.
Thus, from (8) and (9), we get
Ω+DA−λLA−1t=I−Q−1Ω+DA−1t≤I−Q−1Ω+DA−1t,
<I−∣Q∣−1I−∣Q∣t=t.
So, we obtain
∥Ω+DA−λLA−1∥∞<1.
Uniqueness: Letx⋆ and z⋆ be two different solutions of the AVE (1). Using (5), we get
(10)x⋆=λΩ+DA−λLA−1∣x⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAx⋆+λb,(11)z⋆=λΩ+DA−λLA−1∣z⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAz⋆+λb.
From (10) and (11), we get
x⋆−z⋆=λΩ+DA−λLA−1∣x⋆∣−∣z⋆∣+DA−λLA−11−λΩ+DA+λΩ+UAx⋆−z⋆.
Based on Lemma1 and Eq. (7), the above equation can be expressed as follows:
∥x⋆−z⋆∥∞≤λ∥Ω+DA−λLA−1∥∞∥∣x⋆∣−∣z⋆∣∥∞+∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞∥x⋆−z⋆∥∞,
<λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞+1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
∥x⋆−z⋆∥∞−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞<1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞<1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
∥x⋆−z⋆∥∞<∥x⋆−z⋆∥∞,which is a contradiction. Thus, x⋆=z⋆.Convergence: We will considerx⋆ as the unique solution to AVE (1). Consequently, from (10) andxi+1=λΩ+DA−λLA−1∣xi+1∣+Ω+D−λLA−11−λΩ+DA+λΩ+UAxi+λb, we deducexi+1−x⋆=λΩ+DA−λLA−1∣xi+1∣−∣x⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAxi−xå.By taking infinity norm and Lemma1, we have∥xi+1−x⋆∥∞−λ∥Ω+DA−λLA−1∥∞∥xi+1−x⋆∥∞≤∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞∥xi−x⋆∥∞,and since ∥Ω+DA−λLA−1∥∞<1, it follows that∥xi+1−x⋆∥∞≤∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞/1−λ∥Ω+DA−λLA−1∥∞∥xi−x⋆∥∞.According to the inequality above, the presented approach converges to the solution when condition (7) is met.


### 3.2. NGGS Method II for AVE

In this section, we describe the NGGS method II. Based on (3) and (4), we can express the suggested method for determining AVE (1) as follows (see Appendix):Ω+DA−λLAxi+1−λ∣xi+1∣=1−λΩ+DA+λΩ+UAxi+1+λb,i=0,1,2,⋯.In the following, we will examine the convergence results for NGGS method II.Theorem 3.
Suppose that AVE (1) is solvable, let the diagonal values of A>1 and DA−LA−I be row diagonally dominant, and then the sequence of the NGGS method II converges to the unique solution x⋆ of AVE (1).Proof.
The uniqueness can be inferred directly from Theorem2. For convergence, considerxi+1−x⋆=λΩ+DA−λLA−1xi+1+Ω+DA−λLA−11−λΩ+DA+λΩ+UAxi+1+λb−λΩ+DA−λLA−1x⋆+Ω+DA−λLA−11−λΩ+DA+λΩ+UAx⋆+λb,Ω+DA−λLAxi+1−x⋆=λ∣xi+1∣−∣x⋆∣+1−λΩ+DA+λΩ+UAxi+1−x⋆,λDA−LA−UAxi+1−λxi+1=λDA−LA−UAx⋆−λx⋆,(12)DA−LA−UAxi+1−∣xi+1∣=DA−LA−UAx⋆−∣x⋆∣.From (4) and (12), we haveAxi+1−∣xi+1∣=Ax⋆−∣x⋆∣Axi+1−∣xi+1∣=b.Therefore,xi+1 solves the system of AVE (1).


## 3.1. NGGS Method I for AVE

Recalling that the AVE (1) has the following form,Ax−∣x∣=b.Multiplyingλ, then we get
(3)λAx−λ∣x∣=λb.Let(4)A=DA−LA−UA=Ω+DA−LA−Ω+UA,where DA=diagA,LA, and UA are strictly lower and upper triangular parts of A, respectively. Furthermore, Ω=ΨI, where 0≤Ψ≤1 and I denote the identity matrix. Using (3) and (4), the NGGS Method I is suggested as
(5)Ω+DA−λLAx−λx=1−λΩ+DA+λΩ+UAx+λb.Using the iterative scheme, so (5) can be written as
(6)Ω+DA−λLAxi+1−λxi+1=1−λΩ+DA+λΩ+UAxi+λb,wherei=0,1,2,⋯, and 0<λ≤1 (see Appendix). Note that if λ=1 and Ω=0, then Eq. (6) reduces to the GGS method [23].The next step in the analysis is to verify the convergence of NGGS method I by using the following theorem.Theorem 2.
Suppose that AVE (1) is solvable, let the diagonal values of A>1 and DA−LA−I matrix be the strictly row wise diagonally dominant. If
(7)∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞<1−λ∥Ω+DA−λLA−1∥∞,then the sequence xi of the NGGS method I converges to the unique solution x⋆ of AVE (1).Proof.
We will prove first∥Ω+DA−λLA−1∥∞<1. Clearly, if we put LA=0, then ∥Ω+DA−λLA−1∥∞=∥Ω+DA−1∥∞<1. If we assume that LA≠0, we get
0≤∣λLA∣t<Ω+DA−It,if we take
∣λLA∣t<Ω+DA−It.
Taking both side byΩ+DA−1, we get
Ω+DA−1∣λLA∣t<Ω+DA−1Ω+DA−It,
∣λΩ+DA−1LA∣t<I−Ω+DA−1t,
∣λΩ+DA−1LA∣t<t−Ω+DA−1t,
Ω+DA−1t<t−∣λΩ+DA−1LA∣t,(8)Ω+DA−1t<1−∣Q∣t,where Q=λΩ+DA−1LA and t=1,1,⋯,1T. Also, we have
0≤I−Q−1=I+Q+Q2+Q3+⋯+Qn−1,(9)≤I+∣Q∣+Q2+Q3+⋯+Qn−1=I−∣Q∣−1.
Thus, from (8) and (9), we get
Ω+DA−λLA−1t=I−Q−1Ω+DA−1t≤I−Q−1Ω+DA−1t,
<I−∣Q∣−1I−∣Q∣t=t.
So, we obtain
∥Ω+DA−λLA−1∥∞<1.
Uniqueness: Letx⋆ and z⋆ be two different solutions of the AVE (1). Using (5), we get
(10)x⋆=λΩ+DA−λLA−1∣x⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAx⋆+λb,(11)z⋆=λΩ+DA−λLA−1∣z⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAz⋆+λb.
From (10) and (11), we get
x⋆−z⋆=λΩ+DA−λLA−1∣x⋆∣−∣z⋆∣+DA−λLA−11−λΩ+DA+λΩ+UAx⋆−z⋆.
Based on Lemma1 and Eq. (7), the above equation can be expressed as follows:
∥x⋆−z⋆∥∞≤λ∥Ω+DA−λLA−1∥∞∥∣x⋆∣−∣z⋆∣∥∞+∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞∥x⋆−z⋆∥∞,
<λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞+1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
∥x⋆−z⋆∥∞−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞<1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞<1−λ∥Ω+DA−λLA−1∥∞∥x⋆−z⋆∥∞,
∥x⋆−z⋆∥∞<∥x⋆−z⋆∥∞,which is a contradiction. Thus, x⋆=z⋆.Convergence: We will considerx⋆ as the unique solution to AVE (1). Consequently, from (10) andxi+1=λΩ+DA−λLA−1∣xi+1∣+Ω+D−λLA−11−λΩ+DA+λΩ+UAxi+λb, we deducexi+1−x⋆=λΩ+DA−λLA−1∣xi+1∣−∣x⋆∣+Ω+DA−λLA−11−λΩ+DA+λΩ+UAxi−xå.By taking infinity norm and Lemma1, we have∥xi+1−x⋆∥∞−λ∥Ω+DA−λLA−1∥∞∥xi+1−x⋆∥∞≤∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞∥xi−x⋆∥∞,and since ∥Ω+DA−λLA−1∥∞<1, it follows that∥xi+1−x⋆∥∞≤∥Ω+DA−λLA−11−λΩ+DA+λΩ+UA∥∞/1−λ∥Ω+DA−λLA−1∥∞∥xi−x⋆∥∞.According to the inequality above, the presented approach converges to the solution when condition (7) is met.


## 3.2. NGGS Method II for AVE

In this section, we describe the NGGS method II. Based on (3) and (4), we can express the suggested method for determining AVE (1) as follows (see Appendix):Ω+DA−λLAxi+1−λ∣xi+1∣=1−λΩ+DA+λΩ+UAxi+1+λb,i=0,1,2,⋯.In the following, we will examine the convergence results for NGGS method II.Theorem 3.
Suppose that AVE (1) is solvable, let the diagonal values of A>1 and DA−LA−I be row diagonally dominant, and then the sequence of the NGGS method II converges to the unique solution x⋆ of AVE (1).Proof.
The uniqueness can be inferred directly from Theorem2. For convergence, considerxi+1−x⋆=λΩ+DA−λLA−1xi+1+Ω+DA−λLA−11−λΩ+DA+λΩ+UAxi+1+λb−λΩ+DA−λLA−1x⋆+Ω+DA−λLA−11−λΩ+DA+λΩ+UAx⋆+λb,Ω+DA−λLAxi+1−x⋆=λ∣xi+1∣−∣x⋆∣+1−λΩ+DA+λΩ+UAxi+1−x⋆,λDA−LA−UAxi+1−λxi+1=λDA−LA−UAx⋆−λx⋆,(12)DA−LA−UAxi+1−∣xi+1∣=DA−LA−UAx⋆−∣x⋆∣.From (4) and (12), we haveAxi+1−∣xi+1∣=Ax⋆−∣x⋆∣Axi+1−∣xi+1∣=b.Therefore,xi+1 solves the system of AVE (1).


## 4. Numerical Tests

Here, four examples are provided to illustrate the performance of the novel approaches from three different perspectives:(i)
The number of iterations (indicated by “Itr”)(ii)
The computational time (s) (exposed by “Time”)(iii)
The residual error (represented by “RSV”)Here, “RSV” is defined byRSV≔∥Axi−∣xi∣−b∥2/∥b∥2≤10−6.All numerical tests were conducted on a personal computer with 1.80 GHz CPU (Intel(R) Core (TM) i5-3337U) and 4 GB of memory using MATLAB (2016a). In addition, the zero vector is the initial vector for Example4Example 4.
LetA=tridiag−1,4,−1∈Rn×n.Calculateb=Ax⋆−∣x⋆∣∈Rn with x⋆=x1,x2,x3,⋯,xnT∈Rn such that xi=−1i. Here, the proposed methods are compared to two existing methods: the SOR-like optimal parameters technique shown in [16] (expressed by SLM using ω=0.825) and the shift splitting iteration approach described in [22] (represented by SM). The results are provided in Table 1.Table 1
Numerical results for Example4 with Ψ=0.3 and λ=0.95.
Methodsn1000200030004000SLMItr18181818Time3.015613.124933.910465.1345RSV6.92e–076.93e–076.93e–076.94e–07SMIter14141414Time2.81289.095417.302829.1644RSV8.91e-078.92e-078.93e-078.93e-07NGGS method IItr10101010Time2.46307.622814.632523.0959RSV9.70e-076.85e–075.60e–074.85e–07NGGS method IIItr6666Time1.13222.73424.08457.7877RSV3.70e-063.68e-073.69e-073.69e-07Table1 presents the solution x⋆ for various values of n. The result of this comparison shows that our proposed techniques are more efficient than SLM and SM approaches in terms of “Itr” and “Time.”Example 5.
ConsiderA=M+4I∈Rn×n and b=Ax⋆−∣x⋆∣∈Rn with
M=tridiag−In,Hn,−In∈Rn×n,x⋆=−1,1,−1,1,⋯,−1,1T∈Rn,where Hn=tridiag−1,4,−1∈Rv×v, I∈Rv×v, being a unit matrix and n=v2. For Examples 5 and 6, use the same stopping criterion and initial guess mentioned in [18]. The recommended methods are compared with the AOR approach [14] and the mixed-type splitting (MTS) iterative technique [18]. The outcomes are summarized in Table 2.Table 2
Numerical results for Example5 with Ψ=0.2 and λ=0.98.
Methodsn6425610244096AORItr14141535Time0.34831.97882.38715.8097RSV5.215e-076.293e-076.548e-078.741e-07MTSItr14141525Time0.31681.09521.96472.2194RSV4.310e-075.468e-075.069e-079.384e-07NGGS method IItr12131314Time0.21310.52851.85532.0033RSV8.80e-077.32e-079.49e-074.11e-07NGGS method IIItr5555Time0.14750.41871.35821.9283RSV1.26e-071.40e-071.45e-071.47e-07In Table2, we present the numeric outcomes of the AOR method, MTS method, NGGS method I, and NGGS method II, respectively. Our results indicate that the proposed methods are more effective than both AOR and MTS approaches.Example 6.
ConsiderA=M+I∈Rn×n and b=Ax⋆−∣x⋆∣∈Rn with
M=tridiag−1.5In,Hn,−0.5In∈Rn×n,x⋆=1,2,1,2,⋯T∈Rn,where Hn=tridiag−1.5,4,−0.5∈Rv×v and n=v2. The findings are summarized in Table 3.Table 3
Numerical results for Example6 with Ψ=0.2 and λ=0.98.
Methodsn10040090016004900AORItr97190336706384Time0.47212.82033.21746.38879.2344RSV9.80e-079.61e-079.73e-079.84e-079.36e-07MTSItr88157250386342Time0.40411.79533.02195.76268.8965RSV8.91e-079.65e-079.18e-079.56e-079.89e-07NGGS method IItr39597692112Time0.23090.42501.96332.54133.4387RSV8.39e-078.90e-079.32e-079.31e-077.42e-07NGGS method IIItr2233435288Time0.14860.25370.92551.36711.7898RSV5.09e-077.45e-077.63e-079.17e-078.90e-07Table3 presents the solution x⋆ for various values of n. The result of this comparison shows that our proposed techniques are more efficient than AOR and MTS approaches in terms of “Itr” and “Time.”Example 7.
Let
A=tridiag−1,8,−1∈Rn×n,x⋆=−1h,h=1,2,⋯,nT∈Rnand b=Ax⋆−∣x⋆∣∈Rn. Applying the same stopping criteria and initial guess as given in [37], we compare the novel approaches with the technique shown in [37] (expressed by SA using ω=1.0455) and the SOR-like technique presented in [15] (denoted by SOR).Table4 shows that all tested techniques can quickly compute AVE (1). However, we see that the “Itr” and “Time” of the proposed approaches are less than the other known approaches. In conclusion, we find that the proposed approaches are feasible and useful for AVEs.Table 4
Numerical results for Example7 with Ψ=0.3 and λ=0.95.
Methodsn10002000300040005000SAItr1313141414Time3.99288.868024.403151.394673.3394RSV6.04e-078.54e-072.33e-072.69e-073.01e-07SORItr1213131313Time1.51363.38176.12627.17159.5261RSV9.45e-082.69e-083.29e-083.80e-084.25e-07NGGS method IItr1010101010Time1.39112.97363.60035.91127.7228RSV5.77e–075.78e–075.78e–075.78e–075.78e–07NGGS method IIItr56666Time0.27530.99101.39852.35152.9527RSV7.15e–071.67e–082.04e–082.62e–083.81e–07


## 5. Conclusions

In this work, two novel NGGS approaches are presented for the purpose of determining AVEs, and their convergence properties are discussed in detail. Then, numerical experiments are used to demonstrate their effectiveness. Ultimately, the numerical tests show that the recommended procedures are more efficient in iteration steps and computing time than the existing methods.



---

*Source: 4266576-2022-05-06.xml*