On sensitivity of eigenvalues and eigendecompositions of matrices (Q1763838): Difference between revisions

Two problems concerning the sensitivity of eigenvalues and eigendecompositions of matrices are studied and solved in a certain sense. The first problems posed by \textit{J. H. Wilkinson} [The algebraic eigenvalue problem (1965; Zbl 0258.65037); pp. 90--93] is to find and characterise for a given matrix \(A\) with simple eigenvalues a nearest matrix \(A'\) with multiple eigenvalues.\ Let \[ d(A) = \min\{\| A-A'\| :A' \text{ has multiple eigenvalues}\}. \] Let \(\Lambda(A)\) denote the spectrum of \(A\) and for \(\varepsilon > 0\) let \[ \Lambda_{\varepsilon}(A)=\bigcup\{\lambda(A'): \| A-A'\| \leq \varepsilon\} \] the \(\varepsilon\)-pseudospectrum of \(A\). The geometric separation \(gsep(\lambda)\) of an eigenvalue \(\lambda \in \Lambda(A)\) is the smallest \(\varepsilon\) for which a component of \(\Lambda_{\varepsilon}(A)\) containing \(\lambda\) coalesces with another component. It is shown that if for some \(\varepsilon > 0\) two components of \(\Lambda_{\varepsilon}(A)\) coalesce at \(z_0\), then \(z_0\) is a multiple eigenvalue of some \(A'\) with \(\| A-A'\| = \varepsilon\). This leads to the main result that \[ d(A)=\min\{gsep(\lambda): \lambda \in \Lambda(A)\}. \] Hence \(d(A)\) can be read off from the pseudospectrum. In the last chapter a more general problem, formulated by \textit{J. W. Demmel} [Linear Algebra Appl. 79, 163--193 (1986; Zbl 0627.65031)], concerning stability of eigendecompositions is solved in a similar way. Here an eigendecomposition of \(A\) is \(A=Xdiag(A_i)X^{-1}\) where \(\Lambda(A_i) \cap \Lambda(A_j) = \emptyset\) for \(i \neq j\).\ Defining the geometric separation of a subset \(\sigma\) of \(\Lambda(A)\), \(gsep(\sigma, A)\) in a similar way it is shown that \(\varepsilon = \min_i gsep(\Lambda(A_i),A)\) is the largest value for which the eigendecomposition is continuous in the set \(\{A': \| A-A'\| \leq \varepsilon\}\). A computational procedure for determining \(d(A)\) is described and some numerical examples are given.