Measures for Robust Stability and Controllability
Michael L. Overton, Emre Mengi · 2009
A linear time-invariant dynamical system is robustly stable if the system and all of its nearby systems in a neighborhood of interest are stable. An important property of robustly stable systems is that they decay asymptotically without exhibiting significant transient behavior. The first part of this thesis work focuses on measures revealing the degree of robust stability. We put special emphasis on pseudospectral measures, those based on the eigenvalues of nearby matrices for a first-order system or matrix polynomials for a higher-order system. We present new algorithms with quadratic rate of convergence for the computation of pseudospectral measures and analyze their accuracy in the presence of rounding errors. We also provide an efficient new algorithm for computing the numerical radius of a matrix, the modulus of the outermost point in the set of Rayleigh quotients of the matrix. We call a system robustly controllable if it is controllable and remains controllable under perturbations of interest. We describe efficient methods for the algorithm for the distance to uncontrollability of a first-order system depends on a grid and is well-suited for low-precision approximation. We then discuss algorithms for high-precision approximation. These are based on the bisection method of Gu and the trisection variant of Burke-Lewis-Overton. These algorithms require the extraction of the real eigenvalues of matrices of size O(n2), typically at a cost of O(n6), where n is the dimension of the state space. We propose a new divide-and-conquer algorithm for real eigenvalue extraction that reduces the cost to O(n4) on average in both theory and practice, and is O(n 5) in the worst case. For higher-order systems we derive a singular-value characterization and exploit this characterization for the computation of the higher-order distance to uncontrollability to low precision. The algorithms in this thesis assume that arbitrary complex perturbations are applicable and require the extraction of the imaginary eigenvalues of Hamiltonian matrices (or even matrix polynomials) or the unit eigenvalues of symplectic pencils (or palindromic matrix polynomials). MATLAB implementations of all algorithms discussed are freely available.