Measures for Robust Stability and Controllability

Candidate: Emre Mengi

Advisor: Michael Overton

A linear time-invariant dynamical system is robustly stable if the system as well as all
of its nearby systems in a neighborhood of interest are stable. An important property of
robustly stable systems is they decay asymptotically without exhibiting significant transient
behavior. The first part of this thesis work focuses on measures revealing the degree of
robust stability of a dynamical system. 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 algorithms for the computation of
pseudospectral measures for continuous and discrete systems with quadratic rate of convergence
and analyze their accuracy in the presence of rounding errors. We also provide an efficient
algorithm for the numerical radius of a matrix, the modulus of the outermost point in the
field of values (the set of Rayleigh quotients) of the matrix. These algorithms are inspired
by algorithms of Byers, Boyd-Balakrishnan and Burke-Lewis-Overton.

The second part is devoted to indicators of robust controllability. We call a system robustly
controllable if it is controllable and remains controllable under perturbations of interest.
We describe efficient methods for the computation of the distance to the closest uncontrollable
system. Our first algorithm for the first-order distance to uncontrollability depends on a grid
and is well-suited for low precision approximation. We then discuss algorithms for high precision
approximation of the first-order distance to uncontrollability. 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 that reduces the cost to $O(n4)$ on average in both theory and
practice and $O(n5)$ in the worst case. The new iterative approach to the extraction of real
eigenvalues may also be useful in other contexts. 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 arbitrary
complex perturbations are applicable to the input system and usually 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).