# Numerical Solution of the Absolute Value Equation Using Modified Iteration Methods

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

---

## Abstract

This article suggests two new modified iteration methods called the modified Gauss-Seidel (MGS) method and the modified fixed point (MFP) method to solve the absolute value equation. Using appropriate assumptions, we examine the convergence of the given methods. Lastly, numerical examples illustrate the usefulness of the new strategies.


---

## Body

## 1. Introduction

Let the absolute value equation (AVE) be(1)Ax−x=b.In this case, the order of theA matrix is n×n, b∈Rn, and x describes the component-wise absolute value of x vector. The AVE is an important nondifferentiable and nonlinear problem in optimization, such as convex quadratic programming, linear complementarity problems (LCPs), and linear programming (see [1–12]).The development of numerical procedures for AVE has been extensively studied recently, and several techniques have been presented. For example, Fakharzadeh and Shams [13] introduced the mixed-type splitting approach to determine AVE (1) and showed the new convergence properties under appropriate conditions. Edalatpour et al. [14] introduced the generalized form of the Gauss-Seidel approach for determining (1). The following summarizes this approach:
(2)DA−EAxk+1−xk+1=FAxk+b.k=0,1,2,⋯,where DA,EA, and FA are expressed in Equation (4), respectively. Ke and Ma [15] offered an SOR-like strategy to obtain the AVE (1). This method is defined as follows:
(3)xj+1=1−ω¨xj+ω¨A−1yj+b,yj+1=1−ω¨yj+ω¨xj+1,j=0,1,2,⋯,where x0∈Rn, y0∈Rn, A∈Rn×n, and ω¨>0. Chen et al. [16] showed the SOR-like strategy with optimal parameters and examined some novel convergence situations different from [15]. Zamani and Hladík [17] offered a new concave minimization approach for AVE (1), which addresses the deficiency of the system proposed in [18] and others (see [19–23]).The remainder of this study is organized in the following manner. Section2 presents various notations and definitions. Section 3 discusses the proposed methods as well as their convergence for AVE (1). We demonstrate the efficiency of the new techniques in Section 4 by providing numerical examples. In the last section, we make concluding remarks.


## 2. Preliminaries

The purpose of this section is to briefly review some of the symbols and concepts used in this article.SupposeA=aij∈Rn×n; we describe the spectral radius and absolute value of A as ρA and A=aij, respectively.Lemma 1 (see [24]).
LetA be an invertible matrix. If A−1<1, then for any vector b, Equation (1) has a unique solution.


## 3. Modified Iteration Methods

Here, we present a detailed discussion of the proposed modified methods for solving AVEs.


### 3.1. MGS Method for AVE

Let us divide matrixA as follows:
(4)A=DA−EA−FA,whereFA, EA, and DA are strictly upper-triangular, strictly lower-triangular, and diagonal matrices of A, respectively. Based on (4), the MGS approach to solving (1) can be expressed as follows:In the MGS method, letA∈Rn×n with A≠0 and b∈Rn. Based on an starting vector x0∈Rn and for k=0,1,2,⋯, until the iterative sequence xkk=0∞ is convergent, calculate
(5)xk+1/2=DA−EA−1xk+DA−EA−1FAxk+b,xk+1=DA−FA−1xk+1/2+DA−FA−1EAxk+1/2+b.The next step is to examine the convergence of the MGS approach by utilizing the subsequent theorem.Theorem 2.
Assume that AVE (1) is solvable, and matrix A satisfies Lemma 1. If
(6)xk+1−x⋆≤GR+GRV+GJR+GJRVxk−x⋆,where
(7)G=DA−EA−1,R=DA−FA−1,J=FAandV=EA.
Then, for any starting vectorx0, the sequence xkk=0∞ created by the MGS approach converges to the unique solution x⋆ of the Equation (1).Proof.
Suppose thatx⋆ is the solution of Equation (1); then we obtain
(8)xk+1/2−x⋆=DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,xk+1−x⋆=DA−FA−1xk+1/2−x⋆+DA−FA−1EAxk+1/2−x⋆.
Using absolute values for each side of the first equation of (8), we get
(9)xk+1/2−x⋆≤DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,≤DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,or equivalently
(10)xk+1/2−x⋆≤Gxk−x⋆+GJxk−x⋆,≤G+GJxk−x⋆.
Similarly, the second part of (8) indicates
(11)xk+1−x⋆≤R+RVxk+1/2−x⋆.
From (10) and (11), we obtain
(12)xk+1−x⋆≤G+GJ×R+RVxk−x⋆.
So,(13)xk+1−x⋆≤GR+GRV+GJR+GJRVxk−x⋆.
GR+GRV+GJR+GJRV is nonnegative. Note that if ρGR+GRV+GJR+GJRV<1, then the sequence xkk=0∞ of MGS approach converges to the unique solution x⋆ of AVE.


### 3.2. MFP Method for AVE

First, we will briefly discuss the fixed point method of determining the AVE. The AVE (1) is equivalent to the fixed point problem of solving
(14)x=Fx,such that
(15)Fx=x−ϕEAx−x−b,where ϕ>0 and E is a positive diagonal matrix. If we take ϕE=DA−1, then, the fixed point method for solving AVE (1) is defined as follows:
(16)xk+1=xk−DA−1Axk−xk−b,k=0,1,2,⋯.The purpose of this article is to discuss the MFP method. Then, the offered method is expressed as follows:In the MFP method, letA∈Rn×n with detA≠0 and b∈Rn. Based on an starting vector x0∈Rn and for k=0,1,2,⋯, until the iterative sequence xkk=0∞ is convergent, calculate
(17)xk+1/2=xk−DA−1Axk−xk−b,xk+1=xk−DA−1Axk+1/2−xk+1/2−b.The next step is to examine the convergence of the MFP method by utilizing the subsequent theorem.Theorem 3.
Let matrixA satisfy Lemma 1. If
(18)xk+1−x⋆≤I−DA−1A+DA−12xk−x⋆,then the xkk=0∞ sequence derived from (17) converges to the unique solution x⋆.Proof.
Supposex⋆ represents the solution to AVE (1); then we obtain
(19)xk+1/2−x⋆=xk−x⋆−DA−1Axk−x⋆−xk−x⋆,xk+1−x⋆=xk+1/2−x⋆−DA−1Axk+1/2−x⋆−xk+1/2−x⋆.(20)xk+1/2−x⋆=xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,xk+1−x⋆=xk+1/2−x⋆−DA−1Axk+1/2−x⋆+DA−1xk+1/2−x⋆.
Using absolute values for each side of the first equation of (20), we get
(21)xk+1/2−x⋆≤xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,≤xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,or equivalently
(22)xk+1/2−x⋆≤I−DA−1A+DA−1xk−x⋆.
Similarly, the second part of (20) indicates
(23)xk+1−x⋆≤I−DA−1A+DA−1xk+1/2−x⋆.
From (22) and (23), we obtain
(24)xk+1−x⋆≤I−DA−1A+DA−1×I−DA−1A+DA−1xk−x⋆.
So,(25)xk+1−x⋆≤I−DA−1A+DA−12xk−x⋆.
Evidently, ifρI−DA−1A+DA−12<1, the iteration sequence xkk=0∞ created by the MFP method is convergent (Table 1).Table 1
Abbreviations of testing methods.
MethodsDescriptionSORLaoptSOR-like approach with approximate optimal parameter [16]SORLoSOR-like method [15, 16]SORLoptSOR-like approach with optimal parameter [16]GGSGeneralized Guass-Seidel method [14]MGSModified Guass-Seidel method (our algorithm 3.1)MFPModified fixed point method (our algorithm 3.2)


## 3.1. MGS Method for AVE

Let us divide matrixA as follows:
(4)A=DA−EA−FA,whereFA, EA, and DA are strictly upper-triangular, strictly lower-triangular, and diagonal matrices of A, respectively. Based on (4), the MGS approach to solving (1) can be expressed as follows:In the MGS method, letA∈Rn×n with A≠0 and b∈Rn. Based on an starting vector x0∈Rn and for k=0,1,2,⋯, until the iterative sequence xkk=0∞ is convergent, calculate
(5)xk+1/2=DA−EA−1xk+DA−EA−1FAxk+b,xk+1=DA−FA−1xk+1/2+DA−FA−1EAxk+1/2+b.The next step is to examine the convergence of the MGS approach by utilizing the subsequent theorem.Theorem 2.
Assume that AVE (1) is solvable, and matrix A satisfies Lemma 1. If
(6)xk+1−x⋆≤GR+GRV+GJR+GJRVxk−x⋆,where
(7)G=DA−EA−1,R=DA−FA−1,J=FAandV=EA.
Then, for any starting vectorx0, the sequence xkk=0∞ created by the MGS approach converges to the unique solution x⋆ of the Equation (1).Proof.
Suppose thatx⋆ is the solution of Equation (1); then we obtain
(8)xk+1/2−x⋆=DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,xk+1−x⋆=DA−FA−1xk+1/2−x⋆+DA−FA−1EAxk+1/2−x⋆.
Using absolute values for each side of the first equation of (8), we get
(9)xk+1/2−x⋆≤DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,≤DA−EA−1xk−x⋆+DA−EA−1FAxk−x⋆,or equivalently
(10)xk+1/2−x⋆≤Gxk−x⋆+GJxk−x⋆,≤G+GJxk−x⋆.
Similarly, the second part of (8) indicates
(11)xk+1−x⋆≤R+RVxk+1/2−x⋆.
From (10) and (11), we obtain
(12)xk+1−x⋆≤G+GJ×R+RVxk−x⋆.
So,(13)xk+1−x⋆≤GR+GRV+GJR+GJRVxk−x⋆.
GR+GRV+GJR+GJRV is nonnegative. Note that if ρGR+GRV+GJR+GJRV<1, then the sequence xkk=0∞ of MGS approach converges to the unique solution x⋆ of AVE.


## 3.2. MFP Method for AVE

First, we will briefly discuss the fixed point method of determining the AVE. The AVE (1) is equivalent to the fixed point problem of solving
(14)x=Fx,such that
(15)Fx=x−ϕEAx−x−b,where ϕ>0 and E is a positive diagonal matrix. If we take ϕE=DA−1, then, the fixed point method for solving AVE (1) is defined as follows:
(16)xk+1=xk−DA−1Axk−xk−b,k=0,1,2,⋯.The purpose of this article is to discuss the MFP method. Then, the offered method is expressed as follows:In the MFP method, letA∈Rn×n with detA≠0 and b∈Rn. Based on an starting vector x0∈Rn and for k=0,1,2,⋯, until the iterative sequence xkk=0∞ is convergent, calculate
(17)xk+1/2=xk−DA−1Axk−xk−b,xk+1=xk−DA−1Axk+1/2−xk+1/2−b.The next step is to examine the convergence of the MFP method by utilizing the subsequent theorem.Theorem 3.
Let matrixA satisfy Lemma 1. If
(18)xk+1−x⋆≤I−DA−1A+DA−12xk−x⋆,then the xkk=0∞ sequence derived from (17) converges to the unique solution x⋆.Proof.
Supposex⋆ represents the solution to AVE (1); then we obtain
(19)xk+1/2−x⋆=xk−x⋆−DA−1Axk−x⋆−xk−x⋆,xk+1−x⋆=xk+1/2−x⋆−DA−1Axk+1/2−x⋆−xk+1/2−x⋆.(20)xk+1/2−x⋆=xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,xk+1−x⋆=xk+1/2−x⋆−DA−1Axk+1/2−x⋆+DA−1xk+1/2−x⋆.
Using absolute values for each side of the first equation of (20), we get
(21)xk+1/2−x⋆≤xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,≤xk−x⋆−DA−1Axk−x⋆+DA−1xk−x⋆,or equivalently
(22)xk+1/2−x⋆≤I−DA−1A+DA−1xk−x⋆.
Similarly, the second part of (20) indicates
(23)xk+1−x⋆≤I−DA−1A+DA−1xk+1/2−x⋆.
From (22) and (23), we obtain
(24)xk+1−x⋆≤I−DA−1A+DA−1×I−DA−1A+DA−1xk−x⋆.
So,(25)xk+1−x⋆≤I−DA−1A+DA−12xk−x⋆.
Evidently, ifρI−DA−1A+DA−12<1, the iteration sequence xkk=0∞ created by the MFP method is convergent (Table 1).Table 1
Abbreviations of testing methods.
MethodsDescriptionSORLaoptSOR-like approach with approximate optimal parameter [16]SORLoSOR-like method [15, 16]SORLoptSOR-like approach with optimal parameter [16]GGSGeneralized Guass-Seidel method [14]MGSModified Guass-Seidel method (our algorithm 3.1)MFPModified fixed point method (our algorithm 3.2)


## 4. Numerical Tests

In this section, we investigate experimentally the performance of newly developed approaches for determining the AVEs. The computations have been performed on an Intel Core (TM) i7-10875H, with 32 GB memory, and a 5.1 GHz CPU, as well as using MATLAB (2017a). The initial guess is a zero vector, and the current iteration ends when it meets the requirement(26)RES≔Axk−xk−b2≤10−8.Example 1 (see [16]).
Let(27)A8−1−18−1−18⋱⋱⋱−1−18∈Rn×n,x=−11⋮−11∈Rn,and vector b=Ax−x∈Rn. Table 2 summarizes the outcomes.Listed in Table2 are the iteration steps (Iter), CPU time in seconds (Time), and residuals (RES) for each method. Table 2 provides numerical results that show the suggested methods to be more efficient in terms of time and iteration steps than all other compared methods. Additionally, we compare all approaches graphically for n=1000 and n=3000. The graphical outcomes are shown in Figure 1.Example 2 (see [16]).
LetM+4I=A∈Rn×n and Ax−x=b∈Rn using
(28)MS−I−IS−I−IS⋱⋱⋱−I−IS∈Rn×n,x=−11⋮−11∈Rn,where I∈Rv×v is the identity matrix, v2=n, and
(29)S=tridiag−1,4,−1=4−1−14−1−14⋱⋱⋱−1−14∈Rv×vis a tridiagonal matrix. Table 3 outlines the results.Table 2
Calculations of Example1.
Approachesn10002000300040005000SORLaoptIter2020202020Time0.00140.00280.00480.00580.0073RES4.13e–095.84e–097.15e–098.26e–099.23e–09SORLoIter1616171717Time0.00140.00230.00390.00570.0064RES6.27e–099.51e–092.59e–093.00e–093.35e–09SORLoptIter1212131313Time0.00070.00190.00270.00360.0039RES5.75e–095.75e–095.75e–095.75e–095.75e–09RES6.80e–099.63e–091.19e−091.37e–091.53e–09GGSIter1111111111Time0.00370.00630.00860.01690.1921RES2.40e–092.76e–073.07e–093.36e–093.63e–09MFPIter1010101010Time0.00060.00110.00170.00290.0033RES2.68e–093.791e–094.65e–095.37e–096.01e–09MGSIter78888Time0.00030.00070.00120.00180.0031RES9.80e–095.09e–106.18e–107.11e–107.93e–10Figure 1
Comparison of different approaches in a graph form.
(a)
n=1000(b)
n=3000Table 3
Calculations of Example2.
Methodn6425610244096SORLaoptIter23242526Time0.00360.00860.02830.1466RES4.24e–095.32e–094.92e–094.08e–09SORLoIter20212222Time0.00320.00810.02580.1162RES3.15e–094.03e–093.38e–097.41e–09SORLoptIter13141415Time0.00180.00470.01360.0855RES4.93e−073.01e−076.77e−071.82e−07GGSIter18191919Time0.00270.00680.01210.1107RES2.94e–093.62e–096.26e–099.55e–09MFPIter15171718Time0.00170.00390.01060.0671RES6.85e–092.99e–098.66e–095.57e–09MGSIter11121213Time0.00090.00130.00980.0192RES3.87e–092.05e–095.16e–091.69e–09From Table3, we can notice that the MGS method has higher accuracy for different values of n. The MGS method needs less time and a number of iterations as compared with other methods. Furthermore, we observe that the MFP method converges to the solution rapidly as compared with the SORLaopt method, SORLo method, and GGS method. However, the time of the MFP approach is better than the SORLopt strategy. Furthermore, we take n=64 and n=1024 for Example 2 and compare all approaches in a graph form. The graphical outcomes are shown in Figure 2.Figure 2
Comparison of different approaches in a graph form.
(a)
n=64(b)
n=1024The graphical forms in Figures1 and 2 show the implementation of the offered methods. Graphically, representation displays that the convergence of the presented strategies is faster than other methods.


## 5. Conclusion

We examined two new iteration approaches for determining AVEs called the MGS method as well as the MFP method, and we discussed the necessary circumstances for convergence between both methods. To ensure the efficacy of the defined approaches, numerical examples have also been conducted. According to the theoretical analyses and numerical investigations, the presented strategies seem to be vowing to determine the AVEs.



---

*Source: 2828457-2022-07-25.xml*