Modified Iteration Algorithm for Solving Absolute Value Equations

Abstract

A new iterative algorithm has been proposed in this study for the efficient solution of the absolute value equation (AVE). Through an equivalent transformation, the AVE has been restructured into a two-by-two block nonlinear equation, which led to the development of our new iteration method. The convergence characteristics and optimal parameters of this approach have been analyzed, and new convergence conditions, differing from previous findings, have been introduced. Numerical experiments have demonstrated that the proposed strategy is both feasible and effective.

Headnote

A new iterative algorithm has been proposed in this study for the efficient solution of the absolute value equation (AVE). Through an equivalent transformation, the AVE has been restructured into a two-by-two block nonlinear equation, which led to the development of our new iteration method. The convergence characteristics and optimal parameters of this approach have been analyzed, and new convergence conditions, differing from previous findings, have been introduced. Numerical experiments have demonstrated that the proposed strategy is both feasible and effective.

Index Terms-Iterative algorithm, Absolute value equation, Convergence, Optimal parameters.

Abstract

I. INTRODUCTION

IN this study, we investigate the absolute value equation (AVE):

Az - |x| - b, (1)

where A = (a;;) € ВХ", b € В", and let |x| represent the absolute values of the components of vector x € К", that is |x| = (|z1], |72],...,|7n|)". The AVE of the form (1) has garnered significant scholarly interest due to its wide applicability across various domains. In practical and engineering contexts, AVE plays an important role, particularly in economic management, which facilitates the optimization of resource allocation and enhances decision-making processes. Within the mathematical discipline, the relevance of the AVE extends to several areas, such as linear programming problems [2-5]. Furthermore, the AVE is closely related to the computation of basis pursuit problems and the determination of generalized inverses [7, 8].

The generalized form of the equation (1) is

Ах + В |2| - b, (2)

where В € R™ ™. In [2], the generalized absolute value equation (GAVE) is introduced within a broader theoretical framework, leading to a series of scholarly inquiries documented umented in [3, 9]. The AVE is demonstrated to be transformable into an equivalent linear complementarity problem (LCP), as indicated in [3, 6]. In [10], Bai proposed a modular matrix splitting iterative method for solving the LCP, and subsequent research has extended Bai's method with various modulus-based iteration techniques [11]. Due to its equivalence with the LCP, which establishes a direct connection between the two problems, the AVE is also classified as an

Unique solvability criteria for both the specific AVE (1) and its generalized version (2) have been established [2, 3]. Notably, a demonstration by Mangasarian and Meyer [3] establishes the uniqueness of the solution to the AVE (1) for all constant vectors, provided that the smallest singular value of the corresponding matrix exceeds 1. Recently, the application of feasible iterative methods to obtain numerical solutions for the AVE (1) has been a focus of academic research. For instance, Mangasarian introduced a variant of the Newton method in [1] for solving the AVE, which generates a sequence defined by

(A - H(xP)) xD =p, 3)

where H(z) = diag(sign(x)), x € К". Additionally, Mangasarian provides the following sufficient conditions for the generalized Newton iterations (3) to converge linearly:

Proposition 1.1111 Suppose NA < + and H(x0)) #0. Under these conditions, for any vector b, the AVE presented in (1) possesses a unique solution, and the generalized Newton iteration method described in (3) is defined, this iteration method converges linearly from any initial starting point x) to the unique solution of the AVE (1).

In addition, a multitude of numerical techniques has been developed to address both linear and nonlinear matrix equations. Because the AVE (1) exhibits weak nonlinearity, the Picard method has attracted significant interest. Inspired by [12], Salkuyeh proposed an iterative approach, termed the Picard-HSS method to address the AVE [13]. Subsequently, Miao et al. [14] introduced an iterative framework, referred to as the Picard-SHSS approach, specifically designed for the AVE (1). Guo [15] combined the HSS and SHSS techniques by incorporating them into internal iterative loops, creating two residual update frameworks to address the GAVE. The SOR-like method, as highlighted in studies [16, 17], has been extensively used across various problem areas in recent times. Dong et al. [18] introduced the NSOR, a two-parameter technique, as an efficient solution for the AVE. Recently, the solution of the AVE has emerged as a focal point of ongoing research, evolving into an active area of investigation with an increasing number of scholars contributing to the field [19-21].

In this study, the AVE (1) is transformed into a nonlinear system. An iterative solution for matrix A satisfying the condition 0 < A < 2/2 is developed, and the effectiveness of the proposed approach is demonstrated. To validate the feasibility of the suggested technique, various numerical examples are provided.

Hereafter, the study is structured as follows: Section 2 presents the necessary notation and relevant lemmas. In Section 3, we introduce a novel approach for solving the AVE and examine its convergence. Sections 4 and 5 present the experimental results and conclusions.

II. PRELIMINARIES

In the following, we present relevant notations and preliminary results that will be utilized subsequently.

Let ВХ" represent all n x n real matrices and К" represent all n x 1 real matrices. For each à = 1,2,...,n, the à - th component of vector x € К" is represented by x;. The notation Г, represents the identity matrix, and the symbol ·7" denotes the n-dimensional identity matrix. The sign(x) function generates a vector whose components are determined as follows: for a real number m is satisfied

1, if m>0, if m=0, 4) if т < 0.

H(z) expresses the same meaning as (3), representing the diagonal matrix related to sign(x). If C = (c;;) € R" satisfies c;; > O(c;; > 0) forall 1 <mand>

The following conclusions contribute to the research presented in this study.

Proposition 2.15! Let A is a real matrix of n dimensions, if | AI] < 1, then the AVE in (1) has a unique solution for any be В".

Lemma 2.1 For any vector и € К", о € R", the following results hold:

(D) |lel = [oll] < flu - olf;

(2) if 0 < и <w,>

(3) if u < v and М is a nonnegative matrix, then Ми < Mv.

Lemma 2.2 For any matrix P € R"·", Q € R"·", if 0< P<q,>

III. NEW ALGORITHM

Let y = |x|, consider the equivalent of the AVE (1) to the following equation

Ах -y=0,

that is

~ A -Л\ /x b =

where г = [x,y], À = H(z) = diag(sign(x)), © = [b,0]7, х Е К". Let

- (A - A O 0 I к- (5 1)=(Za мег) (0 à) 7)

where a given positive constant. Consider

(& ato 1) GC) " (o ar) GC) (o): ©

that is

According to (9), Algorithm 3.1 is obtained as follows:

Here, we will validate the core conclusion regarding the convergence of the iterative process of Algorithm 3.1. We first define the iteration error: (x·,y·) is a pair of solutions satisfying (6), and (x) yl) is the sequence pair of each iteration of algorithm 3.1, where the iteration error is expressed as ef = z· - x) and el = y - у".

Theorem 3.1 Assume A € R™·™ be non-singular matrix, defines ||A7·|| = 8 and ·+1 = (Gr if €k+1

2 0< 3 < 2 (11)

and

1- 1 + \/1 - 6? 0<t>

the inequality

lH < le" | (13)

is ture for k = 0,1,2,....

Proof. We first have

ARTA (14) 1 A · - H · · и = Ar ay),

where (x·,y·) is a pair of solutions that satisfy (6), by subtracting (10) from (14), we can obtain

ef = Atel, (15)

and

Chil = Tra Tekn + ae). (16)

From (15), we have

lez | = A ex] < ||[4 || lle = Bllexl- (17)

According to (16) and Lemma 2.1, we obtain

1 7 xT ler = rafa + ací) | a = | chas + > x a "Te [Bda] + ETÜ ST Ita A le | Ia q Пе! 1 xT < тра НЙ + Es на. (18)

We get

1 я x Ca ) Ч) = © EĞ) o - Ita бы Tra Hex |

Further, let

1 0 M=| 1 1)? 0, (20) 1+a

and then let's consider it

Ue )= er)" CD

where

"(9 GE) ma 1 0 TA 0 В -u (o 2)- (o). © 1+ 1+a

we can obtain

0 0 0 ß ww (a aia) (o E) 8 TN + 0 0 = a 2). (23) o p+ (3)

Also, according to the Proposition 2.1, we consider

2 a+ В W 150% - 1 пи < ей + (FL) <

<> Ba? + 2(6? + В - о + 28? - 1 < 0.

(24)

If 0 < В < 1, then the two roots of the quadratic function is first given " the following equation

о, = 5 18) + 1200-1808 1), es

a = > [19)- VIRB) = 4820252 DI), 6

where h(6) = 2(1 - 8 - 6 ).

Obviously, we can obtain

1- 1- 4/1 - 62

then, if 0 < 8 < 1, clearly a; < O, this is a contradictory inequality.

We now need to discuss the range of a1, given the range of 6 established above.

Situation 1: If 0 <a,>< 1, that is

14/15 0< )( 7 9) 21, (29)

we get

3 v2 т = = 30 5

< 9 (30)

Therefore, и3 < 8 < Y and0 < а < DEV у1-6 y

it is ture that ||Wİ| < 1.

Situation 2: If a, > 1, that is

JU + 1-5?) 32

we get 3 0

Therefore, if 0 < 8 < 3

it is ture that |W] < 1.

Combining these two situations, if 0 < 8 < 2 and O < a < ar , we obtain |W || < 1.

Clearly, if the stipulations of Theorem 3.1 are fulfilled, then

0H SWE = - = WC]. 63) О

If |W] < 1, we can get Em |Е·|| = 0, Jim ler | = O and ¿im lle] = O is given by the definition of the 2-norm. -00 Based on Proposition 2.1, the sequence {z·)}, derived from (10), will converge to the unique solution of the AVE (1). The description has been completed.

IV. NUMERICAL EXPERIMENTS

Within this segment, we conduct computational trials to evaluate the effectiveness of Algorithm 3.1 in numerically deriving solutions for the AVE (1). We compare Algorithm 3.1 with the SOR-like method from [21] based on the iteration count (IT), the CPU processing time (in seconds), and the residual value, where «,,; and wopt denote the optimal parameter values for synthesis, which are not unique. Among the two test methods, the zero vector was selected as the universal starting point for each algorithm. The termination of the algorithm is triggered when the RES drops below 1078 or upon the iteration count exceeds 1000, where 'RES' represents the relative residual, that is

Art - [=] = o] Ho |

The complete set of numerical experiments was conducted on a personal computer with a 2.11 GHz Intel Core 15-10210U CPU and 16 GB of RAM, using MATLAB R2016b.

Example 4.1 Assume the AVE as presented in (1) to be

A = tridiag(-1,4, - 1) ER" x· = (=1,1, - 1,1,...)7,

and b = Ax" - |x·| in [16].

Table I presents the numerical results of the two test methods, including IT, CPU, and RES. Under the corresponding experimental optimal parameters, both test methods exhibit rapid convergence. The numerical results in Table I indicate that Algorithm 3.1 demonstrates superior computational efficiency compared to the SOR-like method, as evidenced by lower CPU usage and residual values.

Example 4.2 Assume the AVE as presented in (1) to be where A = A+41,2 and Ш

- 7 -Sn -İn 0 - 0 0 I, -S, -İn 0 0 A 0 -İn -Sn - 0 0 2.2 A - ; € К" xn , ` чо 0 0 0 -Sn -İn | 0 0 0 -In -$Sn|

where

CL Sn = tridiag(-1,4, - 1) | _ 4 -1 0 - 0 0 -1 4 1. 0 0 0 -{1 4 0 O x a - : о | © RS nxn 0 0 O 4 -l 0 0 0 -1 4

and b = ones(n?,1).

Table II presents the numerical results obtained from the two test methods. In this case, the optimal experimental parameters were selected following a comprehensive analysis of the numerical results. The data in Table II indicate that both methods converge quickly. Although Algorithm 3.1 requires more iterative steps, it achieves a higher convergence rate. Overall, the performance of Algorithm 3.1 is superior to that of the SOR-like method. Example 4.3 Assume the AVE as presented in (1) to be

А = A+61,2(6 > 0) and -z -I 0 - 0 0 | 1, Zn -h - 0 0 - 0 In -Zn ос 0 0 > A = . . ; . . ЕК" x", : : : : : 0 0 0 Zn In LO 0 0 -h -Z,]

а Zn = tridiag(-1,8, - 1) [8 - 0 - O 0] -1 8 -l 0 0 0 -1 8 0 0 - e RX" : О 0 0 O 8 -1 о 0 0 18 - -

a· =(-1,1,-1,...) € R" and b - Ax· - |a·| € в.

As shown in Table I, the numerical results of Example 4.3 are presented in Tables Ш and IV, these results are consistent with those reported in Tables I and II. Under specific и . . conditions, compared to the SOR-like method, Algorithm 3.1 demonstrates exceptional computational performance, enhancing time efficiency by nearly fifty percent.

V. CONCLUSIONS

In this paper, AVE (1) has been restructured into a nonlinear equation represented by 2-by-2 block matrix, and subsequently simplified to derive a new iterative algorithm. The convergence conditions for the proposed iterative method are examined in detail. Through numerical simulations, we illustrate the efficacy of our method, particularly in comparison to conventional methods like the SOR-like method. Furthermore, the selection of specific optimal parameters in theory, as well as the application of the proposed algorithm to practical problems, warrants further study.

References

REFERENCES

[1] O. L. Mangasarian, "A generalized Newton method for absolute value equations," Optimization Letters, vol. 3, pp. 101-108, 2009.

[2] J. Rohn, "A theorem of the alternatives for the equation Ax+B|x|=b," Linear and Multilinear Algebra, vol. 52, no. 6, pp. 421-426, 2004.

[3] О. L. Mangasarian, К. К. Meyer, "Absolute value equations," Linear Algebra and Its Applications, vol. 419, no. 2-3, pp. 359-367, 2006.

[4] S. L. Wu, P. Guo, "Modulus-based matrix splitting algorithms for the quasi-complementarity problems," Applied Numerical Mathematics, vol. 132, pp. 127-137, 2018.

[5] D. Е. Ding, М. L. Fang, Y. T. Sheng, and A. Xu, "A modulus-based Shamanskii-Like Levenberg-Marquardt method for solving nonlinear complementary problems," IAENG International Journal of Applied Mathematics, vol. 54, no. 3, pp. 411-416, 2024.

[6] S. J. Chung, "NP-completeness of the linear complementarity problem," Journal of Optimization Theory and Applications, vol. 60, pp. 393-399, 1989.

[7] T. Saha, S. Srivastava, S. Khare, et al. "An improved algorithm for basis pursuit problem and its applications," Applied Mathematics and Computation, vol. 355, pp. 385-398, 2019.

[8] M. D. Petkovié, М. A. Krstié, К. P. Rajkovié, "Rapid generalized Schultz iterative methods for the computation of outer inverses," Journal of Computational and Applied Mathematics, vol. 344, pp. 572-584, 2018.

[9] O. Prokopyev, "On equivalent reformulations for absolute value equations," Computational Optimization and Applications, vol. 44, pp. 363-372, 2009.

[10] 7. 7. Bai, "Modulus-based matrix splitting iteration methods for linear complementarity problems," Numerical Linear Algebra with Applications, vol. 17, no. 6, pp. 917-933, 2010.

[11] P. F. Dai, J. С. Li, J. С. Bai, and J. М. Qiu, "A preconditioned two-step modulus-based matrix splitting iteration method for linear complementarity problem," Applied Mathematics and Computation, vol. 348, pp. 542-551, 2019.

[12] 7. 7. Bai, X. Yang, "On HSS-based iteration methods for weakly nonlinear systems," Applied Numerical Mathematics, vol. 59, no. 12, pp. 2923-2936, 2009.

[13] D. K. Salkuyeh, "The Picard-HSS iteration method for absolute value equations," Optimization Letters, vol. 8, pp. 2191-2202, 2014.

[14] S. X. Miao, X. T. Xiong, J. Wen, "On Picard-SHSS iteration method for absolute value equation," AIMS Mathematics, vol. 6, no. 2, pp. 1743-1753, 2021.

[15] M. Guo, Q. B. Wu, "Two effective inexact iteration methods for solving the generalized absolute value equations," AIMS Mathematics, vol. 7, no. 10, pp. 18675-18689, 2022.

[16] Y. Е. Ke, С. Е. Ma, "SOR-like iteration method for solving absolute value equations," Applied Mathematics and Computation, vol. 311, pp. 195-202, 2017.

[17] Y. М. Zhang, D. М. Yu, Y. Е. Yuan, "On the alternative SOR-like iteration method for solving absolute value equations," Symmetry, vol. 15, no. 3, pp. 589, 2023.

[18] X. Dong, X. H. Shao, H. L. Shen, "A new SOR-like method for solving absolute value equations," Applied Numerical Mathematics, vol. 156, pp. 410-421, 2020.

[19] Y. F. Ke, "The new iteration algorithm for absolute value equation," Applied Mathematics Letters, vol. 99, pp. 105990, 2020.

[20] J. Y. Liu, T. T. Luo, С. К. Chen, "Further study on two fixed point iterative schemes for absolute value equations," Computational and Applied Mathematics, vol. 44, no. 1, pp. 1-13, 2025.

[21] X. H. Yu, Q. B. Wu, "Two efficient iteration methods for solving the absolute value equations," Applied Numerical Mathematics, vol. 208, pp. 148-159, 2025.