# The error and perturbation bounds for the absolute value equations with some
applications††thanks: This research was supported by National Natural Science
Foundation of China (No.11961082).

Shi-Liang Wu, Cui-Xia Li
School of Mathematics, Yunnan Normal University,
Kunming, Yunnan, 650500, P.R. China Corresponding author:
slwuynnu<EMAIL_ADDRESS>
###### Abstract

In this paper, inspired by in the pervious published work in [Math. Program.,
198 (2023), pp. 85-113] by Zamani and Hladík, we focus on the error and
perturbation bounds for the general absolute value equations because so far,
to our knowledge, the error and perturbation bounds for the general absolute
value equations are not discussed. In order to fill in this study gap, in this
paper, by introducing a class of absolute value functions, we study the error
bounds and perturbation bounds for two types of absolute value equations
(AVEs): $Ax-B|x|=b$ and $Ax-|Bx|=b$. Some useful error bounds and perturbation
bounds for the above two types of absolute value equations are presented. By
applying the absolute value equations, we also obtain the error and
perturbation bounds for the horizontal linear complementarity problem (HLCP).
In addition, a new perturbation bound for the LCP without constraint
conditions is given as well, which are weaker than the presented work in [SIAM
J. Optim., 2007, 18: 1250-1265] in a way. Besides, without limiting the matrix
type, some computable estimates for the above upper bounds are given, which
are sharper than some existing results under certain conditions. Some
numerical examples for the AVEs from the LCP are given to show the feasibility
of the perturbation bounds.

Keywords: Absolute value equations; the error bound; the perturbation bound;
horizontal linear complementarity problem; linear complementarity problem

AMS classification: 65G50, 90C33

##  1 Introduction

Consider the following two types of the absolute value equations (AVEs)

$Ax-B|x|=b$ (1.1)

and

$Ax-|Bx|=b,$ (1.2)

where $A,B\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$, $|\cdot|$
denotes the componentwise absolute value of the vector. The AVEs (1.1) and
(1.2), respectively, were introduced in [1] by Rohn and [2] by Wu. Clearly,
when $B=I$ in (1.1) and (1.2), where $I$ denotes the identity matrix, the AVEs
(1.1) and (1.2) reduce to the standard absolute value equations

$Ax-|x|=b,$ (1.3)

which was considered in [3] by Mangasarian and Meyer.

Over these years, the AVEs (1.1), (1.2) and (1.3) have excited much interest
since they often occur in many significant mathematical programming problems,
including linear programs, quadratic programs, bimatrix game, linear
complementarity problem (LCP), see [3, 5, 4, 6] and references therein. For
instance, the AVEs (1.1) is equivalent to the LCP of determining a vector
$z\in\mathbb{R}^{n}$ such that

$w=Mz+q\geq 0,\ z\geq 0\ \mbox{and}\ z^{T}w=0\ \mbox{with}\
M\in\mathbb{R}^{n\times n}\ \mbox{and}\ q\in\mathbb{R}^{n}.$ (1.4)

By using $z=|x|+x$ and $w=|x|-x$ for (1.4), the AVEs (1.1) is obtained with
$A=I+M$, $B=I-M$ and $b=-q$.

Although the AVEs in [3] is a NP-hard problem, so far, a large number of
theoretical results, numerical methods and applications have been extensively
excavated. For instance, among the theoretical results, in spite of
determining the existence of the solution of the AVEs in [5, 20] is NP-hard,
and checking whether the AVEs has unique or multiple solutions in [6] is also
NP-complete, there still exist some very important conclusions, in particular,
some sufficient and necessary conditions for ensuring the existence and
uniqueness of the solutions of the AVEs (1.1), (1.2) and (1.3) were
established for any $b\in\mathbb{R}^{n}$, see [7, 8, 2, 9].

Likewise, solving the AVEs in [5] is NP-hard as well. It may be due to the
fact that the AVEs contains a non-linear and non-differential absolute value
operator. Even so, some efficient numerical methods have been developed, such
as the generalized Newton method [10], Newton-based matrix splitting method
[11], the exact and inexact Douglas-Rachford splitting method [12], the
Picard-HSS method [13], the sign accord method [14], the concave minimization
method [15], the Levenberg-Marquardt method [16], and so on.

As an important application of the AVEs, for all we know, the AVEs was first
viewed as a very effective tool to gain the numerical solution of the LCP in
[17], called the modulus method. At present, this numerical method has
achieved rapid development and its many various versions were proposed, see
[18, 19] and references therein. Since the modulus method has the
superiorities of simple construction and quick convergence behavior, it is
often regarded as a top-priority method for solving the large-scale and sparse
complementarity problem (CP).

In addition to the above aspects about the AVEs, another very important
problem is the sensitivity and stability analysis of the AVEs, i.e., how the
solution variation is when the data is perturbed. More specifically, when
$\Delta A,\Delta B~{}\mbox{and}~{}\Delta b$ are the perturbation terms of
$A,B~{}\mbox{and}~{}b$ in (1.1) and (1.2), respectively, how do we
characterize the change in the solution of the perturbed AVEs. With respect to
this regard, to our knowledge, the perturbation analysis of the AVEs (1.1) and
(1.2) has not been discussed. In addition, for the error bound of AVEs, under
the assumption of strongly monotone property, a global projection-type error
bound was provided in [20]. Obviously, this kind of conditional projection-
type error bound frequently has great limitation.[39] only provides some upper
bounds for the error bound of the AVE (1.1) with $B=I$ (the identity matrix).
Therefore, based on these considerations, in this paper, we in-depth discuss
the error bounds and the perturbation bounds of the AVEs. The contributions
are given below:

  * •

Firstly, by introducing a class of the absolute value functions, the framework
of error bounds for the AVEs are presented without any constraints. Without
limiting the matrix type, some computable estimates for their upper bounds are
given. These bounds are sharper than the existing bounds in [20] under certain
conditions.

  * •

Secondly, we establish the framework of perturbation bounds for the AVEs and
present some computable upper bounds. It is pointed out that when the
nonlinear term $B|x|$ in (1.1) is vanished, the presented perturbation bounds
reduce to the classical perturbation bounds for the linear systems $Ax=b$,
including Theorem 1.3 in numerical linear algebra textbooks [26] and Theorem
2.1 [27].

  * •

Thirdly, to our knowledge, the error and perturbation bounds of HLCP have not
been discussed. In order to fill in this study gap, we convert the HLCP to the
equal certain absolute value equations, obtain the framework of error bounds
and perturbation bounds for the HLCP, which is viewed as another aspect of
applications of the absolute value equations. In particular, two new equal
error bounds for the LCP are exploited, concomitantly, three new computable
upper bounds are obtained and sharper than that in [30] for the system matrix
being an $H_{+}$-matrix under proper conditions. Further, without the
constraint conditions, we display a new framework of perturbation bound of the
LCP and obtain three new computable upper bounds advantage over that in [33]
for the system matrix being a symmetric positive definite matrix and an
$H_{+}$-matrix.

  * •

Fourthly, a new approach for some existing perturbation bounds in [33] for the
LCP is provided as well.

  * •

Of course, finally, to show the efficiency of some proposed bounds, some
numerical examples for the AVEs from the LCP are investigated.

The rest of the article is organized as follows. Section 2 provides the
framework of error bounds for the AVEs by introducing a class of absolute
value functions. In Section 3, some perturbation bounds for the AVEs are
provided. In Section 4, the frameworks of error bounds and perturbation bounds
for the HLCP are presented by using the AVEs. In Section 5, some numerical
examples for the AVEs from the LCP are given to show the feasibility of some
perturbation bounds. Finally, in Section 6, we end up with this paper with
some conclusions.

Finally, to end this section, we remind some notations, definitions and
conclusions in [34, 2, 7], which will be used in the later discussion.

Let $A=(a_{ij})$ and $N=\\{1,2,\ldots,n\\}$. Then we denote $|A|=(|a_{ij}|)$.
$A=(a_{ij})$ is called an $M$-matrix if $A^{-1}\geq 0$ and $a_{ij}\leq 0$
($i\neq j$) for $i,j\in N$; an $H$-matrix if its comparison matrix $\langle
A\rangle$ (i.e., $\langle a_{ii}\rangle=|a_{ii}|,\langle
a_{ij}\rangle=-|a_{ij}|$ $i\neq j$ for $i,j\in N$) is an $M$-matrix; an
$H_{+}$-matrix if $A$ is an $H$-matrix with $a_{ii}>0$ for $i\in N$; a
$P$-matrix if all principal minors of $A$ are positive. Let $\rho(\cdot)$,
$\sigma_{\min}$ and $\sigma_{\max}$ denote the spectral radius, the smallest
singular value and the largest singular value of matrix, respectively. For two
vectors $q,e\in\mathbb{R}^{n}$, by $q_{+}$ and $q_{-}$ we denote
$q_{+}=\max\\{0,q\\}$, $q_{-}=\max\\{0,-q\\}$ and $e=(1,1,\ldots,1)^{T}$. The
norm $\|\cdot\|$ means $p$-norm, i.e., $\|\cdot\|_{p}$ with $p\geq 1$.

The AVEs (1.1) has a unique solution for any $b\in\mathbb{R}^{n}$ if and only
if $A-BD$ is nonsingular for any diagonal matrix $D=diag(d_{i})$ with
$d_{i}\in[-1,1]$, see Theorem 3.2 in [7]; the AVEs (1.2) has a unique solution
for any $b\in\mathbb{R}^{n}$ if and only if $A-DB$ is nonsingular for any
diagonal matrix $D=diag(d_{i})$ with $d_{i}\in[-1,1]$, see Theorem 3.3 in [2].

##  2 Error bound

In this section, without further illustration, we always assume that the AVEs
(1.1) and (1.2) have the unique solution. Under this premise, we can give the
framework of error bounds on the distance between the approximate solution and
the exact solution of the AVEs (1.1) and (1.2).

###  2.1 Framework of error bounds for AVEs

In this subsection, the framework of error bounds for the AVEs is obtained. To
achieve our goal, the following absolute value function is introduced, see
Lemma 2.1.

######  Lemma 2.1.

Let $a=(a_{1},a_{2},\ldots,a_{n})^{T},b=(b_{1},b_{2},\ldots,b_{n})^{T}$ be any
two vectors in $\mathbb{R}^{n}$. Then there exist $d_{i}\in[-1,1]$ such that

$|a_{i}|-|b_{i}|=d_{i}(a_{i}-b_{i}),\mbox{for\ all}\ i=1,2,\ldots,n.$ (2.1)

######  Proof..

Its proof is straightforward, which is omitted. $\square$

Let

$r(x)=Ax-B|x|-b.$

Clearly, $x^{\ast}$ is a solution of the AVEs (1.1) if and only if
$r(x^{\ast})=0$. The function $r(x)$ is called the natural residual of the
AVEs (1.1). Let $x^{\ast}$ be the unique solution of the AVEs (1.1). Then from
Lemma 2.1 we have

$\displaystyle r(x)=$ $\displaystyle Ax-B|x|-b-(Ax^{\ast}-B|x^{\ast}|-b)$
$\displaystyle=$ $\displaystyle A(x-x^{\ast})-B(|x|-|x^{\ast}|)$
$\displaystyle=$ $\displaystyle A(x-x^{\ast})-B\tilde{D}(x-x^{\ast})$
$\displaystyle=$ $\displaystyle(A-B\tilde{D})(x-x^{\ast}),$

where $\tilde{D}=diag(\tilde{d}_{i})$ with $\tilde{d}_{i}\in[-1,1]$, which
promptly results in the error bounds for the AVEs (1.1), see Theorem 2.1.

######  Theorem 2.1.

Let $x^{*}$ be the unique solution of AVEs (1.1). Then for any
$x\in\mathbb{R}^{n}$,

$\frac{1}{\underline{\alpha}}\|r(x)\|\leq\|x-x^{\ast}\|\leq\overline{\alpha}\|r(x)\|,$
(2.2)

where

$\underline{\alpha}=\max\\{\|A-BD\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}$

and

$\overline{\alpha}=\max\\{\|(A-BD)^{-1}\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}.$

In Theorem 2.1, $\underline{\alpha}\overline{\alpha}\geq 1$. In fact,

$\displaystyle\underline{\alpha}\overline{\alpha}$
$\displaystyle\geq\max\\{\|A-BD\|\|(A-BD)^{-1}\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}$
$\displaystyle\geq\max\\{\|(A-BD)(A-BD)^{-1}\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}$
$\displaystyle=1.$

Similarly, the following involved results, i.e., Theorem 2.2, Corollary 2.1,
Theorem 4.1 and Corollary 4.2, are completely analogical.

By using the same technique for the AVEs (1.2), we have

######  Theorem 2.2.

Let $x^{*}$ be the unique solution of AVEs (1.2). Then for any
$x\in\mathbb{R}^{n}$,

$\frac{1}{\underline{\beta}}\|r(x)\|\leq\|x-x^{\ast}\|\leq\overline{\beta}\|r(x)\|,$
(2.3)

where

$\underline{\beta}=\max\\{\|A-DB\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}$

and

$\overline{\beta}=\max\\{\|(A-DB)^{-1}\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}.$

When $B=I$ in Theorem 2.1 or Theorem 2.2, the error bounds for the AVEs (1.3)
can be obtained, see Corollary 2.1.

######  Corollary 2.1.

Let $x^{*}$ be the unique solution of AVEs (1.3). Then for any
$x\in\mathbb{R}^{n}$,

$\frac{1}{\underline{\gamma}}\|r(x)\|\leq\|x-x^{\ast}\|\leq\overline{\gamma}\|r(x)\|,$
(2.4)

where

$\underline{\gamma}=\max\\{\|A-D\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}$

and

$\overline{\gamma}=\max\\{\|(A-D)^{-1}\|:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\\}.$

######  Remark 2.1.

Clearly, Corollary 2.1 provides the lower and upper error bounds for the AVEs
(1.3). Meanwhile, it is not difficult to find that the right side in (2.4) is
equal to Theorem 7 in [39], which is a main result in [39]. Not only that, we
present a lower error bound for the AVEs (1.3). In this way, we remedy their
work.

In [20], with strongly monotone property, Chen et al. also considered the
global error bound of the AVEs (1.3) and presented the following result.

######  Theorem 2.3.

(Theorem 4.1 in [20]) Let $x^{*}$ be the unique solution of AVEs (1.3). Then
for any $x\in\mathbb{R}^{n}$,

$\frac{1}{\underline{C}}\|r(x)\|\leq\|x-x^{\ast}\|\leq\overline{C}\|r(x)\|,$
(2.5)

where

$\underline{C}=\|A+I\|+\|A-I\|\ \mbox{and}\
\overline{C}=\frac{\|A+I\|+\|A-I\|}{\sigma_{\min}(A)^{2}-1}\ \mbox{with}\
\sigma_{\min}(A)>1.$

Now, we show that the error bounds in Corollary 2.1 are sharper than that in
Theorem 2.3. Here, we consider $\|\cdot\|_{2}$ for Corollary 2.1 and Theorem
2.3.

######  Theorem 2.4.

Let the assumptions of Corollary 2.1 and Theorem 2.3 be satisfied. Then for
any diagonal matrix $D=diag(d_{i})$ with $d_{i}\in[-1,1]$,

$\|A+I\|_{2}+\|A-I\|_{2}\geq\max\|A-D\|_{2}$ (2.6)

and

$\max\|(A-D)^{-1}\|_{2}\leq\frac{\|A+I\|_{2}+\|A-I\|_{2}}{\sigma_{\min}(A)^{2}-1}.$
(2.7)

######  Proof..

Firstly, we prove (2.6). Since $\max\|A-D\|_{2}$ is a convex polyhedron, its
maximum value is obtained at the vertex of $D$, i.e.,

$\max\|A-D\|_{2}=\max\\{\|A+I\|_{2},\|A-I\|_{2}\\},$

from which we prove (2.6).

Next, we prove (2.7). From $\sigma_{\min}(A)>1$, we know $\|A^{-1}\|_{2}<1$.
Further,

$\|A^{-1}\|_{2}\|D\|_{2}<1.$

By Banach Perturbation Lemma in [21], clearly,

$\|(A-D)^{-1}\|_{2}\leq\frac{\|A^{-1}\|_{2}}{1-\|A^{-1}\|_{2}\|D\|_{2}}\leq\frac{\|A^{-1}\|_{2}}{1-\|A^{-1}\|_{2}}.$

By the simple computation, we have

$\displaystyle\|A^{-1}\|_{2}(\sigma_{\min}(A)^{2}-1)=$
$\displaystyle\|A^{-1}\|_{2}(\frac{1}{\sigma_{\max}(A^{-1})^{2}}-1)$
$\displaystyle=$ $\displaystyle\|A^{-1}\|_{2}(\frac{1}{\|A^{-1}\|_{2}^{2}}-1)$
$\displaystyle=$ $\displaystyle\frac{1-\|A^{-1}\|_{2}^{2}}{\|A^{-1}\|_{2}}.$

Since

$\|I+A^{-1}\|_{2}+\|I-A^{-1}\|_{2}=\|A^{-1}(I+A)\|_{2}+\|A^{-1}(I-A)\|_{2}\leq\|A^{-1}\|_{2}(\|A+I\|_{2}+\|A-I\|_{2}),$

we only show that

$1+\|A^{-1}\|_{2}\leq\|I+A^{-1}\|_{2}+\|I-A^{-1}\|_{2}.$ (2.8)

In fact, the inequality (2.8) holds because

$\displaystyle
1+\|A^{-1}\|_{2}<2=\|2I\|_{2}=\|I+A^{-1}+I-A^{-1}\|_{2}\leq\|I+A^{-1}\|_{2}+\|I-A^{-1}\|_{2}.$

This proves (2.7). $\square$

From the proof of Theorem 2.4, we find some interesting results for the matrix
norm, see Proposition 2.1.

######  Proposition 2.1.

The following statements hold:

$(1)$ For $A\in\mathbb{R}^{n\times n}$ and $\alpha>0$ in $\mathbb{R}$,

$2\alpha-\|A\|\leq\|\alpha I+A\|+\|\alpha I-A\|.$

$(2)$ Let $A\in\mathbb{R}^{n\times n}$ and $\alpha\geq 0$ in $\mathbb{R}$.
Then for $\|A\|\leq\alpha$,

$\alpha+\|A\|\leq\|\alpha I+A\|+\|\alpha I-A\|.$

###  2.2 Estimations of $\overline{\alpha}$, $\overline{\beta}$ and
$\overline{\gamma}$

In the Section 2.1, we have given some error bounds for the AVEs (1.1), (1.2)
and (1.3) in Theorem 2.1, Theorem 2.2, and Corollary 2.1, respectively. From
the proof of Theorem 2.4, it is not difficult to find that

$\underline{\alpha}=\underline{\beta}=\max\\{\|A-B\|,\|A+B\|\\}\ \mbox{and}\
\underline{\gamma}=\max\\{\|A-I\|,\|A+I\|\\}.$

However, in general, it is difficult to compute quantities
$\overline{\alpha}$, $\overline{\beta}$ and $\overline{\gamma}$ because they
contain any $D=diag(d_{i})$ with $d_{i}\in[-1,1]$. To overcome this
disadvantage, in this subsection, we explore some computable estimations for
$\overline{\alpha}$, $\overline{\beta}$ and $\overline{\gamma}$.

In the following, we focus on estimating the value of $\overline{\alpha}$. For
$\overline{\beta}$, its process is completely analogical, with regard to
$\overline{\gamma}$ just for their special case. To present the reasonable
estimations for $\overline{\alpha}$, here we consider three aspects: (1)
$\rho(|A^{-1}B|)<1$; (2) $\sigma_{\min}(A)>\sigma_{\max}(B)$; (3)
$\sigma_{max}(A^{-1}B)<1$. For these three cases, the AVEs (1.1) for any
$b\in\mathbb{R}^{n}$ has a unique solution, see Theorem 2 in [23] and Theorem
2.1 in [24], Corollary 3.2 in [7]. Similarly, for $\overline{\beta}$, we
display three aspects: (1) $\rho(|BA^{-1}|)<1$; (2)
$\sigma_{\min}(A)>\sigma_{\max}(B)$; (3) $\sigma_{max}(BA^{-1})<1$. For these
three cases, the AVEs (1.2) for any $b\in\mathbb{R}^{n}$ has a unique solution
as well, see Corollary 3.3 in [2] and Lemma 2.2 in [25], Corollary 3.2 in [2].

####  2.2.1 Case I

Assume that matrices $A$ and $B$ in (1.1) satisfy

$\rho(|A^{-1}B|)<1.$

We can present a reasonable estimation for $\overline{\alpha}$, see Theorem
2.5.

######  Theorem 2.5.

Let $\rho(|A^{-1}B|)<1$ in _( 1.1)_. Then

$\overline{\alpha}\leq\|(I-|A^{-1}B|)^{-1}\|\|A^{-1}\|.$ (2.9)

######  Proof..

Since $A^{-1}BD\leq|A^{-1}BD|\leq|A^{-1}B|$ for any $D=diag(d_{i})$ with
$d_{i}\in[-1,1]$, by Theorem 8.1.18 of [22], we get

$\rho(A^{-1}BD)\leq\rho(|A^{-1}BD|)\leq\rho(|A^{-1}B|)<1.$

So

$\displaystyle|(I-A^{-1}BD)^{-1}|=$
$\displaystyle|I+(A^{-1}BD)+(A^{-1}BD)^{2}+...|$ $\displaystyle\leq$
$\displaystyle I+(|A^{-1}BD|)+(|A^{-1}BD|)^{2}+...$ $\displaystyle\leq$
$\displaystyle I+(|A^{-1}B|)+(|A^{-1}B|)^{2}+...$ $\displaystyle=$
$\displaystyle(I-|A^{-1}B|)^{-1}.$

Combining

$\|(A-BD)^{-1}\|=\|(I-A^{-1}BD)^{-1}A^{-1}\|\leq\|(I-A^{-1}BD)^{-1}\|\|A^{-1}\|$

with

$\|(I-A^{-1}BD)^{-1}\|\leq\||(I-A^{-1}BD)^{-1}|\|\leq\|(I-|A^{-1}B|)^{-1}\|,$

the desired bound (2.9) can be gained. $\square$

Similar to the proof of Theorem 2.5, for $\overline{\beta}$, we have

######  Theorem 2.6.

Let $\rho(|BA^{-1}|)<1$ in _( 1.2)_. Then

$\overline{\beta}\leq\|A^{-1}\|\|(I-|BA^{-1}|)^{-1}\|.$

Needless to say, for $\overline{\gamma}$, we have

######  Corollary 2.2.

Let $\rho(|A^{-1}|)<1$ in _( 1.3)_. Then

$\overline{\gamma}\leq\|A^{-1}\|\|(I-|A^{-1}|)^{-1}\|.$

####  2.2.2 Case II

If $\sigma_{\min}(A)>\sigma_{\max}(B)$ in (1.1), then for $\overline{\alpha}$
we have Theorem 2.7.

######  Theorem 2.7.

Let $\sigma_{\min}(A)>\sigma_{\max}(B)$ in _( 1.1)_. Then

$\overline{\alpha}\leq\frac{1}{\sigma_{\min}(A)-\sigma_{\max}(B)}.$ (2.10)

######  Proof..

For any diagonal matrix $D=diag(d_{i})$ with $d_{i}\in[-1,1]$,

$\sigma_{\min}(A)-\sigma_{\max}(BD)\geq\sigma_{\min}(A)-\sigma_{\max}(B)\sigma_{\max}(D)\geq\sigma_{\min}(A)-\sigma_{\max}(B)$

and

$\sigma_{\min}(A-BD)\geq\sigma_{\min}(A)-\sigma_{\max}(BD).$

So

$\displaystyle\|(A-BD)^{-1}\|_{2}=$ $\displaystyle\sigma_{\max}((A-BD)^{-1})$
$\displaystyle=$ $\displaystyle\frac{1}{\sigma_{\min}(A-BD)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sigma_{\min}(A)-\sigma_{\max}(BD)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sigma_{\min}(A)-\sigma_{\max}(B)}.$

This completes the proof for Theorem 2.7. $\square$

For $\overline{\beta}$, we have the same as the result in Theorem 2.8.

######  Theorem 2.8.

Let $\sigma_{\min}(A)>\sigma_{\max}(B)$ in _( 1.2)_. Then

$\overline{\beta}\leq\frac{1}{\sigma_{\min}(A)-\sigma_{\max}(B)}.$

######  Corollary 2.3.

Let $\sigma_{\min}(A)>1$ in _( 1.3)_. Then

$\overline{\gamma}\leq\frac{1}{\sigma_{\min}(A)-1}.$

It is easy to see that the upper bound in Corollary 2.3 is still sharper than
that in Theorem 2.3, i.e.,

$\frac{1}{\sigma_{\min}(A)-1}\leq\frac{\|A+I\|_{2}+\|A-I\|_{2}}{\sigma_{\min}(A)^{2}-1},$

which is equal to

$\sigma_{\min}(A)+1\leq\|A+I\|_{2}+\|A-I\|_{2}.$

In fact, by using Proposition 2.1, we have

$1+\|A^{-1}\|_{2}\leq\|I+A^{-1}\|_{2}+\|I-A^{-1}\|_{2}\leq\|A^{-1}\|_{2}(\|A+I\|_{2}+\|A-I\|_{2}).$

######  Remark 2.2.

The conditions in Theorems 2.5 and 2.7 are not included each other, e.g.,
taking

$A=\left[\begin{array}[]{ccc}1&0\\\ 0&1\\\
\end{array}\right],B=\left[\begin{array}[]{ccc}0.9&-0.4\\\ 0.4&0.9\\\
\end{array}\right].$

By the simple computation,

$\sigma_{\min}(A)=1>\sigma_{\max}(B)=0.9849,$

but

$\rho(|A^{-1}B|)=1.3>1.$

This shows that matrices $A$ and $B$ satisfy the condition in Theorem 2.7, do
not satisfy the condition in Theorem 2.5. Now we take

$A=\left[\begin{array}[]{ccc}2&1\\\ 0&2\\\ \end{array}\right],\
B=\left[\begin{array}[]{ccc}1.6&0\\\ 0&1.6\\\ \end{array}\right].$

By the simple computation,

$\rho(|A^{-1}B|)=0.8000<1,$

but

$\sigma_{\min}(A)=1.5616<\sigma_{\max}(B)=1.6.$

This shows that matrices $A$ and $B$ satisfy the condition in Theorem 2.5, do
not satisfy the condition in Theorem 2.7.

####  2.2.3 Case III

Here, we consider this case that $B$ is nonsingular and
$\sigma_{max}(A^{-1}B)<1$ in (1.1). Based on this, for $\overline{\alpha}$ we
have Theorem 2.9.

######  Theorem 2.9.

Let $B$ be nonsingular and $\sigma_{max}(A^{-1}B)<1$ in _( 1.1)_. Then

$\overline{\alpha}\leq\frac{\|A^{-1}B\|_{2}\|B^{-1}\|_{2}}{1-\|A^{-1}B\|_{2}}.$
(2.11)

######  Proof..

From Corollary 3.2 in [7], $A+BD$ is nonsingular for any diagonal matrix
$D=diag(d_{i})$ with $d_{i}\in[-1,1]$ under the assumptions. So, we have

$\|(A-BD)^{-1}\|_{2}=\|(B^{-1}A-D)^{-1}B^{-1}\|_{2}\leq\|(B^{-1}A-D)^{-1}\|_{2}\|B^{-1}\|_{2}.$

Noting that $\sigma_{max}(A^{-1}B)<1$ is equal to $\|A^{-1}B\|_{2}<1$ and

$\|A^{-1}BD\|_{2}\leq\|A^{-1}B\|_{2}\|D\|_{2}<1.$

Making use of Banach perturbation lemma in [21] leads to

$\displaystyle\|(B^{-1}A-D)^{-1}\|_{2}\leq$
$\displaystyle\frac{\|A^{-1}B\|_{2}}{1-\|A^{-1}B\|_{2}\|D\|_{2}}\leq\frac{\|A^{-1}B\|_{2}}{1-\|A^{-1}B\|_{2}}.$

Therefore, the proof of Theorem 2.9 is completed. $\square$

For $\overline{\beta}$, we have

######  Theorem 2.10.

Let $B$ be nonsingular and $\sigma_{max}(BA^{-1})<1$ in _( 1.2)_. Then

$\overline{\beta}\leq\frac{\|B^{-1}\|_{2}\|BA^{-1}\|_{2}}{1-\|BA^{-1}\|_{2}}.$

######  Corollary 2.4.

Let $\sigma_{max}(A^{-1})<1$ in _( 1.3)_. Then

$\overline{\gamma}\leq\frac{\|A^{-1}\|_{2}}{1-\|A^{-1}\|_{2}}.$

Usually, Corollary 2.4 is equal to Corollary 2.3.

######  Remark 2.3.

Comparing Theorem 2.7 with Theorem 2.9, it is easy to find that

$\sigma_{max}(A^{-1}B)\leq\sigma_{max}(A^{-1})\sigma_{max}(B)=\frac{\sigma_{max}(B)}{\sigma_{min}(A)}.$

Whereas, it does not show that Theorem 2.9 is weaker than Theorem 2.7 because
Theorem 2.9 asks for $B$ being nonsingular. Besides, we need to point out that
Theorem 2.9 sometimes performs better than Theorem 2.7, vice versa. To
illustrate this, we take

$A=\left[\begin{array}[]{ccc}2&0\\\ 0&3\\\ \end{array}\right],\
B=\left[\begin{array}[]{ccc}1&0\\\ 0&1.5\\\ \end{array}\right].$

Obviously, $B$ is nonsingular,

$\sigma_{max}(A^{-1}B)=0.5<1,\sigma_{min}(A)=2>\sigma_{max}(B)=1.5.$

This shows that the conditions in Theorem 2.7 with Theorem 2.9 are satisfied.
From Theorem 2.7 and Theorem 2.9, we have

$\frac{\|A^{-1}B\|_{2}\|B^{-1}\|_{2}}{1-\|A^{-1}B\|_{2}}=1<\frac{1}{\sigma_{min}(A)-\sigma_{\max}(B)}=2,$

from which shows that the upper bound in Theorem 2.9 is sharper than that in
Theorem 2.7. Now, we take

$A=\left[\begin{array}[]{ccc}2&0\\\ 0&3\\\ \end{array}\right],\
B=\left[\begin{array}[]{ccc}1.5&0\\\ 0&1\\\ \end{array}\right].$

Likewise, $B$ is nonsingular,

$\sigma_{max}(A^{-1}B)=0.75<1,\sigma_{min}(A)=2>\sigma_{max}(B)=1.5.$

This implies that the conditions in Theorem 2.7 with Theorem 2.9 are satisfied
as well. From Theorem 2.7 and Theorem 2.9, we have

$\frac{\|A^{-1}B\|_{2}\|B^{-1}\|_{2}}{1-\|A^{-1}B\|_{2}}=5>\frac{1}{\sigma_{min}(A)-\sigma_{\max}(B)}=2,$

which implies that the upper bound in Theorem 2.7 is sharper than that in
Theorem 2.9.

######  Remark 2.4.

Although in [39] Zamani and Hladík presented some estimations for
$\overline{\gamma}$, their results are either impossible to achieve or
difficult to calculate, see Theorem 8 and Proposition 11 in [39],
respectively.

##  3 Perturbation bound

In this section, we focus on the perturbation analysis of AVEs when $A,B$ and
$b$ are perturbed. For instance, for the AVEs (1.1), when $\Delta A$, $\Delta
B$ and $\Delta b$ are the perturbation terms of $A$, $B$ and $b$,
respectively, how do we characterize the change in the solution of the
following perturbed AVEs (3.1)

$(A+\Delta A)y-(B+\Delta B)|y|=b+\Delta b.$ (3.1)

For the AVEs (1.1), firstly, we consider the following special case

$Ay-B|y|=b+\Delta b.$ (3.2)

Assume that the AVEs (3.2) has the unique solution $y^{\ast}$. Let $x^{\ast}$
be the unique solution of AVEs (1.1). Subtracting (1.1) from (3.2), we have

$Ax^{\ast}-B|x^{\ast}|-(Ay^{\ast}-B|y^{\ast}|)=-\Delta b,$

which is equal to

$x^{\ast}-y^{\ast}=-(A-B\tilde{D})^{-1}\Delta b,$ (3.3)

where $\tilde{D}=diag(\tilde{d}_{i})$ with $\tilde{d}_{i}\in[-1,1]$. Making
use of the norm for both sides of (3.3), noting that

$\|(A-B\tilde{D})^{-1}\|\leq\max\|(A-BD)^{-1}\|$ (3.4)

for any $D=diag(d_{i})$ with $d_{i}\in[-1,1]$, we have

$\|x^{\ast}-y^{\ast}\|\leq\max\|(A-BD)^{-1}\|\|\Delta b\|.$ (3.5)

Moreover, from the AVEs (1.1) with $x^{\ast}$, it is easy to check that

$\frac{\|b\|}{\|x^{\ast}\|}\leq\|A\|+\|B\|.$ (3.6)

Combining (3.5) with (3.6), for any $D=diag(d_{i})$ with $d_{i}\in[-1,1]$, we
obtain

$\displaystyle\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq$
$\displaystyle\frac{\max\|(A-BD)^{-1}\|\|\Delta
b\|}{\|x^{\ast}\|}=\frac{\max\|(A-BD)^{-1}\|\|\Delta
b\|}{\|b\|}\frac{\|b\|}{\|x^{\ast}\|}$ $\displaystyle\leq$
$\displaystyle\frac{\max\|(A-BD)^{-1}\|\|\Delta b\|}{\|b\|}(\|A\|+\|B\|),$

from which we immediately get

######  Theorem 3.1.

Let $x^{\ast}$, $y^{\ast}$ be the unique solutions of AVEs (1.1) and (3.2),
respectively. Then

$\displaystyle\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{\overline{\alpha}\|\Delta
b\|}{\|b\|}(\|A\|+\|B\|),$

where $\overline{\alpha}$ is defined in Theorem 2.1.

Similarly, we assume that $y^{\ast}$ is the unique solution of AVEs (3.1). The
following theorem is the framework of AVEs (1.1) perturbation.

######  Theorem 3.2.

Let $x^{\ast}$, $y^{\ast}$ be the unique solutions of AVEs (1.1) and (3.1),
respectively. Then

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\mu_{1}\bigg{(}\frac{\|\Delta
b\|}{\|b\|}(\|A\|+\|B\|)+\|\Delta A\|+\|\Delta B\|\bigg{)}.$ (3.7)

where

$\mu_{1}=\max\\{\|(A-BD+(\Delta A-\Delta BD))^{-1}\|:D=diag(d_{i})\
\mbox{with}\ d_{i}\in[-1,1]\\}.$

######  Proof..

Based on the assumptions, the AVEs (1.1) is equal to

$(A+\Delta A)x^{\ast}-(B+\Delta B)|x^{\ast}|=b+\Delta Ax^{\ast}-\Delta
B|x^{\ast}|.$ (3.8)

Subtracting (3.8) from (3.1) with $y^{\ast}$, we have

$(A-B\tilde{D}+(\Delta A-\Delta B\tilde{D}))(x^{\ast}-y^{\ast})=-\Delta
b+\Delta Ax^{\ast}-\Delta B|x^{\ast}|,$ (3.9)

where $\tilde{D}=diag(\tilde{d}_{i})$ with $\tilde{d}_{i}\in[-1,1]$. Using the
norm for (3.9), similar to (3.4), results in

$\|x^{\ast}-y^{\ast}\|\leq\mu_{1}(\|\Delta b\|+(\|\Delta A\|+\|\Delta
B\|)\|x^{\ast}\|).$ (3.10)

By making use of (3.10) and (3.6), the desired bound (3.7) can be obtained.
$\square$

######  Remark 3.1.

Here, a special case is considered, i.e, when $B=0$ in (1.1), the AVEs (1.1)
reduces to the linear systems

$Ax=b.$

It is not difficult to find that from Theorem 3.2 we easily obtain a classical
perturbation bound for the linear systems $Ax=b$, i.e.,

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{\kappa(A)}{1-\frac{\kappa(A)\|\Delta
A\|}{\|A\|}}\Bigg{(}\frac{\|\Delta b\|}{\|b\|}+\frac{\|\Delta
A\|}{\|A\|}\Bigg{)}$

for $\|A^{-1}\|\|\Delta A\|<1$, where $\kappa(A)=\|A^{-1}\|\|A\|$, see Theorem
1.3 in numerical linear algebra textbooks [26].

In addition, when $|\Delta A|\leq\epsilon|A|$, $|\Delta B|\leq\epsilon|B|$ and
$|\Delta b|\leq\epsilon|b|$, we have

######  Theorem 3.3.

Let $x^{\ast}$, $y^{\ast}$ be the unique solutions of AVEs (1.1) and (3.1),
respectively. Assume that $|\Delta A|\leq\epsilon|A|$, $|\Delta
B|\leq\epsilon|B|$ and $|\Delta b|\leq\epsilon|b|$. Then

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{\epsilon\|\mu_{2}(|b|+(|A|+|B|)|x^{\ast}|)\|}{(1-\epsilon\|\mu_{2}(|A|+|B|)\|)\|x^{\ast}\|},$
(3.11)

where $\epsilon\|\mu_{2}(|A|+|B|)\|<1$ with

$\mu_{2}=\max\\{|(A-BD)^{-1}|:D=diag(d_{i})\ \mbox{with}\ d_{i}\in[-1,1]\\}.$

######  Proof..

From (3.9), we have

$x^{\ast}-y^{\ast}=(A-B\tilde{D})^{-1}(-(\Delta A-\Delta
B\tilde{D})(x^{\ast}-y^{\ast})-\Delta b+\Delta Ax^{\ast}-\Delta B|x^{\ast}|),$

and so

$\displaystyle|x^{\ast}-y^{\ast}|=$
$\displaystyle|(A-B\tilde{D})^{-1}(-(\Delta A-\Delta
B\tilde{D})(x^{\ast}-y^{\ast})-\Delta b+\Delta Ax^{\ast}-\Delta B|x^{\ast}|)|$
$\displaystyle\leq$ $\displaystyle|(A-B\tilde{D})^{-1}||(\Delta A-\Delta
B\tilde{D})(x^{\ast}-y^{\ast})|+|(A-B\tilde{D})^{-1}|(|\Delta b|+|\Delta
Ax^{\ast}|+|\Delta B|x^{\ast}||)$ $\displaystyle\leq$
$\displaystyle\epsilon|(A-B\tilde{D})^{-1}|(|A|+|B|)|x^{\ast}-y^{\ast}|+\epsilon|(A-B\tilde{D})^{-1}|(|b|+(|A|+|B|)|x^{\ast}|)$
$\displaystyle\leq$
$\displaystyle\epsilon\mu_{2}(|A|+|B|)|x^{\ast}-y^{\ast}|+\epsilon\mu_{2}(|b|+(|A|+|B|)|x^{\ast}|).$

Hence,

$\|x^{\ast}-y^{\ast}\|\leq\epsilon\|\mu_{2}(|A|+|B|)\|\|x^{\ast}-y^{\ast}\|+\epsilon\|\mu_{2}(|b|+(|A|+|B|)|x^{\ast}|)\|,$

from which we obtain the desired bound (3.11). $\square$

######  Remark 3.2.

Similar to Remark 3.1, when $B=0$ in (1.1), Theorem 3.3 reduces to another
classical perturbation bound for the linear systems $Ax=b$, i.e.,

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{\epsilon\||A^{-1}|(|b|+|A||x^{\ast}|)\|}{(1-\epsilon\||A^{-1}||A|\|)\|x^{\ast}\|}$

where $\epsilon\||A^{-1}||A|\|<1$, see Theorem 2.1 [27] and Theorem 1.1 in
[28].

Noting that $|(I-A^{-1}BD)^{-1}|\leq(I-|A^{-1}B|)^{-1}$ for
$\rho(|A^{-1}B|)<1$ from Theorem 2.5, together with Theorem 3.3, Theorem 3.4
is obtained and its advantage successfully avoids any diagonal matrix
$D=diag(d_{i})$ with $d_{i}\in[-1,1]$.

######  Theorem 3.4.

Let $x^{\ast}$, $y^{\ast}$ be the unique solutions of AVEs (1.1) and (3.1),
respectively. Assume that $|\Delta A|\leq\epsilon|A|$, $|\Delta
B|\leq\epsilon|B|$, $|\Delta b|\leq\epsilon|b|$ and $\rho(|A^{-1}B|)<1$. Then

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{\epsilon\|(I-|A^{-1}B|)^{-1}|A^{-1}|(|b|+(|A|+|B|)|x^{\ast}|)\|}{(1-\epsilon\|(I-|A^{-1}B|)^{-1}|A^{-1}|(|A|+|B|)\|)\|x^{\ast}\|},$
(3.12)

where $\epsilon\|(I-|A^{-1}B|)^{-1}|A^{-1}|(|A|+|B|)\|<1$.

######  Remark 3.3.

Making use of “$DB$” and/or “$D\Delta B$” instead of “$BD$” and/or “$\Delta
BD$” in Theorems 3.1, 3.2 and 3.3 directly, some perturbation bounds for the
AVEs (1.2) can be obtained. Of course, by using the simple modifications for
Theorem 3.4, its modified vesion is suit for the AVEs (1.2) as well, which is
omitted.

######  Remark 3.4.

It is easy to see that $B=I$ and/or $\Delta B=0$ in Theorems 3.1-3.4, some
perturbation bounds for the AVEs (1.3) can be obtained as well.

######  Remark 3.5.

By directly making use of the results in the Section 2.2, naturally, we can
present some computable upper bounds for $\overline{\alpha}$ in Theorem 3.1
and $\mu_{1}$ in Theorem 3.2.

##  4 Application in HLCP

In this section, by making use of the AVEs (1.1), we can derive some error
bounds and perturbation bounds for the HLCP. Coincidentally, two new
equivalent forms about the error bounds for LCP are given. Without constraint
conditions, a new perturbation bound for LCP is obtained, compared with
Theorem 3.1 in [33].

As is known, the horizontal linear complementarity problem is to determine a
pair of vectors $w,z$ in $\mathbb{R}^{n}$ such that

$Mz-Nw=q,z\geq 0,w\geq 0,z^{T}w=0,$ (4.1)

where $M,N\in\mathbb{R}^{n\times n}$ and $q\in\mathbb{R}^{n}$, respectively,
are given known matrices and the vector, which is denoted by HLCP and comes
from the well-known book [29] by Cottle et al. Clearly, when $N=I$, the HLCP
(4.1) reduces to the well-known LCP.

###  4.1 Error bound for HLCP

In this subsection, we will discuss the error bound for HLCP. Our approach is
to display the HLCP (4.1) in the form of absolute value equations to study the
error bound for HLCP. For this goal, we take $w=\frac{|x|-x}{2}$ and
$z=\frac{|x|+x}{2}$ for (4.1). Under this transformation, the HLCP (4.1) is
equally converted to the following absolute value equations

$\frac{M+N}{2}x-\frac{N-M}{2}|x|=q.$ (4.2)

Obviously, to gain the error bound for the HLCP (4.1) is equivalent to gain
the error bound for the AVEs (4.2). That is to say, we can discuss the error
bound for the HLCP (4.1) from the point of absolute value equations. This
approach is completely different from the published work in [30].

To help our discussion, the following definition and lemma are required.

######  Definition 4.1.

[31] Matrix $H=\\{M,N\\}$ has the column $\mathcal{W}$-property if the
determinants of all column representative matrices of $H=\\{M,N\\}$ are all
positive or all negative.

By using Theorem 2 (b) in [31], Lemma 4.1 can be obtained, its proof is
omitted.

######  Lemma 4.1.

Matrix $H=\\{M,N\\}$ has the column $\mathcal{W}$-property if and only if
$M(I-T)+NT$ is nonsingular for any nonnegative diagonal matrix
$T=\mbox{diag}(t)$ with $t\in[0,1]^{n}$.

######  Remark 4.1.

Gabriel and Moré in [37] proved that $A$ is a $P$-matrix if and only if
$A+T(I-A)$ is nonsingular for any nonnegative diagonal matrix
$T=\mbox{diag}(t)$ with $t\in[0,1]^{n}$. Clearly, Lemma 4.1 is a
generalization of their result.

From Theorem 2 in [31], we know that the HLCP (4.1) has the unique solution
for $H$ having the column $\mathcal{W}$-property. Without loss of generality,
we always assume that the block matrix $H$ satisfies the conditions of Lemma
4.1 such that the HLCP (4.1) has the unique solution $(w^{\ast},z^{\ast})$. In
this case, the corresponding $x^{\ast}$ ($x^{\ast}=z^{\ast}-w^{\ast}$) is the
unique solution of the AVEs (4.2).

Let

$r_{h}(x)=\frac{M+N}{2}x-\frac{N-M}{2}|x|-q.$

By making use of Theorem 2.1 directly and the simple passages, we present the
error bounds for the HLCP (4.1), see Theorem 4.1.

######  Theorem 4.1.

Let $x^{*}$ be the unique solution of AVEs (4.2). Then for any
$x\in\mathbb{R}^{n}$,

$\frac{1}{H_{l}}\|r_{h}(x)\|\leq\|x-x^{\ast}\|\leq H_{u}\|r_{h}(x)\|,$ (4.3)

where

$H_{l}=\max\bigg{\\{}\bigg{\|}\frac{M+N}{2}-\frac{N-M}{2}D\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}}$

and

$H_{u}=\max\bigg{\\{}\bigg{\|}\bigg{(}\frac{M+N}{2}-\frac{N-M}{2}D\bigg{)}^{-1}\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}},$

which is equal to

$\frac{1}{\bar{H}_{l}}\|r_{h}(x)\|\leq\|x-x^{\ast}\|\leq\bar{H}_{u}\|r_{h}(x)\|,$
(4.4)

with

$\bar{H}_{l}=\max\\{\|N(I-\Lambda)+M\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$

and

$\bar{H}_{u}=\max\\{\|(N(I-\Lambda)+M\Lambda)^{-1}\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

It is well known that, if $N$ is nonsingular in (4.1), the HLCP can be
equivalently written as the LCP

$w=N^{-1}Mz-N^{-1}q,z\geq 0,w\geq 0,z^{T}w=0.$

If we apply the error bounds of Eq. (2.3) on page 516 in [30] to such LCP,
then we directly obtain

$\frac{1}{C_{l}}\|r(x)\|\leq\|x-x^{\ast}\|\leq C_{u}\|r(x)\|,$ (4.5)

where

$C_{l}=\max\\{\|I-\Lambda+\Lambda
N^{-1}M\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$

and

$C_{u}=\max\\{\|(I-\Lambda+\Lambda
N^{-1}M)^{-1}\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

Comparing (4.4) with (4.5), the advantages of the former are obvious. Firstly,
the former does not need that $N$ must be nonsingular matrix. Secondly, when
using the latter for calculating the error bounds, the inverse of matrix $N$
has to address. Whereas, the former successfully prevent this form happening.

By making use of Theorems 2.5, 2.7 and 2.9, some computable estimates for
$H_{u}$ or $\bar{H}_{u}$ are obtained off-hand, see Corollary 4.1.

######  Corollary 4.1.

Let $A=\frac{M+N}{2}$ and $B=\frac{N-M}{2}$. The following statements hold:

$(i)$ Let $\rho(|A^{-1}B|)<1$. Then

$H_{u}=\bar{H}_{u}\leq\|(I-|A^{-1}B|)^{-1}\|\|A^{-1}\|.$ (4.6)

$(ii)$ Let $\sigma_{\min}(A)>\sigma_{\max}(B)$. Then

$H_{u}=\bar{H}_{u}\leq\frac{1}{\sigma_{\min}(A)-\sigma_{\max}(B)}.$ (4.7)

$(iii)$ Let $\sigma_{max}(A^{-1}B)<1$. Then

$H_{u}=\bar{H}_{u}\leq\frac{\|A^{-1}B\|_{2}\|B^{-1}\|_{2}}{1-\|A^{-1}B\|_{2}}.$
(4.8)

Naturally, for $N=I$ in (4.2), combining Theorem 4.1 with Corollary 4.1, we
immediately obtain the error bounds for LCP, see Corollary 4.2.

######  Corollary 4.2.

Let $x^{*}$ be the unique solution of AVEs (4.2) with $N=I$. Then for any
$x\in\mathbb{R}^{n}$,

$\frac{1}{L_{l}}\|r_{h}(x)\|\leq\|x-x^{\ast}\|\leq L_{u}\|r_{h}(x)\|,$ (4.9)

where

$L_{l}=\max\bigg{\\{}\bigg{\|}\frac{M+I}{2}-\frac{I-M}{2}D\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}}$

and

$L_{u}=\max\bigg{\\{}\bigg{\|}\bigg{(}\frac{M+I}{2}-\frac{I-M}{2}D\bigg{)}^{-1}\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}},$

which is equal to

$\frac{1}{\bar{L}_{l}}\|r_{h}(x)\|\leq\|x-x^{\ast}\|\leq\bar{L}_{u}\|r_{h}(x)\|,$
(4.10)

with

$\bar{L}_{l}=\max\\{\|I-\Lambda+M\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$

and

$\bar{L}_{u}=\max\\{\|(I-\Lambda+M\Lambda)^{-1}\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

Further, let $\bar{A}=\frac{M+I}{2}$ and $\bar{B}=\frac{I-M}{2}$. The
following statements hold:

$(i)$ Let $\rho(|\bar{A}^{-1}\bar{B}|)<1$. Then

$\bar{L}_{u}=L_{u}\leq\|(I-|\bar{A}^{-1}\bar{B}|)^{-1}\|\|\bar{A}^{-1}\|.$
(4.11)

$(ii)$ Let $\sigma_{\min}(\bar{A})>\sigma_{\max}(\bar{B})$. Then

$\bar{L}_{u}=L_{u}\leq\frac{1}{\sigma_{\min}(\bar{A})-\sigma_{\max}(\bar{B})}.$
(4.12)

$(iii)$ Let $\sigma_{max}(\bar{A}^{-1}\bar{B})<1$. Then

$\bar{L}_{u}=L_{u}\leq\frac{\|\bar{A}^{-1}\bar{B}\|_{2}\|\bar{B}^{-1}\|_{2}}{1-\|\bar{A}^{-1}\bar{B}\|_{2}}.$
(4.13)

######  Remark 4.2.

Based on Theorem 2.1 in [32], the lower and upper error bounds in (4.10) are
the same as that in (2.3) on page 516 in [30]. In addition, their new equal
form, i.e., (4.9), is exploited as well. Moreover, from (4.9), we present some
estimates of the upper bounds for three cases: (1)
$\rho(|\bar{A}^{-1}\bar{B}|)<1$; (2)
$\sigma_{\min}(\bar{A})>\sigma_{\max}(\bar{B})$; (3)
$\sigma_{max}(\bar{A}^{-1}\bar{B})<1$, where $\bar{A}=\frac{M+I}{2}$ and
$\bar{B}=\frac{I-M}{2}$. These estimates are not limited by the special type
of matrix.

Since in theory it is difficult to compare the upper bounds in Corollary 4.2
and Theorem 2.1 in [30], here, we can adopt some numerical examples to
investigate the upper bounds in Corollary 4.2 and Theorem 2.1 in [30]. For the
sake of simplicity, we only list a simple example, see Example 4.1.

Example 4.1 Let

$M=\left[\begin{array}[]{ccc}1&-0.5\\\ 0.5&1\end{array}\right].$

Obviously, $M$ is an $H_{+}$-matrix. By the simple computations, from Theorem
2.1 in [30], we get

$\|\langle M\rangle^{-1}\max\\{D_{M},I\\}\|_{2}=2,$

where $D_{M}$ denotes the diagonal part of $M$.

From Corollary 4.2 (i), we get

$\rho(|\bar{A}^{-1}\bar{B}|)=0.2941<1,\ \mbox{and}\
\|(I-|\bar{A}^{-1}\bar{B}|)^{-1}\|_{2}\|\bar{A}^{-1}\|_{2}=1.3744<2.$

From Corollary 4.2 (ii), we get

$\sigma_{\min}(\bar{A})=1.0308>\sigma_{\max}(\bar{B})=0.2500,\ \mbox{and}\
\frac{1}{\sigma_{\min}(\bar{A})-\sigma_{\max}(\bar{B})}=1.2808<2.$

From Corollary 4.2 (iii), we get

$\sigma_{max}(\bar{A}^{-1}\bar{B})=0.2425,\ \mbox{and}\
\frac{\|\bar{A}^{-1}\bar{B}\|_{2}\|\bar{B}^{-1}\|_{2}}{1-\|\bar{A}^{-1}\bar{B}\|_{2}}=1.2807<2.$

The above results imply that (i), (ii) and (iii) in Corollary 4.2 are sharper
than that in Theorem 2.1 in [30] under proper conditions. This implies that
our presented bounds, (i), (ii) and (iii) in Corollary 4.2, are meaningful in
a way, and may advantage over that in Theorem 2.1 in [30] under certain
conditions.

###  4.2 Perturbation bound for HLCP

In this subsection, we fasten on the perturbation analysis of the HLCP (4.1)
when $M,N$ and $q$ are perturbed to $M+\Delta M,N+\Delta N$ and $q+\Delta q$,
respectively. In this case, the perturbed HLCP is to find a pair of vectors
$s,t$ in $\mathbb{R}^{n}$ such that

$(M+\Delta M)s-(N+\Delta N)t=q+\Delta q,s\geq 0,t\geq 0,s^{T}t=0.$ (4.14)

Assume that $\\{M+\Delta M,N+\Delta N\\}$ satisfies the conditions of Lemma
4.1 such that the perturbed HLCP (4.14) has the unique solution.

Let

$t=\frac{|y|-y}{2}\ \mbox{and}\ s=\frac{|y|+y}{2}.$

Then the perturbed HLCP (4.14) is equally transformed into the following
absolute value equations

$\frac{M+N+\Delta M+\Delta N}{2}y-\frac{N-M+\Delta N-\Delta M}{2}|y|=q+\Delta
q.$ (4.15)

By making use of Theorem 3.2 directly and the simple passages, together with
Theorems 2.5, 2.7 and 2.9, and

$\frac{\|q\|}{\|x\|}\leq\frac{1}{2}(\|M+N\|+\|M-N\|),$

we present the perturbation bound for the HLCP (4.1), see Theorem 4.2.

######  Theorem 4.2.

Let $x^{\ast}$, $y^{\ast}$ be the unique solutions of AVEs (4.2) and (4.15),
respectively. Then

$\displaystyle\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}$
$\displaystyle\leq\overline{\alpha}_{r}\bigg{(}\frac{\|\Delta
q\|}{\|q\|}\bigg{(}\frac{\|M+N\|+\|M-N\|}{2}\bigg{)}+\frac{\|\Delta M+\Delta
N\|+\|\Delta M-\Delta N\|}{2}\bigg{)}$

with

$\small{\overline{\alpha}_{r}=\max\bigg{\\{}\bigg{\|}\bigg{(}\frac{(M+\Delta
M)(I+D)+(N+\Delta
N)(I-D)}{2}\bigg{)}^{-1}\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}}}$

or

$\overline{\alpha}_{r}=\max\\{\|((N+\Delta N)(I-\Lambda)+(M+\Delta
M)\Lambda)^{-1}\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

Moreover, let $\hat{A}=\frac{M+N+\Delta M+\Delta N}{2}$ and
$\hat{B}=\frac{N-M+\Delta N-\Delta M}{2}$. The following statements hold:

$(i)$ Let $\rho(|\hat{A}^{-1}\hat{B}|)<1$. Then

$\overline{\alpha}_{r}\leq\|(I-|\hat{A}^{-1}\hat{B}|)^{-1}\|\|\hat{A}^{-1}\|.$
(4.16)

$(ii)$ Let $\sigma_{\min}(\hat{A})>\sigma_{\max}(\hat{B})$. Then

$\overline{\alpha}_{r}\leq\frac{1}{\sigma_{\min}(\hat{A})-\sigma_{\max}(\hat{B})}.$
(4.17)

$(iii)$ Let $\sigma_{\max}(\hat{A}^{-1}\hat{B})<1$. Then

$\overline{\alpha}_{r}\leq\frac{\|\hat{A}^{-1}\hat{B}\|_{2}\|\hat{B}^{-1}\|_{2}}{1-\|\hat{A}^{-1}\hat{B}\|_{2}}.$
(4.18)

When $N=I$ and $\Delta N=0$ in Theorem 4.2, we immediately obtain the
corresponding perturbation bound for LCP, see Corollary 4.3.

######  Corollary 4.3.

Let $N=I$ and $\Delta N=0$ in Theorem 4.2, and $x^{\ast}$, $y^{\ast}$ be the
unique solutions of AVEs (4.2) and (4.12), respectively. Then

$\displaystyle\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}$
$\displaystyle\leq\overline{\alpha}_{l}\bigg{(}\frac{\|\Delta
q\|}{\|q\|}\bigg{(}\frac{\|M+I\|+\|M-I\|}{2}\bigg{)}+2\|\Delta M\|\bigg{)}$

with

$\overline{\alpha}_{l}=\max\bigg{\\{}\bigg{\|}\bigg{(}\frac{M+I+\Delta
M}{2}-\frac{I-M-\Delta
M}{2}D\bigg{)}^{-1}\bigg{\|}:D=diag(d_{i})~{}\mbox{with}~{}d_{i}\in[-1,1]\bigg{\\}}$

or

$\overline{\alpha}_{l}=\max\\{\|(I-\Lambda+(M+\Delta
M)\Lambda)^{-1}\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

Moreover, let $\tilde{A}=\frac{M+I+\Delta M}{2}$ and
$\tilde{B}=\frac{I-M-\Delta M}{2}$. The following statements hold:

$(i)$ Let $\rho(|\tilde{A}^{-1}\tilde{B}|)<1$. Then

$\overline{\alpha}_{l}\leq\|(I-|\tilde{A}^{-1}\tilde{B}|)^{-1}\|\|\tilde{A}^{-1}\|.$
(4.19)

$(ii)$ Let $\sigma_{\min}(\tilde{A})>\sigma_{\max}(\tilde{B})$. Then

$\overline{\alpha}_{l}\leq\frac{1}{\sigma_{\min}(\tilde{A})-\sigma_{\max}(\tilde{B})}.$
(4.20)

$(iii)$ Let $\sigma_{\max}(\tilde{A}^{-1}\tilde{B})<1$. Then

$\overline{\alpha}_{l}\leq\frac{\|\tilde{A}^{-1}\tilde{B}\|_{2}\|\tilde{B}^{-1}\|_{2}}{1-\|\tilde{A}^{-1}\tilde{B}\|_{2}}.$
(4.21)

Comparing Corollary 4.3 with Theorem 3.1 in [33] (also see Theorem 4.3 in the
following Section 4.3), the perturbation bound in Corollary 4.3 is more
general. Not only that, our perturbation bound unlike Theorem 3.1 in [33] here
does not subject to certain conditions. In a way, this new perturbation bound
for the LCP perfects the work in [33]. In particular, these computable
estimates of the upper bound in Corollary 4.3 are not limited by the special
type of matrix.

###  4.3 A new approach for the existing perturbation bounds of LCP

The approach of the above results gained in the Sections 4.1 and 4.2 is to
that the HLCP is equally transformed into the corresponding absolute value
equations by making use of change of variable. As is known, for the LCP,
without making use of change of variable, it is also transformed into a
certain absolute value equations by the fact that

$w=Mz+q,z\geq 0,w\geq 0,z^{T}w=0\Leftrightarrow\min\\{z,Mz+q\\}=0,$

see [30, 36]. Noting that

$\min\\{a,b\\}=\frac{1}{2}(a+b-|a-b|)\ \forall a,b\in\mathbb{R}^{n},$

obviously, the LCP $(M,q)$ is equal to the following absolute value equations

$\frac{1}{2}((M+I)z+q)=\frac{1}{2}|(M-I)z+q|.$ (4.22)

In fact, by making use of the AVEs (4.22), we also obtain Theorem 2.8 and
Theorem 3.1 in [33]. To achieve this goal, without loss of generality, we
consider the relationship between the solution of the LCP$(A,b)$ and the
solution of LCP$(B,c)$. Assume that $x^{\ast}$ and $y^{\ast}$ are the unique
solutions of the LCP$(A,b)$ and the LCP$(B,c)$, respectively. Then

$\frac{1}{2}((A+I)x^{\ast}+b)=\frac{1}{2}|(A-I)x^{\ast}+b|$ (4.23)

and

$\frac{1}{2}((B+I)y^{\ast}+c)=\frac{1}{2}|(B-I)y^{\ast}+c|.$ (4.24)

Combining (4.23) with (4.24), by the simple passages, we have

$\frac{I+\tilde{D}+(I-\tilde{D})A}{2}(x^{\ast}-y^{\ast})=-\frac{(I-\tilde{D})(A-B)}{2}y^{\ast}-\frac{(I-\tilde{D})(b-c)}{2},$

where $\tilde{D}=diag(\tilde{d}_{i})$ with $\tilde{d}_{i}\in[-1,1]$, which is
equal to

$(I-\tilde{\Lambda}+\tilde{\Lambda}A)(x^{\ast}-y^{\ast})=-\tilde{\Lambda}(A-B)y^{\ast}-\tilde{\Lambda}(b-c),$
(4.25)

where $\tilde{\Lambda}=\frac{I-\tilde{D}}{2}=diag(\tilde{\lambda}_{i})$ with
$\tilde{\lambda}_{i}\in[0,1]$. From (4.25), we have

$\displaystyle\|x^{\ast}-y^{\ast}\|=$
$\displaystyle\|(I-\tilde{\Lambda}+\tilde{\Lambda}A)^{-1}\tilde{\Lambda}((A-B)y^{\ast}+b-c)\|$
$\displaystyle\leq$
$\displaystyle\|(I-\tilde{\Lambda}+\tilde{\Lambda}A)^{-1}\tilde{\Lambda}\|\|(A-B)y^{\ast}+b-c\|$
$\displaystyle\leq$
$\displaystyle\|(I-\tilde{\Lambda}+\tilde{\Lambda}A)^{-1}\tilde{\Lambda}\|(\|A-B\|\|y^{\ast}\|+\|b-c\|)$
$\displaystyle\leq$ $\displaystyle\beta(A)(\|A-B\|\|y^{\ast}\|+\|b-c\|),$
(4.26)

where $\beta(A)=\max\\{\|(I-\Lambda+\Lambda
A)^{-1}\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$,
or

$\displaystyle\|x^{\ast}-y^{\ast}\|\leq$
$\displaystyle\beta(B)(\|A-B\|\|x^{\ast}\|+\|b-c\|),$ (4.27)

where $\beta(B)=\max\\{\|(I-\Lambda+\Lambda
B)^{-1}\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$.

Noting that 0 is the solution of LCP$(B,c_{+})$, repeating the above process,
we obtain

$\|y^{\ast}\|\leq\beta(B)\|(-c)_{+}\|.$ (4.28)

Furthermore, from $Ax^{\ast}+b\geq 0$, we obtain
$(-b)_{+}\leq(Ax^{\ast})_{+}\leq|Ax|$, which implies that

$\frac{1}{\|x^{\ast}\|}\leq\frac{\|A\|}{\|(-b)_{+}\|}.$ (4.29)

Hence, combining (4.3), (4.27), (4.28) with (4.29), we have

######  Lemma 4.2.

Assume that $x^{\ast}$ and $y^{\ast}$ are the unique solutions of the
LCP$(A,b)$ and the LCP$(B,c)$, respectively. Let

$\beta(A)=\max\\{\|(I-\Lambda+\Lambda
A)^{-1}\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}$

and

$\beta(B)=\max\\{\|(I-\Lambda+\Lambda
B)^{-1}\Lambda\|:\Lambda=diag(\lambda_{i})~{}\mbox{with}~{}\lambda_{i}\in[0,1]\\}.$

Then

$\|x^{\ast}-y^{\ast}\|\leq\beta(A)(\beta(B)\|A-B\|\|(-c)_{+}\|+\|b-c\|)$

and

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\beta(B)(\|A-B\|+\frac{\|b-c\|\|A\|}{\|(-b)_{+}\|}).$

Let

$\mathcal{M}:=\\{A|\beta(M)\|M-A\|\leq\eta<1\\}.$ (4.30)

Then for any $A\in\mathcal{M}$, we have

$\beta(A)\leq\alpha(M)=\frac{1}{1-\eta}\beta(M),$ (4.31)

see [33]. Together with Lemma 4.2, Theorem 4.3 can be obtained, i.e., Theorems
2.8 and 3.1 in [33].

######  Theorem 4.3.

(Theorems 2.8 and 3.1 in [33]) Assume that $x^{\ast}$ and $y^{\ast}$ are the
unique solutions of the LCP$(A,b)$ and the LCP$(B,c)$, respectively. Then for
any $A,B\in\mathcal{M}$, where $\mathcal{M}$ is defined as in (4.30),

$\|x^{\ast}-y^{\ast}\|\leq\alpha(M)^{2}\|A-B\|\|(-c)_{+}\|+\alpha(M)\|b-c\|,$

where $\alpha(M)$ is defined as in (4.31). Further, let $A=M$, $B=M+\Delta M$,
$b=q$, $c=q+\Delta q$ with $\|\Delta M\|\leq\epsilon\|M\|$ and $\|\Delta
q\|\leq\epsilon\|(-q)_{+}\|$, $\epsilon\beta(M)\|M\|=\delta<1$. Then

$\frac{\|x^{\ast}-y^{\ast}\|}{\|x^{\ast}\|}\leq\frac{2\delta}{1-\delta}.$

Similarly, here we compare Corollary 4.3 with Theorem 4.3 by a simple example.
For the sake of convenience, we consider two cases that $M$ is a symmetric
positive definite matrix, and also is an $H_{+}$-matrix. In this case, it’s
going to be converted to compare Corollary 3.2 (i) and (ii) in [33] with
Corollary 4.3. Specifically, see Example 4.2.

Example 4.2 Assume that $\epsilon$ is a sufficiently small positive number.
Let

$M=\left[\begin{array}[]{ccc}1.5&0\\\
0&1.5\end{array}\right],q=\left[\begin{array}[]{ccc}-1\\\
2\sqrt{6}\end{array}\right].$

Obviously, $M$ is a symmetric positive definite matrix, and also is an
$H_{+}$-matrix. Taking $\Delta M=\epsilon M$ with $\|\Delta
q\|\leq\epsilon\|(-q)_{+}\|$, it is easy to obtain that

$\kappa_{\infty}(\langle M\rangle)=\kappa_{2}(M)=1,$

where $\kappa(\cdot)$ denotes the condition number, see Corollary 3.2 (i) and
(ii) in [33]. Hence, we can obtain

$\frac{2\delta}{1-\delta}=\frac{2\epsilon}{1-\epsilon}.$

From Corollary 4.3 (i), we get

$\rho(|\tilde{A}^{-1}\tilde{B}|)=\frac{1+3\epsilon}{5+3\epsilon}<1$

and

$\|(I-|\tilde{A}^{-1}\tilde{B}|)^{-1}\|_{\infty}\|\tilde{A}^{-1}\|_{\infty}=\frac{5+3\epsilon}{4}\times\frac{2}{2.5+1.5\epsilon}=1.$

Further,

$\displaystyle\frac{\|\Delta
q\|_{\infty}}{\|q\|_{\infty}}\bigg{(}\frac{\|M+I\|_{\infty}+\|M-I\|_{\infty}}{2}\bigg{)}+\epsilon\|M\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon\|(-q)_{+}\|_{\infty}}{\|q\|_{\infty}}\bigg{(}\frac{\|M+I\|_{\infty}+\|M-I\|_{\infty}}{2}\bigg{)}+\epsilon\|M\|_{\infty}$
$\displaystyle=$ $\displaystyle(\frac{1}{4\sqrt{6}}+\frac{1}{2})3\epsilon.$

Hence,

$\displaystyle\|(I-|\tilde{A}^{-1}\tilde{B}|)^{-1}\|_{\infty}\|\tilde{A}^{-1}\|_{\infty}\bigg{(}\frac{\epsilon\|(-q)_{+}\|_{\infty}}{\|q\|_{\infty}}\bigg{(}\frac{\|M+I\|_{\infty}+\|M-I\|_{\infty}}{2}\bigg{)}+\epsilon\|M\|_{\infty}\bigg{)}$
$\displaystyle=$ $\displaystyle(\frac{1}{4\sqrt{6}}+\frac{1}{2})3\epsilon.$

It is easy to check that

$(\frac{1}{4\sqrt{6}}+\frac{1}{2})3\epsilon<\frac{2\epsilon}{1-\epsilon}.$

From Corollary 4.3 (ii), we get

$\sigma_{\min}(\tilde{A})=\frac{2.5+1.5\epsilon}{2},\sigma_{\max}(\tilde{B})=\frac{0.5+1.5\epsilon}{2},$

frow which we have

$\frac{1}{\sigma_{\min}(\tilde{A})-\sigma_{\max}(\tilde{B})}=1.$

Further,

$\displaystyle\frac{\|\Delta
q\|_{2}}{\|q\|_{2}}\bigg{(}\frac{\|M+I\|_{2}+\|M-I\|_{2}}{2}\bigg{)}+\epsilon\|M\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{\epsilon\|(-q)_{+}\|_{2}}{\|q\|_{2}}\bigg{(}\frac{\|M+I\|_{2}+\|M-I\|_{2}}{2}\bigg{)}+\epsilon\|M\|_{2}=1.8\epsilon.$

In this case,

$\frac{1}{\sigma_{\min}(\tilde{A})-\sigma_{\max}(\tilde{B})}\bigg{(}\frac{\epsilon\|(-q)_{+}\|_{2}}{\|q\|_{2}}\bigg{(}\frac{\|M+I\|_{2}+\|M-I\|_{2}}{2}\bigg{)}+\epsilon\|M\|_{2}\bigg{)}=1.8\epsilon.$

It is easy to check that

$1.8\epsilon<\frac{2\epsilon}{1-\epsilon}.$

From Corollary 4.3 (iii), we have

$\sigma_{\max}(\tilde{A}^{-1}\tilde{B})=\frac{1+3\epsilon}{5+3\epsilon}<1\
\mbox{and}\ \sigma_{\max}(\tilde{B}^{-1})=\frac{2}{0.5+1.5\epsilon}.$

Likewise, it is easy to check that

$\frac{\frac{1+3\epsilon}{5+3\epsilon}\times\frac{2}{0.5+1.5\epsilon}\times
1.8\epsilon}{1-\frac{1+3\epsilon}{5+3\epsilon}}<\frac{2\epsilon}{1-\epsilon}.$

The above numerical results show that our presented upper bounds, (i), (ii)
and (iii) in Corollary 4.3, are sharper than Corollary 3.2 (i) and (ii) in
[33] under certain conditions. This implies that our presented upper bounds,
(i), (ii) and (iii) in Corollary 4.3, are significative in a way.

##  5 Numerical examples

In this section, we focus on investigating the feasibility of the relative
perturbation bounds of Theorem 3.2 and Theorem 3.4 in the Section 3 by making
use of some numerical examples. For the sake of convenience, we consider the
AVEs (1.1)

$Ax-B|x|=b,\ \mbox{with}\ A=I+M,B=I-M\ \mbox{and}\ b=-q,$

which is from the LCP (1.4) by making use of change of variable $z=|x|+x$ and
$w=|x|-x$. For the convenient comparison, here we introduce some notations,
i.e.,

$r=\frac{\|x^{\ast}-y^{\ast}\|_{2}}{\|x^{\ast}\|_{2}},w=\frac{\|\Delta
b\|_{2}}{\|b\|_{2}}(\|A\|_{2}+\|B\|_{2})+\|\Delta A\|_{2}+\|\Delta B\|_{2},$
$\tau=\|(I-|\mathcal{A}^{-1}\mathcal{B}|)^{-1}\|_{2}\|\mathcal{A}^{-1}\|_{2}w,\upsilon=\frac{1}{\sigma_{\min}(\mathcal{A})-\sigma_{\max}(\mathcal{B})}w,\nu=\frac{\|\mathcal{A}^{-1}\mathcal{B}\|_{2}\|\mathcal{B}^{-1}\|_{2}w}{1-\|\mathcal{A}^{-1}\mathcal{B}\|_{2}}$

and

$\delta=\frac{\epsilon\|(I-|A^{-1}B|)^{-1}|A^{-1}|(|b|+(|A|+|B|)|x^{\ast}|)\|_{2}}{(1-\epsilon\|(I-|A^{-1}B|)^{-1}|A^{-1}|(|A|+|B|)\|_{2})\|x^{\ast}\|_{2}},$

where $\mathcal{A}=A+\Delta A$ and $\mathcal{B}=B+\Delta B$, $x^{\ast}$ and
$y^{\ast}$ denote the solutions of the corresponding AVEs and the perturbed
AVEs, respectively, which can be obtained by using the iteration method on
page 364 in [3] with the initial vector being zero and the corresponding
absolute error less than $10^{-6}$. All the computations are done in Matlab
R2021b on an HP PC (Intel@ Celeron@ G4900, 3.10GHz, 8.00 GB of RAM).

Example 5.1 [38] Let

$M=\mbox{tridiag}(1,4,-2)\in\mathbb{R}^{n\times n},q=-4e\in\mathbb{R}^{n}.$

Obviously, $M$ is an $H_{+}$-matrix. This implies that the corresponding LCP
has a unique solution, i.e., the equal AVEs has a unique solution.

One is interested in the perturbation error for the solution of the
corresponding AVEs (1.1) caused by small changes in $A$, $B$ and $b$. The
perturbation way we do it is

$\Delta A=\epsilon\mbox{tridiag}(1,2,-1),\Delta
B=\epsilon\mbox{tridiag}(1,1,1),\Delta b=\epsilon e.$

$\epsilon$ |  0.01 |  0.015 |  0.02 |  0.025 |  0.03
---|---|---|---|---|---
$r$ |  0.0040 |  0.0061 |  0.0081 |  0.0101 |  0.0122
$\tau$ |  0.2845 |  0.4124 |  0.5321 |  0.6442 |  0.7495
$\upsilon$ |  0.0465 |  0.0692 |  0.0916 |  0.1138 |  0.1356
$\nu$ |  0.1104 |  0.1650 |  0.2194 |  0.2736 |  0.3275
$\delta$ |  0.0048 |  0.0072 |  0.0097 |  0.0121 |  0.0146

Table 1: Relative perturbation bounds of Example 5.1 with $n=30$. $\epsilon$ |  0.01 |  0.015 |  0.02 |  0.025 |  0.03
---|---|---|---|---|---
$r$ |  0.0041 |  0.0061 |  0.0082 |  0.0102 |  0.0123
$\tau$ |  0.2956 |  0.4282 |  0.5519 |  0.6677 |  0.7762
$\upsilon$ |  0.0473 |  0.0704 |  0.0932 |  0.1157 |  0.1378
$\nu$ |  0.1112 |  0.1663 |  0.2211 |  0.2757 |  0.3301
$\delta$ |  0.0046 |  0.0069 |  0.0093 |  0.0116 |  0.0140

Table 2: Relative perturbation bounds of Example 5.1 with $n=40$.

In Tables 1 and 2, we list the numerical results for four relative
perturbation bounds with the different size and $\epsilon$, from which we find
that among four relative bounds, $\delta<\nu$, $\delta<\upsilon$ and
$\delta<\tau$, i.e., $\delta$ is closet to the true relative error. In
addition, these numerical results also illustrate that the proposed bounds are
very close to the real relative value when the perturbation is very small.
From Tables 1 and 2, it is easy to find that the relative perturbation bounds
given by Theorem 3.2 and Theorem 3.4 are feasible and effective under some
suitable conditions.

Next, we investigate another example, which is from [18].

Example 5.2 [18] Let $M=\hat{M}+\mu I$, $q=-Mz^{\ast}$, where $\mu=4$,

$\hat{M}=\mbox{blktridiag}(-I,S,-I)\in\mathbb{R}^{n\times
n},S=\mbox{tridiag}(-1,4,-1)\in\mathbb{R}^{m\times m},n=m^{2},$

and $z^{\ast}=(1,2,1,2,\ldots,1,2,\ldots)^{T}\in\mathbb{R}^{n}$ is the unique
solution of the corresponding LCP. Of course, the equal AVEs has a unique
solution as well.

For Example 5.2, the perturbation way we do it is

$\Delta A=\epsilon\mbox{tridiag}(-1,2,-1),\Delta
B=\epsilon\mbox{tridiag}(1,-1,1),\Delta b=\epsilon e.$

$\epsilon$ |  0.01 |  0.015 |  0.02 |  0.025 |  0.03
---|---|---|---|---|---
$r$ |  0.0028 |  0.0042 |  0.0056 |  0.0070 |  0.0084
$\tau$ |  0.2571 |  0.3870 |  0.5177 |  0.6493 |  0.7817
$\upsilon$ |  0.0422 |  0.0631 |  0.0839 |  0.1046 |  0.1252
$\nu$ |  0.1731 |  0.2598 |  0.3465 |  0.4334 |  0.5203
$\delta$ |  0.0055 |  0.0083 |  0.0111 |  0.0139 |  0.0167

Table 3: Relative perturbation bounds of Example 5.2 with $n=225$. $\epsilon$ |  0.01 |  0.015 |  0.02 |  0.025 |  0.03
---|---|---|---|---|---
$r$ |  0.0030 |  0.0045 |  0.0060 |  0.0075 |  0.0090
$\tau$ |  0.2798 |  0.4212 |  0.5637 |  0.7071 |  0.8516
$\upsilon$ |  0.0466 |  0.0697 |  0.0927 |  0.1155 |  0.1382
$\nu$ |  0.1835 |  0.2754 |  0.3674 |  0.4595 |  0.5517
$\delta$ |  0.0055 |  0.0083 |  0.0111 |  0.0139 |  0.0167

Table 4: Relative perturbation bounds of Example 5.2 with $n=400$.

Similarly, with the different size and $\epsilon$, Tables 3 and 4 list these
four relative perturbation bounds for Example 5.2. From Tables 3 and 4, we can
draw the same conclusion. That is to say, among these four bounds, $\delta$ is
optimal, compared with other three bounds. These numerical results in Tables 3
and 4 further illustrate that when the perturbation term is very small, the
proposed bounds are very close to the real relative value. Meanwhile, this
further confirms that under some suitable conditions, Theorem 3.2 and Theorem
3.4 indeed provide some valid relative perturbation bounds.

##  6 Conclusion

In this paper, by introducing a class of absolute value functions, the
frameworks of error and perturbation bounds for two types of absolute value
equations (AVEs) have been established. After then, by applying the absolute
value equations, the frameworks of error and perturbation bounds for the
horizontal linear complementarity problem (HLCP) are obtained. Incidentally,
some equal new frameworks of error bounds for linear complementarity problem
(LCP) are given and its more general perturbation bound is presented as well.
Besides, without limiting the matrix type, some computable estimates for the
above upper bounds are given, which are sharper than some existing results
under certain conditions. In addition, some numerical examples for absolute
value equations from the LCP are given to show the feasibility of the proposed
perturbation bounds.

## Conflict of interest

The authors declare no competing interests.

## References

  * [1] J. Rohn, A theorem of the alternatives for the equation $Ax+B|x|=b$, Linear Multilinear A., 52 (2004), pp. 421-426.
  * [2] S.-L. Wu, The unique solution of a class of the new generalized absolute value equation, Appl. Math. Lett., 116 (2021), 107029.
  * [3] O.L. Mangasarian and R.R. Meyer, Absolute value equations, Linear Algebra Appl., 419 (2006), pp. 359-367.
  * [4] J. Rohn, Systems of linear interval equations, Linear Algebra Appl., 126 (1989), pp. 39-78.
  * [5] O.L. Mangasarian, Absolute value programming, Comput. Optim. Appl., 36(1) (2007), pp. 43-53.
  * [6] O. Prokopyev, On equivalent reformulations for absolute value equations, Comput. Optim. Appl., 44(3) (2009), pp. 363-372.
  * [7] S.-L. Wu and S.-Q. Shen, On the unique solution of the generalized absolute value equation, Optim. Lett., 15 (2021), pp. 2017-2024.
  * [8] S.-L. Wu and C.-X. Li, The unique solution of the absolute value equations, Appl. Math. Lett., 76 (2018), pp. 195-200.
  * [9] F. Mezzadri, On the solution of general absolute value equations, Appl. Math. Lett., 107 (2020), 106462.
  * [10] O.L. Mangasarian, A generalized Newton method for absolute value equations, Optim. Lett., 3 (2009), pp. 101-108.
  * [11] H.-Y. Zhou, S.-L. Wu, and C.-X. Li, Newton-based matrix splitting method for generalized absolute value equation, J. Comput. Appl. Math., 394 (2021), 113578.
  * [12] C.-R. Chen, D.-M. Yu, and D.-R. Han, Exact and inexact Douglas-Rachford splitting methods for solving large-scale sparse absolute value equations, IMA J. Numer. Anal., https://doi.org/10.1093/imanum/drab105.
  * [13] D.K. Salkuyeh, The Picard-HSS iteration method for absolute value equations, Optim. Lett., 8 (2014), pp. 2191-2202.
  * [14] J. Rohn, An algorithm for solving the absolute value equations, Electron J. Linear Al., 18 (2009), pp. 589-599.
  * [15] O.L. Mangasarian, Absolute value equation solution via concave minimization, Optim. Lett., 1(1) (2007), pp. 3-8.
  * [16] J. Iqbal, A. Iqbal, and M. Arif, Levenberg-Marquardt method for solving systems of absolute value equations, J. Comput. Appl. Math., 282 (2015), pp. 134-138.
  * [17] W.M.G.V. Bokhoven, A class of linear complementarity problems is solvable inpolynomial time, (unpublished paper), Department of Electrical Engineering, University of Technology, The Netherlands, 1980\.
  * [18] Z.-Z. Bai, Modulus-based matrix splitting iteration methods for linear complementarity problems, Numer. Linear Algebra Appl., 17 (2010), pp. 917-933.
  * [19] S.-L. Wu and C.-X. Li, A class of new modulus-based matrix splitting methods for linear complementarity problem, Optim. Lett., 16 (2022), pp. 1427-1443.
  * [20] C.-R. Chen, Y.-N. Yang, D.-M. Yu, and D.-R. Han, An inverse-free dynamical system for solving the absolute value equations, Appl. Numer. Math., 168 (2021), pp. 170-181.
  * [21] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970.
  * [22] R.A. Horn and C.R. Johnson, Matrix Analysis (2nd Edition), Cambridge University Press, New York, 2013.
  * [23] J. Rohn, V. Hooshyarbakhsh, and R. Farhadsefat, An iterative method for solving absolute value equations and sufficient conditions for unique solvability, Optim. Lett., 8 (2014), pp. 35-44.
  * [24] S.-L. Wu and C.-X. Li, A note on unique solvability of the absolute value equation, Optim. Lett., 14 (2020), pp. 1957-1960.
  * [25] C.-X. Li, Sufficient conditions for the unique solution of a class of new Sylvester-like absolute value equation, J. Optim. Theory Appl., 195 (2022), pp. 676-683.
  * [26] J.-G. Sun, Matrix Perturbation Theory (in Chinese), Science press, Beijing, 2001.
  * [27] R.D. Skeel, Scaling for numerical stability in Gauss elimination, J. Assoc. Comput. Mach., 26 (1979), pp. 494-526.
  * [28] Y. Wei, Perturbation bound of singular linear systems, Appl. Math. Comput., 105 (1999), pp. 211-220.
  * [29] R.W. Cottle, J.-S. Pang, and R.E. Stone, The Linear Complementarity Problem, Academic, San Diego, 1992.
  * [30] X.-J. Chen and S.-H. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program., 106 (2006), pp. 513-525.
  * [31] R. Sznajder and M.S. Gowda, Generalizations of P0- and P-properties; extended vertical and horizontal linear complementarity problems, Linear Algebra Appl., 223-224 (1995), pp. 695-715.
  * [32] L. Elsner, V. Monov, and T. Szulc, On some properties of convex matrix sets characterized by P-matrices and block P-Matrices, Linear Multilinear A., 50(3) (2002), pp. 199-218.
  * [33] X.-J. Chen and S.-H. Xiang, Perturbation bounds of P-matrix linear complementarity problems, SIAM J. Optim., 18 (2007), pp. 1250-1265.
  * [34] A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic, New York, 1979.
  * [35] F.H. Clarke, Optimization and Nonsmooth Analysis (2nd edition), Classics in Applied Mathematics 5, SIAM, Philadephia, P.A., 1990.
  * [36] C. Zhang, X.-J. Chen, and N.-H. Xiu, Global error bounds for the extended vertical LCP, Comput. Optim. Appl., 42 (2009), pp. 335-352.
  * [37] S. Gabriel and J. Moré, Smoothing of mixed complementarity problems, in: M.C. Ferris, J.S. Pang (Eds.), Complementarity and Variational Problems: State of the Art, SIAM, Philadelphia, 1997, pp. 105-116.
  * [38] B.H. Ahn, Iterative methods for linear complementarity problems with upperbounds on primary variables, Math. Program., 26 (1983), pp. 295-315.
  * [39] M. Zamani and M. Hladík, Error bounds and a condition number for the absolute value equations, Math. Program., 198 (2023), pp. 85-113.