Rapport Gratuit
Équation de Sylvester et méthode ADI
De nombreux problèmes de modélisation en mathématiques appliquées débouchent sur la résolution approchée d’une équation de Sylvester AX − XB = C d’inconnue X en grande dimension. En particulier, la discrétisation d’une équation aux dérivées partielles elliptique à variables séparables sur un domaine rectangulaire, où A et B représentent respectivement des opérateurs de différences finies dans les directions d’abscisse et d’ordonnée produit naturellement ce type d’équation. Dans ce chapitre, on donne la définition et quelques propriétés élémentaires des équations de Sylvester puis on expose rapidement quelques méthodes classiques de résolution d’une telle équation. On s’intéresse ensuite à la méthode ADI qui jouera un rôle important dans cette thèse, on présente donc cette méthode ainsi que quelques unes de ces variantes dédiées à la résolution approchée d’une équation de Sylvester. La majoration de l’erreur commise par la méthode ADI pour la résolution d’une équation de Sylvester après n itérations donne lieu à un problème d’approximation rationnelle discret dans le plan complexe, le troisième problème de Zolotarev. On définit alors ce problème avant de donner quelques autres connexions de celui-ci avec des problémes d’algèbre linéaire.
Équation de Sylvester
Définition 1.1.1. On note équation de Sylvester l’équation
AX − XB = C, (1.1)
où A ∈ C N×N , B ∈ C M×M, C ∈ C N×M sont trois matrices à coefficients complexes données, et X l’inconnue, également élément de C N×M. Dans le cas où A = −B, l’équation (1.1) devient
AX + XA = C
et est appelée équation de Lyapounov ou parfois équation de Sylvester symétrique.
Donnons le résultat classique d’existence et d’unicité de la solution d’une équation de Sylvester après la définition du produit de Kronecker qui permet de reformuler une telle équation en système linéaire.
Définition 1.1.2. Soit M une matrice carrée à coefficients complexes. On note dorénavant Λ(M) le spectre de M.
Méthodes de résolution d’une équation de Sylvester
Méthodes directes de résolution d’une équation de Sylvester
Il existe beaucoup de méthodes conçues pour la résolution approchée d’une équation de Sylvester (1.1)
AX − XB = C,
où A et B sont de tailles respectives N × N et M × M, mais même les méthodes les plus efficaces nécessitent O(M3 + N3 ) opérations, et surtout, ne tiennent pas compte de la structure de la matrice C qui est de rang petit devant N et M dans beaucoup d’applications. La formulation en produit de Kronecker permet de transformer la résolution d’une équation de Sylvester en résolution de système linéaire, et cette résolution nécessite O(N3M3 ) opérations par la méthode d’élimination de Gauss. Citons ici les méthodes directes décrites dans la littérature données par les algorithmes de Bartels-Stewart [BaSt72], Hessenberg-Schur [GoNaVL79] et Hammarling [Ham82]. Ces algorithmes reposent tous sur le même principe, à savoir transformer A en une matrice triangulaire ou une matrice de Hessenberg par une suite de transformations élémentaires. Si A = U ⋆T U et B = V RV ⋆ où U et V sont unitaires et T et R sous forme de Schur ou de Hessenberg, on obtient en multipliant l’équation de Sylvester (1.1) par U ⋆ à gauche et par V à droite l’équation de Sylvester
T (U⋆XV ) + (U⋆XV ) R = U⋆CV, (1.2)
à coefficients des matrices de Schur ou de Hessenberg. On peut maintenant obtenir la solution de l’équation modifiée (1.2) en résolvant des systèmes triangulaires supérieurs, et retrouver ensuite la matrice X par multiplication par des matrices unitaires. Ces algorithmes de résolution directe ont tous une complexité qui exclut de facto toute tentative de résolution d’une équation de Sylvester pour des matrices de grandes dimensions. Dans le cas de deux matrices A et B creuses, cas par exemple d’un schéma de discrétisation aux différences finies, ces algorithmes présentent enfin l’inconviénient majeur de ne pas conserver cette structure creuse, ce qui impose le stockage de beaucoup plus de coefficients lors de la transformation de A et B sous forme de Schur ou de Hessenberg. La méthode ADI de Peaceman et Rachford [PeRa55] et ses variantes forment la classe des algorithmes les plus utilisés pour la résolution approchée d’une équation de Sylvester dans le cas de matrices creuses de grande dimension .
Itération ADI, estimation de l’erreur
Avant de définir la méthode ADI et d’évaluer l’erreur commise lors de la résolution approchée d’une équation de Sylvester, on rappelle ici quelques faits bien connus concernant l’algorithme du gradient conjugué afin de mettre en perspective les résultats obtenus. L’algorithme du gradient conjugué est un algorithme très utilisé pour la résolution approchée du système linéaire AX = b où A ∈ R N×N est symétrique définie positive.
L’article de Penzl [Pe00b] généralise la méthode de Smith pour une équation de Lyapounov en considérant une suite périodique de paramètres, ce qui permet d’accélérer la convergence pour un choix judicieux de la périodicité, on rencontre ce type de méthode sous le nom de méthode de Smith cyclique. On mentionne également l’article récent [BeLiTr08] qui généralise les travaux de [Pe00b] au cas d’une équation de Sylvester et fait le point sur les différentes généralisations de la méthode ADI présentées ici. Les travaux de Benner et de ses collaborateurs [BeQu02] et [BeQu06] étudient de plus l’utilisation de la méthode ADI et ses généralisations dans un contexte de réduction de système en théorie du contrôle linéaire. La thèse récente de Sabino [Sa06] fait l’inventaire de l’ensemble des algorithmes évoqués dans cette section, les compare à travers de nombreux exemples numériques et propose une méthode de résolution d’une équation de Lyapounov basée sur une méthode de Smith par blocs. On cite enfin la méthode ADI généralisée, notée dans la littérature GADI, où l’on n’impose plus l’alternance stricte entre la résolution des deux équations de (1.5). Cette méthode a été étudiée dans [LeRe93] et donne lieu à un problème d’approximation rationnelle dans Rn,m, où les degrés du numérateur et du dénominateur des fractions rationnelles mises en jeu ne sont plus supposés égaux.
Problème de Zolotarev et algèbre linéaire
Valeurs singulières des matrices de petit rang de déplacement
Le lien exposé ci-dessous entre le problème de Zolotarev pour un ensemble discret et la décroissance des valeurs singulières de matrices de petit rang de déplacement est important dans les applications, mais nous sera également utile à plusieurs reprises dans l’étude théorique que nous mènerons par la suite. En particulier, nous utiliserons ce lien pour la preuve d’un cas de dégénérescence de la solution du problème de Zolotarev pour des ensembles discrets, mais également pour établir une borne inférieure dans l’étude asymptotique de ce problème.
Définition 1.3.1. Pour A, B, deux matrices comme en (1.1), le rang de déplacement par rapport au couple (A, B) de la matrice X est l’entier ρ(A,B) défini par
ρ(A,B)(X) := rg(AX − XB).
Pour certains choix simples de (A, B), par exemple des matrices diagonales, des matrices structurées comme les matrices de Vandermonde, de Krylov, de Cauchy, de Pick, de Loewner, de Hankel, et d’autres encore, le rang de déplacement par rapport à (A, B) est égal à 1 ou 2, voir [Be04]. Avec les notations classiques σ1(X) > σ2(X) > σ3(X) > … pour les valeurs singulières de la matrice X, on donne dans [Be04] des éléments de preuve du résultat suivant : pour tous les entiers n > 1 tels que 1 + nρ < min(M, N) .
|
Table des matières
Introduction
1 Équation de Sylvester et méthode ADI
1.1 Équation de Sylvester
1.2 Méthodes de résolution d’une équation de Sylvester
1.2.1 Méthodes directes de résolution d’une équation de Sylvester
1.2.2 Itération ADI, estimation de l’erreur
1.2.3 Problème de Zolotarev
1.2.4 Variantes de la méthode ADI
1.3 Problème de Zolotarev et algèbre linéaire
1.3.1 Valeurs singulières des matrices de petit rang de déplacement
1.3.2 Approximation du signe
2 Équation de Sylvester et réalisation d’un système dynamique
2.1 Introduction
2.2 Système dynamique continu
2.3 Fonction de transfert
2.4 Commandabilité et observabilité
2.5 Réalisation d’un système dynamique
2.6 Grammiens
2.7 Réalisation équilibrée
2.8 Grammien croisé
3 Problème de Zolotarev pour des ensembles discrets
3.1 Présentation du problème
3.1.1 Cas classique
3.1.2 Cas discret
3.2 Existence et dégénérescence de la solution
3.2.1 Existence du minimiseur pour le problème de Zolotarev
3.2.2 Étude exhaustive d’un cas simple
3.2.3 Dégénérescence d’un minimiseur
4 Minimisation d’énergie sous contrainte : cas des mesures signées
4.1 Contexte, première définitions
4.1.1 Superharmonicité, principe du maximum
4.1.2 Potentiel et énergie logarithmique
4.2 Minimisation d’énergie sous contrainte
4.2.1 Semi-continuité inférieure de l’énergie
4.2.2 Problème de minimisation, existence et unicité du minimiseur
4.2.3 Régularité du potentiel logarithmique
4.2.4 Conditions d’équilibre pour le minimiseur
4.2.5 Un cas particulier important
4.2.6 Caractérisations de la mesure minimisante
4.3 Synthèse
5 Étude asymptotique du problème de Zolotarev
5.1 Hypothèses techniques
5.2 Résultat principal
5.2.1 Borne supérieure
5.2.2 Points de Fekete rationnels discrets
5.2.3 Quantité de Zolotarev contrainte par localisation des pôles et zéros
5.2.4 Points de Fekete et fractions rationnelles
5.2.5 Borne inférieure
Conclusion
Télécharger le rapport complet
