<!DOCTYPE html>
<html lang="en">
<head>
<script>
  MathJax = { 
    tex: {
		    inlineMath: [['\\(','\\)']]
	} }
</script>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js">
</script>
<meta name="generator" content="plasTeX" />
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Preconditioned conjugate gradient methods for absolute value equations: Preconditioned conjugate gradient methods for absolute value equations</title>
<link rel="stylesheet" href="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/styles/theme-white.css" />
</head>

<body>

<div class="wrapper">

<div class="content">
<div class="content-wrapper">


<div class="main-text">



<div class="titlepage">
<h1>Preconditioned conjugate gradient methods for absolute value equations</h1>
<p class="authors">
<span class="author">Nassima Anane\(^\ast \) Mohamed Achache\(^\bullet \)</span>
</p>
<p class="date">October 11, 2019; accepted: February 27, 2020; published online: August 11, 2020.</p>
</div>
<div class="abstract"><p> In this paper, we investigate the NP-hard <i class="it">absolute value equations</i> (AVE), \(Ax-B\left\vert x\right\vert =b\), where \(A,B\) are given symmetric matrices in \(\mathbb {R}^{n\times n}\), \(b\in \mathbb {R}^{n}\). By reformulating the AVE as an equivalent unconstrained convex quadratic optimization, we prove that the unique solution of the AVE is the unique minimum of the corresponding quadratic optimization. Then across the latter, we adopt the preconditioned conjugate gradient methods to determining an approximate solution of the AVE. The computational results show the efficiency of these approaches in dealing with the AVE. </p>
<p><b class="bf">MSC.</b> 65F08, 90C33, 93C05, 90C20 </p>
<p><b class="bf">Keywords.</b> Absolute value equations, linear system, unconstrained convex quadratic optimization, linear complementarity problems </p>
</div>
<p>\(^\ast \) Département de génés des procédures. Faculté de Technologie. Université ferhat Abbas, Sétif 1. Sétif 19000, Algérie, e-mail: nasimaannan@gmail.com. </p>
<p>\(^\bullet \) Laboratoire de Mathématiques Fondamentales et Numériques. Université ferhat Abbas, Sétif 1. Sétif 19000, Algérie, e-mail: achache_m@univ-setif.dz. This work has been supported by: La Direction Générale de la Recherche Scientifique et du Développement Technologique (DGRSDT-MESRS), under project PRFU number C00L03UN190120190004. Algérie. </p>
<h1 id="a0000000002">1 Introduction</h1>
<p> The <i class="it">absolute value equations</i> (AVE) of the type:</p>
<div class="equation" id="f1">
<p>
  <div class="equation_content">
    \begin{equation}  Ax-B|x|=b,\label{f1} \end{equation}
  </div>
  <span class="equation_label">1</span>
</p>
</div>
<p>where \(A\) and \(B\) are given matrices in \(\mathbb {R}^{n\times n},\, b\in \mathbb {R}^{n}\) and \(\left\vert x\right\vert \) denotes the vector with absolute values of each components of the vector \(x\), was investigated by <span class="cite">
	[
	<a href="#1" >1</a>
	]
</span>, <span class="cite">
	[
	<a href="#11" >11</a>
	]
</span>, <span class="cite">
	[
	<a href="#12" >12</a>
	]
</span>, <span class="cite">
	[
	<a href="#15" >15</a>
	]
</span>. A special case of <a href="#f1" class="eqref">1</a> when \(B=I\) (\(I\) denotes the identity matrix) is the AVE of the type: </p>
<div class="displaymath" id="a0000000003">
  \[  Ax-|x|=b.  \]
</div>
<p>The AVEs arise in many scientific areas and mathematical problems such as <i class="it">linear complementarity problems</i> (LCP), boundary value problems, equilibrium problems and interval linear equations. As is known in <span class="cite">
	[
	<a href="#11" >11</a>
	]
</span>, the general NP-hard linear complementarity can be formulated as the AVE <a href="#f1" class="eqref">1</a>, then it is an NP-hard in its general form. Furthermore, much research has been devoted to achieve their numerical solutions efficiently (see, <i class="it">e.g.</i>, <span class="cite">
	[
	<a href="#1" >1</a>
	]
</span>, <span class="cite">
	[
	<a href="#2" >2</a>
	]
</span>, <span class="cite">
	[
	<a href="#7" >7</a>
	]
</span>, <span class="cite">
	[
	<a href="#8" >8</a>
	]
</span>, <span class="cite">
	[
	<a href="#9" >9</a>
	]
</span>, <span class="cite">
	[
	<a href="#12" >12</a>
	]
</span>, <span class="cite">
	[
	<a href="#15" >15</a>
	]
</span>). </p>
<p>In this paper, by reformulating the AVE <a href="#f1" class="eqref">1</a> into an equivalent unconstrained quadratic optimization problem, we prove first under the condition that the smallest singular value of \(A\) is greater than the largest singular value of \(B\), the AVE <a href="#f1" class="eqref">1</a> is uniquely solvable for any \(b\). Secondly, we show that the unique minimum of the corresponding unconstrained quadratic problem is the unique solution of the AVE <a href="#f1" class="eqref">1</a>. Then across the latter, we apply the conjugate gradient algorithms to approximate numerically the solution of the AVE <a href="#f1" class="eqref">1</a>. In the presence of the ill-conditioned, preconditioned conjugate gradient methods can be used to ensure and to accelerate the convergence of the basic CG algorithms. We show across some examples of the AVE, the efficiency of these approaches. </p>
<p>Now we describe our notation. The scalar product of two vectors \(x\) and \(y\) in \(\mathbb {R}^{n}\) is denoted by \(x^{T}y\). For \(x\in \mathbb {R}^{n}\), the norm \(\Vert x\Vert \) will denote the Euclidean norm \((x^{T}x)^{1/2}\), and \(\operatorname {sign}(x)\) will denote a vector with components equal to \(+1, 0\) or \(- 1\), depending on whether the corresponding component of \(x\) is positive, zero or negative, respectively. In addition, \(D(x)\):= \(\partial \vert x\vert =\operatorname {sign}(x))\) will denote the diagonal matrix corresponding to \(\operatorname {sign} (x)\) where \(\partial \vert x\vert \) denotes the generalized Jacobian for the absolute value \(\vert x\vert \) based on a sub-gradient. The vector of ones and the inverse of a nonsingular matrix \(A\) are denoted, respectively, by \(e\) and \(A^{-1}\). \(\lambda _{\min }(M)\) and \(\lambda _{\max }(M)\) stand for the minimal and the maximal eigenvalues of a matrix \(M\). </p>
<p>As it is known, for a symmetric matrix \(M\), the minimal and the maximal singular values of \(M\), are defined by \(\sigma _{\min }(M)=\min _{\Vert y\Vert =1}\Vert My\Vert \) and \(\sigma _{\max }(M)=\Vert M\Vert = \max _{\Vert y\Vert =1}\Vert My\Vert \), respectively. Here, \(\Vert M\Vert \) is called the spectral induced norm. Finally, the spectral condition number of a non-singular symmetric matrix \(M\) is denoted by \(\kappa ({M})=\frac{\vert \lambda _{\max }(M)\vert }{\vert \lambda _{\min }(M)\vert }\). </p>
<p>The paper is built as follows. In <a href="#sect.2">section 2</a>, the unique solvability of the AVE <a href="#f1" class="eqref">1</a> as well as its equivalence reformulation to unconstrained quadratic optimization and the basic conjugate gradient methods for solving the AVE <a href="#f1" class="eqref">1</a> are stated. In <a href="#sect.3">section 3</a>, the preconditioned conjugate gradient algorithms are proposed. Numerical results are reported in <a href="#sect.4">section 4</a>. The paper is ended with a conclusion and future work in <a href="#sect.5">section 5</a>. </p>
<h1 id="sect.2">2 Basic conjugate gradient methods</h1>
<p> Before describing the conjugate gradient algorithm, the following results are useful. For given symmetric matrices \(A\) and \(B\), we define, for any diagonal matrix \(D\) whose elements are equal to \(1, 0\) or \(-1\), the matrix \(Q=A-BD\). To prove the unique solvability of the AVE <a href="#f1" class="eqref">1</a>, the following result is required. <div class="lemma_thmwrapper " id="lem.1">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">1</span>
  </div>
  <div class="lemma_thmcontent">
  <p> If symmetric matrices \(A\) and \(B\) satisfy: </p>
<div class="displaymath" id="a0000000004">
  \[  \sigma _{\min }(A){\gt}\sigma _{\max }(B),  \]
</div>
<p> then the matrix \(A-BD\) is nonsingular for any diagonal matrix \(D\) whose elements are equal to \(+1\), \(0\) or \(-1\). </p>

  </div>
</div> </p>
<p><div class="proof_wrapper" id="a0000000005">
  <div class="proof_heading">
    <span class="proof_caption">
    Proof
    </span>
    <span class="expand-proof">â–¼</span>
  </div>
  <div class="proof_content">
  
  </div>
</div>Assume the contrary, that \(A-BD\) is singular, then for some nonzero vector \(x\) with \(\Vert x\Vert =1\), we then have that \((A-BD)x=0,\) which derives a contradiction. This implies that \(Ax=BDx\). Hence </p>
<div class="displaymath" id="a0000000006">
  \begin{eqnarray*}  \sigma _{\min }(A) & =& \min _{\left\Vert y\right\Vert =1}\Vert Ay\Vert \leq \Vert Ax\Vert =\Vert BDx \Vert \\ & \leq & \Vert B\Vert \Vert D\Vert \Vert x\Vert \leq \Vert B\Vert =\sigma _{\max }(B). \end{eqnarray*}
</div>
<p> This contradicts our condition. Hence \(A-BD\) is non-singular.<span class="qed">â–¡</span></p>
<p>Now according to the equality \(D(x)x=\vert x\vert \), with \(D(x)=\operatorname {diag}(\operatorname {sign} (x)\)) the AVE <a href="#f1" class="eqref">1</a> can be transformed into the following linear system of equations: </p>
<div class="equation" id="f2">
<p>
  <div class="equation_content">
    \begin{equation}  Qx=b,\label{f2} \end{equation}
  </div>
  <span class="equation_label">2</span>
</p>
</div>
<p>where \(Q=A-BD\). <div class="lemma_thmwrapper " id="a0000000007">
  <div class="lemma_thmheading">
    <span class="lemma_thmcaption">
    Lemma
    </span>
    <span class="lemma_thmlabel">2</span>
  </div>
  <div class="lemma_thmcontent">
  <p>If symmetric matrices \(A\) and \(B\) satisfy </p>
<div class="displaymath" id="a0000000008">
  \[  \sigma _{\min }(A){\gt}\sigma _{\max }(B),  \]
</div>
<p> then the AVE <a href="#f1" class="eqref">1</a> is uniquely solvable for any \(b\). </p>

  </div>
</div> </p>
<p><div class="proof_wrapper" id="a0000000009">
  <div class="proof_heading">
    <span class="proof_caption">
    Proof
    </span>
    <span class="expand-proof">â–¼</span>
  </div>
  <div class="proof_content">
  
  </div>
</div>Based on the result of <a href="#lem.1">lemma 1</a>, the matrix \(Q\) is non-singular for any arbitrary diagonal matrix \(D\) whose elements are equal to \(1, 0\) or \(- 1\) and therefore the AVE <a href="#f1" class="eqref">1</a> has a unique solution for any \(b\).<span class="qed">â–¡</span></p>
<p>One of the important numerical tools to solve the system <a href="#f2" class="eqref">2</a> is to transform it into an equivalent quadratic optimization problem: </p>
<div class="equation" id="f3">
<p>
  <div class="equation_content">
    \begin{equation}  \min _{x\in \mathbb {R}^{n}}f(x)=\tfrac {1}{2}(Qx-b)^{T}(Qx-b) \label{f3}. \end{equation}
  </div>
  <span class="equation_label">3</span>
</p>
</div>
<p>The gradient and the Hessian matrix of \(f(x)\) are given by: </p>
<div class="displaymath" id="a0000000010">
  \[  g(x):=\partial f(x)=Q^{T}(Qx-b)  \]
</div>
<p>and </p>
<div class="displaymath" id="a0000000011">
  \[  H(x):=\partial ^{2}f(x)=Q^{T}Q.  \]
</div>
<p>Since \(H(x)\) is positive definite for any diagonal matrix \(D\) whose elements are equal to \(+1\), \(0\) or \(- 1\), the problem <a href="#f3" class="eqref">3</a> has a unique minimum that satisfies</p>
<div class="displaymath" id="a0000000012">
  \[  g(x)=0  \]
</div>
<p>or </p>
<div class="equation" id="f4">
<p>
  <div class="equation_content">
    \begin{equation}  Q^{T}Qx=Q^{T}b.\label{f4} \end{equation}
  </div>
  <span class="equation_label">4</span>
</p>
</div>
<p>Since \(Q\) is non-singular therefore <a href="#f4" class="eqref">4</a> is equivalent to <a href="#f2" class="eqref">2</a> and so is equivalent to AVE <a href="#f1" class="eqref">1</a>. Hence solving the AVE <a href="#f1" class="eqref">1</a> is equivalent to find the unique minimum of <a href="#f3" class="eqref">3</a>. </p>
<p>The conjugate gradient methods are known to be effective in solving quadratic problems in finite termination <span class="cite">
	[
	<a href="#4" >4</a>
	]
</span>, <span class="cite">
	[
	<a href="#5" >5</a>
	]
</span>, <span class="cite">
	[
	<a href="#16" >16</a>
	]
</span>, <span class="cite">
	[
	<a href="#17" >17</a>
	]
</span>, <span class="cite">
	[
	<a href="#18" >18</a>
	]
</span>. These methods start with an initial point \(x_{0}\) and generate a sequence \(\left\{  x_{k}\right\} \) according to the following recurrence formula: </p>
<div class="equation" id="f5">
<p>
  <div class="equation_content">
    \begin{equation}  x_{k+1}=x_{k}+\alpha _{k}d_{k},\qquad k=0,\, 1,\, 2,\dots \label{f5} \end{equation}
  </div>
  <span class="equation_label">5</span>
</p>
</div>
<p>where \(\alpha _{k}{\gt}0\) is the step-size obtained by a line search and the directions \(d_{k}\) are computed by the rule: </p>
<div class="equation" id="f6">
<p>
  <div class="equation_content">
    \begin{equation}  d_{k}=-g_{k}+\beta _{k}d_{k-1},\quad k\geq 1,\, d_{0}=-g_{0}, \label{f6} \end{equation}
  </div>
  <span class="equation_label">6</span>
</p>
</div>
<p>where \(\beta _{k}\) is a suitable positive scalar known as the conjugate updating parameter and \(g_{k}\) refers to \(g(x_{k})\). </p>
<h2 id="a0000000013">2.1 Exact line search</h2>
<p> Determining the step-size \(\alpha _{k}\) in <a href="#f5" class="eqref">5</a> along the direction \(d_{k}\), for an objective function \(f(x)\), which is to be minimized, can be simplified to finding the value of \(\alpha _{k}=\alpha \) which consequently minimizes the function: </p>
<div class="displaymath" id="a0000000014">
  \[  f(x_{k+1})=f(x_{k}+\alpha d_{k})=m(\alpha ).  \]
</div>
<p>The function \(m(\alpha )\) is of a single variable, that is \(\alpha \). Therefore, the \(\alpha _{k}\) is calculated by an exact line search as follows. Using Taylor’s expansion, we have, </p>
<div class="displaymath" id="a0000000015">
  \[  m(\alpha )=f(x_{k}+\alpha d_{k})=f(x_{k})+\alpha g_{k}^{T}d_{k}+\tfrac {\alpha ^{2}}{2}d_{k}^{T}H_{k}d_{k},  \]
</div>
<p>so </p>
<div class="displaymath" id="a0000000016">
  \[  \tfrac {\partial m}{\partial \alpha }=0\Leftrightarrow \alpha =-\tfrac {g_{k}^{T}d_{k}}{d_{k}^{T}H_{k}d_{k}}.  \]
</div>
<p>Therefore the exact line search is taken as: </p>
<div class="equation" id="f7">
<p>
  <div class="equation_content">
    \begin{equation}  \alpha _{k}=-\tfrac {g_{k}^{T}d_{k}}{d_{k}^{T}H_{k}d_{k}},\label{f7} \end{equation}
  </div>
  <span class="equation_label">7</span>
</p>
</div>
<p>where \(H_{k}\) refers to \(H(x_{k})\). </p>
<h2 id="a0000000017">2.2 Computation of \(\protect \beta _{k}\)</h2>
<p> The coefficients \(\beta _{k}\) being chosen in such a way that \(d_{k}\) is conjugated with all the preceding directions, in other words </p>
<div class="displaymath" id="a0000000018">
  \[  d_{k}^{T}Qd_{k-1}=0,  \]
</div>
<p>then it implies that: </p>
<div class="displaymath" id="a0000000019">
  \[  d_{k}^{T}Qd_{k-1}=-g_{k}^{T}Qd_{k-1}+(\beta _{k}d_{k-1})^{T}Qd_{k-1}=0,  \]
</div>
<p>and so: </p>
<div class="equation" id="f8">
<p>
  <div class="equation_content">
    \begin{equation} \label{f.8} \beta _{k}=\tfrac {g_{k}^{T}Qd_{k-1}}{d_{k-1}^{T}Qd_{k-1}}. \end{equation}
  </div>
  <span class="equation_label">8</span>
</p>
</div>

<h2 id="a0000000020">2.3 Basic conjugate gradient algorithms.</h2>
<p> We are now ready to state the basic CG algorithms for solving the AVE <a href="#f1" class="eqref">1</a>. </p>
<ul class="itemize">
  <li><p><b class="bfseries">Step 1.</b> Choose an arbitrary initial point \(x_{0}\in \mathbb {R}^{n}\), \(\epsilon {\gt}0\) and \(d_{0}=-g_{0}\), \(k=0\); </p>
</li>
  <li><p><b class="bfseries">Step 2.</b> Compute \(\alpha _{k}\) from <a href="#f7" class="eqref">7</a> and set \(x_{k+1}=x_{k}+\alpha _{k}d_{k}\); </p>
</li>
  <li><p><b class="bfseries">Step 3.</b> If \(\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert {\lt}\epsilon \) then STOP, otherwise compute \(d_{k}\) according to \(d_{k}=-g_{k}+\beta _{k}d_{k-1}\) with \(\beta _{k}\) is computed from <a href="#f8" class="eqref">8</a>; </p>
</li>
  <li><p><b class="bfseries">Step 4.</b> Set \(k=k+1,\) and go to <b class="bfseries">Step 2</b>. </p>
</li>
</ul>
<p>In <span class="cite">
	[
	<a href="#4" >4</a>
	]
</span>, and <span class="cite">
	[
	<a href="#17" >17</a>
	]
</span>, it is shown that the convergence of the \(CG\) methods is linearly global to the unique minimum \(x^{\ast }\). It is known that the convergence of \(CG\) methods depends heavily on the condition number \(\kappa (Q).\) If \(\kappa (Q)\) is close to \(1\), <i class="it">i.e.</i>, if the matrix \(Q\) is well-conditioned then \(CG\) methods converge fast to the solution. Otherwise, in the presence of ill-conditioned of the matrix \(Q\), these methods have a very slow convergence. </p>
<h1 id="sect.3">3 Preconditioned conjugate gradient algorithms</h1>
<p> Preconditioning is mainly used in \(CG\) methods in order to accelerate their convergence when \(\kappa (Q)\) is very far from \(1\), <i class="it">i.e.</i>, when \(Q\) is ill-conditioned. Based on this fact, we can consider the preconditioned AVE <a href="#f1" class="eqref">1</a>: </p>
<div class="equation" id="f9">
<p>
  <div class="equation_content">
    \begin{equation}  PAx-PB\left\vert x\right\vert =Pb,\label{f9} \end{equation}
  </div>
  <span class="equation_label">9</span>
</p>
</div>
<p> where \(P\) is a non-singular matrix, called the preconditioner. Obviously, the form <a href="#f9" class="eqref">9</a> is a general form of the AVE <a href="#f1" class="eqref">1</a>. For \(P=I\), the form <a href="#f9" class="eqref">9</a> reduced to the AVE <a href="#f1" class="eqref">1</a>. Again using \(D(x)x=\left\vert x\right\vert \), then <a href="#f9" class="eqref">9</a> becomes the following preconditioned linear system:</p>
<div class="equation" id="f10">
<p>
  <div class="equation_content">
    \begin{equation}  PQx=Pb.\label{f10} \end{equation}
  </div>
  <span class="equation_label">10</span>
</p>
</div>
<p> Hence the system <a href="#f10" class="eqref">10</a> has a unique solution if the matrix \(PQ\) is invertible. Since \(P\) is assumed to be non-singular, then we only prove that \(Q\) is non-singular. By <a href="#lem.1">lemma 1</a>, the matrix \(Q\) is non-singular for any diagonal matrix \(D\) whose elements are \(1, 0\), or \(-1\), and consequently, the system <a href="#f10" class="eqref">10</a> has a unique solution and so the preconditioned AVE in <a href="#f9" class="eqref">9</a> is uniquely solvable for each \(b\). Based on this observation, therefore, the equivalent preconditioned quadratic optimization problem is: </p>
<div class="equation" id="f11">
<p>
  <div class="equation_content">
    \begin{equation}  \min _{x\in \mathbb {R}^{n}}f_{P}(x)=\tfrac {1}{2}(PQx-Pb)^{T}(PQx-Pb).\label{f11} \end{equation}
  </div>
  <span class="equation_label">11</span>
</p>
</div>
<p> The gradient and the Hessian matrix of \(f\) are:</p>
<div class="displaymath" id="a0000000021">
  \[  g^{P}(x):=\partial f_{P}(x)=(PQ)^{T}(PQx-Pb)  \]
</div>
<p>and </p>
<div class="displaymath" id="a0000000022">
  \[  H^{P}(x):=\partial ^{2}f_{P}(x)=(PQ)^{T}(PQ).  \]
</div>
<p> It is clear that if \(P=I\), the problem <a href="#f11" class="eqref">11</a> reduces to the original problem <a href="#f3" class="eqref">3</a>. Also since \((PQ)^{T}(PQ)\) is positive definite matrix, the problem <a href="#f11" class="eqref">11</a> has a unique minimum that satisfies: </p>
<div class="displaymath" id="a0000000023">
  \[  g^{P}(x)=0,  \]
</div>
<p> or</p>
<div class="displaymath" id="a0000000024">
  \[  (PQ)^{T}(PQx-Pb)=0,  \]
</div>
<p> which means that the unique minimum is the unique solution of the preconditioned system and which is in turn the unique solution of the AVE <a href="#f1" class="eqref">1</a>. For the preconditioned problem <a href="#f10" class="eqref">10</a>, with same manner as the basic CG algorithms, we compute the exact line search \(\alpha _{k}\) and the conjugate parameter \(\beta _{k}\) along the new preconditioned modified search direction by the formulas:</p>
<div class="equation" id="f12">
<p>
  <div class="equation_content">
    \begin{equation}  \alpha _{k}=-\frac{(g_{k}^{P})^{T}d_{k}}{d_{k}^{T}H_{k}^{P}d_{k}}, \label{f12} \end{equation}
  </div>
  <span class="equation_label">12</span>
</p>
</div>
<p> and</p>
<div class="equation" id="f13">
<p>
  <div class="equation_content">
    \begin{equation}  \beta _{k}=\frac{(g_{k}^{P})^{T}Qd_{k-1}}{d_{k-1}^{T}Qd_{k-1}}. \label{f13} \end{equation}
  </div>
  <span class="equation_label">13</span>
</p>
</div>
<p> Now the preconditioned conjugate gradient \((PCG)\) algorithm for solving the AVE <a href="#f1" class="eqref">1</a> is described as follows. </p>
<h2 id="a0000000025">3.1 Preconditioned conjugate gradient algorithm</h2>
<ul class="itemize">
  <li><p><b class="bfseries">Step 1.</b> Choose an arbitrary \(x_{0}\in \mathbb {R}^{n}\), a preconditioner matrix \(P\), \(\epsilon {\gt}0\) and \(d_{0}=-g_{0}^{P}\), \(k=0\); </p>
</li>
  <li><p><b class="bfseries">Step 2.</b> Compute \(\alpha _{k}\) from <a href="#f12" class="eqref">12</a> and set \(x_{k+1}=x_{k}+\alpha _{k}d_{k}\); </p>
</li>
  <li><p><b class="bfseries">Step 3.</b> If \(\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert {\lt}\epsilon \) then STOP, otherwise compute \(d_{k}\) according to \(d_{k}=-g_{k}^{P}+\beta _{k}d_{k-1}\) with \(\beta _{k}\) is computed from <a href="#f13" class="eqref">13</a>; </p>
</li>
  <li><p><b class="bfseries">Step 4.</b> Set \(k=k+1,\) and go to <b class="bfseries">Step 2</b>. </p>
</li>
</ul>
<p> Note that there is no unique strategy for choosing the preconditioning matrix \(P\) for the conjugate \(CG\) methods. In fact, the strategy of choosing \(P\) is based on a such way that the \(\kappa (PQ)\ll \kappa (Q).\) For more details see <span class="cite">
	[
	<a href="#4" >4</a>
	]
</span>. </p>
<h1 id="sect.4">4 Numerical experiments</h1>

<p>In this section, we present some numerical experiments on some examples of solvable AVE <a href="#f1" class="eqref">1</a> to confirm the viability of the \(PCG\) algorithms. The experiments are performed with MATLAB 7.9 and carried out on a PC where our tolerance is set to \(\epsilon = 10^{-6}\). The initial point and the true solution of AVE <a href="#f1" class="eqref">1</a> are denoted by \(x_{0}\) and \(x^{\ast }\), respectively. Meanwhile, the number of iterations, the elapsed times and the residue are denoted by <b class="bfseries">Iter</b>, <b class="bfseries">CPU</b> and <b class="bfseries">RSD</b>=\(\Vert Ax_{k}-B\vert x_{k}\vert -b\Vert \), respectively. In our numerical implementation, the appropriate choice of the preconditioners are \(P=\frac{1}{n}I,n\geq 1,\) and \(P=A^{-1}\).<br /></p>
<p><div class="example_thmwrapper " id="ex.3">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">3</span>
  </div>
  <div class="example_thmcontent">
  <p> Let the symmetric matrices \(A\), \(B\) and the vector \(b\) be given as: </p>
<div class="displaymath" id="a0000000026">
  \begin{align*}  A =& (a_{ij})=\begin{cases}  4n, &  \mbox{if } i=j, \\ n, &  \mbox{if } \left\vert i-j\right\vert =1 \\ 0.5, &  \mbox{otherwise} \end{cases}\\ B =& (b_{ij})= \begin{cases}  n, &  \mbox{if } i=j, \\ \frac{1}{n}, &  \mbox{if } \left\vert i-j\right\vert =1, \\ 0.125, &  \mbox{otherwise} \end{cases}\end{align*}
</div>
<div class="displaymath" id="a0000000027">
  \begin{align*} b=& (548,647.5,\ldots ,647.5,548)^{T}. \end{align*}
</div>
<p>With the initial points \(x_{1}^{0}=(0.001,\ldots ,0.001)^{T}\) and \(x_{2}^{0}=(0.9,\ldots ,0.9)^{T},\) the computational results with different size of \(n\), are summarized in <a href="#tab:t1">table 1</a>.</p>
<div class="table"  id="tab:t1">
   <small class="small"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> Size \(n\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=I\) (basic CGA) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=\frac{1}{n}I,n{\gt}1\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=A^{-1}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 29 \\ 0.0186 \\ {6.0870e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 21 \\ 0.0161 \\ {8.4089e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 0.0057 \\ {4.5068e-07}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(100\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 27 \\ 0.0178 \\ {6.7790e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 19 \\ 0.0158 \\ {9.1783e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 0.0074 \\ {6.9333e-06}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 33 \\ 3.5787 \\ {5.4336e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 21 \\ 2.4979 \\ {8.5594e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 0.2273 \\ {4.5352e-08}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(1000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 31 \\ 3.3429 \\ {6.0443e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 19 \\ 2.0959 \\ {9.3010e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 0.3293 \\ {8.8665e-15}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 34 \\ 26.6083 \\ {5.7908e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 21 \\ 16.2365 \\ {8.4035e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 1.5644 \\ {2.2684e-08}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(2000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 32 \\ 24.4110 \\ {6.4720e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 19 \\ 14.6529 \\ {9.2160e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 2.2716 \\ {1.5029e-14}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 34 \\ 90.5026 \\ {8.4709e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 21 \\ 53.2645 \\ {8.3032e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 4.9661 \\ {1.5124e-08}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(3000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 32 \\ 83.9471 \\ {9.5473e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 19 \\ 48.7091 \\ {9.1581e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 5.7692 \\ {2.7556e-14}\end{array}\) </p>

    </td>
  </tr>
</table></small> <figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">1</span> 
  <span class="caption_text">Numerical results for <a href="#ex.3">example 3</a>.</span> 
</figcaption>  
</div>
<p>The true solution is \(x^{\ast }=(\frac{4}{3},\frac{4}{3},\ldots ,\frac{4}{3},\frac{4}{3})^{T}\). </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="ex.4">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">4</span>
  </div>
  <div class="example_thmcontent">
  <p> The hydrodynamic equations (equilibrium problem <span class="cite">
	[
	<a href="#13" >13</a>
	]
</span>, is modeled as the following non-differentiable algebraic equations: </p>
<div class="displaymath" id="a0000000028">
  \[  Bx+\max (0,x)=c,  \]
</div>
<p>where \(B\in \mathbb {R}^{n\times n}\),\(c\in \mathbb {R}^{n}\) are given. Using the identity </p>
<div class="displaymath" id="a0000000029">
  \[  \max \left( a,b\right) =\tfrac {1}{2}\left( a+b+\left\vert a-b\right\vert \right) ,  \]
</div>
<p>equality, the hydrodynamic equation can be reformulated as an AVE <a href="#f1" class="eqref">1</a>. We have, \(Bx+\frac{1}{2}\left( x+\left\vert x\right\vert \right) =c\Leftrightarrow Ax-\left\vert x\right\vert -b=0 \) where \(A=-(2B+I)\) and \(b=-2c\).</p>
<p>Consider now, a randomly hydrodynamic equation where \(B\in \mathbb {R}^{n\times n}\) and \(c\) are given by: </p>
<div class="displaymath" id="a0000000030">
  \[  B=(b_{ij})=\left\{  \begin{array}{l} b_{ii}=-25.5, \\ b_{i,i+1}=a_{i+1,i}=-2.5, \\ b_{ij}=0,\end{array}\right.  \]
</div>
<p>and </p>
<div class="displaymath" id="a0000000031">
  \[  c=\left( -27,-29.5,\ldots ,-29.5,-27\right) ^{T}.  \]
</div>
<p>The initial points are \(x_{1}^{0}=(0.5,\ldots ,0.5)^{T}\) and \(x_{2}^{0}=(0.9,\ldots ,0.9)^{T}.\) The computational results with different size of \(n\), are summarized in <a href="#tab:t2">table 2</a>. </p>
<div class="table"  id="tab:t2">
   <small class="small"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> Size \(n\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=I\) (basic CGA) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=\frac{1}{n}I,n{\gt}1\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=A^{-1}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 11 \\ 0.0143 \\ {6.1357e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 8 \\ 0.0133 \\ {5.7939e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.0081 \\ {4.8013e-8}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(100\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 10 \\ 0.0170 \\ {5.6321e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 0.0113 \\ {5.1941e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 0.0068 \\ {2.0096e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 11 \\ 1.1760 \\ {5.8906e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 0.7838 \\ {2.5537e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 1.5308 \\ {4.8112e-8}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(1000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 10 \\ 1.1115 \\ {5.4239e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 0.6666 \\ {2.2815e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 1.1335 \\ {2.0219e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 11 \\ 8.9451 \\ {5.8609e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 4.7227 \\ {5.7002e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 5.5383 \\ {4.8116e-8}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(2000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 10 \\ 8.1684 \\ {5.4023e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 5 \\ 4.0932 \\ {5.0782e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 5.3227 \\ {2.0226e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 11 \\ 28.4459 \\ {5.8503e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 15.5639 \\ {3.7993e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 13.9749 \\ {4.8117e-8}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(3000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 10 \\ 25.7548 \\ {5.3948e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 5 \\ 12.8931 \\ {3.3853e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 10.7083 \\ {2.0228e-6}\end{array}\) </p>

    </td>
  </tr>
</table></small> <figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">2</span> 
  <span class="caption_text">Numerical results for <a href="#ex.4">example 4</a>.</span> 
</figcaption>  
</div>
<p>The true solution of this example is \(x^{\ast }=e.\) </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="ex.5">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">5</span>
  </div>
  <div class="example_thmcontent">
  <p> Given a matrix \(M\) and a vector \(q\), the LCP <span class="cite">
	[
	<a href="#3" >3</a>
	]
</span>, consists in finding \(w,\) \(z\in \mathbb {R}^{n}\) such that </p>
<div class="displaymath" id="a0000000032">
  \[  w\geq 0,\; z\geq 0,\, w-Mz=q,\, z^{T}w=0.  \]
</div>
<p> Letting \(w=\left\vert x\right\vert -x,\, \, z=\left\vert x\right\vert +x,\) then, \(w\geq 0,\, z\geq 0,\) and \(z^{T}w=0\). By substituting \(w\) and \(z\) in LCP, then an equivalent AVE <a href="#f1" class="eqref">1</a> with \(A=(I-M)^{-1}(I+M)\), and \(b=-(I-M)^{-1}q\), provided that \((I-M)\) is invertible, is obtained. Note that if \(x\) solves the AVE <a href="#f1" class="eqref">1</a>, then \(z=\left\vert x\right\vert +x\geq 0\) solves the LCP. Let \(M\in \mathbb {R}^{n\times n}\) and \(q\) be given as:</p>
<div class="displaymath" id="a0000000033">
  \begin{align*}  M=& (a_{ij})= \begin{cases}  0.6, &  \mbox{if } i=j, \\ -0.01, &  \mbox{if } \left\vert i-j\right\vert =1, \\ 0, &  \mbox{otherwise} ,\end{cases}\\ q=& -e. \end{align*}
</div>
<p>The initial points are \(x_{1}^{0}=(0.001,\cdots ,0.001)^{T}\) and \(x_{2}^{0}=(0.9,\cdots ,0.9)^{T}\) and the obtained computational results with different size of \(n\), are stated in <a href="#tab:t3">table 3</a>. </p>
<div class="table"  id="tab:t3">
   <small class="small"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> Size \(n\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=I\) (basic CGA) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=\frac{1}{n}I,n{\gt}1\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=A^{-1}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 0.0152 \\ {2.0378e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 5 \\ 0.0090 \\ {2.3141e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.0083 \\ {9.3375e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(100\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 0.0106 \\ {3.3940e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.0081 \\ {3.8226e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.0104 \\ {7.3068e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 1.6359 \\ {1.9182e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 1.0504 \\ {2.4378e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.9420 \\ {9.34412e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(1000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 1.4547 \\ {3.2870e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 0.6995 \\ {4.1163e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 0.9617 \\ {7.3117e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 7.2802 \\ {1.9091e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 4.1854 \\ {1.2187e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 4.1506 \\ {9.3440e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(2000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 6.1432 \\ {3.2795e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 3.0415 \\ {2.0590e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 4.8948 \\ {7.3116e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(x_{1}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 7 \\ 20.3593 \\ {1.9059e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 8.6417 \\ {6.7655e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 11.5123 \\ {9.3440e-6}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="text-align:left; border-right:1px solid black; border-left:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(3000\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(x_{2}^{0}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 6 \\ 18.1800 \\ {3.2770e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3 \\ 8.6375 \\ {1.3729e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:left; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 4 \\ 11.6423 \\ {7.3116e-6}\end{array}\) </p>

    </td>
  </tr>
</table></small> <figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">3</span> 
  <span class="caption_text">Numerical results for <a href="#ex.5">example 5</a>.</span> 
</figcaption>  
</div>
<p>The true solution is </p>
<div class="displaymath" id="a0000000034">
  \[  x^{\ast }=(0.8477,\, 0.8618,\, 0.8621,\ldots ,\, 0.8621,\, 0.8618,\, 0.8477)^{T},  \]
</div>
<p> and then </p>
<div class="displaymath" id="a0000000035">
  \[  z^{\ast }=(1.6954,1.7237,1.7241,\ldots ,1.7241,1.7237,1.6954)^{T}  \]
</div>
<p> is the solution of LCP. </p>

  </div>
</div> </p>
<p><div class="example_thmwrapper " id="ex.6">
  <div class="example_thmheading">
    <span class="example_thmcaption">
    Example
    </span>
    <span class="example_thmlabel">6</span>
  </div>
  <div class="example_thmcontent">
  <p> The matrices \(A\) and \(B\) are given by: </p>
<div class="displaymath" id="a0000000036">
  \begin{align*}  A=& (a_{ij})= \begin{cases}  a_{ii}=10001, &  \mbox{if } i=1, \\ a_{ij}=\frac{1}{i+j-1}, &  \mbox{if } i\neq j, \\ a_{ii}=\frac{1}{i+j-1}+1, &  i=j,i\neq 1,\end{cases}\\ B=& I. \end{align*}
</div>
<p>For example, if \(n=4\), then:</p>
<div class="displaymath" id="a0000000037">
  \[  A=\left( \begin{smallmatrix} 10001 &  \frac{1}{2} &  \frac{1}{3} &  \frac{1}{4} \\ \frac{1}{2} &  \frac{4}{3} &  \frac{1}{4} &  \frac{1}{5} \\ \frac{1}{3} &  \frac{1}{4} &  \frac{6}{5} &  \frac{1}{6} \\ \frac{1}{4} &  \frac{1}{5} &  \frac{1}{6} &  \frac{8}{7}\end{smallmatrix}\right).  \]
</div>
<p> The spectrum of \(A\) is given by \(\left\{  10001,1.657,1.0189,1.0002\right\} \). Since \(\lambda _{\min }(A)=1.0002{\gt} \lambda _{\max }(I)=1,\) then the AVE is uniquely solvable for any \(b\). The matrix \(A\) is ill-conditioned since \(\kappa (A)=\frac{10001}{1.0002}=9999 \gg 1\). Based on \(\kappa (A)\), we have deduced that \(\kappa (Q)\gg 1\) for some matrices \(D\) whose diagonal elements are \(1\), \(0\), or \(-1\), which confirms for \(n=4\) that \(Q\) is ill conditioned. For \(n \geq 4\), a careful investigation is needed to confirm the ill-conditioning of \(Q\). In fact, the matrix \(A\) is constructed from the Hilbert matrix, which is known to be ill-conditioned. </p>
<p>Next, for \(b=(A-I)e\in \mathbb {R}^{n},\) and with the initial point \(x_{0}=(0,0,\cdots ,0)^{T},\) the computational results for this example with different size of \(n\), are illustrated in <a href="#tab:t4">table 4</a>. </p>
<div class="table"  id="tab:t4">
   <div class="centered"><small class="small"><table class="tabular">
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p> Size \(n\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">&nbsp;</td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=I\) (basic CGA) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=\frac{1}{n}I, n{\gt}1\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(P=A^{-1}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p>4 </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 3530 \\ 0.1300 \\ {9.9959e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2701 \\ 0.0983 \\ {9.9952e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 0.0050 \\ {4.1168e-16}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p>10 </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \mbox{Iter} \\ \mbox{CPU(s)} \\ \mbox{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 16483 \\ 0.6712 \\ {9.9991e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 12079 \\ 0.4594 \\ {9.9983e-6}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 0.0051 \\ {6.753e-16}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-left:1px solid black" 
        rowspan=""
        colspan="">
      <p>1000 </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(*\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(*\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 0.2494 \\ {3.9550e-14}\end{array}\) </p>

    </td>
  </tr>
  <tr>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-left:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p>2000 </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} \text{Iter} \\ \text{CPU(s)} \\ \text{RSD}\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} * \\*\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} * \\*\end{array}\) </p>

    </td>
    <td  style="border-top-style:solid; border-top-color:black; border-top-width:1px; text-align:center; border-right:1px solid black; border-bottom-style:solid; border-bottom-color:black; border-bottom-width:1px" 
        rowspan=""
        colspan="">
      <p> \(\begin{array}{c} 2 \\ 1.5669 \\ {7.2000e-14}\end{array}\) </p>

    </td>
  </tr>
</table></small> <figcaption>
  <span class="caption_title">Table</span> 
  <span class="caption_ref">4</span> 
  <span class="caption_text">Numerical results for <a href="#ex.6">example 6</a>.</span> 
</figcaption>  </div>
</div>
<p>The "*" means that the basic CG and the preconditioned CG with \(P=\frac{1}{n} I,n{\gt}1\) algorithms failed. </p>
<p>The true solution of this example is \(x^{\ast }=e\). </p>

  </div>
</div> </p>
<h1 id="sect.5">5 Conclusion and future work</h1>
<p> In this paper, we have presented preconditioned conjugate gradient methods for solving the NP-hard absolute value equations. The obtained numerical results with the preconditioned matrix \(P=A^{-1}\) are the best since the number of iterations and the elapsed times are minimum compared with those obtained by the basic conjugate gradient algorithms \((P=I).\) We hope that the preconditioned absolute value equations serves as a basis for future research on other more choice for the preconditioned matrix \(P\) to intend an efficient study of the absolute value equations. </p>
<p><small class="footnotesize">  </small></p>
<div class="bibliography">
<h1>Bibliography</h1>
<dl class="bibliography">
  <dt><a name="1">1</a></dt>
  <dd><p><a href ="https://doi.org/10.23952/jnfa.2018.39"> <i class="sc">M. Achache, N. Hazzam</i>, <i class="it">Solving absolute value equations via linear complementarity and interior-point methods</i>, J. Nonl. Funct. Anal., 2018, pp.&#160;1–10. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="2">2</a></dt>
  <dd><p><a href ="https://doi.org/10.1155/2012/406232"> <i class="sc">M.A. Noor, J. Iqbal, E. Al-Said</i>, <i class="it">Residual iterative method for solving absolute value equations</i>, Abstract Appl. Anal., Article ID 406232, (2012), pp.&#160;1–9. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="3">3</a></dt>
  <dd><p><i class="sc">R.W. Cottle, J.S. Pang, R.E. Stone</i>, <i class="it">The Linear Complementarity Problem</i>, Academic Press, New-York, 1992. </p>
</dd>
  <dt><a name="4">4</a></dt>
  <dd><p><i class="sc">R. Fletcher</i>, <i class="it">Practical Methods of Optimization</i>, John Wiley and Sons, New-York, 1987. </p>
</dd>
  <dt><a name="5">5</a></dt>
  <dd><p><a href ="https://doi.org/10.1093/comjnl/7.2.149"> <i class="sc">R. Fletcher, C.M. Reeves</i>, <i class="it">Functions minimization by conjugate gradients</i>, Computational Journal, <b class="bf">7</b> (1964), pp.&#160;149–154. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="6">6</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s10589-017-9939-0"> <i class="sc">M. Hladick</i>, <i class="it">Bounds for the solution of absolute value equations</i>, Comput. Optimiz. Appl., <b class="bf">69</b> (2018), pp.&#160;243–266. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="7">7</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11590-011-0332-0"> <i class="sc">J. Iqbal, M.A. Noor, K.I. Noor</i>, <i class="it">On iterative method for solving absolute value equations</i>, Optimiz. Lett., <b class="bf">6</b> (2012), pp.&#160; 1027–1033. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="8">8</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.camwa.2012.03.015"> <i class="sc">S. Ketabchi, H. Moosaei</i>, <i class="it">An efficient method for optimal correcting of absolute value equations by minimal changes in the right hand side</i>, Comput. Math. Appl., <b class="bf">64</b> (2012), pp.&#160; 1882–1885. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="9">9</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11590-008-0094-5"> <i class="sc">O.L. Mangasarian</i>.<i class="it">A generalized Newton method for absolute value equations</i>. Optimiz. Lett. <b class="bf">3</b>, (2009), pp.&#160;101–108. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="10">10</a></dt>
  <dd><p><a href ="https://doi.org/10.1023/b:jota.0000026128.34294.77"> <i class="sc">O.L. Mangasarian</i>, <i class="it">A Newton method for linear programming</i>, J. Optim. Theory Appl., <b class="bf">121</b> (2004), pp.&#160; 1–18. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="11">11</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.laa.2006.05.004"> <i class="sc">O.L. Mangasarian, R.R. Meyer</i>, <i class="it">Absolute value equations</i>, Linear Algebra Appl., <b class="bf">419</b> (2006), pp.&#160;359–367. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="12">12</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.cam.2017.06.019"> <i class="sc">T. Migot, L. Abdellah, M. Haddou</i>, <i class="it">Solving absolute value equation using complementarity and smoothing functions</i>, Comput. Appl. Math., <b class="bf">327</b> (2018), <br />pp.&#160;196–207. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="13">13</a></dt>
  <dd><p><i class="sc">L. Lehmann, M. Radons, M. Rump, CH. Strom</i>, <i class="it">Sign controlled solvers for the absolute value equation with an application to support vector machines</i>, 2010. </p>
</dd>
  <dt><a name="14">14</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11590-009-0129-6"> <i class="sc">J. Rohn</i>, <i class="it">On unique solvability of the absolute value equations</i>, Optimiz. Lett., <b class="bf">3</b> (2009), pp.&#160;603–606. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="15">15</a></dt>
  <dd><p><a href ="https://doi.org/10.1007/s11590-011-0305-3"> <i class="sc">J. Rohn</i>, <i class="it">An algorithm for computing all solutions of an absolute value equation</i>, Optimiz. Lett., <b class="bf">6</b> (2012), pp.&#160;851–856. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="16">16</a></dt>
  <dd><p><a href ="https://doi.org/10.12988/ijcms.2007.07072"> <i class="sc">Y. Shi</i>, <i class="it">Modified quasi-Newton methods for solving systems of linear equations</i>, Int. J. Contemp. Math. Sci., <b class="bf">15</b> (2007), pp.&#160;737–744. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
  <dt><a name="17">17</a></dt>
  <dd><p><i class="sc">G. Zoutendijk</i>, <i class="it">Nonlinear Programming, Computational Methods</i>, in: Integer and Nonlinear Programming, J. Abadie, ed., North- Holland, Amsterdam, 1970, pp.&#160;37–86. </p>
</dd>
  <dt><a name="18">18</a></dt>
  <dd><p><a href ="https://doi.org/10.1016/j.amc.2005.11.128"> <i class="sc">N. Ujevic</i>, <i class="it">A new iterative method for solving linear systems</i>, Appl. Math. Comput., <b class="bf">179</b> (2006), pp.&#160;725–730. <img src="img-0001.png" alt="\includegraphics[scale=0.1]{ext-link.png}" style="width:12.0px; height:10.700000000000001px" />
</a> </p>
</dd>
</dl>


</div>
</div> <!--main-text -->
</div> <!-- content-wrapper -->
</div> <!-- content -->
</div> <!-- wrapper -->

<nav class="prev_up_next">
</nav>

<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/jquery.min.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/plastex.js"></script>
<script type="text/javascript" src="/var/www/clients/client1/web1/web/files/jnaat-files/journals/1/articles/js/svgxuse.js"></script>
</body>
</html>