Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure. (English) Zbl 1229.65067
The authors develop a numerical isospectral method including convergence results and error estimates for the solution of the following generalized inverse eigenvalue problem:
Given a set of complex numbers \(\lambda = \{\lambda_j\} \in {\mathbb{C}, \, j = 1(1)n}\), a subset of index subscript pairs \({(i_{\nu}, j_{\nu})}_{\nu = 1}^l, \, 1 \leqq i_{\nu}, j_{\nu} \leqq n\), and a subset of prescribed values \(a_\nu \in \mathbb{R}, \, a_\nu \geqq 0, \, \nu = 1(1)l\).
Find a nonnegative matrix \(X = \{x_{i,j}\} \in {\mathbb{R}}^{n \times n}\) such that \(\lambda (X) = \lambda\) and \(x_{i_\nu, j_\nu} = a_{\nu}, \, \nu = 1(1)l\).
A corresponding problem is treated for symmetric nonnegative matrices.
The described problems reduce to the common nonnegative inverse eigenvalue problems if the subset of prescribed entries \(\{a_\nu\}\) is empty. The here investigated problems have multiple solutions as the most inverse eigenvalue problems.
Roughly speaking, the isospectral method for the reconstruction of the matrix \(X\) consists of the finding the intersection of a set determinated by the spectral constraints \(\{\lambda_j\}\) and a set depending on the structural constraints \(\{a_\nu\}\). The intersection is formulated as the distance between the two sets which is minimized using the steepest descent method. The first set is built of the isospectral surface \(V \Lambda V^{-1}, \, V \in {\mathbb{R}}^{n \times n}\), where \(V\) is nonsingular and \(\Lambda \in {\mathbb{R}}^{n \times n}\) denotes a diagonal block matrix (with blocks of order 1 or 2) with the given spectrum. The second set is constructed by the Hadamard product \(A \circ A\) of the matrix \(A\) built by the prescribed entries.
The ill-posedness of nonnegative inverse eigenvalue problems (NIEP) caused by nonunique solutions is transferred to the dependence of solutions of ordinary differential equations on initial values, i.e., different initial values correspond with different solutions of the NIEP.
The results are validated by numerical tests, particulary a nonnegative symmetric tridiagonal matrix is reconstructed from the prescribed spectrum and with positive codiagonal entries.
For important applications the authors refer to other publications.
Given a set of complex numbers \(\lambda = \{\lambda_j\} \in {\mathbb{C}, \, j = 1(1)n}\), a subset of index subscript pairs \({(i_{\nu}, j_{\nu})}_{\nu = 1}^l, \, 1 \leqq i_{\nu}, j_{\nu} \leqq n\), and a subset of prescribed values \(a_\nu \in \mathbb{R}, \, a_\nu \geqq 0, \, \nu = 1(1)l\).
Find a nonnegative matrix \(X = \{x_{i,j}\} \in {\mathbb{R}}^{n \times n}\) such that \(\lambda (X) = \lambda\) and \(x_{i_\nu, j_\nu} = a_{\nu}, \, \nu = 1(1)l\).
A corresponding problem is treated for symmetric nonnegative matrices.
The described problems reduce to the common nonnegative inverse eigenvalue problems if the subset of prescribed entries \(\{a_\nu\}\) is empty. The here investigated problems have multiple solutions as the most inverse eigenvalue problems.
Roughly speaking, the isospectral method for the reconstruction of the matrix \(X\) consists of the finding the intersection of a set determinated by the spectral constraints \(\{\lambda_j\}\) and a set depending on the structural constraints \(\{a_\nu\}\). The intersection is formulated as the distance between the two sets which is minimized using the steepest descent method. The first set is built of the isospectral surface \(V \Lambda V^{-1}, \, V \in {\mathbb{R}}^{n \times n}\), where \(V\) is nonsingular and \(\Lambda \in {\mathbb{R}}^{n \times n}\) denotes a diagonal block matrix (with blocks of order 1 or 2) with the given spectrum. The second set is constructed by the Hadamard product \(A \circ A\) of the matrix \(A\) built by the prescribed entries.
The ill-posedness of nonnegative inverse eigenvalue problems (NIEP) caused by nonunique solutions is transferred to the dependence of solutions of ordinary differential equations on initial values, i.e., different initial values correspond with different solutions of the NIEP.
The results are validated by numerical tests, particulary a nonnegative symmetric tridiagonal matrix is reconstructed from the prescribed spectrum and with positive codiagonal entries.
For important applications the authors refer to other publications.
Reviewer: Georg Hebermehl (Berlin)
MSC:
| 65F18 | Numerical solutions to inverse eigenvalue problems |
| 65K10 | Numerical optimization and variational techniques |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
Keywords:
nonnegative inverse eigenvalue problem; nonnegative symmetric inverse eigenvalue problem; structured matrix; isospectral flow method; minimization problem; steepest descent method; numerical examplesReferences:
| [1] | Chu, M. T., Inverse eigenvalue problems, SIAM Rev., 40, 1, 1-39 (1998) · Zbl 0915.15008 |
| [2] | Chu, M. T.; Golub, G., Structured inverse eigenvalue problems, Acta Numer., 11, 1-71 (2002) · Zbl 1105.65326 |
| [3] | Berman, A.; Plemmons, R. J., (Nonnegative Matrices in the Mathematical Sciences. Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics, vol. 9 (1994), SIAM: SIAM Philadelphia) · Zbl 0815.15016 |
| [4] | Minc, H., Nonnegative Matrices (1988), Wiley: Wiley New York · Zbl 0638.15008 |
| [5] | Perfect, H., On positive stochastic matrices with real characteristic roots, Proc. Cambridge Philos. Soc., 48, 271-276 (1952) · Zbl 0046.35003 |
| [6] | Kellogg, R., Matrices similar to a positive or essentially positive matrix, Linear Algebra Appl., 4, 191-204 (1971) · Zbl 0215.37504 |
| [7] | Salzmann, F. L., A note on eigenvalues of nonnegative matrices, Linear Algebra Appl., 5, 329-338 (1972) · Zbl 0255.15009 |
| [8] | Fiedler, M., Eigenvalues of nonnegative symmetric matrices, Linear Algebra Appl., 9, 119-142 (1974) · Zbl 0322.15015 |
| [9] | Soules, G. W., Constructing symmetric nonnegative matrices, Linear Multilinear Algebra, 13, 241-251 (1983) · Zbl 0516.15013 |
| [10] | Guo, W., An inverse eigenvalue problem for nonnegative matrices, Linear Algebra Appl., 249, 67-78 (1996) · Zbl 0865.15009 |
| [11] | Guo, W., Eigenvalues of nonnegative matrices, Linear Algebra Appl., 266, 261-270 (1997) · Zbl 0903.15003 |
| [12] | Egleston, P. D.; Lenker, T. D.; Narayan, S. K., The nonnegative inverse eigenvalue problem, Linear Algebra Appl., 379, 475-490 (2004) · Zbl 1040.15009 |
| [13] | Soto, R. L.; Rojo, O., Applications of a Brauer theorem in the nonnegative inverse eigenvalue problem, Linear Algebra Appl., 416, 844-856 (2006) · Zbl 1097.15014 |
| [14] | Laffey, T. J.; Šmigoc, H., Construction of nonnegative symmetric matrices with given spectrum, Linear Algebra Appl., 421, 97-109 (2007) · Zbl 1116.15012 |
| [15] | Soto, R. L., Existence and construction of nonnegative matrices with prescribed spectrum, Linear Algebra Appl., 369, 169-184 (2003) · Zbl 1031.15018 |
| [16] | Chu, M. T., A list of matrix flows with applications, (Hamiltonian and Gradient Flows, Algorithms and Control Fields Inst. Commun., vol. 3 (1994), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 87-97 · Zbl 0815.65094 |
| [17] | Chu, M. T.; Driessel, K. R., Constructing symmetric nonnegative matrices with prescribed eigenvalues by differential equations, SIAM J. Math. Anal., 22, 1372-1387 (1991) · Zbl 0739.58053 |
| [18] | Chu, M. T.; Guo, Q., A numerical method for the inverse stochastic spectrum problem, SIAM J. Matrix Anal. Appl., 19, 1027-1039 (1998) · Zbl 0917.65037 |
| [19] | Orsi, R., Numerical methods for solving inverse eigenvalue problems for nonnegative matrices, SIAM J. Matrix Anal. Appl., 28, 190-212 (2006) · Zbl 1113.65034 |
| [20] | Hadeler, K. P.; Chugunov, V. N., Inverse matrix eigenvalue problem, J. Math. Sci., 98, 1, 51-136 (2000) · Zbl 0954.65032 |
| [21] | Chu, M. T.; Diele, F.; Sgura, I., Gradient flow method for matrix completion with prescribed eigenvalues, Linear Algebra Appl., 379, 85-112 (2004) · Zbl 1055.15026 |
| [22] | Rojo, O.; Soto, R.; Egaña, J., A note on the construction of a positive oscillatory matrix with a prescribed spectrum, Comput. Math. Appl., 41, 353-361 (2001) · Zbl 0984.65038 |
| [23] | Kirsch, A., An introduction to the Mathematical Theory of Inverse Problems (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0865.35004 |
| [24] | Woodward, L. A., Introduction to the Theory of Molecular Vibrations and Vibrational Spectroscopy (1972), Oxford University Press: Oxford University Press Oxford |
| [25] | Wilson, E. B.; Decius, J. C.; Cross, P. C., Molecular Vibrations (1955), McGraw-Hill: McGraw-Hill New York |
| [26] | Gladwell, G. M.L., Inverse Problems in Vibration (2004), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0646.73013 |
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.
