A general modulus-based matrix splitting method for quasi-complementarity problem

1.   Introduction

Consider the quasi-complementarity problem (QCP) ^[28,35], to find a couple of vector solutions $z, w \in \mathbb{R}^{n}$ such that

where $A = (a_{ij}) \in \mathbb{R}^{n\times n}$ and $q \in \mathbb{R}^{n}$ are given, $\Psi(\cdot)$ is a nonlinear transformation from $\mathbb{R}^{n}$ into itself and $\Phi(\cdot)$ denotes a point-to-point mapping. Here and in the sequel, '$\geqslant$' denotes the componentwise defined partial ordering between two vectors and $(\cdot)^T$ stands for the transpose of either a vector or a matrix. In fact, the QCP (1.1) can be regarded as a generalized case of many well-known complementarity problems ^[21]. In greater detail, if $\Phi(\cdot)$ is the zero mapping, then the QCP (1.1) reduces to the weakly or restricted nonlinear complementarity problem (WNCP) ^[25]. If $\Psi(\cdot) = 0$, then the QCP (1.1) reduces to the implicit complementarity problem (ICP) ^[11,19]. If the conditions about $\Phi(\cdot)$ and $\Psi(\cdot)$ mentioned above are met simultaneously, then the QCP (1.1) reduces to the well-known linear complementarity problem (LCP) ^[2,13,14].

As is well-known, many problems in engineering and economics applications result in the form of QCP and its special cases, including the linear and quadratic programming ^[13], the Nash equilibrium problems ^[12], the traffic bottleneck model simulation ^[10,30], the free boundary problems ^[37], the nonnegatively constrained image restoration ^[15] and so on, see ^[13,16,21] and references therein for more details. Due to the exponential computational complexity of direct complementarity pivot algorithms, iterative methods for solving the QCP (1.1) are preferred and widely studied. For instance, the inexact Newton methods ^[27,29], the projected methods ^[24], the matrix multisplitting iteration method ^[1,4,5], the modulus-based matrix splitting (MMS) iteration methods ^[2,14,32,35] and so forth. Among these existing iterative methods, the MMS iteration method has attracted considerable attention due to its simple structure and high performance.

The modulus method was first devised to solve the finite-dimensional discrete linear complementarity problems ^[31]. The basic idea of the modulus method is to cast the LCP as an absolute value equation (AVE) ^[34] by setting two nonnegative and orthogonal vectors and construct high efficiency algorithm to solve the AVE. Then, on one hand, abundant improvements have been done to accelerate the convergence rate and improve the computing efficiency of the modulus method, including the modified modulus-based iteration method ^[14], the modulus-based matrix splitting (MMS) iteration method ^[2], the general MMS iteration method ^[26], the two-step MMS iteration method ^[23,36], the modulus-based synchronous multisplitting iteration method ^[8] and so on. On the other hand, the classical modulus method and its improvements have been extended to study the ICP ^[11,19,22], the WNCP ^[25,38], the QCP ^[32,35]. Numerical results indicate that the modulus-based iteration methods perform much better than the Newton-based iteration methods and the projected iteration methods.

Let $g(z) = z-\Phi(z)$ be invertible and $A = M-N$ be a splitting of the matrix $A \in \mathbb{R}^{n\times n}$. By introducing a positive parameter $\gamma > 0$, a positive diagonal matrix $\Omega$ and letting

then $z = g^{-1}(\frac{1}{\gamma}(|x|+x))$ and the QCP (1.1) can be equivalently expressed as the following implicit fixed point equation

Further, define a set

then the MMS iteration method is briefly summarized as follow.

Method 1.1. ^[35] (The MMS iteration method for QCP)

Step 1. Given $\varepsilon > 0$, $z^{ (0)}\in Z$, set $k = 0$.

Step 2. Find the solution $z^{(k+1)}$:

(1) Calculate the initial vector

and set $j$ = 0.

(2) Compute $x^{(j+1, k)}$ by iteratively solving

(3) Compute

Step 3. If $RES (z^{(k+1)}) = |(Az^{(k+1)}+q+\Psi (z^{(k+1)}))^{T} (z^{(k+1)}-\Phi (z^{(k+1)}))| < \varepsilon$, then stop; otherwise, set $k = k+1$ and return to step 2.

It can be seen from Method 1.1 that the MMS iteration method for solving the QCP (1.1) belongs to a class of inner-outer iteration methods. Depending on that the step of inner iteration $j$ is fixed or varies with the number of outer iteration $k$, the MMS iteration method can be classified into two categories, i.e. the stationary and nonstationary MMS methods. Generally speaking, the convergence rate of the inner solver has great impact on the global convergence rate ^[11,36].

To improve the convergence rate of the inner iteration of the MMS iteration method so as to obtain fast global convergence rate, inspired and motivated by the general MMS iteration method studied in ^[26] for solving the LCP, we propose a general modulus-based matrix splitting (GMMS) iteration method for solving the QCP (1.1). In the GMMS iteration method, an additional diagonal matrix is introduced for $g(z)$. Through the selection of appropriate diagonal matrices, the GMMS iteration method not only covers the existing MMS method, but also leads to a new series of modulus-based relaxation methods. Convergence conditions are analyzed in detail when the system matrix is either an $H_{+}$-matrix or a positive definite matrix. Moreover, in the case of $H_{+}$-matrix, weaker convergence conditions than that given in [35,Theorem 3.3] can be obtained.

The rest of this paper is organized as follows. In Section 2, we establish the GMMS iteration method for solving the QCP (1.1). Convergence conditions of the GMMS iteration method are proved in Section 3. In Section 4, two numerical examples are presented to demonstrate the effectiveness and advantages of the new proposed GMMS iteration method. Finally, we end this paper with a brief conclusion and outlook in Section 5.

2.   A general modulus-based matrix splitting iteration method

Let $\Omega_1\in \mathbb{R}^{n\times n}$, $\Omega_2\in \mathbb{R}^{n\times n}$ be two positive diagonal matrices, and

then we have

Further let $A\Omega_{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ be a splitting of $A\Omega_1 \in \mathbb{R}^{n\times n}$. Then similar to (1.2), we can transform the original QCP (1.1) into the following implicit fixed-point equation with respect to $x$:

It follows from [35,Theorem 3.1] that if $x$ is a solution of (2.1), then $(z, w) = (g^{-1}(\Omega_1(|x|+x)), \Omega_2(|x|-x))$ is a solution pair of the QCP (1.1).

Based on (2.1), the initial set (1.3) and the MMS iteration method (Method 1.1), a general modulus-based matrix splitting iteration method is proposed as follows.

Method 2.1. (The GMMS iteration method for QCP)

Step 1. Given $\varepsilon > 0$, $z^{ (0)}\in Z$, set $k = 0$.

Step 2. Find the solution $z^{(k+1)}$:

(1) Calculate the initial vector

and set $j$ = 0.

(2) Compute $x^{(j+1, k)}$ by iteratively solving

(3) Compute

Step 3. If $RES (z^{(k+1)}) = |(Az^{(k+1)}+q+\Psi (z^{(k+1)}))^{T} (z^{(k+1)}-\Phi (z^{(k+1)}))| < \varepsilon$, then stop; otherwise, set $k = k+1$ and return to step 2.

Remark 2.1. In particular, if $\Omega_1 = \frac{1}{\gamma}I$, $\Omega_2 = \frac{1}{\gamma}\Omega$, $M_{\Omega_1} = \frac{1}{\gamma}M$ and $N_{\Omega_1} = \frac{1}{\gamma}N$, then (2.3) can be rewritten as

which reduces to the MMS iteration scheme in ^[35].

From the new proposed GMMS iteration method (see Method 2.1) and the original MMS iteration method (see Method 1.1), we see that only the inner iteration (i.e. the second step) is different. As we discussed in Section 1, the inner iteration is critical for the MMS iteration method. Here, we provide a general framework for the inner iteration. With suitable choices of the positive diagonal matrices $\Omega_1$ and $\Omega_2$, we can speed up the inner iteration so as to get fast convergence rate of the outer iteration.

We would emphasize that the implicit fixed-point equation (2.1) is a weakly nonlinear system ^[3,7]. By selecting different parameter matrices, Method 2.1 can also yield a series of general modulus-based relaxation methods. More specifically, let $A\Omega_1 = D_{A\Omega_1}-L_{A\Omega_1}-U_{A\Omega_1}$, with $D_{A\Omega_1}$, $-L_{A\Omega_1}$, $-U_{A\Omega_1}$ being the diagonal, strictly lower-triangular, and strictly upper-triangular matrices of $A\Omega_1$, respectively. Then four specific iteration schemes can be obtained:

(a) When $M_{\Omega _{1}} = D_{A\Omega _{1}}$ and $N_{\Omega _{1}} = L_{A\Omega _{1}}+U_{A\Omega _{1}}$, Method 2.1 is known as the general modulus-based Jacobi (GMJ) iteration method.

with $z^{(k+1)} = \Omega _{1} (| x^{(j+1, k)} |+x^{(j+1, k)})+\Phi (z^{(k)})$.

(b) When $M_{\Omega _{1}} = D_{A\Omega _{1}}-L_{A\Omega _{1}}$ and $N_{\Omega _{1}} = U_{A\Omega _{1}}$, Method 2.1 is named as the general modulus-based Gauss-Seidel (GMGS) iteration method.

with $z^{(k+1)} = \Omega _{1} (| x^{(j+1, k)} |+x^{(j+1, k)})+\Phi (z^{(k)})$.

(c) When $M_{\Omega _{1}} = \frac{1}{\alpha }D_{A\Omega _{1}}-L_{A\Omega _{1}}$ and $N_{\Omega _{1}} = (\frac{1}{\alpha } - 1)D_{A\Omega _{1}}+U_{A\Omega _{1}}$, Method 2.1 is referred to as the general modulus-based successive overrelaxation (GMSOR) iteration method.

with $z^{(k+1)} = \Omega _{1} (| x^{(j+1, k)} |+x^{(j+1, k)})+\Phi (z^{(k)})$.

(d) When $M_{\Omega _{1}} = \frac{1}{\alpha }(D_{A\Omega _{1}}-\beta L_{A\Omega _{1}})$ and $N_{\Omega _{1}} = \frac{1}{\alpha }\left [(1-\alpha)D_{A\Omega _{1}}+ (\alpha -\beta)L_{A\Omega _{1}}+\alpha U_{A\Omega _{1}}\right]$, Method 2.1 reduces to the general modulus-based accelerated overrelaxation (GMAOR) iteration method.

with $z^{(k+1)} = \Omega _{1} (| x^{(j+1, k)} |+x^{(j+1, k)})+\Phi (z^{(k)})$.

The above four modulus-based splitting iteration methods based on classical matrix splitting iteration methods for system of linear equations ^[6]. Obviously, computational workload of solving the inverse of system matrix $A$ can be reduced. In addition, the relaxation parameters $\alpha$ and $\beta$ can be tuned in order to improve the convergence speed in GMAOR method. But in practice, different combination of parameters $\alpha$ and $\beta$ have a great influence on the iteration steps. As a result, the GMGS iteration method appears to be more competitive compared with the GMSOR and GMAOR methods.

Remark 2.2. In actual computations, the choices of the parameter matrices $\Omega_1$ and $\Omega_2$ in the GMMS iteration method are flexible. One can choose $tI\; (t > 0)$, or $sD_A\; (s > 0)$ with $D_A$ being the diagonal matrix of $A$, or other positive diagonal matrices with unequal diagonal elements. By suitable choosing the parameter matrices, faster convergence rate of the proposed GMMS iteration method can be obtained.

3.   Convergence analysis

In this section, we will make convergence analysis on the GMMS iteration methods when the system matrix $A$ of the QCP(1.1) is an $H_+$-matrix and a positive definite matrix.

The following notations, definitions and lemmas are to be used in the subsequent sections. Let $A = (a_{ij})$, $B = (b_{ij}) \in \mathbb{R}^{n \times n}$ be two square matrices. Define $A \geqslant B\ (A > B)$ if $a_{ij} \geqslant b_{ij}\ (a_{ij} > b_{ij})$, for all $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant n$. We say $A$ is a nonnegative (positive) matrix if $a_{ij} \geqslant 0\ (a_{ij} > 0)$. $A$ is called a $Z$-matrix if $a_{ij} \leqslant 0$ for any $i\neq j$. If $A$ is a $Z$-matrix and $A^{-1} \geqslant 0$, then $A$ is an $M$-matrix. If the comparison matrix $\langle A\rangle = (\langle a\rangle_{ij})\in\mathbb{R}^{n\times n}$, where we define

is an $M$-matrix, $A$ is called an $H$-matrix. In particular, an $H$-matrix is called an $H_+$-matrix when its diagonal entries are positive.

We use $sp(A)$, $\rho(A)$ to represent the spectrum and the spectral radius of the matrix $A$, respectively. The splitting $A = M-N$ is an $M$-splitting if $M$ is a nonsingular $M$-matrix and $N$ is nonnegative. $A = M-N$ is called an $H$-splitting if $\langle M \rangle - |N|$ is an $M$-matrix. Further, if $\langle A\rangle = \langle M\rangle-|N|$, then $A = M-N$ is called an $H$-compatible splitting ^[9]. $I$ is the identity matrix of the corresponding scale.

Lemma 3.1. ^[18] Let $A \in \mathbb{R}^{n\times n}$ be an $M$-matrix and $B \in \mathbb{R}^{n\times n}$ be an $Z$-matrix. If $A \leqslant B$, then $B$ is an $M$-matrix.

Lemma 3.2. ^[17] If $A \in \mathbb{R}^{n\times n}$ is an $H_{+}$-matrix, then $|A^{-1}| \leqslant \langle A\rangle^{-1}$.

Lemma 3.3. ^[33] Let $A \in \mathbb{R}^{n\times n}$, then $\rho (A) < 1$ iff $\lim\limits_{n\to+\infty} A^{n} = 0$.

Lemma 3.4. ^[6] $A \in \mathbb{R}^{n \times n}$ is a generalized strictly diagonally dominant matrix if and only if there exists a positive diagonal matrix $D$ such that the matrix $AD$ is strictly diagonally dominant.

Lemma 3.5. ^[20] Let $B \in \mathbb{R}^{n\times n}$ be a strictly diagonally dominant (s.d.d.) matrix, then for any matrix $C \in \mathbb{R}^{n\times n}$,

holds, where $e = (1, 1, \dots 1)^T$.

Assume that $z^{(*)}$ is the exact solution of the QCP (1.1) and $x^{(*)}$ is the exact solution of the implicit fixed point equation (2.1). And from (2.2)–(2.4), we have

and

3.1.   The case of $H_{+}$-matrix

In this subsection, we derive sufficient convergence conditions for the GMMS iteration method when the system matrix $A$ is an $H_{+}$-matrix. To this end, the following two notations are introduced:

Theorem 3.1. Let $\Omega_{1}, \Omega_{2} \in \mathbb{R}^{n\times n}$ be two positive diagonal matrices, $A \in \mathbb{R}^{n\times n}$ be an $H_{+}$-matrix and $A\Omega _{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ be an $H$-splitting of the matrix $A\Omega_1$. Let $\Phi (\cdot)$ and $\Psi (\cdot)$ be two Lipschitz continuous functions, and satisfy

$l_{1}$, $l_{2}$ are Lipschitz constants. $D$ is a positive diagonal matrix and $\langle M_{\Omega_1} \rangle - |N_{\Omega_1}|$ is a generalized strictly diagonally dominant matrix. If

where $\|\delta _{1}\|_{2} < 1$, then the sequence $\left \{ z^{(k)}\right \}_{k = 0}^{+\infty}$ generated by GMMS method converges to the unique solution $z^{(*)}$ of the QCP (1.1) for any initial values for the vector $z^{(0)} \in Z$.

Proof. Since $A\Omega _{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ is an $H$-splitting of the matrix $A\Omega_1$, $\hat{A}_{\Omega_1} = \langle M_{\Omega_1} \rangle - |N_{\Omega_1}|$ is an $M$-matrix. Evidently, $\langle M_{\Omega_1}\rangle \geqslant \hat{A}_{\Omega_1}$, by Lemma 3.1, $\langle M_{\Omega_1} \rangle$ is an $M$-matrix and $\Omega_2 + M_{\Omega_1}$ is an $H_+$-matrix. Again by the application Lemma 3.2, we have

Subtracting (3.1) from (2.4) and taking the absolute value, we obtain

Substituting $x^{(*)}$ into (2.3) and then subtracting from (2.3) gives

Then

From (3.2) and (2.2),

Thus,

Let $\bar Y = \Omega _{1}\delta _{1}^{j+1}(|\Omega _{1}^{-1}-\Omega _{2}^{-1}A|+l_{1}|\Omega _{1}^{-1}|+l_{2}|\Omega _{2}^{-1}|)+2\Omega _{1}\delta _{2}\sum_{i = 0}^{j}\delta _{1}^{i}+l_{1}I$, now we just have to prove that $\rho (\bar Y) < 1$.

From Lemma 3.4, since $\langle M_{\Omega_1} \rangle - |N_{\Omega_1}|$ is a generalized s.d.d., there exists a positive diagonal matrix $D$ such that $(\langle M_{\Omega_1} \rangle - |N_{\Omega_1}|)D$ is s.d.d. And by Lemma 3.5, we have $\rho (\delta _{1}) < 1$, refer to ^[26] for detailed proof. Then by Lemma 3.3, $\lim\limits_{j\to+\infty}\delta _{1}^{j+1} = 0$ holds true. Therefore, for any $\epsilon_1 > 0$, there exists $J_1$ such that for all $j \geqslant J_{1}$, $\|\Omega _{1}\delta _{1}^{j+1}\|_{2}\leqslant \epsilon_1$. Note that $\|\ |\Omega _{1}^{-1}-\Omega _{2}^{-1}A|+l_{1}|\Omega _{1}^{-1}|+l_{2}|\Omega _{2}^{-1}|\ \|_{2}$ is a constant. Hence, there is a positive integer $J_{1}$ such that

for any $\epsilon_1 > 0$ ($\epsilon_1 \ll 1$). Finally, we acquire

This completes the proof.

Remark 3.1. In Theorem 3.1, $A\Omega _{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ is assumed to be an $H$-splitting of the matrix $A\Omega _{1}$, whereas the condition in [35,Theorem 3.3] is required $A = M-N$ to be an $H$-compatible splitting of the matrix $A$. We present a simple example to show that our convergence condition weakens from $H$-compatible splitting to $H$-splitting. Suppose that $\Omega _{1} = I$, the matrix $A$ and the splitting matrices of $A\Omega _{1}$ are

Obviously, one can see from the above simple example, this way of splitting does not satisfy [35,Theorem 3.3], but it is possible in Theorem 3.1.

3.2.   The case of positive definite matrix

In this subsection, the convergence analysis of the GMMS iteration method is analyzed when the system matrix $A$ is a positive definite matrix.

Theorem 3.2. Let $\Omega_{1}, \Omega_{2}\in \mathbb{R}^{n\times n}$ be two positive diagonal matrices, $A \in \mathbb{R}^{n\times n}$ be a positive definite matrix and $A\Omega _{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ be a splitting of the matrix $A\Omega_1$. Define $\eta _{1} = \|(\Omega _{2}+ M_{\Omega _{1}})^{-1}N_{\Omega_{1}}\|_{2}+\|(\Omega _{2}+ M_{\Omega _{1}})^{-1}(\Omega _{2}-A\Omega _{1})\|_{2}$, $\eta _{2} = \|(\Omega _{2} + M_{\Omega _{1}})^{-1}A\|_{2}l_{1}+\|(\Omega _{2}+ M_{\Omega _{1}})^{-1}\|_{2}l_{2}$. Suppose that $\Phi (\cdot)$ and $\Psi (\cdot)$ are Lipschitz continuous functions, i.e., for any $s, t \in \mathbb{R}^{n}$ satisfy

where $l_{1}$, $l_{2}$ are Lipschitz constants. If

holds true, then for any initial vector $z^{(0)} \in Z$, the sequence $\left \{ z^{(k)}\right \}_{k = 0}^{+\infty}$ generated by GMMS iteration method converges to the unique solution $z^{(*)}$ of the QCP (1.1).

Proof. Similar to the analysis of Theorem 3.1, subtracting (3.1) from (2.4) and taking the 2-norm on both sides give the error expression:

Substituting $x^{(*)}$ into (2.3) and subtracting from (2.3), we have

Then

Subtracting (3.2) from (2.2) and take the 2-norm, we have

Thus, the inequality holds,

It can be seen from (3.3), the iteration method of Method 2.1 converges to the unique solution of the QCP (1.1) for any initial vector $z^{(0)} \in Z$. This completes the proof.

In particular, if $\Omega_{1} = \omega_1 I$, $\Omega_{2} = \omega_2 I \in \mathbb{R}^{n\times n}$ are positive diagonal matrices, define $\tau = \|A\|_2$, then

naturally, we can draw the following corollary.

Corollary 3.1. Let $\Omega_{1} = \omega_1 I$, $\Omega_{2} = \omega_2 I \in \mathbb{R}^{n\times n}$ be two positive diagonal matrices, $A\Omega _1 = M_{\Omega _1}-N_{\Omega _1}$ be a splitting of the matrix $A\Omega_1$ and $A \in \mathbb{R}^{n \times n}$ be a positive definite matrix. Define $\tau = \|A\|_2$, $\eta _{1} = \|(\Omega _{2}+ M_{\Omega _{1}})^{-1}N_{\Omega_{1}}\|_{2}+\|(\Omega _{2}+ M_{\Omega _{1}})^{-1}(\Omega _{2}-A\Omega _{1})\|_{2}$, $\eta _{2} = \|(\Omega _{2} + M_{\Omega _{1}})^{-1}A\|_{2}l_{1}+\|(\Omega _{2}+ M_{\Omega _{1}})^{-1}\|_{2}l_{2}$. Suppose that $\Phi (\cdot)$ and $\Psi (\cdot)$ are Lipschitz continuous functions, i.e., for any $s, t \in \mathbb{R}^{n}$ satisfy

where $l_{1}$, $l_{2}$ are Lipschitz constants. If

holds true, then for any initial vector $z^{(0)} \in Z$, the sequence $\left \{ z^{(k)}\right \}_{k = 0}^{+\infty}$ generated by GMMS iteration method converges to the unique solution $z^{(*)}$ of the QCP (1.1).

Suppose that $M_{\Omega_{1}} \in \mathbb{R}^{n\times n}$ is a symmetric positive definite matrix and $\Omega_{2} = \omega I \in \mathbb{R}^{n\times n}$ is a positive scalar matrix, a specific sufficient condition for the convergence is discussed in the next theorem.

Theorem 3.3. Let $A\Omega _{1} = M_{\Omega_{1}}-N_{\Omega_{1}}$ be a splitting of the matrix $A\Omega_1 \in \mathbb{R}^{n\times n}$ with $M_{\Omega_{1}} \in \mathbb{R}^{n\times n}$ being symmetric positive definite, $\Omega_{2} = \omega I \in \mathbb{R}^{n\times n}$ being a positive scalar matrix. Use $\lambda_{max}$ and $\lambda_{min}$ to represent the largest and smallest eigenvalues of the matrix $M_{\Omega_{1}}$. Define $\tau_{1} = \|M_{\Omega_{1}}^{-1}N_{\Omega_{1}}\|_{2}$, $\tau_{2} = \|M_{\Omega_{1}}^{-1}(\Omega_{2}-A\Omega_{1})\|_{2}$. If the Lipschitz constant $l_{1}$ and the iteration parameter $\omega$ meet the following conditions:

then the iteration sequence $\{z^{(k)}\}_{k = 0}^{\infty}\in \mathbb{R}^{n}_{+}$ generated by Method 2.1 converges to the unique solution $z^{(*)}$ of the QCP (1.1) for any initial vector $z^{(0)}\in Z$.

Proof. We only need to prove the condition for (3.3) is true. From the characteristics of the matrices $M_{\Omega_{1}}$ and $\Omega _{2}$, we have

Analogously, we have

Hence, it holds that when $\omega > \lambda_{max}(\tau_1+\tau_2-1)$, then

accordingly, $\lim\limits_{j\to+\infty}\eta_{1}^{j+1} = 0$. Note that $\|\Omega _{1}\|_{2}((1+l_{1})\|\Omega _{1}^{-1}\|_{2}+(\|A\|_{2}+l_{2})\|\Omega _{2}^{-1}\|_{2})$ is a constant. Therefore, there must exist a positive integer $J_2$ such that for any $\epsilon_2 > 0$, when $j \geqslant J_2$, the following inequality holds:

From $\eta_1 < 1$, we can derive

Combine (3.3), (3.5) and (3.6), we can find a small enough $\epsilon_2 > 0(\epsilon_2 \ll 1)$ for all $j \geqslant J_2$, it satisfies

Therefore, when $j\to+ \infty$, we have $\eta _{1}^{j+1}\|\Omega _{1}\|_{2}((1+l_{1})\|\Omega _{1}^{-1}\|_{2}+\frac{1}{\omega}(\|A\|_{2}+l_{2})+2\|\Omega _{1}\|_{2}\eta _{2}\sum\limits_{i = 0}^{j}\eta _{1}^{i}+l_{1} < 1$ provided that the condition (3.4) holds. This completes the proof.

4.   Numerical experiments

In this section, two numerical experiments are performed to verify the effectiveness of Method 2.1 for solving the QCP (1.1). Both experiments are investigating the factors of iteration steps (denoted by "IT"), the elapsed CPU time in seconds (denoted by "CPU") and residual errors (denoted by "RES"). Experiment 1 is studying when the matrix considered is symmetric, while Experiment 2 is focusing on a nonsymmetric case.

In our experiments, "RES" is defined as

initially, the vector $z^{(k)}$ is chosen to be $z^{(0)} = (0, 0, \cdots 0)^{T}\in \mathbb{R}^{n}$. For Method 1.1, we take $\Omega = 7I, \gamma = 1$. For Method 2.1, we take $\Omega _{1} = 0.06D_A$, $D_A = diag(A)$, $\Omega _{2} = I$. Parameters $\alpha$ and $\beta$ are experimentally found optimal ones, which lead to the least iteration steps. The total step of inner iteration is set $j = 2$ in both Methods 1 and 2 to simplify the process. The termination criteria is $RES(z^{(k)})\leqslant 10^{-6}$, or when $k$ reaches the maximum number of iterations, e.g. 50. Both experiments are performed in MATLAB (R2018b) where all variables are defined as double. Intel(R) Core(TM) with i7-10710U CPU and 16 GB RAM, under Windows 10 operating system are used. Table 1 lists the abbreviations used in the following description of the experiments.

4.1.   Experiment 1-the case of symmetric ^[32]

Let $m$ be a positive integer and $n = m^{2}$. Consider QCP (1.1), in which $A = \hat{A}+\mu I \in \mathbb {R}^{n \times n}$ and $q \in \mathbb {R}^{n}$ are defined as follows.

is a symmetric block tridiagonal matrix,

is a tridiagonal matrix, and

the point-to-point mapping $\Phi(z)$ and the nonlinear transformation $\Psi(\cdot)$ are defined as

In the Experiment 1, we take $\mu = 0$ and $\mu = 1$, respectively. Five different sizes of matrix $A$ are analyzed with $n$ is given the values of 900, 3600, 14400, 57600, 230400. For each matrix size, seven iteration methods have been employed with $\sigma = 0.01$. The three performance evaluation indicators are given in Tables 2 and 3 when $\mu = 0$ and $\mu = 1$ respectively. In addition, the factor of $\sigma$ is investigated by giving it three different values: 0.001, 0.01 and 0.1, when the size of matrix $n = 14400$ and $\mu = 1$. The results are shown in Table 4.

The findings are as follows:

(a) For most methods except GMSOR and GMAOR methods when $\mu = 0$, $\sigma = 0.01$ and $n = 3600$, the iteration steps increase with the size of the matrix. However, all the methods can converge rapidly in spite of the size $n$.

(b) MGS requires the most number of iteration steps while the proposed GMAOR method needs the least number of iterations. The proposed GMSOR method achieves a similar performance as the GMAOR.

(c) The three proposed methods: GMGS, GMAOR and GMSOR demonstrate a slight improvement in terms of iteration steps and elapsed CPU times. GMMS iteration method uses almost half of iteration steps of MMS, especially when $\mu = 0$.

(d) The proposed three methods show a close performance for all three indicators, however, GMAOR and GMSOR need extra-optimization on the parameter $\alpha$ and $\beta$ to complete the calculation.

4.2.   Experiment 2-the case of nonsymmetric ^[32]

Given that $m$ to be a positive integer and $n = m^{2}$ in the QCP (1.1), where $A = \widehat{A}+\mu I \in \mathbb {R}^{n \times n}$ and $q \in \mathbb {R}^{n}$ are defined as follows.

is a nonsymmetric block tridiagonal matrix,

is a block tridiagonal matrix, and $q$ is still,

the $\Phi(z)$ is the same as in the Experiment 1, and $\Psi(z)$ are defined as

In this experiment, we also take $\mu = 0$ and $\mu = 1$. Five different matrix sizes are considered, i.e. $n = 900, 3600, 14400, 57600, 230400$. The results are shown in the Tables 5 and 6 for $\mu = 0$ and $\mu = 1$ respectively.

From Tables 5 and 6, we find:

(a) The GMAOR method requires the least number of iterations among the proposed three methods. For the four conventional methods, MAOR needs the least.

(b) The GMAOR method can obtain a better performance when $\mu = 1$ than that when $\mu = 0$, where the system matrix $A$ is strictly diagonally dominant when $\mu = 1$.

(c) GMMS achieves a similar performance despite the chosen value for $n$.

4.3.   Discussions

It has been verified that the proposed GMMS iteration methods including GMGS, GMSOR and GMAOR are much more efficient than that conventional MMS based methods. The performance is improved in both the running time and the iteration steps. The effectiveness of the proposed methods were proved regardless the status of symmetry for the system matrix.

In particular, GMGS method can converge without a need for $\alpha$ and $\beta$ optimization such as in GMSOR and GMAOR, but with a slight increase in iteration steps. This implies that it might be more useful in practice. Compared with the conventional methods, the three proposed methods involve two scalar matrices rather than one, this added complexity to make a choice in the computation. However, the benefit from the proposed methods weighs out the cost.

5.   Conclusions

For solving QCP (1.1), the general modulus-based matrix splitting iteration method including GMGS, GMSOR, GMAOR are proposed. They are analogy to the MMS methods but with a better convergence rate. Two experiments have been performed to verify the effectiveness of the proposed methods considering the factor of symmetry condition of the system matrix. It is indicated that the methods are more efficient for all three indicators. It was proven that the more stringent conditions for the $H$-compatible splitting employed in the classic methods are relaxed to a simpler one, i.e., $H$-splitting. GMGS method can converge without requiring optimization on the parameters $\alpha$ and $\beta$, which is considered to be more useful in practice.

Acknowledgments

This work was supported by the QingLan Project of Jiangsu Province, the '226' Talent Scientific Research Project of Nantong City, and the Science and Technology Project of Nantong City (No. JC2021198).

Conflict of interest

We declare no conflicts of interest in publishing this article.