[Perturbation de valeurs propres de faisceaux matriciels et problème d'affectation optimale]
Nous étendons au cas des valeurs propres de faisceaux de matrices la théorie des perturbations de Višik, Ljusternik et Lidskiı̆, ce qui permet de résoudre certains cas dégénérés de cette théorie. Nous montrons que les asymptotiques au premier ordre des valeurs propres d'un faisceau perturbé peuvent être calculées génériquement au moyen de méthodes de l'algèbre min-plus et d'algorithmes d'affectation optimale. Nous illustrons ce résultat en discutant un problème de perturbation singulière considéré par Najman.
We extend the perturbation theory of Višik, Ljusternik and Lidskiı̆ to the case of eigenvalues of matrix pencils. This extension allows us to solve certain degenerate cases of this theory. We show that the first order asymptotics of the eigenvalues of a perturbed matrix pencil can be computed generically by methods of min-plus algebra and optimal assignment algorithms. We illustrate this result by discussing a singular perturbation problem considered by Najman.
Accepté le :
Publié le :
@article{CRMATH_2004__339_2_103_0,
author = {Akian, Marianne and Bapat, Ravindra and Gaubert, St\'ephane},
title = {Perturbation of eigenvalues of matrix pencils and the optimal assignment problem},
journal = {Comptes Rendus. Math\'ematique},
pages = {103--108},
publisher = {Elsevier},
volume = {339},
number = {2},
year = {2004},
doi = {10.1016/j.crma.2004.05.001},
language = {en},
url = {http://www.numdam.org/articles/10.1016/j.crma.2004.05.001/}
}
TY - JOUR AU - Akian, Marianne AU - Bapat, Ravindra AU - Gaubert, Stéphane TI - Perturbation of eigenvalues of matrix pencils and the optimal assignment problem JO - Comptes Rendus. Mathématique PY - 2004 SP - 103 EP - 108 VL - 339 IS - 2 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2004.05.001/ DO - 10.1016/j.crma.2004.05.001 LA - en ID - CRMATH_2004__339_2_103_0 ER -
%0 Journal Article %A Akian, Marianne %A Bapat, Ravindra %A Gaubert, Stéphane %T Perturbation of eigenvalues of matrix pencils and the optimal assignment problem %J Comptes Rendus. Mathématique %D 2004 %P 103-108 %V 339 %N 2 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2004.05.001/ %R 10.1016/j.crma.2004.05.001 %G en %F CRMATH_2004__339_2_103_0
Akian, Marianne; Bapat, Ravindra; Gaubert, Stéphane. Perturbation of eigenvalues of matrix pencils and the optimal assignment problem. Comptes Rendus. Mathématique, Tome 339 (2004) no. 2, pp. 103-108. doi : 10.1016/j.crma.2004.05.001. http://www.numdam.org/articles/10.1016/j.crma.2004.05.001/
[1] M. Akian, R. Bapat, S. Gaubert, Generic asymptotics of eigenvalues and min-plus algebra, Rapport de recherche 5104, INRIA, Le Chesnay, France, February 2004. Also arXiv: | arXiv
[2] Finding all essential terms of a characteristic maxpolynomial, Discrete Appl. Math., Volume 130 (2003) no. 3, pp. 367-380
[3] Synchronization and Linearity, Wiley, 1992
[4] Nonnegative Matrices and Applications, Cambridge University Press, 1997
[5] An algebra for piecewise-linear minimax problems, Dicrete Appl. Math., Volume 2 (1980), pp. 267-294
[6] Perturbation theory of non-conjugate operators, Zh. Vychisl. Mat. i Mat. Fiz., Volume 1 (1965) no. 1, pp. 73-85
[7] On the Lidskii–Vishik–Lyusternik perturbation theory for eigenvalues of matrices with arbitrary Jordan structure, SIAM J. Matrix Anal. Appl., Volume 18 (1997) no. 4, pp. 793-817
[8] Nongeneric eigenvalue perturbations of Jordan blocks, Linear Algebra Appl., Volume 273 (1998), pp. 45-63
[9] The asymptotic behavior of the eigenvalues of a singularly perturbed linear pencil, SIAM J. Matrix Anal. Appl., Volume 20 (1999) no. 2, pp. 420-427
[10] Combinatorial Optimization, vol. A, Springer, 2003
[11] Solution of some perturbation problems in the case of matrices and self-adjoint or non-selfadjoint differential equations. I, Russian Math. Surveys, Volume 15 (1960) no. 3, pp. 1-73
Cité par Sources :
