A new error bound for linear complementarity problems involving $B-$matrices

1.   Introduction and preliminaries

The linear complementarity problem $LCP(A, q)$ has a wide range of applications in the contact problems, the optimal stopping, the free boundary problem for journal bearing, and the network equilibrium problems, etc, for more details see ^[1,2,3]. The $LCP(A, q)$ is to find a vector $x\in R^n$ satisfying

where $q\in R^n$ and $A = (a_{ij})\in R^{n\times n}$. As we all know that a matrix $A = (a_{ij})\in R^{n\times n}$ is called an $P-$matrix if all its principal minors are positive ^[4], and that the $LCP(A, q)$ has a unique solution for any $q\in R^n$ if and only if $A$ is an $P-$matrix ^[2]. In ^[5], Chen and Xiang presented the following error bound of the $LCP(A, q)$ when $A$ is an $P-$matrix:

where $x^{*}$ is the solution of the $LCP(A, \; q)$, $r(x) = \min\{x, \; Ax+q\}$, $D = diag(d_{1}, \; \cdots, d_{n})$ $(0\leqslant d_{i}\leqslant1)$, and the min operator $r(x)$ denotes the componentwise minimum of two vectors.

The upper bound of the $\max\limits_{d\in [0, 1]^{n}}\Vert(I-D+DA)^{-1}\Vert_\infty$ is related with the special structure of the matrix $A$ which is involved in the $LCP(A, q)$, for details, see ^[7,8,9] and references therein. $B-$matrices which are introduced in ^[4] is a subclass of $P-$matrices. M. García-Esnaola and J.M. Peňa in ^[7] presented the upper bound of the $\max\limits_{d\in [0, 1]^{n}}\Vert(I-D+DA)^{-1}\Vert_\infty$ when $A$ is an $B-$matrix.

Definition 1. [4, Definition 2.1]. A matrix $A = (a_{ij})\in R^{n\times n}$ is called an $B-$matrix if for any $i, j\in N = \{1, 2, \cdots, n\}$,

Theorem 1. [7, Theorem 2.2]. Let $A = (a_{ij})\in R^{n\times n}$ be an $B\textrm{-}$matrix with the form $A = B^++C$, where

and $r_i^+ = \max\{0, \; a_{ij}|j\neq i\}$, then

where $\beta = \min\limits_{i\in N}\{\beta_i\}$ and $\beta_i = b_{ii}-\sum\limits_{j\neq i}|b_{ij}|.$

In 2016, Li et al. improved the previous bound (3) as show below.

Theorem 2. [8, Theorem 4]. Let $A = (a_{ij})\in R^{n\times n}$ be an $B\textrm{-}$matrix with the form $A = B^++C$, where $B^+ = (b_{ij})$ is expressed as (2). Then

where $\bar{\beta}_i = b_{ii}-\sum\limits_{j = i+1}^n|b_{ij}|l_i(B^+), \; l_k(B^+) = \max\limits_{k\leqslant i\leqslant n}\Bigg\{\dfrac{\sum\limits_{j = k, \neq i}^n|b_{ij}|}{|b_{ii}|}\Bigg\}$ and

In the same year, Li et al. also derived the error bounds for linear complementarity problems of weakly chained diagonally dominant $B-$matrix, this bound holds for the case that weakly chained diagonally dominant $B-$matrix is an $B-$matrix. the error bound as follows.

Theorem 3. [9, Theorem 2]. Let $A = (a_{ij})\in R^{n\times n}$ be an $B\textrm{-}$matrix with the form $A = B^++C$, where $B^+ = (b_{ij})$ is expressed as (2). Then

where $\widetilde{\beta}_i = b_{ii}-\sum\limits_{j = i+1}^n|b_{ij}| > 0$ and $\prod\limits_{j = 1}^{i-1}\dfrac{b_{jj}}{\widetilde{\beta}_j} = 1$ if i = 1.

Next, we will continue to research the upper bound of the $\max\limits_{d\in [0, 1]^{n}}\Vert(I-D+DA)^{-1}\Vert_\infty$ when the matrix $A$ is an $B-$matrix based on the bound of the infinity norm of the inverse of strictly diagonally dominant $M-$matrices. We first recall some related definitions.

Definition 2. [4, Corollary 2.7]. A matrix $A = (a_{ij})\in R^{n\times n}$ is called an $Z-$matrix if $a_{ij}\leqslant0$ for any $i\neq j$.

Definition 3. [6, Corollary 3]. A matrix $A = (a_{ij})\in R^{n\times n}$ is called a strictly diagonally dominant ($SDD$) matrix if for any $i, j\in N = \{1, 2, \cdots, n\}$,

Definition 4. [6, Corollary 4]. A matrix $A = (a_{ij})\in R^{n\times n}$ is called an $M-$matrix if $A$ is an $Z-$matrix and $A^{-1}\geqslant0$.

For convenience, we employ the following notations throughout the paper. Let $A = (a_{ij})\in R^{n\times n}, i, j, k, m, n\in N, i\neq j,$ denote

2.   Main results

In this part, we first give some lemmas which will be used later, then a new upper bound of the $\max\limits_{d\in[0, 1]^n}\parallel(I-D+DA)^{-1}\parallel_\infty$ when $A$ is an $B-$matrix will be derived.

Lemma 1. [10, Theorem 5]. Let $A = (a_{ij})\in R^{n\times n}$ be an $SDD$ $M\textrm{-}$matrix. Then

where $\prod\limits_{j = 1}^0\dfrac{u_j}{(1-u_jq^{(j)})} = 1$ and $\prod\limits_{j = 1}^0\dfrac{1}{(1-u_jq^{(j)})} = 1.$

Lemma 2. [9, Lemma 4]. Let $\theta > 0$ and $\eta\geqslant0$. Then for any $x\in[0, 1]$,

and

Lemma 3. [9, Lemma 5]. Let $A = (a_{ij})\in R^{n\times n}$ and $a_{ii} > \sum\limits_{k = i+1}^n|a_{ik}|(\forall i \in N)$. Then for any $x_{i}\in[0, 1]$,

Lemma 4. [7, Theorem 2.2]. Let $P = (p_1, p_2, \cdots, p_n)^Te, \; e = (1, 1, \cdots, 1), \; p_1, p_2, \cdots, p_n\geqslant0,$ then

Theorem 4. Let $A = (a_{ij})\in R^{n\times n}$ be an $B\textrm{-}$matrix with the form $A = B^++C$, where $B^+ = (b_{ij})$ is expressed as (2). Then

where $t_i = b_{ii}-\sum\limits_{j = i+1}^n|b_{ij}|q_{ji}^{(i)}(B^+), \; \; \widetilde{t}_j = b_{jj}-\sum\limits_{k = j+1}^n|b_{jk}|q^{(j)}(B^+).$

Proof. Let $A_D = I-D+DA$. Then

where $B^+_D = I-D+DB^+$ and $C_D = DC$. By Theorem 2.2 in ^[7], we can get that $B^+_D$ is an $SDD$ $M$-matrix with positive diagonal elements, by Lemma 4, then

Next, we will give an upper bound for $\parallel(B^+_D)^{-1}\parallel_\infty$. By Lemma 1, we have

By Lemma 2, we can easily deduce the following results for any $i, j, k, m, n\in N$,

By (13)–(15), we have

By analogy, we can get that for any $m\geqslant2$,

therefore

Because of

and

By (20), (21) and Lemma 2, we get

By (22) and Lemma 2, we have

By (23), we have

By Lemmas 2 and 3, we obtain

and

By (24)–(26), we have

Therefore, (10) holds from (11) and (27).

Theorem 5. Let $A = (a_{ij})\in R^{n\times n}$ be an $B\textrm{-}$matrix with the form $A = B^++C$, where $B^+ = (b_{ij})$ is expressed as (2). Then

where $\bar{\beta}_i$ and $\widetilde{\beta}_i$ are defined as (4), (5).

Proof. Since $B^+ = (b_{ij})$ is an $SDD$ matrix with positive diagonal elements, by Theorem 6 in ^[10], we have

Notice that

then

and

By (30)–(33), we can obtain (28).

Theoretical analysis shows that the new upper bound (10) of the $\max\limits_{d\in [0, 1]^{n}}\Vert(I-D+DA)^{-1}\Vert_\infty$ when the matrix $A$ is an $B-$matrix is better than bounds (4) and (5) which all be provided by Li in ^[8,9]. Next, we further illustrate the effectiveness of the result through numerical example.

Example 1. Consider the family of $B-$matrices in ^[8]:

where $k\geqslant1$. Then $A_k = B_k^++C_k,$ where

By Theorem 1, we have

it is obvious to see that $30(k+1)\rightarrow +\infty$, when $k\rightarrow +\infty$. bound (3) in Theorem 1 can be arbitrarily large.

By Theorem 2, we have

when $k = 1$,

when $k = 2$,

By Theorem 3, for each $k\in N = \{1, 2, \cdots, n\}$, we have

By Theorem 4, we have

when $k = 1$,

when $k = 2$,

The numerical example above further illustrate that the bound (10) in Theorem 4 is better than those bounds in Theorems 1–3.

3.   Conclusions

In this paper, we present a new upper bound for $\max\limits_{d\in[0, 1]^n}\|(I-D+DA)^{-1}\|_\infty$ when $A$ is an $B-$matrix, theoretical analysis and numerical example illustrate that the new estimation improves the bounds obtained in ^[7,8,9].

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgements

The authors would like to thank editors and referees for their valuable suggestions.

This work is supported by the National Natural Science Foundation of China (No. 11461027), Scientific Research Fund of Hunan Education Department (No. 16A173). We are grateful for their help.

Conflict of interest

The authors declare no conflict of interest.