×

Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components. (English) Zbl 1228.65062

This paper deals with the distance (in 2-norm or Frobenius norm) \(w(A)\) of a complex matrix \(A\) to the nearest defective matrix. Considering that the distance of a matrix to the set of matrices having a defective eigenvalue is the same as the distance to the set of matrices having multiple eigenvalues, this problem is equivalent to the relationship between \(w(A)\) and \(c(A)\), where \(c(A)\) is the supremum of the pseudo spectra of \(A\), with distinct elements. It is classical that in general \(w(A)\geq c(A)\). Via coalescence of the pseudospectral components the authors extend a previous result that \(w(A)=c(A)\) with the 2-norm to be valid also with the Frobenius norm. In addition a variant of the Newton’s method to compute the nearest defective matrix and a respective backward error analysis are presented.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Software:

Eigtool; Seigtool
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alam, R.; Bora, S., On sensitivity of eigenvalues and eigendecompositions of matrices, Linear Algebra Appl., 396, 273-301 (2005) · Zbl 1084.15017
[2] Alam, R., Wilkinson’s problem revisited, J. Anal., 4, 176-205 (2006) · Zbl 1193.65035
[3] Bunse-Gerstner, A.; Byers, R.; Mehrmann, V.; Nichols, N. K., Numerical computation of an analytic singular value decomposition of a matrix valued function, Numer. Math., 60, 1, 1-39 (1991) · Zbl 0743.65035
[4] Borwein, J. M.; Lewis, A. S., Convex Analysis and Nonlinear Optimization: Theory and Examples (2000), Springer: Springer New York · Zbl 0953.90001
[5] Burke, J. V.; Lewis, A. S.; Overton, M. L., Optimization and pseudospectra, with applications to robust stability, SIAM J. Matrix Anal. Appl., 25, 80-104 (2003), Corrigendum: http://www.cs.nyu.edu/overton/papers/pseudo_corrigendum.html. · Zbl 1061.15007
[6] Burke, J. V.; Lewis, A. S.; Overton, M. L., Spectral conditioning and pseudospectral growth, Numer. Math., 107, 27-37 (2007) · Zbl 1124.15004
[7] Boulton, L.; Lancaster, P.; Psarrakos, P., On pseudospectra of matrix polynomials and their boundaries, Math. Comput., 77, 313-334 (2007) · Zbl 1141.65026
[8] F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983. Reprinted by SIAM, Philadelphia, 1990.; F.H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983. Reprinted by SIAM, Philadelphia, 1990. · Zbl 0582.49001
[9] J.W. Demmel, A Numerical Analyst’s Jordan Canonical Form, Ph.D. thesis, University of California at Berkeley, 1983.; J.W. Demmel, A Numerical Analyst’s Jordan Canonical Form, Ph.D. thesis, University of California at Berkeley, 1983.
[10] Demmel, J. W., Computing stable eigendecompositions of matrices, Linear Algebra Appl., 79, 163-193 (1986) · Zbl 0627.65031
[11] Demmel, J. W., Nearest defective matrices and the geometry of ill-conditioning, (Reliab. Numer. Comput. (1990), Oxford Univ. Press), 35-55
[12] S. Friedland, J. Nocedal, M.L. Overton, Four quadratically convergent methods for solving inverse eigenvalue problems, in: D.F. Griffiths (Ed.), Numerical Analysis, Pitman Research Note in Mathematics, vol. 140, John Wiley, New York, 1986, pp. 47-65.; S. Friedland, J. Nocedal, M.L. Overton, Four quadratically convergent methods for solving inverse eigenvalue problems, in: D.F. Griffiths (Ed.), Numerical Analysis, Pitman Research Note in Mathematics, vol. 140, John Wiley, New York, 1986, pp. 47-65. · Zbl 0642.65025
[13] Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0576.15001
[14] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0729.15001
[15] Kato, T., A Short Introduction to Perturbation Theory for Linear Operators (1982), Springer-Verlag: Springer-Verlag New York · Zbl 0493.47008
[16] R.A. Lippert, A. Edelman, The computation and sensitivity of double eigenvalues, in: Z. Chen, Y. Li, C.A. Micchelli, Y. Xu (Eds.), Advances in Computational Mathematics: Proceedings of the Guangzhou International Symposium, Dekker, New York, 1999, pp. 353-393.; R.A. Lippert, A. Edelman, The computation and sensitivity of double eigenvalues, in: Z. Chen, Y. Li, C.A. Micchelli, Y. Xu (Eds.), Advances in Computational Mathematics: Proceedings of the Guangzhou International Symposium, Dekker, New York, 1999, pp. 353-393. · Zbl 0932.65055
[17] Lewis, A. S.; Pang, C. H.J., Variational analysis of pseudospectra, SIAM J. Optim., 19, 1048-1072 (2008) · Zbl 1221.15018
[18] A.S. Lewis, C.H.J. Pang, Private communication, 2009.; A.S. Lewis, C.H.J. Pang, Private communication, 2009.
[19] Malyshev, A. N., A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues, Numer. Math., 83, 3, 443-454 (1999) · Zbl 0972.15011
[20] E. Mengi, Private communication, 2009.; E. Mengi, Private communication, 2009.
[21] Moré, J. J.; Munson, T. S., Computing mountain passes and transition states, Math. Program., 100, 151-182 (2004) · Zbl 1063.49021
[22] Nocedal, J.; Overton, M. L., Numerical methods for solving inverse eigenvalue problems, (Pereyra, V.; Reinoza, A., Lecture Notes in Mathematics, vol. 1005 (1983), Springer-Verlag: Springer-Verlag New York) · Zbl 0642.65025
[23] Stewart, G. W., Matrix Algorithms. II: Eigensystems (2001), SIAM · Zbl 0984.65031
[24] Sun, J.-G., A note on simple nonzero singular values, J. Comput. Math., 6, 3, 258-266 (1988) · Zbl 0662.15008
[25] Trefethen, L. N.; Embree, M., Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators (2005), Princeton University Press · Zbl 1085.15009
[26] Varah, J. M., On the separation of two matrices, SIAM J. Numer. Anal., 16, 216-222 (1979) · Zbl 0435.65034
[27] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037
[28] Wilkinson, J. H., On neighbouring matrices with quadratic elementary divisors, Numer. Math., 44, 1-21 (1984) · Zbl 0545.65025
[29] Wilkinson, J. H., Sensitivity of eigenvalues, Util. Math., 25, 5-76 (1984) · Zbl 0551.65018
[30] Wilkinson, J. H., Sensitivity of Eigenvalues. II, Util. Math., 30, 243-286 (1986) · Zbl 0611.65019
[31] T.G. Wright, EigTool: A Graphical Tool for Nonsymmetric Eigenproblems, Oxford University Computer Laboratory, 2002. Available from: <http://web.comlab.ox.ac.uk/pseudospectra/eigtool/>; T.G. Wright, EigTool: A Graphical Tool for Nonsymmetric Eigenproblems, Oxford University Computer Laboratory, 2002. Available from: <http://web.comlab.ox.ac.uk/pseudospectra/eigtool/>
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.