Error bounds for linear complementarity problems of strong $SDD_{1}$ matrices and strong $SDD_{1}$-$B$ matrices

1.   Introduction

Many fundamental problems in optimization and mathematical programming can be described as linear complementarity problems, such as quadratic programming, nonlinear obstacle problems, invariant capital stock, the Nash eqilibrium point of a bimatrix game, optimal stopping, free boundary problems for journal bearing and so on, see for instance, ^[1,2,3,4].

Some basic definitions for the special matrices are given as follows: let $n$ be an integer number, $N = \{ 1, 2, \ldots, n\}$, and let $R^{n\times n}$ be the set of all real matrices of order $n$. Matrix $A = (a_{ij})\in R^{n\times n}$ is called a $Z$-matrix, if $a_{ij}\leq 0$ for any $i\neq j$; a $P$-matrix, if all its principal minors are positive; an $M$-matrix, if $A$ is a $Z$-matrix with eigenvalues whose real parts are non-negative; an $H$-matrix, if its comparison matrix $\langle A\rangle = (\bar{a}_{ij})$ is an $M$-matrix, where

Linear complementarity problem of matrix $A$, denoted by $LCP(A, q)$, is to find a vector $x\in R^{n}$ such that

or to prove that no such vector $x$ exists, where $A\in R^{n\times n}$ and $q\in R^{n}$. One of the essencial problems in $LCP(A, q)$ is to estimate

where $D = diag(d_{i})$, $d = (d_{1}, d_{2}, \cdots, d_{n})$, $0\leq d_{i}\leq 1$, $i = 1, 2, \cdots, n$. It is well known that when $A$ is a $P$-matrix, there is a unique solution to linear complementarity problems.

In ^[4], Chen et al. gave the following error bound for $LCP(A, q)$,

where $x^{*}$ is the solution of $LCP(A, q)$, $r(x) = \min\{x, Ax+q\}$, and the min operator $r(x)$ denotes the componentwise minimum of two vectors. It is well known that when real $H$-matrix $A$ with positive diagonal entries is a subclass of $P$-matrices, error bound of $LCP(A, q)$ can be obtained by formula $(2.4)$ in ^[4]. Furthermore, to avoid the high-cost computations of the inverse matrix in $(2.4)$, some easily computable bounds for $LCP(A, q)$ are derived for the different subclass of $H$-matrices, such as $Ostrowski$ matrices ^[5], $QN$-matrices ^[6], $Nekrasov$ matrices ^[7], $S$-$SDDS$ matrices ^[8] and $DZ$-matrices ^[9], which only depends on the entries of the involved matrix $A$.

When the class of involved matrices is subclass of $P$-matrices that are not $H$-matrices, error bounds of $LCP(A, q)$ also need to be studied, such as, $B_{\pi}^{R}$-matrices ^[10], $B$-Nekrasov matrices ^[11] and $CKV$-type-$B$-matrices ^[12].

In this paper, we apply upper bound for infinity norm of the inverse of strong $SDD$$_ {1}$ matrix to estimate the error for linear complementarity problems of strong $SDD$$_ {1}$ matrices and strong $SDD$$_ {1}$-$B$ matrices. Numerical examples show that the obtained results can improve other existing bounds.

2.   Preliminaries

In this section, some definitions and lemmas are given. Assume that $S$ denotes a nonempty subset of $N$ and $\overline{S}: = N\backslash S$ the complement of $S$. For each $i \in N$, ${r_i}\left(A \right): = \sum\limits_{j \ne i} |a_{ij} |$, $r_{i}^{S}(A): = \sum\limits_{j\in S\backslash \{ i\} } |a_{ij}|$.

Definition 1. ^[13] Matrix $A = ({{a_{ij}}}) \in {R^{n \times n}}$ is called a strictly diagonally dominant $\left({SDD} \right)$ matrix if, for all $i \in N$,

Definition 2. ^[14] Matrix $A = ({{a_{ij}}}) \in {R^{n \times n}}$ is said a strong $SDD$$_ {1}$ matrix if there exists a subset $S$ of $N$ such that

● (i) $|a_{ii}| > r_{i}(A)$, for $i\in S$ satisfying $r_{i}^{\overline{S}}(A) = 0$,

● (ii) $|a_{jj}| > r_{j}(A)$, for $j\in \overline{S}$,

● (iii) $[|a_{ii}|-r_{i}^{S}(A)]|a_{jj}| > r_{i}^{\overline{S}}(A)r_{j}(A)$, for $i\in S$ and $j\in \overline{S}$ such that $a_{ij}\neq 0$.

Definition 3. Let $A = (a_{ij})\in R^{n\times n}$ ($n\geq 2$) be a matrix with the form of $A = B^{+}+C$. We say that $A$ is a strong $SDD$$_ {1}$-$B$ matrix if $B^{+}$ is a strong $SDD$$_ {1}$ matrix with positive diagonal entries, where

and $r_{i}^{+} = max\left\{{0, a_{ij}\mid j\neq i}\right\}$.

There is an equivalence definition of $B$-matrices in ^[1,15], which is closely related to strictly diagonally dominant matrices.

Definition 4. ^[15] Matrix $A = ({{a_{ij}}}) \in {R^{n \times n}}$ is called a $B$-matrix if, for all $i \in N$,

Definition 5. ^[1] Let $A = (a_{ij})\in R^{n\times n}$ and $A = B^{+}+C$, where $B^{+}$ is defined as in $({2.1})$. We say that $A$ is a $B$-matrix if $B^{+}$ is an $SDD$ matrix.

Next, we will introduce some useful lemmas.

Lemma 1. ^[14] Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ be a strong $SDD_{1}$ matrix. Then,

Lemma 2. ^[14] If matrix $A = ({{a_{ij}}}) \in {R^{n \times n}}$ is a strong $SDD$$_ {1}$ matrix, then $A$ is a nonsingular $H$-matrix.

Lemma 3. ^[15] Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ be a nonsingular $M$-matrix, and let $P$ be a nonnegative matrix with rank $1$. Then $A+P$ is a $P$-matrix.

Lemma 4. Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ $(n\geq 2)$ be a strong $SDD$$_{1}$-$B$ matrix. Then $A$ is a $P$-matrix.

Proof. By Definition $3$, we have that $C$ in $({2.1})$ is a nonnegative matrix with rank $1$. By Lemma 2, we get that $B^{+}$ is a nonnegative $M$-matrix. We can conclude that $A$ is a $P$-matrix from Lemma $3$. □

Remark 1. From Definitions $1$–$5$, Lemmas $2$ and $4$, we have the following relationships:

Lemma 5. Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ be a strong $SDD_{1}$ matrix. Then $\widetilde{A} = (\tilde{a}_{ij}) = I - D + DA$ is also a strong $SDD_{1}$ matrix, where $D = diag\left({{d_i}} \right)$ with $0 \le {d_i} \le 1$, $\forall i\in N$.

Proof. Since $\widetilde{A} = I-D+DA = (\tilde{a}_{ij})$, then,

Based on $A$ is a strong $SDD_{1}$ matrix and $D = diag(d_{i})$, $0\leq d_{i}\leq 1(\forall i\in N)$, by Lemma $3$, we can get the following results.

$1)$ For $i\in S$, satisfying $r_{i}^{\overline{S}} (\widetilde{A}) = 0$, by Definition $3$, it holds that if $d_{i} = 0$, then

If $d_{i}\neq 0$, then

$2)$ For $j\in \overline{S}$, it follows that if $d_{j} = 0$, then

If $d_{j}\neq0$, then

$3)$ For $i\in S$, $j\in \overline{S}$, satisfying $\tilde{a}_{ij}\neq 0$, i.e., $d_i \neq 0$ and $a_{ij} \neq 0$, we can obtain that if $d_{i}\neq0$, $d_{j} = 0$, then

If $d_{i}\neq 0$, $d_{j}\neq 0$, then

Therefore, $\widetilde{A}$ is a strong $SDD_{1}$ matrix, the conclusion follows. □

Lemma 6. ^[16] Let $\gamma > 0$ and $\eta \ge 0$. Then for any $x \in \left[{0, 1} \right]$,

Lemma 7. ^[17] If $A = ({{a_{ij}}}) \in {R^{n \times n}}$ is an $SDD$ matrix, then

Lemma 8. ^[1] Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ be a $B$-matrix, and let $B^{+}$ be the matrix in $(3)$. Then

where $\beta = \min\limits_{i\in N}\left\{\beta_{i}\right\}$, $\beta_{i} = |b_{ii}|-\sum\limits_{j\neq i}^{n}|b_{ij}|$.

3.   Error bound for linear complementarity problems involving strong ${SDD_{1}}$ matrices

In this section, new error bound of $LCP(A, q)$ is provided when $A$ is a strong ${SDD_{1}}$ matrix.

Theorem 1. Let $A = (a_{ij}) \in {R^{n \times n}}$, $n\geq 2$, be a strong ${SDD_{1}}$ matrix with poistive diagonal entries, and let $\widetilde{A} = (\tilde{a}_{ij}) = I - D + DA$, where $D = diag\left({{d_i}} \right)$ with $0 \le {d_i} \le 1$. Then

where

Proof. Since ${\widetilde{A}} = (\tilde{a}_{ij}) = I - D + DA$, then from Lemma $5$, we know that $\widetilde{A}$ is a strong ${SDD_{1}}$ matrix with positive diagonal entries. By Lemma $1$, it holds that

Note that $r_{i}(\widetilde{A}) = d_{i}r_{i}(A)$, $r_{j}(\widetilde{A}) = d_{j}r_{j}(A)$ for all $i\in S$, $j\in \bar{S}$. Next, we divide into three cases to prove the result.

Case 1. For $i\in S$, satisfying $r_{i}^{\overline{S}}(\widetilde{A}) = 0$, it follows that $d_{i} = 0$ or $r_{i}^{\overline{S}}(A) = 0$. If $d_{i} = 0$ and $r_{i}^{\bar{S}}(A) = 0$, $i\in S$, then

If $d_{i}\neq 0$ and $r_{i}^{\overline{S}}(A) = 0$, $i\in S$, by Lemma $6$, we have

If $d_{i} = 0$ and $r_{i}^{\overline{S}}(A)\neq 0$, $i\in S$, then there exists $j\in \overline{S}$ such that $a_{ij}\neq 0$. Thus, by Lemma $6$, we get

So, it holds that

Case 2. For $j\in \overline{S}$, if $d_{j} = 0$, then

If $d_{j}\neq0$, by Lemma $6$, we get

Case 3. For $i\in S$ and $j\in \overline{S}$, such that $\tilde{a}_{ij}\neq 0$, it holds that $d_{i}\neq0$ and $a_{ij}\neq 0$. Thus, by Lemma $6$, it holds that

From Cases $1$–$3$, the conclusion follows. □

Next, let's use the following two examples to illustrate the advantages of our results.

Example 1. Consider the matrix:

Then, $A$ is not only an $SDD$ matrix but also a strong $SDD_{1}$ matrix for $S = \left\{{1, 2}\right\}$. From Lemma $7$, we have

By Theorem $1$, we get

Example 2. Consider the tri-diagonal matrix $A\in R^{n\times n}$ arising from the finite difference method for free boundary problems ^[4], where

Take that $n = 500$, $a = -0.5$, $b = 3$, $c = -2.3$ and $\alpha = 0$. Then $A$ is not only an $SDD$ matrix but also a strong $SDD_{1}$ matrix for $S = \left\{{2, \cdots, 499}\right\}$. From Lemma $7$, we get

By Theorem $1$, we have

Example 3. Consider the matrix:

It is easy to verify that $A$ is a strong $SD{D_1}$ matrix for $S = \left\{{1, 2, 4}\right\}$, but not an $SDD$ matrix and nor $S$-$SDD$ matrix for any nonempty subset $S$ of $N$. By Theorem $1$, we have

4.   Error bound for linear complementarity problems involving strong $SD{{D}_{1}}$-$B$ matrices

In this section, a new error bound of $LCP(A, q)$ is presented when $A$ is a strong $SD{{D}_{1}}$-$B$ matrix.

Theorem 2. Let $A = ({{a_{ij}}}) \in {R^{n \times n}}$ be a strong $SD{{D}_{1}}$-$B$ matrix with the form of $A = B^{+}+C$, and let ${B^ + } = (b_{ij})$ be the matrix in $(2.1)$. Denote ${A_D} = I - D + DA$, where $D = diag\left({{d_i}} \right)$ with $0 \le {d_i} \le 1$. Then

where

Proof. For $D = diag\left({{d_i}} \right)$ with $0 \le {d_i} \le 1 (\forall i \in N)$, we have

where $B_D^ {+} = (\tilde{b}_{ij}) = I - D + D{B^ + }$ and ${C_D} = DC$. Notice that ${{B^ + }}$ is a strong $SDD_{1}$ matrix with positive diagonal entries, then by Lemma $5$, it follows that $B_D^ + = I - D + D{B^ + }$ is also a strong $SDD_{1}$ matrix with positive diagonal entries. Similarly as the proof of Theorem 2.2 in ^[1], we can obtain:

We now bound $\left\| {{{({B_D^ + })}^{ - 1}}} \right\|_\infty$. By Lemma $1$, it holds that

where

Next, we divide into three cases to prove the conclusion.

Case 1. For $i\in S$, satisfying $r_{i}^{\overline{S}}(B_{D}^{+}) = 0$, then $r_{i}^{\overline{S}}(B^{+}) = 0$ or $d_{i} = 0$. If $d_{i} = 0$, $r_{i}^{\overline{S}}(B^{+})\neq 0$, $i\in S$, then there exists $j\in \overline{S}$ such that $a_{ij}\neq 0$. Hence, by Lemmas $6$ and $7$, we get

If $d_{i} = 0$, $r_{i}^{\overline{S}}(B_{D}^{+}) = 0$, $i\in S$, we have

Case 2. For $j\in \overline{S}$, it holds that

Case 3. For $i\in S$ and $j\in \overline{S}$, such that $\tilde{b}_{ij}\neq 0$, then $d_{i}\neq0$ and $b_{ij}\neq 0$. Thus, by Lemma 6, we have

Consequently, from Cases $1$–$3$, the conclusion follows. □

The bound in Theorem $2$ also holds for $B$-matrix, because $B$-matrix is a subclass of strong $SDD_{1}$-$B$-matrix. Next, we will indicate that the bound in Theorem $2$ is better than that in Lemma $8$ in some cases.

Theorem 3. Let $A = (a_{ij})\in R^{n\times n}$ be a $B$-matrix with $A = B^{+}+C$, and let $B^{+} = (b_{ij})$ be the matrix in $(2.1)$. If $0 < b_{ii}\leq 1 (\forall i\in N)$, then

where $\zeta(B^{+})$ and $\beta$ are defined as in Theorem $2$ and Lemma $8$, respectively.

Proof. By $0 < b_{ii}\leq1$ ($\forall i\in N$), we have

and

For ${i\in S}$ and ${j\in \overline{S}}$, such that $b_{ij}\neq 0$, it follows that if ${b_{ii}-r_{i}(B^{+})}\leq{b_{jj}-r_{j}(B^{+})}$, then

If ${b_{jj}-r_{j}(B^{+})}\leq{b_{ii}-r_{i}(B^{+})}$, then

Therefore, the conclusion follows. □

The following numerical examples show the validity of the error bounds for strong $SDD_{1}$-$B$ matrix.

Example 4. Consider the matrix:

We can write it as $A = B^{+}+C$, where

It is easy to check that $A$ is a $B$-matrix, consequently, a strong $SDD_{1}$-$B$ matrix. By Lemma $8$, we have

When $S = \left\{1 \right\}$, by Theorem $2$, we have

It is shown by Figure 1, in which the first $1000$ matrices are given by the following MATLAB codes, that $25$ is better than $30$ for $\max\|(I-D+DA)^{-1}\|_{\infty}$. Blue stars in Figure 1 represent the $\|(I-D+DA)^{-1}\|_{\infty}$ when matrices $D$ come from $1000$ different random matrices in $[0, 1]$.

Example 5. Consider the matrix:

Matrix $A$ can be split into $A = B^{+}+C$, where

It is easy to verify that $A$ is neither an $SDD$ matrix nor a $B$-matrix. On the other hand, $A$ is a strong $SDD_{1}$-$B$ matrix for $S = \left\{1, 2, 3 \right\}$. By Theorem $2$, we get

5.   Conclusions

Based on the properties strong $SDD_{1}$ matrices, we introduce a new subclass of $P$-matrices called strong $SDD_{1}$-$B$ matrices. Moreover, we apply upper bound for the infinity norm of the inverse of $SDD_{1}$ matrices to estimate error bounds for linear complementarity problems of $SDD_{1}$ matrices and $SDD_{1}$-$B$ matrices, which is useful for free boundary problems. Numerical examples are given to show the sharpness of the proposed bounds. In the future, based on the proposed infinity norm bound, we will explore the computable global error bounds of extended vertical linear complementarity problems for $SDD_{1}$ matrices and $SDD_{1}$-$B$ matrices.

Use of AI tools declaration

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

Acknowledgments

This research is supported by Guizhou Provincial Science and Technology Projects (20191161), the Natural Science Research Project of Department of Education of Guizhou Province (QJJ2022015, QJJ2023012, QJJ2023062), the Talent Growth Project of Education Department of Guizhou Province (2018143), and the Research Foundation of Guizhou Minzu University (2019YB08).

Conflict of interest

The authors declare that they have no competing interests.