TY - JOUR

T1 - Entrywise perturbation theory for diagonally dominant M-matrices with applications

AU - Alfa, Attahiru Sule

AU - Xue, Jungong

AU - Ye, Qiang

PY - 2002/1

Y1 - 2002/1

N2 - This paper introduces a new perspective on the study of computational problems related to diagonally dominant M-matrices by establishing some new entrywise perturbation results. If a diagonally dominant M-matrix is perturbed in a way that each off-diagonal entry and its row sums (i.e. the quantities of diagonal dominance) have small relative errors, we show that its determinant, cofactors, each entry of the inverse and the smallest eigenvalue all have small relative errors. The error bounds are given and they do not depend on any condition number. Applying this result to the studies of electrical circuits and tail probabilities of a queue whose embedded Markov chains is of GI/M/1 type, we discuss the relative sensitivity of the operating speed of circuits and of the percentile of the queue length, respectively.

AB - This paper introduces a new perspective on the study of computational problems related to diagonally dominant M-matrices by establishing some new entrywise perturbation results. If a diagonally dominant M-matrix is perturbed in a way that each off-diagonal entry and its row sums (i.e. the quantities of diagonal dominance) have small relative errors, we show that its determinant, cofactors, each entry of the inverse and the smallest eigenvalue all have small relative errors. The error bounds are given and they do not depend on any condition number. Applying this result to the studies of electrical circuits and tail probabilities of a queue whose embedded Markov chains is of GI/M/1 type, we discuss the relative sensitivity of the operating speed of circuits and of the percentile of the queue length, respectively.

UR - http://www.scopus.com/inward/record.url?scp=0036002579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036002579&partnerID=8YFLogxK

U2 - 10.1007/s002110100289

DO - 10.1007/s002110100289

M3 - Article

AN - SCOPUS:0036002579

SN - 0029-599X

VL - 90

SP - 401

EP - 414

JO - Numerische Mathematik

JF - Numerische Mathematik

IS - 3

ER -