Structure de Toeplitz et fonctions de matrices

Structure de Toeplitz et fonctions de matrices

Calculer une fonction de matrice de Toeplitz f(A) pour A ∈ C n×n et f une fonction apparaît nécessaire dans plusieurs applications mathématiques comme les systèmes de préfiltres [3, Section 7.2.1.2], les résolutions d’EDP obtenues par semi-discrétisation des equations intégrales [67, example 3], [73] ou encore des problèmes aux valeurs propres [57, Section 2.10]. Cependant les méthodes classiques de calcul de fonctions de matrices ne prenant pas compte de la structure de la matrice A, celles-ci vont généralement nécessiter un coût de l’ordre de n3 opérations élémentaires.

Définitions et propriétés des fonctions de matrices

Le premier à étudier le domaine des fonctions de matrices fut Cayley dans A Memoir on the Theory of Matrices paru en 1858 ([21]), dans lequel il étudie la fonction de matrice racine carrée. Puis les ingénieurs aérospatiaux Frazer, Duncan, et Collar ont montré dans Applications to Dynamics and Differential Equations ([35]) l’importance et l’utilité de la fonction exponentielle de matrice. Nous renvoyons le lecteur à [15] pour d’autres exemples concrets de l’application des fonctions de matrices.

Quelques méthodes de calcul

L’emploi des définitions précédentes de fonctions de matrices n’est généralement pas une bonne idée pour une implémentation numérique. Cependant, des alternatives pour l’implémentation numérique d’une fonction de matrice existent, certaines ne prenant en compte ni la structure de la matrice ni la fonction considérée et d’autres plus spécifiques à certaines fonctions. Nous décrivons brièvement ici quelques méthodes numériques pour le calcul de la fonction de matrice f(A), avec l’étude du cas particulier des fonctions polynomiales à l’aide la méthode de Horner, puis dans un cadre plus général, nous rappelons la méthode de Schur-Parlett applicable à toute fonction f. Nous renvoyons également au livre de Higham [57] pour d’autres références sur le calcul de f(A).

Méthodes d’approximation

Plutôt que de calculer nos fonctions de matrices à l’aide d’algorithmes directes, puisque les fonctions polynomiales ou rationnelles sont généralement plus facilement calculables que les fonctions elles-mêmes, on peut alors chercher si un approximant polynômial ou rationnel pour une fonction de matrice existe. Comme l’approximation polynomiale et rationnelle en dimension 1 dispose d’une large littérature, nous pouvons envisager de transposer ces approximants au cas matriciel et ainsi considérer la fonction de matrice g(A) approchant f(A) lorsque g est un approximant polynomial ou rationnel de la fonction f en dimension 1. Dans cette section, nous motivons l’étude des approximants de fonctions à l’aide des ensembles K-spectraux, nous permettant de mesurer l’erreur d’approximation de notre fonction de matrice f(A) par g(A) à l’aide de l’erreur d’approximation en dimension 1. Ce résultat nous permet alors de considérer plusieurs approximants potentiels de la fonction tels que les polynômes de Faber ou les approximants de Padé.

Rang de déplacement et générateurs : les matrices Toeplitz-lik

Nous venons de voir que l’image par l’opérateur de déplacement d’une matrice de Toeplitz possédait une structure particulière avec une colonne et une ligne non nulles. Il nous reste alors à voir comment exploiter cette structure. D. Kressner et R. Luce, en considérant l’opérateur de déplacement sous la forme Stein T 7→ T − ZT Z avec Z = Z0 matrice shift [65], définissent un ensemble de matrices à partir du rang de l’image par cet opérateur de déplacement. Lorsque celui-ci est petit, l’image est alors décomposée comme un produit de matrices de dimension inférieure, permettant par la suite d’obtenir une arithmétique particulière sur laquelle les différentes opérations telles que la somme, le produit ou l’inversion peuvent être effectuées avec une complexité réduite par rapport à l’arithmétique pleine.

Rang de déplacement

Nous venons de voir que l’opérateur de déplacement appliqué à une matrice de Toeplitz donne une matrice image avec structure particulière. On peut alors tenter d’exploiter cette structure en observant en particulier le rang des matrices images par cet opérateur.

Définition 2.2.1. [61, Lemma 1] Soit X ∈ C n×n . Alors le rang de la matrice image S(X) est appelé le rang de déplacement de X, noté ρ = ρ(X) := rang(S(X)).

Exemple 2.2.2.
— La matrice identité, cas particulier des matrices de Toeplitz, est de rang de déplacement 1.
— Pour toute matrice X ∈ C n×n de rang de déplacement ρ et pour tout scalaire s 6= 0, s ∈ C, ρ(sX) = ρ(X).

Proposition 2.2.3. Soit T ∈ C n×n matrice de Toeplitz. Alors T est de rang de déplacement inférieur ou égal à 2.

Démonstration. D’après (2.2), pour toute matrice de Toeplitz T = (ti−j )i,j=1,…,n, S(T) comporte au plus une ligne et une colonne non nulles. Par la méthode du pivot de Gauss, on réduit cette matrice à au plus 2 lignes ou 2 colonnes non nulles.

Remarque 2.2.4. Dans le cas où t0 6= 0 et ti,j = 0 pour tout i 6= j, T = t0I et S(T) est constitué d’un seul élément non-nul et donc T est de rang de déplacement 1. Si T est une matrice circulante non nulle, S(T) est composé d’une seule colonne non nulle et peut se réduire à un seul élément non nul par pivot de Gauss et est donc S(T) de rang de déplacement 1. Si T est anti-circulante, alors S(T) est composée d’une seule ligne non-nulle et est donc de rang de déplacement 1.

Lorsque T ∈ C n×n est de Toeplitz, son inverse ou son produit avec une autre matrice de Toeplitz n’est pas nécessairement une matrice de Toeplitz. Cependant ces matrices possèdent des caractéristiques communes en termes du rang de déplacement :

Définition 2.2.5. Soient n ∈ N∗ et T ∈ C n×n . Alors T est dite Toeplitz-like si ρ(T) est négligeable devant la dimension n. En particulier, toute matrice de Toeplitz est une matrice Toeplitz-like [61],[41, Section 3].

Table des matières

1 Structure de Toeplitz et fonctions de matrices
1.1 La structure Toeplitz
1.2 Définitions et propriétés des fonctions de matrices
1.2.1 La forme canonique de Jordan
1.2.2 Définition par interpolation polynomiale
1.2.3 Définition intégrale
1.2.4 Généralités
1.3 Quelques méthodes de calcul
1.3.1 Evaluation polynômiale et méthode de Horner
1.3.2 La méthode de Schur-Parlett
1.3.3 Méthodes d’approximation
1.3.4 Implémentation des interpolants rationnels
1.4 Motivations
1.5 Conclusion
2 Arithmétique Toeplitz-like
2.1 Opérateur de déplacement
2.1.1 Opérateur sous forme Sylvester
2.1.2 Opérateur de déplacement sur les opérations de matrices
2.2 Rang de déplacement et générateurs : les matrices Toeplitz-like
2.2.1 Rang de déplacement
2.2.2 Construction des générateurs
2.2.3 Reconstruction d’une matrice Toeplitz-like à partir de ses générateurs
2.2.4 Résolution de systèmes Toeplitz-like
2.3 Opérations sur les générateurs de matrices Toeplitz-like
2.3.1 Complément de Schur d’une matrice Toeplitz-like
2.3.2 Somme, produit et inverse des matrices Toeplitz-like
2.3.3 Rang de déplacement numérique et compression des générateurs
2.4 Conclusion
3 Application aux fonctions de matrices racine carrée et signe
3.1 Racine carrée principale de matrice
3.2 Rappels sur la méthode de Newton pour la racine carrée d’une matrice non-structurée
3.2.1 Itération de Newton
3.2.2 Stabilité et précision asymptotique de l’itération de Newton
3.3 Amélioration de la méthode
3.3.1 Choix d’un premier terme
3.3.2 Introduction de paramètres
3.4 Newton pour les matrices Toeplitz-like et expériences numériques
3.4.1 Générateurs associés aux itérations de Newton
3.4.2 Expériences numériques
3.5 La fonction de matrice signe
3.5.1 Rappel sur la méthode de Newton pour la fonction signe
3.5.2 Introduction de paramètres
3.5.3 Newton signe pour les matrices Toeplitz-like et expériences numériques
3.6 Conclusion
4 Fonctions de Markov appliquées aux matrices de Toeplitz
4.1 Erreur d’approximation des fonctions de Markov par interpolation rationnelle
4.1.1 Etat de l’art sur la meilleure approximation rationnelle des fonctions de Markov
4.1.2 Borne supérieure pour l’erreur d’approximation des fonctions de Markov par interpolation rationnelle
4.1.3 Le cas d’un ou 2 points d’interpolation multiples
4.1.4 Le cas général
4.1.5 Le cas du disque
4.2 Représentation des interpolants rationnels aux points optimaux
4.2.1 Représentation en éléments simples des interpolants rationnels
4.2.2 Représentation barycentrique des interpolants rationnels
4.2.3 Représentation en fraction continue des interpolants rationnels
4.3 Applications aux matrices de Toeplitz et expériences numériques
4.3.1 Interpolants rationnels en arithmétique Toeplitz-like
4.3.2 Expériences numériques
4.4 Conclusion
5 Conclusion

Télécharger le rapport complet