An iterative method for computing the pseudospectral abscissa for a class of nonlinear eigenvalue problems

We consider the following class of nonlinear eigenvalue problems, (∑ { Ai pi(λ), i = 1..m}) v = 0, where A1,...,Am are given n x n matrices and the functions p1,... pm 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 ε-pseudospectral abscissa, i.e. the real part of the rightmost point in the ε-pseudospectrum, which is the complex set obtained by joining all solutions of the eigenvalue problem under perturbations { δ Ai : i = 1..m}, of norm at most ε, of the matrices { Ai : i = 1..m}. In analogy to the linear eigenvalue problem we prove that it is sufficient to restrict the analysis to rank-1 perturbations of the form δ Ai = βi u v* where u ∈ ℂn and v ∈ ℂn with &betai ∈ ℂ for all i. Using this main - and unexpected - result we present new iterative algorithms which only require the computation of the spectral abscissa of a sequence of problems obtained by adding rank one updates to the matrices Ai. 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. The methods available for the standard eigenvalue problem in the literature provide a robust and reliable computation but at the cost of full eigenvalue decompositions of order 2 n and singular value decompositions, making them unfeasible for large systems. Moreover, these methods cannot be generalized to nonlinear eigenvalue problems, as we shall explain. Therefore, the presented method is the first generally applicable method for nonlinear problems. In order to be applied it simply requires a procedure to compute the rightmost eigenvalue and the corresponding left and right eigenvectors. In addition, if the matrices Ai are large and sparse then the computation of the rightmost eigenvalue can for many classes of nonlinear eigenvalue problems be performed in an efficient way by iterative algorithms which only rely on matrix vector multiplication and on solving systems of linear equations, where the structure of the matrices (original sparse matrices plus rank one updates) can be exploited. This feature, as well other properties of the presented numerical methods, are illustrated by means of the delay and polynomial eigenvalue problem.nrpages: 26status: publishe