A generalization of the AOR iteration method for solving absolute value equations

1.   Introduction

In this paper, based on the AOR iteration method, we consider the numerical solution of the absolute value equations (AVE)

where $A\in\mathbb{R}^{n\times n}$, $b \in \mathbb{R}^{n}$ and $|x|$ denotes all the components of the vector $x\in \mathbb{R}^{n}$ by absolute value. If '$|x|$' is replaced by '$B|x|$' in (1.1), then the general AVE is obtained, see ^[1,2]. Nowadays, many optimization problems including linear programming, convex quadratic programming and linear complementarity problem ^[3,4,5] can be formulated as the AVE (1.1) such that the AVE (1.1) has been attracted considerable attention.

To efficiently solve the AVE (1.1), in recent years, a great deal of effort has been committed to develop iteration methods. For example, in ^[6], Mangasarian presented a generalized Newton method for solving the AVE (1.1) and simply described below

where $D(x^{(k)})$ is a diagonal matrix of the form $D(x^{(k)}) = diag(sign(x^{(k)}))$. One can see ^[7,8,9,10] and find other versions of the generalized Newton method. Clearly, using the generalized Newton method to solve the AVE (1.1), the inverse of the matrix $A-D(x^{(k)})$ should be computed. Noting that the matrix $A-D(x^{(k)})$ is changed with the iteration index $k$, the computation cost of the generalized Newton method may be highly expensive. To remain the iteration matrix unchanged, the following Picard iteration method was considered in ^[11]

When the matrix $A$ in (1.3) is ill-conditioned, in each iteration of the Picard method, we have to deal with this ill-conditioned linear system. To overcome the inverse of the matrix $A$, by making use of the Hermitian and skew-Hermitian splitting (HSS) of the matrix $A$ in ^[12], Zhu et al. in ^[13] presented the nonlinear HSS-like method and discussed the convergence property of the nonlinear HSS-like method. Other versions of the nonlinear HSS-like method, one can see ^[14,15,16] for more details. In addition, in ^[17], the classical AOR iteration method has been expanded to solve the AVE. Other relative works are ^{[18,19,20,21,22,23,24]}.

Recently, based on the methodology of the Gauss-Seidel method, together with the matrix splitting $A = D-L-U$ of matrix $A$, where $D = \mbox{diag}(A)$, $L$ and $U$ are strictly lower and upper triangular matrices obtained from $-A$, respectively, in ^[25], the generalized Gauss-Seidel (GGS) iteration method was proposed and adopted to solve the AVE (1.1), which is of form

Numerical experiments showed the efficiency of the GGS method.

In this paper, inspired by the work in ^[25], based on the AOR iteration method, a generalization of the AOR iteration method (GAOR) is presented to solve the AVE (1.1) and its convergence conditions are discussed in detail. By making use of some numerical experiments, we present the effectiveness of the GAOR method.

The remainder of the paper is organized as follows: Section 2 goes over some preparatory knowledge. Section 3 presents the GAOR iteration method and its convergence conditions. Section 4 reports some numerical results to show the efficiency of the GAOR method. Finally, Section 5 draws some conclusions.

2.   Preparatory knowledge

Let $C = (c_{ij})\in \mathbb{R}^{n\times n}$. 'diag($C$)' denotes the diagonal part of matrix $C$. For $A = (a_{ij}), B = (b_{ij})\in \mathbb{R}^{n\times n}$, we call $A\geq B$ if $a_{ij}\geq b_{ij}$ for $i, j = 1, 2, \ldots, n$. Matrix $A$ is called non-negative if $A \geq0$; further, $A-B\geq0$ if and only if $A\geq B$. These definitions carry immediately over to vectors by identifying them with $n\times1$ matrices. Matrix $A = (a_{ij})\in \mathbb{R}^{n\times n}$ is called a $Z$-matrix if $a_{ij}\leq 0$ for $i\neq j$; an $L$-matrix if $A$ is a $Z$-matrix and $a_{ii} > 0$ for $i = 1, \ldots, n$; an $M$-matrix if $A$ is a $Z$-matrix and $A^{-1}\geq0$; and an $H$-matrix if its comparison matrix $\langle A\rangle = (\langle a\rangle_{ij}) \in \mathbb{R}^{n\times n}$ is an $M$-matrix, where

If $A$ is an $M$-matrix and $B$ is a $Z$-matrix, then $A\leq B$ implies that $B$ is an $M$-matrix ^[26]. A matrix $A$ is irreducible if the directed graph associated to $A$ is strongly connected ^[27].

Let $A = M-N$. It is called a matrix splitting of $A$ if $\det(M)\neq0$; called regular if $M^{-1}\geq0$ and $N\geq0$; an $M$-splitting of $A$ if $M$ is an $M$-matrix and $N\geq0$. Evidently, if $A = M- N$ is an $M$-splitting and $A$ is a nonsingular $M$-matrix, then $\rho(M^{-1}N) < 1$, where $\rho(\cdot)$ denotes the spectral radius of the matrix.

Lemma 2.1. ^[28] Let $A$ be an $H$-matrix. Then$|A^{-1}|\leq\langle A\rangle^{-1}$.

Lemma 2.2. ^[29] Let $x, y\in \mathbb{R}^{n}$. Then $\||x|-|y|\|_{2}\leq\|x-y\|_{2}$.

3.   GAOR iteration method

In this section, the generalized AOR (GAOR) method is introduced to solve the AVE (1.1). For this purpose, we split $A$ into

with

where $\Omega$ is a positive diagonal matrix, $\omega$ and $r$ are real parameters with $\omega\neq0$, $D = \mbox{diag}(A)$, $L$ and $U$ are the previously mentioned. Based on the matrix splitting (3.1), the AVE (1.1) is rewritten as the fixed-point equations

or

then for $k = 0, 1, \ldots$, we can define the GAOR method for solving (1.1) below

Lemma 3.1. Let $\alpha > \beta > 0$. Then $\alpha x-\beta|x| = b$ with $b\in \mathbb{R}$ has onlyone solution in $\mathbb{R}$. If $b \geq0$, then the solution is$x = \frac{b}{\alpha-\beta}$, otherwise $x = \frac{b}{\alpha+\beta}$.

Proof. The results in Lemma 3.1 are valid, whose proof is omitted here.

Next, based on Lemma 3.1, we present Algorithm 1 to solve each step of the GAOR iteration method (3.3) when all the diagonal entries of the matrix $\Omega+D$ are greater than $\omega$.

Algorithm 1:

For k = 0, 1, $\ldots$, until convergence, do

Set $s = \omega b_{1}$, $x_{i}^{(0)} = 0$.

For $i = 1, 2, \ldots, n$, do

If $s\geq0$, then

$x_{i}^{(k+1)}: = \frac{s}{a_{ii}+\omega_{ii}-\omega}$;

Else

$x_{i}^{(k+1)}: = \frac{s}{a_{ii}+\omega_{ii}+\omega}$;

Endif

set

Enddo

Enddo

Theorem 3.1. Let $\Omega$ be a positive diagonal matrix and all singular valuesof the matrix $\Omega+D-rL$ exceed $\omega$ with $\omega, r > 0$. If

then the GAOR method $(3.3)$ converges to the uniquesolution of the AVE $(1.1)$ for an arbitrary initial guess$x^{(0)}\in \mathbb{R}^{n}$.

Proof. Since all singular values of the matrix $\Omega+D-rL$ exceed $\omega$ with $\omega, r > 0$,

Let $x^{\ast}$ be a solution of the AVE (1.1). Then from (3.2) we have

After subtracting (3.3) from (3.5), we obtain

which is equal to

Taking 2-norm in the latter equation yields

Further,

To show the uniqueness of the solution, let $y^{\ast}$ be another solution of the AVE $(1.1)$. Then, from Eq (3.2) we have

After subtracting (3.6) from (3.5), similar to the above discussion, we obtain

which is contradiction. Therefore, $y^{\ast} = x^{\ast}$. This completes the proof.

When $w = r$ in (3.3), the GAOR method reduces to the GSOR method. Its convergence theory is given in Corollary 3.1.

Corollary 3.1. Let $\Omega$ be a positive diagonal matrix and all singular valuesof the matrix $\Omega+D-\omega L$ exceed $\omega$ with $\omega > 0$.If

then the GSOR method $(3.3)$ converges to the uniquesolution of the AVE $(1.1)$ for an arbitrary initial guess$x^{(0)}\in \mathbb{R}^{n}$.

Further, in Corollary 3.1, if $\omega = 1$, then the convergence theory of GGS is obtained and described in Corollary 3.2.

Corollary 3.2. Let $\Omega$ be a positive diagonal matrix and all singular valuesof the matrix $\Omega+D-L$ exceed $1$. If

then the GGS method $(3.3)$ converges to the unique solutionof the AVE $(1.1)$ for an arbitrary initial guess$x^{(0)}\in \mathbb{R}^{n}$.

Remark 3.1. In Corollary 3.2, if $\Omega$ is a zero matrix, then the results of Corollary 3.2 are similar to Theorem 3 in ^[25]. In fact, if we use 'all singular values of the matrix $D-L$ exceed $1$' instead of 'Let the diagonal entries of $A$ be greater than one and the matrix $D-L-I$ be strictly row diagonally dominant' in Theorem 3 in ^[25], then Theorem 3 in ^[25] holds as well.

It is not difficult to find that the above theoretical results including Theorem 3.1, Corollary 3.1 and Corollary 3.2 are a litter too general and not easy to verify. To overcome these negative factors, an effective approach is to limit the type of matrix $A$. Next, we restrict our attention to this situation where $A$ is an $H$-matrix with positive diagonals. For $A$ being an $H$-matrix with positive diagonals, a simple convergence condition for the GAOR method $(3.3)$ can be obtained, see Theorem 3.2.

Theorem 3.2. Let $A$ be an $H$-matrix with positive diagonals and the positivediagonal matrix $\Omega\geq\omega I$. If $\omega$ and $r$ satisfy

then the GAOR method $(3.3)$ converges to the uniquesolution of $(1.1)$ for an arbitrary initial guess$x^{(0)}\in \mathbb{R}^{n}$.

Proof. Since $A$ is an $H$-matrix with positive diagonals, we have

Further,

It follows that matrix $\Omega+D-rL$ is an $H$-matrix with positive diagonals. It holds that

From the proof of Theorem 3.1, we get

Further,

Since the matrix $\Omega+D-rL$ is an $H$-matrix with positive diagonals, the matrix $\langle\Omega+D-rL\rangle$ is an $M$-matrix and $\langle\Omega+D-rL\rangle^{-1} > 0$. Noting that $\Omega\geq\omega I$, it is easy to obtain that

where $a_{ii}+\omega_{ii}$ denotes the diagonal elements of matrix $\Omega+D$. Hence, from (3.10), we get

Let

Evidently, the GAOR method $(3.3)$ converges to the unique solution of the AVE $(1.1)$ if $\rho(\bar{M}^{-1}\bar{N}) < 1$. Noting that $\bar{A}$ is an $M$-matrix, matrix $\bar{M}$ is an $M$-matrix and $\bar{N}\geq0$. Then, $\bar{A} = \bar{M}-\bar{N}$ is an $M$-splitting. Therefore, $\rho(\bar{M}^{-1}\bar{N}) < 1$.

From Theorem 3.2, the convergence conditions of the corresponding GSOR and GGS methods for $A$ being an $H$-matrix with positive diagonals are obtained, which are omitted.

4.   Numerical experiments

In this section, we give some numerical experiments to assess the efficiency of the GAOR method for solving the AVE (1.1). We compare GAOR with AOR in^[17] from two aspects: the number of iterations (denoted as IT) and the CPU time in seconds (denoted as CPU). Meanwhile, we also investigate the generalized Newton method, the nonlinear HSS-like method ^[13] and the Picard-HSS method ^[14]. The starting iterate is zero vector, all iterations are terminated once the relative residual error satisfies

or if the number of the prescribed iteration $k_{\max} = 500$ is exceeded. All the tests are performed in MATLAB R2016B.

Example 4.1. (^[25,30]) Let $m$ be a prescribed positive integer and $n = m^{2}$. Consider the AVE (1.1), in which $A\in \mathbb{R}^{n\times n}$ is given by $A = \hat{M}+\mu I$, where

with

and $b = Ax^{\ast}-|x^{\ast}|$ with $x^{\ast} = (-1, 1, -1, 1, \ldots, -1, 1)^{T}\in \mathbb{R}^{n}$.

Example 4.1 can be induced by using the finite difference to discretize the flow of water through a porous dam under the equidistant grid ^[30].

Example 4.2. (^[31]) Let $m$ be a prescribed positive integer and $n = m^{2}$. Consider the AVE (1.1), in which $A\in \mathbb{R}^{n\times n}$ is given by $A = \hat{M}+\mu I$, where

with

and $b = Ax^{\ast}-|x^{\ast}|$ with $x^{\ast} = (-1, 1, -1, 1, \ldots, -1, 1)^{T}\in \mathbb{R}^{n}$.

To fairly compare the GAOR method with the AOR method, we choose the same parameters to test the GAOR method and the AOR method. Under this consideration, in Tables 1–4, for Examples 4.1 and 4.2 with $\mu = 2$, $\Omega = 0.1 I$ and $\Omega = 0.5 I$, we list some iteration results to illustrate the convergence behaviors of the GAOR and AOR methods for the different problem sizes of $n$. We observe that the GAOR and AOR methods can calculate a satisfactory approximation to the solution of the AVE. Fixing $\omega$ and $n$ with $r$ increasing, the iteration steps of the GAOR and AOR methods descend. Fixing $\omega$ and $r$ with $n$ increasing, the iteration steps of the GAOR and AOR methods may be hardly sensitive to change. Further, we find that the GAOR method requires less iteration steps than the AOR method, but the GAOR method requires more CPU times than the AOR method. The time-consuming of the GAOR method is due to the code only edited by all the components of the matrix. To make the AOR method more competitive, an effective approach is to optimize the edited code, which is an interesting work in the future.

Tables 5 and 6 list the numerical results of the generalized Newton method, where 'GN' denote the generalized Newton method. Comparing the GAOR method, the AOR method with the generalized Newton method, the generalized Newton method require the least iteration steps, but it also takes the most time. Among three methods, the computational efficiency of the generalized Newton method is worst.

Finally, we compare the GAOR method with the nonlinear HSS-like method and the Picard-HSS method under the same parameter, see Table 7. The explanation is that the nonlinear HSS-like method and the Picard-HSS method only contain a parameter, here, we consider the GAOR method with $\omega = r$, i.e., the GSOR method. When the Picard-HSS method is applied, the stopping criterion for its inner iterations is adopted in ^[13]. In Table 7, 'GSOR', 'NHSS' and 'PHSS', respectively, denote the GSOR method, the nonlinear HSS-like method and the Picard-HSS method, '$-$' denotes that the iteration steps exceed 500, and '$\cdot(\cdot)$' denotes the outer (inner) iteration steps. From Table 7, the numerical results show that the GSOR method is more effective than the nonlinear HSS-like method and the Picard-HSS method.

Overall, based on the numerical results, the GAOR method displays the good performance when the above presented five testing methods are applied to solve the absolute value equations.

5.   Conclusions

In this paper, we have designed a generalization AOR (GAOR) method to solve the absolute value equations. Some convergence properties for the proposed GAOR method are gained. Numerical experiments have been reported to verify the efficiency of the proposed method.

Acknowledgements

The author thanks five anonymous referees for their constructive suggestions and helpful comments, which led to significant improvement of the original manuscript of this paper. The authors are partially supported by National Natural Science Foundation of China (11961082).

Conflict of interest

The authors declare there is no conflicts of interest.