Approximation of the Pseudospectral Abscissa via Eigenvalue Perturbation Theory

ABSTRACT Reliable and efficient computation of the pseudospectral abscissa in the large‐scale setting is still not settled. Unlike the small‐scale setting where there are globally convergent criss‐cross algorithms, all algorithms in the large‐scale setting proposed to date are at best locally convergent. We first describe how eigenvalue perturbation theory can be put in use to estimate the globally rightmost point in the ‐pseudospectrum if is small. Our treatment addresses both general nonlinear eigenvalue problems, and the standard eigenvalue problem as a special case. For small , the estimates by eigenvalue perturbation theory are quite accurate. In the standard eigenvalue case, we even derive a formula with an error. For larger , the estimates can be used to initialize the locally convergent algorithms. We also propose fixed‐point iterations built on the perturbation theory ideas for large that are suitable for the large‐scale setting. The proposed fixed‐point iterations initialized by using eigenvalue perturbation theory converge to the globally rightmost point in the pseudospectrum in a vast majority of the cases that we experiment with.