An Iterative Method for Computing the Pseudospectral Abscissa for a Class of Nonlinear Eigenvalue Problems
Wim Michiels, Nicola Guglielmi · SIAM Journal on Scientific Computing · 2012
We consider the following class of nonlinear eigenvalue problems: $\left(\sum_{i=1}^m A_i p_i(\lambda)\right) v= 0,$ where $A_1, \ldots,A_m$ are given $n \times n$ matrices and the functions $p_1, \ldots, p_m$ are assumed to be entire. This does not only include polynomial eigenvalue problems but also eigenvalue problems arising from systems of delay differential equations. Our aim is to compute the $\epsilon$-pseudospectral abscissa, i.e., the supremum of the real parts of the points in the $\epsilon$-pseudospectrum, which is the complex set obtained by joining all solutions of the eigenvalue problem under perturbations $\{ \delta A_i \}_{i=1}^{m}$, of norm at most $\epsilon$, of the matrices $\{ A_i \}_{i=1}^{m}$. Under mild assumptions, guaranteeing the existence of a globally rightmost point of the $\epsilon$-pseudospectrum, we prove that it is sufficient to restrict the analysis to rank-one perturbations of the form $\delta A_i = \beta_i u v^*$, where $u \in \mathbb{C}^n$ and $v \in \mathbb{C}^n$ with $\beta_i \in \mathbb{C}$ for all $i$. Using this main---and unexpected---result we present new iterative algorithms which require only the computation of the spectral abscissa of a sequence of problems obtained by adding rank one updates to the matrices $A_i$. These provide lower bounds to the pseudspectral abscissa and in most cases converge to it. A detailed analysis of the convergence of the algorithms is made. Their applicability and properties are illustrated by means of the delay and polynomial eigenvalue problem.