On sensitivity of eigenvalues and eigendecompositions of matrices
type: Item
instance of: scholarly article
title: On sensitivity of eigenvalues and eigendecompositions of matrices
zbMATH Open document ID: 1084.15017
author: Rafikul Alam
author: Shreemayee Bora
published in: Linear Algebra and its Applications
publication date: 2005-02-22T00:00:00Z
review text: 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.
reviewed by: Ludwig Elsner
Mathematics Subject Classification ID: 15A42
Mathematics Subject Classification ID: 65F15
zbMATH DE Number: 2136682
zbMATH Keywords: eigendecomposition
zbMATH Keywords: pseudospectrum
zbMATH Keywords: stability
zbMATH Keywords: geometrical separation of eigenvalues
zbMATH Keywords: multiple eigenvalues
zbMATH Keywords: numerical examples
MaRDI profile type: Publication
full work available at URL: j.laa.2004.10.013
OpenAlex ID: W2139330196
cites work: On Stable Eigendecompositions of Matrices
cites work: Stability of eigenvalues and spectral decompositions under linear perturbation
cites work: Effect of linear perturbation on spectra of matrices
cites work: Analytic perturbation theory for matrices and operators. Licensed ed
cites work: Optimization and Pseudospectra, with Applications to Robust Stability
cites work: Robust stability and a criss-cross algorithm for pseudospectra
cites work: Computing stable eigendecompositions of matrices
cites work: On condition numbers and the distance to the nearest ill-posed problem
cites work: Computing spectral value sets using the subharmonicity of the norm of rational matrices
cites work: Q4396493
cites work: Finding well-conditioned similarities to block-diagonalize nonsymmetric matrices is NP-hard
cites work: Pseudospectre d'une suite d'opérateurs bornés
cites work: Q4269334
cites work: Q4257513
cites work: A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues
cites work: Properties of a matrix with a very ill-conditioned eigenproblem
cites work: Q4115333
cites work: Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems
cites work: Q3812379
cites work: Q4288951
cites work: Pseudospectra of Linear Operators
cites work: Q5674306
cites work: Note on matrices with a very ill-conditioned eigenproblem
cites work: On neighbouring matrices with quadratic elementary divisors
cites work: Q3343313
cites work: Q3750910
cites work: On a theorem of Feingold
DOI: 10.1016/J.LAA.2004.10.013
description: scientific article; zbMATH DE number 2136682