# A Two-Step Newton-Type Method for Solving System of Absolute Value Equations

Authors: Lei Shi; Javed Iqbal; Muhammad Arif; Alamgir Khan
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we suggest a Newton-type method for solving the system of absolute value equations. This new method is a two-step method with the generalized Newton method as predictor. Convergence of the proposed method is proved under some suitable conditions. At the end, we take several numerical examples to show that the new method is very effective.


---

## Body

## 1. Introduction

We consider the system of absolute value equations of the form:(1)Ax−x=b,where A∈Rn×n and b∈Rn are known vectors and x denotes the absolute values of the components of x∈Rn. The system of absolute value equations arises in optimization, the economies with institutional restrictions upon prices, the free boundary problems for journal bearing lubrication, and the network equilibrium problems, for example, see [1–12]. Mansoori and Erfanian [13] suggested a dynamic model to obtain the exact solution of equation (1). The development of multistep methods has gained popularity in the field of computational mathematics. Recently, several multistep methods are proposed to solve equation (1), for example, see [3–6].In this paper, we present a Newton-type method for solving the system of absolute value equations. The new method is a two-step method where the well-known numerical quadrature technique is used in the corrector step. The Newton-type method is very simple and easy to implement in practice. The existence and uniqueness of solution shows the importance of the suggested method. The convergence of the new method is discussed in Section 3. Numerical results prove that the Newton-type method is very effective for solving large systems.Forx∈Rn, consider(2)signx=−1,ifx<0,0,ifx=0,1,ifx>0.The diagonal matrixS corresponding to signx is defined as(3)Sx=∂x=diagsignx,where ∂x represents the generalized Jacobian of x. Note that Sxx=x.


## 2. Proposed Method

Consider(4)Hx=Ax−x−b.The generalized Jacobian ofH at x is(5)H′x=∂Hx=A−Sx,where Sx is a diagonal matrix and Sxx=x. We suggest the Newton-type method as(6)yk=A−Sxk−1b,xk+1=xk−4H′xk+2H′xk+yk2+H′yk−1Hxk,k=0,1,2,….The predictor step of equation (6) is the generalized Newton method [8], and the corrector step is the Trapezoidal method. The proposed method can be described as Algorithm1.Algorithm 1
Step 1: select an initial guessx0∈RnStep 2: start fork computeyk=A−Sxk−1bStep 3: usingyk computexk+1=xk−4H′xk+2H′xk+yk/2+H′yk−1HxkStep 4: ifxk+1=xk, then stop. If not, then put k=k+1 and turn back to step 2


## 3. Convergence Analysis

The predictor step is well defined (see Lemma 2 [8]):(7)yk=A−Sxk−1b.Now, we want to prove that(8)H′xk+2H′xk+yk2+H′yk=A−Sxk+2A−2Sxk+yk+A−Syk=4A−Sxk−2Sxk+yk−Syk,which is nonsingular.Lemma 1.
If the singular values ofA∈Rn×n exceed one, then 4A−Sxk−2Sxk+yk−Syk−1 exists for diagonal matrix S.Proof.
If4A−Sxk−2Sxk+yk−Syk is singular, then 4A−Sxk−2Sxk+yk−Sykx=0 for some x≠0. Since singular values of A exceed 1, therefore(9)xTx<xTATAx=116xTSxk+2Sxk+yk+SykSxk+2Sxk+yk+Sykx=116xTSxkSxk+SykSyk+2SykSxk+4Sxk+ykSxk+yk+4Sxk+ykSyk+4Sxk+ykSxkx≤11616xTx=xTx,which is a contradiction; hence, 4A−Sxk−2Sxk+yk−Syk is nonsingular. Subsequently, the sequence in (6) is well defined.In the next result, we establish boundedness of equation (6). Rewrite the corrector step of equation (6) as(10)xk+1=xk−4H′xk+2H′xk+yk2+H′yk−1Hxk.For simplicity, we let(11)E=H′xk+2H′xk+yk2+H′yk.Then, equation (10) converts into(12)xk+1=xk−4E−1Hxk,Exk+1=Exk−4Hxk=Exk−4Axk−xk−b=4A−Sxk−2Sxk+yk−Sykxk−4Axk−Sxkxk−b=3Sxk−2Sxk+yk−Sykxk+4bor(13)4A−Sxk−2Sxk+yk−ykxk+1=3Sxk−2Sxk+yk−Sykxk+4b.Lemma 2.
The sequence in equation (6) is bounded and well defined if the singular values of A exceed one. Hence, there exists an accumulation point x˙ such that(14)4A−S˙x˙−2S˙x˙+y˙−S˙y˙x˙=3S˙x˙−2S˙x˙+y˙−S˙y˙x˙+4b,A−S˙x˙x˙=b,for diagonal matrix S˙.Proof.
Proof of this Lemma is similar to the proof of Proposition 3 of [8].Now, we prove the main result about the convergence of the Newton-type method.Theorem 1.
If4A−Sxk−2Sxk+yk−Syk−1<1/12 for any diagonal matrix S with diagonal entries of 0 or ±1, then the Newton-type method converges to a solution x∗ of equation (1).Proof.
Consider(15)xk+1−x∗=xk−4E−1Hxk−x∗,Exk+1−x∗=Exk−x∗−4Hxk.
Sincex∗ is the solution of equation (1), therefore(16)Hx∗=Ax∗−x∗−b=0.
From equations15 and (16), we have(17)Exk+1−x∗=Exk−x∗−4Hxk+4Hx∗=Exk−x∗−4Hxk−Hx∗=Exk−x∗−4Axk−xk−Ax∗+x∗=E−4Axk−x∗−4x∗−xk=−Sxk+2Sxk+yk+Sykxk−x∗+4xk−x∗,or(18)xk+1−x∗=E−14xk−x∗−Sxk+2Sxk+yk+Sykxk−x∗.
ConsideringC=Sxk+2Sxk+yk+Syk yields(19)xk+1−x∗=E−14xk−x∗−Cxk−x∗,(20)xk+1−x∗≤E−18xk−x∗+Cxk−x∗.
In equation (19), we have used Lipschitz continuity of the absolute value (see Lemma 5 [8]); that is,(21)x−y≤2x−y.
SinceSxk, Syk, and 2Sxk+yk are diagonal matrices with elements equal to ±1 or 0, hence(22)C=Sxk+Syk+2Sxk+yk≤Sxk+2Sxk+yk+Syk≤4.
From equations (20) and (22), we have(23)xk+1−x∗≤12E−1xk−x∗<xk−x∗.
In equation (20), we have used the condition that E−1<1/12. Hence, the sequence xk converges linearly to x∗.Corollary 1.
LetA−1<1/13 and Sxk, Syk, and 2Sxk+yk are nonzero. Then, equation (1) is uniquely solvable for any b and the Newton-type method is well defined and converges to the unique solution of equation (1) for any initial guess x0.Proof.
The unique solvability of equation (1) for any b requires that A−1<1 [9]. A−1 exists, and 4A−1Sxk+2Sxk+yk+Syk<1. By Banach perturbation lemma [14], we have(24)H′xk+2H′xk+yk2+H′yk−1=4A−Sxk−2Sxk+yk−Syk−1≤4A−1Sxk+2Sxk+yk+Syk1−4A−1Sxk+2Sxk+yk+Syk≤1/4A−141−1/4A−14<1/131−1/13<112.
Hence, by Theorem1, the Newton-type method converges linearly to the solution of equation (1). This completes the proof.Remark 1.
In Section4, for the last two examples E−1>1/12, which shows that the Newton-type method may converge for E−1>1/12. The convergence is guaranteed for E−1<1/12.


## 4. Numerical Results

Now, we consider some numerical examples to show the performance of the new method. Let IT denote the number of iterations, RES is the residual, and CPU denotes the time in seconds. All the experiments are done with Intel(R) Core (TM)-5Y10c CPU @ 0.80 GHz 1.00 GHz, 4 GB RAM.Example 1.
(see [2]). Consider the matrix A as follows:
Rand (‘state’, 0); R = rand (m, m); A = R’∗ R + m ∗ eye(m); b = (A− eye (m, m)) ∗ones (m, 1). (Matlab code).We compare the Newton-type method (NTM) with the generalized Traub method (GTM) [5] and improved generalized Newton method (INM) [2]. Numerical results are given in Table 1.Table 1
Numerical results for Example1.
DimGTMINMNTMITRESCPUITRESCPUITRESCPU10031.1360e−110.028231.2528e−110.024827.0174e−120.010320038.0510e−110.057636.7278e−110.042821.2964e−120.019830032.8067e−100.062632.6026e−100.050423.3819e−120.020640036.8738e−100.116735.7847e−100.102127.4447e−120.101650031.1259e−090.228231.1792e−090.219121.1013e−110.217860032.1310e−090.341232.4023e−090.327324.5880e−110.315670032.9880e−090.384633.6051e−090.368524.9918e−110.351280045.1658e−090.531133.8475e−090.401526.2056e−110.395190046.9541e−090.689137.0228e−090.423621.4251e−100.4187100048.8558e−090.861637.3382e−090.551321.3938e−100.4563From the last column of Table1, we conclude that the Newton-type method converges to the approximate solution of (1.1) with high accuracy.Example 2.
(see [2]). Consider the matrix A as follows:
A = round(m∗ (eye(m, m)−0.02 ∗ (2 ∗ rand (m, m)−1))); (MATLAB code). Choose a random ν∈Rm and b=Aν−ν.We takem=1000 (problem size) and compare the Newton-type method (NTM) with the improved generalized Newton method (INM) [2] and the two-step iterative (TSI) method [3] graphically. Numerical results are illustrated in Figure 1.Figure 1
Convergence curves of different methods.Convergence curves show the efficiency of the proposed method. Figure1 illustrates that the convergence of the NTM is better than other two methods.Example 3.
Consider the heat equation as follows:(25)∂r∂tμ,t−∂2r∂μ2μ,t−rμ,t=0,0<μ<1,t>0,with(26)r0,t=r1,t=0,rμ,0=μ1−μ,0≤μ≤1.We use the finite differences to approximate the solution of heat equation. Define the distance step-sizeh=1/m for m>0 and the time step-size k such that μi=ih,i=,1,2,…,m−1, and tj=jk,j=1,2,…,. The partial derivative at the grid point μi,tj can be written as(27)∂r∂txi,tj=rμi,tj−rμi,tj−1k,∂2r∂μ2μi,tj=rμi+1,tj−2rμi,tj+rμi−1,tjh2.Comparison of equation (6) with Maple solutions is given in Figure 2.Figure 2
Convergence curves of different methods.Example 4.
(see [6]). Consider(28)A=tridiag−1,4,−1∈Rn×n,x∗=−1l,l=1…,nT∈Rn,and b=Ax∗−x∗.In this example, we compare the Newton-type method with the SOR-like method [6] and NINA [15]. Comparison is given in Table 2, where ERR=xk−x∗ and x∗ is the exact solution.Table 2
Numerical results for Example4.
Methodn100020003000400050006000NINAIT181818181818RES3.4947e − 074.9580e − 076.0786e − 077.0227e − 077.8541e − 078.6055e − 07ERR1.8652e − 072.6468e − 073.2453e − 073.7494e − 074.1934e − 074.5946e − 07CPU139.2571879.31433083.7005———SOR-like-IT151616161617RES9.8477e − 076.3197e − 077.7428e − 078.9422e − 079.9988e − 072.0134e − 07ERR4.4031e − 077.7428e − 071.2729e − 071.4701e − 071.6438e − 079.0038e − 08CPU0.99997.048223.484954.02271104.1137178.4376NTMIT222222RES1.1960e − 113.5203e − 116.3912e − 119.6775e − 111.4111e − 101.7906e − 10ERR3.2890e − 129.3320e − 121.6375e − 112.5658e − 113.5328e − 114.4462e − 11CPU0.79665.333918.074941.862180.8494137.7330Table2 shows that NTM converges to the solution in just 2 iterations with high accuracy.We taken=1000 (problem size) and compare the Newton-type method (NTM) with the SOR-like method [6] and NINA [11] graphically in Figure 3.Figure 3
Convergence curves of different methods.


## 5. Conclusion

In this paper, we developed the Newton-type method for solving the system of absolute value equations. This new iterative method is very simple and easy to implement. The future work is to extend this idea by taking more than three points in the corrector step. The numerical results show the efficiency and accuracy of the proposed method.



---

*Source: 2798080-2020-12-17.xml*