Abstract

Let $A\in\IR\sp{n,n}$ and $B\in\IR\sp{n,m}$. We suggest a new search algorithm for estimating the distance $\mu(A,B)$ of a controllable pair (A,B) to the set of uncontrollable pairs by estimating the global minimum of the function $\sigma\sb{\rm min}(\lbrack A-\lambda I,B\rbrack )$, $\lambda\in\doubc$, where $\sigma\sb{\rm min}(\cdot)$ denotes the smallest singular value of a matrix. Using simple properties of this function due to Ralph Byers one first observes that, provided $rank(B)<n$, the minimization problem can be transformed to a minimization problem in the bounded region $\{(x,z)\Vert x\vert\le\Vert A\Vert\sb2$, $\vert z\vert\le\Vert A\Vert\sb2\}$ in the two dimensional real plane. The algorithm then progressively partitions this region into simplexes and by determining whether their vertices ($x\sb{j},z\sb{j})$ satisfy that $z\sb{j}>\min\sb{y\in\IR}\sigma\sb{\rm min}(\lbrack A-(x\sb{j}+iy)I,B\rbrack )$, it computes after a finite number of steps upper and lower bounds for $\mu(A,B)$. The difference between the two is small if $\mu(A,B)$ is small, while the lower bound is large if $\mu(A,B)$ is large thus ensuring safe decisions. An error analysis together with numerical examples and an operation count are all presented. Only simple modifications of the search region are necessary to extend the applicability of the algorithm to the case when $rank(B)\le n$.