﻿ 弱链对角占优B-矩阵线性互补问题误差界的新估计式 A New Error Bound for Linear Complementarity Problems for Weakly Chained Diagonally Dominant B-Matrices

Vol.06 No.07(2017), Article ID:22434,7 pages
10.12677/AAM.2017.67102

A New Error Bound for Linear Complementarity Problems for Weakly Chained Diagonally Dominant B-Matrices

Xia Jing, Lei Gao

School of Mathematics and Information Science, Baoji University of Arts and Sciences, Baoji Shaanxi

Received: Oct. 2nd, 2017; accepted: Oct. 16th, 2017; published: Oct. 24th, 2017

ABSTRACT

In this paper, by the infinity norm bound of inverse matrix of weakly chained diagonally dominant M-matrices, we give a new error bound for the linear complementarity problem when the matrix involved is a weakly chained diagonally dominant B-matrix, which improves some existing ones. Numerical examples are given to show the corresponding results.

Keywords:P-Matrix, Weakly Chained Diagonally Dominant B-Matrix, Linear Complementarity Problem, Error Bound

1. 引言

$x\ge 0,\text{}Mx+q\ge 0,\text{}{\left(Mx+q\right)}^{\text{T}}x=0$

${‖x-{x}^{*}‖}_{\infty }\le \underset{d\in {\left[0,1\right]}^{n}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }{‖r\left(x\right)‖}_{\infty }$ (1)

2. 预备知识

${C}^{n×n}$ ( ${R}^{n×n}$ )表示所有n阶复矩阵(实矩阵)构成的集合，指标集 $N=\left\{1,2,\cdots ,n\right\}$ 。设 $A=\left[{a}_{ij}\right]\in {R}^{n×n}$ ，对任意的 $i,\text{}j,\text{}k\in N,\text{}i\ne j$ ，记

${R}_{i}\left(A\right)=\underset{j\ne i}{\sum }|{a}_{ij}|$${u}_{i}\left(A\right)=\frac{1}{|{a}_{ii}|}\underset{j=i+1}{\overset{n}{\sum }}|{a}_{ij}|$

${h}_{l}^{\left(k-1\right)}=\underset{j=k}{\overset{l-1}{\sum }}|{a}_{lj}|\cdot \frac{{h}_{j}^{\left(k-1\right)}}{|{a}_{jj}|}+\underset{j=i+1}{\overset{n}{\sum }}|{a}_{ij}|$ (2)

${c}_{k}=\underset{k\le i\le n}{\mathrm{max}}\left\{\frac{{h}_{i}^{\left(k-1\right)}}{|{a}_{ii}|}\right\},\text{\hspace{0.17em}}k=1,2,\cdots ,n$

${q}_{k}\left(A\right)=\underset{1\le i\le n-k}{\mathrm{max}}\left\{\frac{|{a}_{i+k,k}|+\underset{h=k+1,h\ne i+k}{\overset{n}{\sum }}|{a}_{i+k,k}|{c}_{k}}{|{a}_{i+k,i+k}|}\right\},\text{\hspace{0.17em}}k=1,2,\cdots ,n$ .

$|{a}_{ii}|\ge {R}_{i}\left(A\right)$

${B}^{+}=\left[{b}_{ij}\right]=\left(\begin{array}{ccc}{m}_{11}-{r}_{1}^{+}& \dots & {m}_{1n}-{r}_{1}^{+}\\ ⋮& \ddots & ⋮\\ {m}_{n1}-{r}_{n}^{+}& \cdots & {m}_{nn}-{r}_{n}^{+}\end{array}\right)$ , ${r}_{i}^{+}=\mathrm{max}\left\{0,{m}_{ij}|j\ne i\right\}$ , (3)

${B}^{\text{+}}$ 为弱链对角占优矩阵且所有的主对角元素皆为正，则称 $A$ 为弱链对角占优矩阵。

$\underset{d\in {\left[0,1\right]}^{n}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }\le \underset{i=1}{\overset{n}{\sum }}\frac{n-1}{\mathrm{min}\left\{{\stackrel{¯}{\beta }}_{i},1\right\}}\underset{j=1}{\overset{i-1}{\prod }}\frac{{b}_{jj}}{{\stackrel{¯}{\beta }}_{j}}$ ， (4)

$\begin{array}{l}{‖{A}^{-1}‖}_{\infty }\le \mathrm{max}\left\{\frac{1}{{a}_{11}\left(1-{u}_{1}{q}_{1}\right)}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{{a}_{ii}\left(1-{u}_{i}{q}_{i}\right)}\underset{j=1}{\overset{i-1}{\prod }}\frac{{u}_{j}\left(A\right)}{1-{u}_{j}\left(A\right){q}_{j}\left(A\right)}\right]\text{ },\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\underset{i=2}{\overset{n}{\sum }}\frac{{q}_{1}}{{a}_{11}\left(1-{u}_{1}{q}_{1}\right)}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{{q}_{i}}{{a}_{ii}\left(1-{u}_{i}{q}_{i}\right)}\underset{j=1}{\overset{i-1}{\prod }}\frac{1}{1-{u}_{j}{q}_{j}}\right]\right\}\end{array}$ ,

$\frac{1}{1-x-\gamma x}\le \frac{1}{\mathrm{min}\left\{\gamma ,1\right\}}$$\frac{\eta x}{1-x\text{+}\gamma x}\le \frac{\eta }{\gamma }$ .

3. 主要结果

$\frac{{h}_{l}^{\left(k-1\right)}\left({B}_{D}^{+}\right)}{|{\stackrel{¯}{b}}_{ll}|}\le \frac{{h}_{l}^{\left(k-1\right)}\left({B}^{+}\right)}{|{b}_{ll}|}$ ，(5)

$\frac{{h}_{1}^{\left(0\right)}\left({B}_{D}^{+}\right)}{|{\stackrel{¯}{b}}_{11}|}\text{=}\frac{{d}_{1}\underset{j=2}{\overset{n}{\sum }}|{b}_{1j}|}{1-{d}_{1}+{d}_{1}{b}_{11}}\le \frac{\underset{j=2}{\overset{n}{\sum }}|{b}_{1j}|}{{b}_{11}}=\frac{{h}_{1}^{\left(0\right)}\left({B}^{+}\right)}{|{b}_{11}|}$

$\frac{{h}_{i+1}^{\left(0\right)}\left({B}_{D}^{+}\right)}{|{\stackrel{¯}{b}}_{i+1,i+1}|}=\frac{\underset{j=k}{\overset{n}{\sum }}\frac{|{\stackrel{¯}{b}}_{i+1,j}|}{|{\stackrel{¯}{b}}_{jj}|}\cdot {h}_{j}^{\left(0\right)}\left({B}_{D}^{+}\right)+\underset{j=i+2}{\overset{n}{\sum }}|{\stackrel{¯}{b}}_{i+1,j}|}{|{\stackrel{¯}{b}}_{i+1,i+1}|}\le \frac{{h}_{i+1}^{\left(0\right)}\left({B}^{+}\right)}{|{b}_{i+1,i+1}|}$ .

$\begin{array}{l}\underset{d\in {\left[0,1\right]}^{n}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }\\ \le \left(n-1\right)\cdot \mathrm{max}\left\{\frac{1}{\mathrm{min}\left\{{\alpha }_{1}\left({B}^{+}\right),1\right\}}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{\mathrm{min}\left\{{\alpha }_{i}\left({B}^{+}\right),1\right\}}\cdot \underset{j=1}{\overset{n}{\prod }}\frac{{b}_{jj}\cdot {u}_{j}\left({B}^{+}\right)}{{\alpha }_{i}\left({B}^{+}\right)}\right],\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\frac{{q}_{1}\left({B}^{+}\right)}{\mathrm{min}\left\{{\alpha }_{1}\left({B}^{+}\right),1\right\}}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{{q}_{i}\left({B}^{+}\right)}{\mathrm{min}\left\{{\alpha }_{i}\left({B}^{+}\right),1\right\}}\cdot \underset{j=1}{\overset{i-1}{\prod }}\frac{{b}_{jj}}{{\alpha }_{j}\left({B}^{+}\right)}\right]\right\}\end{array}$ (6)

${M}_{D}=I-D+DM=I-D+D\left({B}^{+}+C\right)={B}_{D}^{+}+{C}_{D}$ ，其中 ${B}_{D}^{+}=I-D+D{B}^{+}$${C}_{D}=DC$ 。由文献 [15] 中的定理2知，是弱链严格对角占优M-阵

${‖{M}_{D}^{-1}‖}_{\infty }\le \left(n-1\right)\cdot {‖{\left({B}_{D}^{+}\right)}^{-1}‖}_{\infty }$ . (7)

$\begin{array}{l}{‖{\left({B}_{D}^{+}\right)}^{-1}‖}_{\infty }\le \mathrm{max}\left\{\frac{1}{{\stackrel{¯}{b}}_{11}\left[1-{u}_{1}\left({B}_{D}^{+}\right){q}_{1}\left({B}_{D}^{+}\right)\right]}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{{\stackrel{¯}{b}}_{ii}\left[1-{u}_{i}\left({B}_{D}^{+}\right){q}_{i}\left({B}_{D}^{+}\right)\right]}\cdot \underset{j=1}{\overset{n}{\prod }}\frac{{u}_{j}\left({B}_{D}^{+}\right)}{1-{u}_{j}\left({B}_{D}^{+}\right){q}_{j}\left({B}_{D}^{+}\right)}\right],\\ \text{}\frac{{q}_{1}\left({B}_{D}^{+}\right)}{{\stackrel{¯}{b}}_{11}\left[1-{u}_{1}\left({B}_{D}^{+}\right){q}_{1}\left({B}_{D}^{+}\right)\right]}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{{q}_{i}\left({B}_{D}^{+}\right)}{{\stackrel{¯}{b}}_{ii}\left[1-{u}_{i}\left({B}_{D}^{+}\right){q}_{i}\left({B}_{D}^{+}\right)\right]}\cdot \underset{j=1}{\overset{i-1}{\prod }}\frac{1}{1-{u}_{j}\left({B}_{D}^{+}\right){q}_{j}\left({B}_{D}^{+}\right)}\right]\right\}\end{array}$ .

${u}_{i}\left({B}_{D}^{+}\right)=\frac{\underset{j=i+1}{\overset{n}{\sum }}|{b}_{ij}|{d}_{i}}{1-{d}_{i}+{b}_{ii}{d}_{i}}\le \frac{\underset{j=i+1}{\overset{n}{\sum }}|{b}_{ij}|}{{b}_{ii}}={u}_{i}\left({B}^{+}\right)$

$\begin{array}{c}{q}_{k}\left({B}_{D}^{+}\right)=\underset{1\le i\le n-k}{\mathrm{max}}\left\{\frac{|{\stackrel{¯}{b}}_{i+k,k}|+\underset{h=k+1,h\ne i+k}{\overset{n}{\sum }}|{\stackrel{¯}{b}}_{i+k,h}|\cdot {\stackrel{¯}{c}}_{k}}{|{\stackrel{¯}{b}}_{i+k,i+k}|}\right\}\\ \le \underset{1\le i\le n-k}{\mathrm{max}}\frac{{d}_{i+k}\left[|{b}_{i+k,k}|+\underset{h=k+1,h\ne i+k}{\overset{n}{\sum }}|{b}_{i+k,h}|\cdot {c}_{k}\right]}{1-{d}_{i+k,i+k}+{d}_{i+k,i+k}|{b}_{i+k,i+k}|}\\ \le \underset{1\le i\le n-k}{\mathrm{max}}\left\{\frac{|{b}_{i+k,k}|+\underset{h=k+1,h\ne i+k}{\overset{n}{\sum }}|{b}_{i+k,h}|\cdot {c}_{k}}{|{b}_{i+k,i+k}|}\right\}={q}_{k}\left({B}^{+}\right)\end{array}$ ,

$\begin{array}{c}\frac{1}{{\stackrel{¯}{b}}_{ii}\left[1-{u}_{i}\left({B}_{D}^{+}\right)\cdot {q}_{i}\left({B}_{D}^{{}^{+}}\right)\right]}=\frac{1}{{\stackrel{¯}{b}}_{ii}-{\stackrel{¯}{b}}_{ii}\cdot {u}_{i}\left({B}_{D}^{+}\right)\cdot {q}_{i}\left({B}_{D}^{{}^{+}}\right)}\\ \le \frac{1}{{\stackrel{¯}{b}}_{ii}-\underset{j=i+1}{\overset{n}{\sum }}|{\stackrel{¯}{b}}_{ij}|\cdot {q}_{i}\left({B}^{+}\right)}\\ \le \frac{1}{\mathrm{min}\left\{{b}_{ii}-\underset{j=i+1}{\overset{n}{\sum }}|{b}_{ij}|\cdot {q}_{i}\left({B}^{+}\right),1\right\}}\\ =\frac{1}{\mathrm{min}\left\{{\alpha }_{i}\left({B}^{+}\right),1\right\}}\end{array}$ ,

$\frac{1}{1-{u}_{j}\left({B}_{D}^{{}^{+}}\right)\cdot {q}_{j}\left({B}_{D}^{{}^{+}}\right)}\le \frac{{b}_{jj}}{{b}_{jj}-\underset{k=j+1}{\overset{n}{\sum }}|{b}_{jk}|\cdot {q}_{j}\left({B}^{+}\right)}=\frac{{b}_{jj}}{{\alpha }_{j}\left({B}^{+}\right)}$ .

$\begin{array}{l}{‖{\left({B}_{D}^{+}\right)}^{-1}‖}_{\infty }\le \mathrm{max}\left\{\frac{1}{\mathrm{min}\left\{{\alpha }_{1}\left({B}^{+}\right),1\right\}}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{1}{\mathrm{min}\left\{{\alpha }_{i}\left({B}^{+}\right),1\right\}}\cdot \underset{j=1}{\overset{n}{\prod }}\frac{{b}_{jj}\cdot {u}_{j}\left({B}^{+}\right)}{{\alpha }_{i}\left({B}^{+}\right)}\right],\\ \text{}\frac{{q}_{1}\left({B}^{+}\right)}{\mathrm{min}\left\{{\alpha }_{1}\left({B}^{+}\right),1\right\}}+\underset{i=2}{\overset{n}{\sum }}\left[\frac{{q}_{i}\left({B}^{+}\right)}{\mathrm{min}\left\{{\alpha }_{i}\left({B}^{+}\right),1\right\}}\cdot \underset{j=1}{\overset{i-1}{\prod }}\frac{{b}_{jj}}{{\alpha }_{j}\left({B}^{+}\right)}\right]\right\}\end{array}$ .(8)

4. 数值算例

$M=\left[\begin{array}{cccc}1.\text{5}& 0.\text{2}& 0.\text{4}& 0.\text{5}\\ -\text{0}\text{.1}& 1.5& 0.5& 0.1\\ 0.5& -0.1& 1.5& 0.1\\ 0.4& 0.4& 0.8& 1.8\end{array}\right]$ ,

$M={B}^{\text{+}}+C$ ，其中

${B}^{\text{+}}=\left[\begin{array}{cccc}1& -0.\text{3}& -0.1& 0\\ -0.6& 1& 0& -0.4\\ 0& -0.6& 1& -0.4\\ -0.4& -0.4& 0& 1\end{array}\right]$ .

$\underset{d\in {\left[0,1\right]}^{4}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }\le \text{41}\text{.1111},$

$\underset{d\in {\left[0,1\right]}^{4}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }\le \text{38}\text{.6334},$

$\underset{d\in {\left[0,1\right]}^{4}}{\mathrm{max}}{‖{\left(I-D+DM\right)}^{-1}‖}_{\infty }\le \text{10}\text{.4724}$ .

A New Error Bound for Linear Complementarity Problems for Weakly Chained Diagonally Dominant B-Matrices[J]. 应用数学进展, 2017, 06(07): 850-856. http://dx.doi.org/10.12677/AAM.2017.67102

1. 1. Chen, X. and Xiang, S. (2007) Perturbation Bounds of P-Matrix Linear Complementarity Problems. SIAM Journal on Optimization, 18, 1250-1265. https://doi.org/10.1137/060653019

2. 2. Cottle, R.W., Pang, J. and Stone, R E. (1992) The Linear Complementarity Problem. Academic Press, San Diego, 1-20.

3. 3. Murty, K.G. (1998) Linear Complementarity, Linear and Nonlinear Programming. Heldermann Verlag, Berlin, 5-18.

4. 4. 黎稳, 郑华. 线性互补问题的数值分析[J]. 华南师范大学学报: 自然科学版, 2015, 47(3): 1-9.

5. 5. Chen, X. and Xiang, S. (2006) Computation of Error Bounds for P-Matrix Linear Complementarity Problem. Mathematical Programming, 106, 513-525. https://doi.org/10.1007/s10107-005-0645-9

6. 6. Chen, T., Li, W., Wu, X., and Vong, S. (2015) Error Bounds for Linear Complementarity Problems of MB-Matrices. Numerical Algorithms, 70, 341-356. https://doi.org/10.1007/s11075-014-9950-9

7. 7. Dai, P. (2011) Error Bounds for Linear Complementarity Problems of DB-Matrices. Linear Algebra and Its Applications, 434, 830-840. https://doi.org/10.1016/j.laa.2010.09.049

8. 8. Dai, P., Lu C. and Li Y. (2013) New Error Bounds for Linear Complementarity Problem with an SB-Matrix. Numerical Algorithms, 64, 741-757.

9. 9. García-Esnaola, M. and Peña, J.M. (2012) Error Bounds for Linear Complementarity Problems Involving BS-Matrices. Applied Mathematics Letters, 25, 1379-1383. https://doi.org/10.1016/j.aml.2011.12.006

10. 10. García-Esnaola, M. and Peña, J.M. (2016) B-Nekrasov Matrices and Error Bounds for Linear Complementarity Problems. Numerical Algorithms, 72, 435-445. https://doi.org/10.1007/s11075-015-0054-y

11. 11. Li, C. and Li, Y. (2016) Note on Error Bounds for Linear Complementarity Problems for B-Matrices. Applied Mathematics Letters, 57, 108-113.

12. 12. Li, C. and Li, Y. (2016) Weakly Chained Diagonally B-Matrices and Error Bounds for Linear Complementarity Problems. Numerical Algorithms, 73, 985-998. https://doi.org/10.1007/s11075-016-0125-8

13. 13. Li, C., Gan, M.T. and Yang, S.R. (2016) A New Error Bounds for Linear Complementarity Problems for B-Matrices. The Electronic Journal of Linear Algebra, 31, 476-484. https://doi.org/10.13001/1081-3810.3250

14. 14. Shivakumar, P.N. and Chew, K.H. (1974) A Sufficient Condition for Nonva-nishing of Determinants. Proceedings of the American Mathematical Society, 43, 63-66. https://doi.org/10.1090/S0002-9939-1974-0332820-0

15. 15. Li, C. and Li, Y. (2016) Weakly Chained Diagonally Dominant B-Matrices and Error Bounds for Linear Complementarity Problems. Numerical Algorithms, 73, 985-998. https://doi.org/10.1007/s11075-016-0125-8

16. 16. 刘新, 杨晓英. 弱链对角占优M-矩阵A的 [J]. 河南科学, 2014, 4: 491-495.

17. 17. 孙德淑. 弱链对角占优B-矩阵线性互补问题的误差界估计[J]. 西南师范大学学报: 自然科学版, 2017, 42: 25-31.