A two-step iteration method for the horizontal nonlinear complementarity problem

Abstract

In this paper, for solving horizontal nonlinear complementarity problem (HNCP), a two-step modulus-based matrix splitting iteration method is established. The convergence analysis of the proposed method is presented. Numerical examples are reported to show the efficiency of the proposed method.

1 Introduction

The horizontal nonlinear complementarity problem (HNCP) is a generalization of some complementarity problems, such as horizontal linear complementarity problem (HLCP), nonlinear complementarity problem (NCP), linear complementarity problem (LCP) [4, 7, 8]. Given $A,B\in {\mathbb {R}}^{n\times {n}}$, $q\in {\mathbb {R}}^n$ and a nonlinear $\varphi :{\mathbb {R}}^n\times {\mathbb {R}}^n\rightarrow {\mathbb {R}}^n$, we focus on solving HNCPs with weak nonlinearity, which consist in finding two vectors $z,r\in {\mathbb {R}}^{n}$ such that

$$\begin{aligned} Az-Br+q+\varphi (z,r)=0,~z,r\ge 0 ~\text {and}~z^{T}r=0, \end{aligned}$$

(1)

where for $F=(f_{ij}), G=(g_{ij})\in {\mathbb {R}}^{m\times {n}}$, the order $F\ge (>) G$ means $f_{ij}\ge (>) g_{ij}$ for any i and j.

The HNCP can arise in some applications, for example from the discretization of the differential equation in hydrodynamic lubrication with complementarity constraints and a weak nonlinear source term [5, 9, 12, 13, 18]. Recently, for solving the HNCP, by reforming the HNCP to an equivalent implicit fixed-point system, the modulus-based matrix splitting (MMS) iteration method was introduced in [16], which generalizes the MMS iteration methods for LCP [2], NCP [11, 19] and HLCP [14, 15, 28, 30], and was shown to be more efficient than the reduction approaches of the HNCP. To see more details on the MMS iteration methods for different complementarity problems, readers can refer to the recent works [17, 21, 24, 26, 27] and the references therein.

In particular, among the existing improved techniques of the MMS, the two-step splittings had been successfully used in LCP [22, 23], NCP [20, 25] and HLCP [29], by making full use of the information contained in the two system matrices. It is interesting to investigate the two-step splittings in the MMS of the HNCP. In this paper, in order to achieve higher computing efficiency, in Sect. 2, we establish the two-step modulus-based matrix splitting (TMMS) iteration method for the HNCP, which directly extends the ones in [16] and [29]. In Sect. 3, the convergence theorems of the proposed method are given, which generalize the existing results. Next, numerical examples are presented to show the efficiency of the proposed method in Sect. 4. Finally, concluding remarks are given in Sect. 5.

Next, we introduce some definitions, notations and existing results.

Let $A=(a_{ij})\in {\mathbb {R}}^{n\times {n}}$ and $A=D_A-L_A-U_A=D_A-C_A$, where $D_A, -L_A, -U_A$ and $-C_A$ denote the diagonal, the strictly lower-triangular, the strictly upper-triangular and the nondiagonal matrices of A, respectively. By |A| we denote $|A|=(|a_{ij}|)$. $\langle {A}\rangle =(\langle {a_{ij}}\rangle )$ is the comparison matrix of A, where $\langle {a_{ii}}\rangle =|a_{ii}|$ if $i = j$ and $\langle {a_{ij}}\rangle =-|a_{ij}|$ if $i\ne {j}$. We call A a Z-matrix if $C_{A} \le 0$; a nonsingular M-matrix if $C_A\le 0$ and $A^{-1}\ge 0$; an H-matrix if $\langle {A}\rangle$ is a nonsingular M-matrix; an $H_+$-matrix if A is an H-matrix with positive diagonal entries; a strictly diagonal dominant (s.d.d.) matrix if $|a_{ii}|>\sum \limits _{j\ne i}|a_{ij}|$ for all $1\le i\le n$ (e.g., see [1, 3]). If $\langle A\rangle =\langle M\rangle -|N|$, we call $A=M-N$ an H-compatible splitting. Denote the identity matrix of order n and the Kronecker product by $I_n$ and “$\otimes$”, respectively.

2 Two-step method

First, the MMS iteration method for solving the HNCP is reviewed.

Let $A=M_A-N_A, B=M_B-N_B$ be two splittings of A and B, respectively. Then, with $z=\frac{1}{\gamma }(|x|+x)$ and $r=\frac{1}{\gamma }\varOmega (|x|-x)$, the HNCP can be equivalently transformed into a system of fixed-point equations

$$\begin{aligned} (M_B\varOmega +M_A)x=(N_B\varOmega +N_A)x+(B\varOmega -A)|x|-\gamma (q+\varphi (z,r)), \end{aligned}$$

(2)

where $\varOmega$ is a positive diagonal parameter matrix and $\gamma$ is a positive constant; see [16] for more details. The MMS iteration method is presented based on (2) as follows:

Method 1

[16] Let $\varOmega \in {\mathbb {R}}^{n\times n}$ be a positive diagonal matrix, $\gamma$ be a positive constant and $A=M_A-N_A, B=M_B-N_B$ be two splittings of the matrix $A\in {\mathbb {R}}^{n\times n}$ and $B\in {\mathbb {R}}^{n\times n}$, respectively. Given an initial vector $x^{(0)}\in {\mathbb {R}}^{n}$, compute $x^{(k+1)}\in {\mathbb {R}}^{n}$ by solving the linear system

$$\begin{aligned} (M_B\varOmega +M_A)x^{(k+1)}=(N_B\varOmega + N_A)x^{(k)}+(B\varOmega -A)|x^{(k)}|-\gamma (q+\varphi (z,r)). \end{aligned}$$

Then set $z^{(k+1)}=\frac{1}{\gamma }(|x^{(k+1)}|+x^{(k+1)})$ and $r^{(k+1)}=\frac{1}{\gamma }\varOmega (|x^{(k+1)}|-x^{(k+1)})$ for $k=0,1,2,\ldots$, until the iteration sequence $\{(z^{(k)},r^{(k)})\}_{k=1}^{+\infty }$ is convergent.

To achieve high computing efficiency, making use of the information in the matrices A and B by two matrix splittings, the TMMS iteration method for solving the HNCP is established as follows:

Method 2

Two-step modulus-based matrix splitting iteration method for the HNCP For any given positive diagonal matrix $\varOmega \in {\mathbb {R}}^{n\times n}$ and $\gamma >0$, let $A=M_{A_1}-N_{A_1}=M_{A_2}-N_{A_2}$ be two splittings of the matrix $A\in {\mathbb {R}}^{n\times n}$, while $B=M_{B_1}-N_{B_1}=M_{B_2}-N_{B_2}$ be two splittings of the matrix $B\in {\mathbb {R}}^{n\times n}$. Given an initial vector $x^{(0)}\in {\mathbb {R}}^{n}$, compute $x^{(k+1)}\in {\mathbb {R}}^{n}$ by solving

$$\begin{aligned} \left\{ \begin{array}{ll} (M_{B_1}\varOmega +M_{A_1})x^{(k+\frac{1}{2})}=&{}(N_{B_1}\varOmega +N_{A_1})x^{(k)}+(B\varOmega -A)|x^{(k)}|\\ &{}-\gamma (q+\varphi (z^{(k)},r^{(k)})), \\ (M_{B_2}\varOmega +M_{A_2})x^{(k+1)}=&{}(N_{B_2}\varOmega +N_{A_2})x^{(k+\frac{1}{2})}+(B\varOmega -A)|x^{(k+\frac{1}{2})}|\\ &{}-\gamma (q+\varphi (z^{(k+\frac{1}{2})},r^{(k+\frac{1}{2})})). \end{array} \right. \end{aligned}$$

(3)

Then set $z^{(k+1)}=\frac{1}{\gamma }(|x^{(k+1)}|+x^{(k+1)})$ and $r^{(k+1)}=\frac{1}{\gamma }\varOmega (|x^{(k+1)}|-x^{(k+1)})$ for $k=0,1,2,\ldots$, until the iteration sequence $\{(z^{(k)},r^{(k)})\}_{k=1}^{+\infty }$ is convergent.

Furthermore, if we take

$$\begin{aligned} \left\{ \begin{array}{ll} M_{A_1}=\frac{1}{\alpha }(D_{A}-\beta {L_{A}}),M_{A_2}=\frac{1}{\alpha }(D_{A}-\beta {U_{A}}), \\ M_{B_1}=\frac{1}{\alpha }(D_{B}-\beta {L_{B}}),M_{B_2}=\frac{1}{\alpha }(D_{B}-\beta {U_{B}}), \end{array} \right. \end{aligned}$$

(4)

we can obtain the two-step modulus-based accelerated overrelaxation (TMAOR) iteration method. Taking $\alpha =\beta$ and $\alpha =\beta =1$, the TMAOR iteration method reduces to the two-step modulus-based successive overrelaxation (TMSOR) iteration method and the two-step modulus-based Gauss-Seidel (TMGS) iteration method, respectively.

It is noted that Method 2 generalizes some existing methods for various complementarity problems:

• if $M_{A_1}=M_{A_2}, N_{A_1}=N_{A_2}, M_{B_1}=M_{B_2}$ and $N_{B_1}=N_{B_2}$, Method 2 reduces to Method 1.

• if $M_{B_1}=M_{B_2}=I, N_{B_1}=N_{B_2}=0$ and $\varphi (z,r)=\varphi (z)$, Method 2 reduces to the two-step modulus-based matrix splitting iteration method for the NCP [20, 25].

• if $\varphi =0$, Method 2 reduces to the two-step modulus-based matrix splitting iteration method for the HLCP [29].

• if $M_{B_1}=M_{B_2}=I, N_{B_1}=N_{B_2}=0$ and $\varphi =0$, Method 2 reduces to the two-step modulus-based matrix splitting iteration method for the LCP [22].

3 Convergence analysis

Some useful lemmas are given first.

Lemma 1

[6] Let A be an H-matrix. Then $|A^{-1}|\le \langle {A}\rangle ^{-1}$.

Lemma 2

[10] Let $B\in {{\mathbb {R}}^{n\times n}}$ be an s.d.d. matrix. Then, $\forall C\in {{\mathbb {R}}^{n\times n}}$,

$$\begin{aligned} ||{B^{-1}C}||_\infty \le {\max \limits _{1\le i\le n}\frac{(|C|e)_i}{(\langle {B}\rangle e)_i}} \end{aligned}$$

holds, where $e=(1,1,\ldots ,1)^T\in {\mathbb {R}}^n$.

Lemma 3

[3] If A is a nonsingular M-matrix, then there exists a positive diagonal matrix D, such that AD is an s.d.d. matrix with positive diagonal entries.

In the following discussion, we assume that the HNCP has an unique solution $(z^{*},r^{*})$. Moreover, we also assume that $\varphi (z,r)$ satisfies the smoothness assumptions as those in [16] as below: let

$$\begin{aligned} \varphi (z,r)=\left( \varphi _1(z_1,r_1),\varphi _2(z_2,r_2),\ldots ,\varphi _n(z_n,r_n)\right) ^T \end{aligned}$$

be differentiable with

$$\begin{aligned} 0\le \frac{\partial \varphi _i}{\partial z_i}\le \psi _{z_i}~~\text {and}~~0\le \frac{\partial \varphi _i}{\partial r_i}\le \psi _{r_i}, \end{aligned}$$

where $\psi _{z_i}, \psi _{r_i}\ge 0, i=1,2,\ldots ,n$.

Then by the same deduction as that in Sect. 3 of [16], we have

$$\begin{aligned}&\varphi (z^{(k)},r^{(k)})-\varphi (z^*,r^*)\nonumber \\&\quad =\frac{1}{\gamma }\left[ (\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega )(x^{(k)}-x^{*})+(\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega )(|x^{(k)}|-|x^{*}|) \right] , \end{aligned}$$

(5)

with $\varPhi _z^{(k)}\le \varPsi _z$ and $\varPhi _r^{(k)}\le \varPsi _r$, where

$$\begin{aligned}&\varPhi _z^{(k)}=\text {diag}\left( \frac{\partial \varphi _1}{\partial z_1}(\eta _1),\frac{\partial \varphi _2}{\partial z_2}(\eta _2),\ldots ,\frac{\partial \varphi _n}{\partial z_n}(\eta _n) \right) ,\\&\varPhi _r^{(k)}=\text {diag}\left( \frac{\partial \varphi _1}{\partial r_1}(\eta _1),\frac{\partial \varphi _2}{\partial r_2}(\eta _2),\ldots ,\frac{\partial \varphi _n}{\partial r_n}(\eta _n) \right) ,\\&\varPsi _z=\text {diag}(\psi _{z_1},\psi _{z_2},\ldots ,\psi _{z_n}),\\&\varPsi _r=\text {diag}(\psi _{r_1},\psi _{r_2},\ldots ,\psi _{r_n}), \end{aligned}$$

and $\eta _i$ is a convex combination of $(z_i^{(k)},r_i^{(k)})$ and $(z_i^{*},r_i^{*})$, $i=1,2,\ldots ,n$.

Then, by (2) and straightforward computation, we can get that $x^{*} = \frac{\gamma }{2} (z^{*} - \varOmega ^{-1}r^{*})$ satisfies the implicit fixed-point equations

$$\begin{aligned} \left\{ \begin{array}{l} (M_{B_1}\varOmega +M_{A_1})x^{*}=(N_{B_1}\varOmega +N_{A_1})x^{*}+(B\varOmega -A)|x^{*}|-\gamma (q+\varphi (z^{*},r^{*})), \\ (M_{B_2}\varOmega +M_{A_2})x^{*}=(N_{B_2}\varOmega +N_{A_2})x^{*}+(B\varOmega -A)|x^{*}|-\gamma (q+\varphi (z^{*},r^{*})). \end{array} \right. \end{aligned}$$

(6)

By subtracting (6) from (3), we have the error equations:

$$\begin{aligned} \left\{ \begin{array}{ll} (M_{B_1}\varOmega +M_{A_1})(x^{(k+\frac{1}{2})}-x^{*})=&{}(N_{B_1}\varOmega +N_{A_1})(x^{(k)}-x^{*})\\ &{}+(B\varOmega -A)(|x^{(k)}|-|x^{*}|)\\ &{}-\gamma [\varphi (z^{(k)},r^{(k)})-\varphi (z^*,r^*)]\\ (M_{B_2}\varOmega +M_{A_2})(x^{(k+1)}-x^{*})=&{}(N_{B_2}\varOmega +N_{A_2})(x^{(k+\frac{1}{2})}-x^{*})\\ &{}+(B\varOmega -A)(|x^{(k+\frac{1}{2})}|-|x^{*}|)\\ &{}-\gamma [\varphi (z^{(k+\frac{1}{2})},r^{(k+\frac{1}{2})})-\varphi (z^*,r^*)].\\ \end{array} \right. \end{aligned}$$

(7)

To prove $\lim \limits _{k\rightarrow +\infty } {z^{(k)}}= z^{*}$ and $\lim \limits _{k\rightarrow +\infty } {r^{(k)}}= r^{*}$, we need only to prove $\lim \limits _{k\rightarrow +\infty } {x^{(k)}}= x^{*}$.

Theorem 3.1

Let $\varOmega =(\omega _{jj})$ be an $n\times n$ positive diagonal matrix and $A,B\in {\mathbb {R}}^{n\times n}$ be two $H_{+}$-matrices. Let D be a positive diagonal matrix such that $\langle A\rangle D$ is an s.d.d. matrix. Assume that $A=M_{A_1}-N_{A_1}=M_{A_2}-N_{A_2}$ and $B=M_{B_1}-N_{B_1}=M_{B_2}-N_{B_2}$ are two H-compatible splittings of A and B, respectively; $|b_{ij}|\omega _{jj}\le |a_{ij}|~~(i\ne j)$ and $\text {sign}(b_{ij})=\text {sign}(a_{ij})~~(b_{ij}\ne 0)$, for all i, j; and $D_B\ge \varPsi _r$. Then for any initial vector $x^{(0)}\in {\mathbb {R}}^{n}$, the iteration sequence $\{(z^{(k)},r^{(k)})\}_{k=1}^{+\infty }$ generated by Method2converges to the unique solution $(z^{*},r^{*})$ of the HNCP provided

$$\begin{aligned} (D_B-\varPsi _r)\varOmega \ge (D_A+\varPsi _z) \end{aligned}$$

(8)

or

$$\begin{aligned} (|C_A|+\varPsi _z)De<(D_B-\varPsi _{r})\varOmega De~~\text {and}~~(D_B-\min \limits _{1\le i\le n}\psi _{r_i})\varOmega \le D_A+\min \limits _{1\le i\le n}\psi _{z_i}. \end{aligned}$$

(9)

Proof

By the assumption of H-compatible splittings, we have

$$\begin{aligned}&\langle M_{B_1}\varOmega + M_{A_1}\rangle De\nonumber \\&\quad \ge (\langle M_{B_1}\rangle \varOmega + \langle M_{A_1}\rangle )De\nonumber \\&\quad =(\langle A\rangle +\langle B\rangle \varOmega +|N_{A_1}|+|N_{B_1}|\varOmega )De\nonumber \\&\quad \ge (D_A+D_B\varOmega -|C_A|-|C_B|\varOmega )De. \end{aligned}$$

(10)

Since $|b_{ij}|\omega _{jj}\le |a_{ij}|~~(i\ne j)$ and $\text {sign}(b_{ij})=\text {sign}(a_{ij})~~(b_{ij}\ne 0)$, for all i, j, we get

$$\begin{aligned} |C_A|\ge |C_B|\varOmega \Rightarrow |C_A+C_B\varOmega |+|C_A-C_B\varOmega |=2|C_A|. \end{aligned}$$

(11)

By (10) and (11), we can obtain

$$\begin{aligned}&\langle M_{B_1}\varOmega + M_{A_1}\rangle De\nonumber \\&\quad \ge \left\{ \begin{array}{ll} (2D_A-2|C_A|+\varPsi _z+\varPsi _r\varOmega )De\ge 2\langle A\rangle De>0,&{}\text {if (8) holds}; \\ (D_A-|C_B|\varOmega +\varPsi _z+\varPsi _r\varOmega )De>(D_A-|C_A|)De=\langle A\rangle De>0,&{} \text {if (9) holds}. \end{array} \right. \end{aligned}$$

Therefore, $\langle M_{B_1}\varOmega + M_{A_1}\rangle D$ is an s.d.d. matrix, which implies that $M_{B_1}\varOmega + M_{A_1}$ is an H-matrix. Then, by Lemma 1, (5) and the first equality of (7), we have

$$\begin{aligned}&|x^{(k+\frac{1}{2})}-x^{*}|\\&\quad =\Big |(M_{B_1}\varOmega +M_{A_1})^{-1}\left\{ (N_{B_1}\varOmega +N_{A_1})(x^{(k)}-x^{*})+(B\varOmega -A)(|x^{(k)}|-|x^{*}|)\right. \\&\qquad \left. -\gamma [\varphi (z^{(k)},r^{(k)})-\varphi (z^*,r^*)]\right. \}\Big |\\&\quad =\Big |(M_{B_1}\varOmega +M_{A_1})^{-1}\left[ (N_{B_1}\varOmega +N_{A_1}-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega )(x^{(k)}-x^{*})\right. \\&\qquad \left. +(B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega )(|x^{(k)}|-|x^{*}|)\right] \Big |\\&\quad \le \langle M_{B_1}\varOmega + M_{A_1}\rangle ^{-1}(|N_{B_1}\varOmega +N_{A_1}-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |\\&\qquad +|B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |)|x^{(k)}-x^{*}|\\&\quad \doteq {\mathcal {P}}_1|x^{(k)}-x^{*}|\\&\quad \doteq {\mathcal {M}}_1^{-1}{\mathcal {N}}_1|x^{(k)}-x^{*}|, \end{aligned}$$

where

$$\begin{aligned} {\mathcal {M}}_1=\langle M_{B_1}\varOmega + M_{A_1}\rangle \end{aligned}$$

and

$$\begin{aligned} {\mathcal {N}}_1=|N_{B_1}\varOmega +N_{A_1}-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |+|B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |. \end{aligned}$$

Similarly, by the second equality of (7), we have

$$\begin{aligned} |x^{(k+1)}-x^{*}|\le {\mathcal {P}}_2|x^{(k+\frac{1}{2})}-x^{*}|={\mathcal {M}}_2^{-1}{\mathcal {N}}_2|x^{(k+\frac{1}{2})}-x^{*}|, \end{aligned}$$

where

$$\begin{aligned} {\mathcal {M}}_2=\langle M_{B_2}\varOmega + M_{A_2}\rangle \end{aligned}$$

and

$$\begin{aligned} {\mathcal {N}}_2=|N_{B_2}\varOmega +N_{A_2}-\varPhi _z^{(k+\frac{1}{2})}+\varPhi _r^{(k+\frac{1}{2})}\varOmega |+|B\varOmega -A-\varPhi _z^{(k+\frac{1}{2})}-\varPhi _r^{(k+\frac{1}{2})}\varOmega |. \end{aligned}$$

By Lemma 2, we have

$$\begin{aligned} ||D^{-1}{\mathcal {P}}_1D||_\infty =||({\mathcal {M}}_1D)^{-1}({\mathcal {N}}_1D)||_\infty \le \max \limits _{1\le i\le n}\frac{({\mathcal {N}}_1De)_i}{({\mathcal {M}}_1De)_i}. \end{aligned}$$

(12)

If (8) holds, we obtain

$$\begin{aligned}&{\mathcal {M}}_1De-{\mathcal {N}}_1De\nonumber \\&\quad =(\langle M_{B_1}\varOmega + M_{A_1}\rangle -|N_{B_1}\varOmega +N_{A_1}-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |\nonumber \\&\qquad -|B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |)De\nonumber \\&\quad \ge (\langle M_{B_1}\varOmega \rangle +\langle M_{A_1}\rangle -|N_{B_1}\varOmega |-|N_{A_1}|-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega -D_B\varOmega +D_A\nonumber \\&\qquad +\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega -|C_A|+|C_B\varOmega |)De\nonumber \\&\quad =2\langle A\rangle De\nonumber \\&\quad >0. \end{aligned}$$

(13)

If (9) holds, we obtain

$$\begin{aligned}&{\mathcal {M}}_1De-{\mathcal {N}}_1De\nonumber \\&\quad =(\langle M_{B_1}\varOmega + M_{A_1}\rangle -|N_{B_1}\varOmega +N_{A_1}-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |\nonumber \\&\qquad -|B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |)De\nonumber \\&\quad \ge (\langle M_{B_1}\varOmega \rangle +\langle M_{A_1}\rangle -|N_{B_1}\varOmega |-|N_{A_1}|-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega +D_B\varOmega -D_A\nonumber \\&\qquad -\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega -|C_A|+|C_B\varOmega |)De\nonumber \\&\quad \ge 2[(D_B-\varPsi _r)\varOmega -|C_A|-\varPsi _z] De\nonumber \\&\quad >0. \end{aligned}$$

(14)

Then, by (12), (13) and (14), we have $||D^{-1}{\mathcal {P}}_1D||_\infty <1$. Similarly, we can get

$$\begin{aligned} ||D^{-1}{\mathcal {P}}_2D||_\infty <1 \end{aligned}$$

if (8) or (9) holds. Hence the next inequality holds:

$$\begin{aligned}&\rho ({\mathcal {P}}_2{\mathcal {P}}_1)\\&\quad =\rho ({D}^{-1}{\mathcal {P}}_2{\mathcal {P}}_1D)\\&\quad \le ||{D}^{-1}{\mathcal {P}}_2DD^{-1}{\mathcal {P}}_1D||_\infty \\&\quad \le ||{D}^{-1}{\mathcal {P}}_2D||_\infty ||D^{-1}{\mathcal {P}}_1D||_\infty \\&\quad <1, \end{aligned}$$

which implies that $\lim \limits _{k\rightarrow +\infty } {x^{(k)}}= x^{*}$, proving the claim. $\square$

Remark 1

If we take $\varphi (z,r)=0$, which implies $\varPsi _z=\varPsi _r=0$, then Theorem 3.1 reduces to Theorem 3.1 of [29].

Remark 2

If $\psi _{r_i}=\psi _{r_j}$ for any i, j, then (9) can be simplified to

$$\begin{aligned} (|C_A|+\varPsi _z)De<(D_B-\varPsi _{r})\varOmega De\le (D_A+\min \limits _{1\le i\le n}\psi _{z_i})De. \end{aligned}$$

Note that the assumption on the matrix splittings in Theorem 3.1 are H-compatible splittings. It is known that the TMAOR with $\alpha >1$ does not belong to the cases. Next, we present the convergence results for the TMAOR.

Lemma 4

[29] Let A, B be two $H_+$-matrices. If

$$\begin{aligned} 0<\alpha <\frac{1}{\rho \left[ (D_A+D_B\varOmega )^{-1}(D_B\varOmega +|C_A|)\right] }, \end{aligned}$$

there exists a positive diagonal matrix ${\bar{D}}$, such that

$$\begin{aligned} \left[ \frac{1+\alpha -|1-\alpha |}{\alpha }D_A+\frac{1-\alpha -|1-\alpha |}{\alpha }D_B\varOmega -2|C_A|\right] {\bar{D}} \end{aligned}$$

is an s.d.d. matrix.

Theorem 3.2

Let $A,B\in {\mathbb {R}}^{n\times n}$ be two $H_{+}$-matrices and $\varOmega \in {\mathbb {R}}^{n\times n}$ be a positive diagonal matrix satisfying $(D_B-\varPsi _r)\varOmega \ge (D_A+\varPsi _z)$. Furthermore, for $i,j=1,2,\ldots ,n$, let $|b_{ij}|\omega _{jj}\le |a_{ij}| (i\ne j)$ and $\text {sign}(b_{ij})=\text {sign}(a_{ij}) (b_{ij}\ne 0)$. Then, the iteration sequence $(z^{(k)},r^{(k)})_{k=1}^{+\infty }$ generated by the TMAOR iteration method converges to the unique solution $(z^{*},r^{*})$ of (1) for any initial vector $x^{(0)}\in {\mathbb {R}}^{n}$ provided

$$\begin{aligned} 0<\beta \le \alpha <\frac{1}{\rho \left[ (D_A+D_B\varOmega )^{-1}(D_B\varOmega +|C_A|)\right] }. \end{aligned}$$

(15)

Proof

With the same notations and discussion as the proof of Theorem 3.1, let ${\bar{D}}$ be the positive diagonal matrix given by Lemma 4. If $(D_B-\varPsi _r)\varOmega \ge (D_A+\varPsi _z)$, by Lemma 4, (4) and (15), we have

$$\begin{aligned}&{\mathcal {M}}_1{\bar{D}}e-{\mathcal {N}}_1{\bar{D}}e\\&\quad =\left[ \langle M_{A_1}+M_{B_1}\varOmega \rangle -|N_{A_1}+N_{B_1}\varOmega -\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |\right. \\&\qquad \left. -|B\varOmega -A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |\right] {\bar{D}}e\\&\quad =\left[ \frac{1}{\alpha }(D_A+D_B\varOmega ) -\frac{\beta }{\alpha }|L_A+L_B\varOmega |-|\frac{|1-\alpha |}{\alpha }(D_A+D_B\varOmega )-\varPhi _z^{(k)}+\varPhi _r^{(k)}\varOmega |\right. \\&\qquad -\frac{|\beta -\alpha |}{\alpha }|L_A+L_B\varOmega |-|U_A+U_B\varOmega |-|D_B\varOmega -D_A-\varPhi _z^{(k)}-\varPhi _r^{(k)}\varOmega |\\&\qquad \left. -|C_B\varOmega -C_A|\right] {\bar{D}}e\\&\quad \ge \left[ \frac{1+\alpha -|1-\alpha |}{\alpha }D_A+\frac{1-\alpha -|1-\alpha |}{\alpha }D_B\varOmega -|C_B\varOmega +C_A|\right. \\&\qquad \left. -|C_B\varOmega -C_A|\right] {\bar{D}}e\\&\quad =\left[ \frac{1+\alpha -|1-\alpha |}{\alpha }D_A+\frac{1-\alpha -|1-\alpha |}{\alpha }D_B\varOmega -2|C_A|\right] {\bar{D}}e\\&\quad >0. \end{aligned}$$

Hence ${\mathcal {M}}_1{\bar{D}}$ is an s.d.d. matrix. Then by Lemma 1, we have $||{\bar{D}}^{-1}{\mathcal {P}}_1{\bar{D}}||_\infty <1$. Similarly, we can get $||{\bar{D}}^{-1}{\mathcal {P}}_2{\bar{D}}||_\infty <1$ too. Therefore we also have $\rho ({\mathcal {P}}_2{\mathcal {P}}_1)<1$, which implies the TMAOR iteration method is convergent. $\square$

Remark 3

Clearly, Theorem 3.2 reduces to Theorem 3.2 of [29] when $\varphi (z,r)=0$.

By the proof of Theorem 3.2, it is easy to have the convergence results for the MAOR iteration method which was not considered in [16].

Corollary 1

With the same notations and assumptions as Theorem 3.2, if (15) holds, the MAOR iteration method for the HNCP converges globally.

4 Numerical examples

In this section, numerical examples are given to show the efficiency of the proposed method. The computations were run on an Intel(R) Core(TM) (2.50 GHz CPU and 4.00 GB RAM).

Consider the following two examples in [16].

Example 1

[16] Consider the 2-D boundary problem:

$$\begin{aligned} \bigtriangleup z+\frac{\partial ^2 r}{\partial ^2 u}+\mu z+\nu r-q-\varphi (z,r)=0, z\ge 0, r\ge 0~~\text {and}~~z^Tr=0, \end{aligned}$$

where z(u, v), r(u, v), q(u, v) are three 2-D mapings and $\mu ,\nu$ are real parameters.

By discretizing the problem using five-point difference scheme with suitable boundary conditions, one can get the HNCP. More concretely, the matrices A and B are given by $A={\hat{A}}+\mu I_n$ and $B={\hat{B}}+\nu I_n$, respectively, where ${\hat{A}}=\text {blktridiag}(-I_m,S,-I_m)\in {\mathbb {R}}^{n\times n}, {\hat{B}}=I_m\otimes S\in {\mathbb {R}}^{n\times n}, S=\text {tridiag}(-1,4,-1)\in {\mathbb {R}}^{m\times m}$ and $n=m^2$.

Example 2

[16] Let $A={\hat{A}}+\mu I_n, B={\hat{B}}+\nu I_n$ and $q=Az^*-Bw^*$, where $n=m^2$, ${\hat{A}}=\text {blktridiag}(-1.5I_m,S,-0.5I_m)\in {\mathbb {R}}^{n\times n}, {\hat{B}}=\text {blktridiag}(-\tau I_m,S,-\tau I_m)\in {\mathbb {R}}^{n\times n}$, $S=\text {tridiag}(-1.5,4,-0.5)\in {\mathbb {R}}^{m\times m}$ and $\mu ,\nu ,\tau$ are real parameters.

Consider the nonlinear functions as below:

$$\begin{aligned}&\varphi _1(z,r)=\frac{z+r+\text {sin}(z)\text {cos}(z)+\text {sin}(r)\text {cos}(r)}{2},\\&\varphi _2(z,r)=-\frac{1}{1+z+r},\\&\varphi _3(z,r)=\frac{\text {arctan}(z)+\text {arctan}(r)}{2},\\&\varphi _4(z,r)=\text {sin}(z+r),\\&\varphi _5(z,r)=\text {ln}(1+z+r). \end{aligned}$$

Note that all these five functions satisfy the smoothness assumptions given in Sect. 3 with $\varPsi _z=\varPsi _r=I$.

Next, we compare the $\text{ TMSOR}_\alpha$ with the $\text{ MSOR}_\alpha$ for Example 1 and Example 2, where the subscript $\alpha$ denotes the relaxation parameter. Let $\gamma =1$, $\varOmega =(D_B-\varPsi _r)^{-1}(D_A+\varPsi _z)$, all initial iteration vectors be $x^{(0)}=e$ and the tolerance be set at $10^{-10}$. In order to compare with the theoretical result, the upper bounds of $\alpha$ in (15) are presented in Table 1 for Example 1 and Example 2. Note that the upper bounds of $\alpha$ in Example 1 listed in Table 1 are all equal to 1 with 2 decimal digit accuracy. However, the exact bounds are all larger than 1, guaranteed by the proof of Lemma 4 in [29]. On the other hand, we also show the numerical results when $\alpha =1.2$ to analyze the behavior of the methods in more critical cases.

Table 1 Upper bounds of $\alpha$ in (15) when $\varOmega =(D_B-\varPsi _r)^{-1}(D_A+\varPsi _z)$

Numerical results are reported in Tables 2 and 3, where “time” and “iter” denote the CPU time in seconds and the iteration steps, respectively. Specially, the percentages of CPU time saved by the TMSOR iteration method from the MSOR iteration method (denoted by “save”) are also presented:

$$\begin{aligned} \text {save}=\frac{\text {time}_{\text {MSOR}}-\text {time}_{\text {TMSOR}}}{\text {time}_{\text {MSOR}}}\times 100\%. \end{aligned}$$

It is also noted that the “best” time for each set of experiments is highlighted by the bold font in Tables 2 and 3.

Table 2 Numerical results of Example 1 when $\mu =0$ and $\nu =4$

Table 3 Numerical results of Example 2 when $\mu =0$ and $\nu =4$

By the numerical results presented in Tables 2 and 3, the MSOR and the TMSOR iteration methods converge in all cases.

• When $\alpha =0.8$ and $\alpha =1.0$, satisfying (15), due to the two-step iteration, the iteration step of the TMSOR is about half of those of the MSOR for each case. Furthermore, the TMSOR always converges faster than the MSOR and the TMSOR can save 16$\%$-53$\%$ CPU time from those of the MSOR for a given $\alpha$.

• When $\alpha =1.2$, outside (15), the CPU time of the TMSOR are also less than those of the MSOR except for $\varphi _2$ in Example 1.

In summary, by the two-step technique, the TMSOR can significantly accelerate the convergence rate of the MSOR with $\alpha$ in (15) and the TMSOR performs the best when $\alpha =1$.

5 Conclusions

We have established the TMMS iteration method for the HNCP by employing two-step matrix splittings, which generalizes the MMS iteration method for the HNCP in [16] and the TMMS iteration method for HLCP in [29]. The convergence results include and extend some existing results. The effectiveness of the TMMS iteration method is shown by numerical experiments. It is worth noticing by the numerical results that the upper bound of $\alpha$ in (15) may be enlarged. How to improve the convergence analysis is the future work.

On the other hand, it is known that multisplitting methods are well-suited for parallel computations. The two-step methods had been coupled with multisplitting techniques in modulus-based methods for LCPs [23]. In the recent work [17], the multisplitting techniques had been applied to HLCPs successfully. It is also an interesting topic to examine the two-step multisplitting methods for HNCP as well based on similar techniques for LCPs and using the multisplittings of the HLCPs.