Probabilistic approach to the stability of interval matrices (Q5932081)

Determining whether or not all \(n \times n\)-matrices \(A = (a_{ij})\) that have entries within the bounds \(b_{ij} \leq a_{ij} \leq B_{ij}\) are stable is a problem of NP-complexity. Therefore, given large \(n\), it is hopeless to find an effective algorithm for its solution. However, the authors show that if the task is changed into the following probabilistic problem, lower estimates for the stability radius \(\gamma\) can be given with the help of the Central Limit Theorem: Let \(\Delta_n(\gamma)\) be a random matrix of order \(n \times n\) the entries of which are i.i.d. uniformly distributed over the interval \([ -\gamma, \gamma ]\). Given the significance level \(\alpha\), find the maximal bound \(\gamma\) for which \(A_n := -I_n + \Delta_n(\gamma)\) is stable with probability \(\geq 1 - \alpha\). The authors compute lower estimates for \(\gamma\) in the form \(\frac{const}{\sqrt{n}} r_R(A) \leq \gamma\) with an explicit constant depending on \(\alpha\) and the ``real'' stability radius \( r_R(A) :=\inf \{ \varepsilon > 0 \mid A+B\) unstable, \(\|B\|\leq \varepsilon \}\).