Skip to Main content Skip to Navigation
Theses

Tropical methods for the localization of eigenvalues and application to their numerical computation

Andrea Marchesini 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Résumé : Dans cette thèse nous utilisons des outils d'algèbre tropicale pour localiser et calculer de façon numérique les valeurs propres de matrices et de polynômes matriciels. La première partie porte sur les valeurs propres de matrices, la deuxième se concentre sur les polynômes matriciels tout en rajoutant à l'étude théorique un coté numérique. ``Localiser'' une valeur propre veut dire pouvoir identifier des bornes entre lesquelles elle se trouve. Cela peut être utile dans des situations où l'on n'a besoin que de valeurs propres approximées; ces approximations permettent aussi d'obtenir de bons points d'initialisation d'algorithmes itératifs de calcul des valeurs propres. Notre résultat pour les matrices prend la forme d'inégalités de type majorisation qui contrôlent le module des valeurs propres. Ces bornes peuvent être vues comme une généralisation au cas matriciel d'un résultat prouvé par Ostrowski pour les polynômes : il a montré (en utilisant une terminologie différente) que le produit des k plus grands modules des racines d'un polynôme sont bornées inférieurement et supérieurement par le produit de ses k plus grandes valeurs propres tropicales, à un facteur multiplicatif près qui est indépendent des coefficients du polynôme. Nous prouvons un résultat analogue pour le cas d'une matrice : le produit des k plus grands modules des valeurs propres est borné, à un facteur multiplicatif près, par le produit des k plus grandes valeurs propres tropicales. On notera que les valeurs propres tropicales peuvent être calculées au moyen de la solution d'un problème d'affectation optimale paramètrique, et ceci de façon stable par rapport à des perturbations des données. On notera aussi que le facteur multiplicatif est de nature combinatoire, et qu'il est inspiré d'un résultat de Friedland, lequel a démontré notre inégalité dans le cas particulier k=1. On peut interpréter le module comme une valuation archimédienne; ainsi, il y a une correspondance entre le résultat présenté ici et un travail précédent d'Akian, Bapat et Gaubert, qui ont traité le même problème pour des matrices à coefficients dans un corps avec une valuation non-archimédienne (notamment le corps des séries de Puiseux, équipé de la valuation donnée par l'exposant dominant) et qui ont montré des bornes supérieures plus sérées pour ce cas, sans facteur multiplicatif, et avec égalité générique à la place de bornes supérieures et inférieures. La deuxième partie de la thèse traite du calcul des valeurs propres de polynômes matriciels. Pour des polynôme matriciels linéaires, des algorithmes stables tels que la méthode QZ sont connus dépuis longtemps. L'approche pour les polynômes de degré supérieur consiste souvent à se ramener au cas linéaire, à l'aide de linéarisations telles que la linéarisation compagnon. Cela peut néanmoins dégrader le conditionnement et l'erreur inverse des valeurs propres calculées, par rapport aux coefficients du polynôme originel (même s'ils restent stables par rapport au linéarisé). Pour faire face à cet inconvénient il est commun de procéder à un changement d'échelle avant de linéariser le polynôme. Plusieurs techniques de changement d'échelle ont été proposées. Dans notre travail, nous introduisons un changement d'échelle par multiplication diagonale à gauche et à droite basée sur les valeurs propres tropicales du polynôme matriciel obtenu en prenant la valuation (archimédienne ou non, selon le cas) de chaque coefficient du polynôme originel. Nous étudions l'effet de ce scaling sur le conditionnement et sur l'erreur inverse, en obtenant des formules analytiques ainsi qu'en donnant des exemples numériques, et nous montrons que la précision des valeurs propres calculées peut être améliorée de plusieurs ordres de grandeur.
Document type :
Theses
Complete list of metadatas

Cited literature [49 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01285110
Contributor : Andrea Marchesini <>
Submitted on : Tuesday, March 8, 2016 - 3:58:24 PM
Last modification on : Thursday, March 5, 2020 - 4:48:49 PM
Document(s) archivé(s) le : Sunday, November 13, 2016 - 11:53:46 AM

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

  • HAL Id : tel-01285110, version 1

Citation

Andrea Marchesini. Tropical methods for the localization of eigenvalues and application to their numerical computation. Spectral Theory [math.SP]. Ecole polytechnique X, 2015. English. ⟨tel-01285110⟩

Share

Metrics

Record views

554

Files downloads

788