Fonctions de matrices de Toeplitz symétriques
Document type :
Thèse
Title :
Fonctions de matrices de Toeplitz symétriques
English title :
Function of matrices of symmetric Toeplitz matrices
Author(s) :
Thesis director(s) :
Bernhard Beckermann
Defence date :
2021-10-22
Jury president :
Emmanuel Creusé [Président]
Paola Boito [Rapporteur]
Andreas Frommer [Rapporteur]
Ana Matos
Martine Olivi
Paola Boito [Rapporteur]
Andreas Frommer [Rapporteur]
Ana Matos
Martine Olivi
Jury member(s) :
Emmanuel Creusé [Président]
Paola Boito [Rapporteur]
Andreas Frommer [Rapporteur]
Ana Matos
Martine Olivi
Paola Boito [Rapporteur]
Andreas Frommer [Rapporteur]
Ana Matos
Martine Olivi
Accredited body :
Université de Lille
Doctoral school :
École doctorale Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....)
NNT :
2021LILUB011
Keyword(s) :
Fonction de matrice
English keyword(s) :
Toeplitz matrices
Rational approximation
Functions of matrices
Rational approximation
Functions of matrices
HAL domain(s) :
Mathématiques [math]/Algèbres d'opérateurs [math.OA]
French abstract :
Le calcul numérique d'une fonction de matrice f(A) avec A matrice carrée de Toeplitz ou Toeplitz-like trouve son intérêt dans divers domaines mathématiques, que ce soit lors de la semi-discrétisation des équations ...
Show more >Le calcul numérique d'une fonction de matrice f(A) avec A matrice carrée de Toeplitz ou Toeplitz-like trouve son intérêt dans divers domaines mathématiques, que ce soit lors de la semi-discrétisation des équations intégrales ou pour des systèmes de filtres. Or, les méthodes classiques de calcul de fonctions de matrices ne nécessitant aucune structure particulière de la matrice A sont de complexité O(n^3). Dans cette thèse, inspirée de l'étude réalisée par D. Kressner et R. Luce sur le calcul de la fonction de matrice exp(T) avec T matrice carrée de Toeplitz, nous cherchons à réduire cette complexité à O(n^2) voire O(n log^2(n)) en exploitant la structure Toeplitz-like de la matrice A , notamment à l'aide d'approximants rationnels de notre fonction f . Après avoir donné quelques rappels concernant les fonctions de matrices et leur approximation, nous définissons une arithmétique sur les matrices Toeplitz-like, formant un sous-ensemble de matrices permettant des opérations rapides comme l’addition, la multiplication ou l’inversion, en complexité O(n^2) voire O(n log^2 n). A l’aide de cette nouvelle arithmétique, nous nous attardons ensuite sur l’approximation des fonctions de matrices racine carrée et signe pour lesquelles nous reprenons et accélérons la méthode de Newton sous ses différentes formes.Enfin nous nous intéressons à l'approximation des fonctions de matrices f(A) par r(A) lorsque f est une fonction de Markov et A une matrice de Toeplitz symétrique. Nous énonçons alors l’un de nos principaux résultats qui est une borne supérieure pour l’erreur relative d’interpolation rationnelle sur l’intervalle spectral de A. Cette borne est ensuite optimisée par un choix particulier des points d’interpolation, permettant de donner de nouvelles et simples estimations d'erreur a priori et a posteriori, et un calcul fiable, efficace et simple en arithmétique exacte. Pour mieux comprendre l'effet de la précision finie, nous discutons trois méthodes différentes et efficaces de calcul de r(A) , notamment celle des fractions continues de Thiele à coefficients positives, une classe à ce jour peu évoquée dans la littérature. Des nombreuses expériences numériques confirment que ces trois approches donnent une petite erreur pour un argument scalaire, mais seulement une d'entre elles pour A une matrice de Toeplitz symétrique.Show less >
Show more >Le calcul numérique d'une fonction de matrice f(A) avec A matrice carrée de Toeplitz ou Toeplitz-like trouve son intérêt dans divers domaines mathématiques, que ce soit lors de la semi-discrétisation des équations intégrales ou pour des systèmes de filtres. Or, les méthodes classiques de calcul de fonctions de matrices ne nécessitant aucune structure particulière de la matrice A sont de complexité O(n^3). Dans cette thèse, inspirée de l'étude réalisée par D. Kressner et R. Luce sur le calcul de la fonction de matrice exp(T) avec T matrice carrée de Toeplitz, nous cherchons à réduire cette complexité à O(n^2) voire O(n log^2(n)) en exploitant la structure Toeplitz-like de la matrice A , notamment à l'aide d'approximants rationnels de notre fonction f . Après avoir donné quelques rappels concernant les fonctions de matrices et leur approximation, nous définissons une arithmétique sur les matrices Toeplitz-like, formant un sous-ensemble de matrices permettant des opérations rapides comme l’addition, la multiplication ou l’inversion, en complexité O(n^2) voire O(n log^2 n). A l’aide de cette nouvelle arithmétique, nous nous attardons ensuite sur l’approximation des fonctions de matrices racine carrée et signe pour lesquelles nous reprenons et accélérons la méthode de Newton sous ses différentes formes.Enfin nous nous intéressons à l'approximation des fonctions de matrices f(A) par r(A) lorsque f est une fonction de Markov et A une matrice de Toeplitz symétrique. Nous énonçons alors l’un de nos principaux résultats qui est une borne supérieure pour l’erreur relative d’interpolation rationnelle sur l’intervalle spectral de A. Cette borne est ensuite optimisée par un choix particulier des points d’interpolation, permettant de donner de nouvelles et simples estimations d'erreur a priori et a posteriori, et un calcul fiable, efficace et simple en arithmétique exacte. Pour mieux comprendre l'effet de la précision finie, nous discutons trois méthodes différentes et efficaces de calcul de r(A) , notamment celle des fractions continues de Thiele à coefficients positives, une classe à ce jour peu évoquée dans la littérature. Des nombreuses expériences numériques confirment que ces trois approches donnent une petite erreur pour un argument scalaire, mais seulement une d'entre elles pour A une matrice de Toeplitz symétrique.Show less >
English abstract : [en]
The numerical implementation of a function of matrices f(A) with A a square Toeplitz matrice of dimension n arises in many applications such as the semi-discretization of integral equations or filters systems. However, ...
Show more >The numerical implementation of a function of matrices f(A) with A a square Toeplitz matrice of dimension n arises in many applications such as the semi-discretization of integral equations or filters systems. However, classical methods to compute these functions of matrices usually require a complexity of O(n^3) elementary operations if it doesn't take into account the special structure of the matrix. In this thesis, following the study of D. Kressner and R. Luce who worked on the calculus of the exponential of a Toeplitz matrix, we aim at decreasing the computation complexity to O(n^2) elementary operations or O(n log^2(n)) by exploiting the Toeplitz and Toeplitz-like structure of our matrices with help of rational approximation to functions.After giving some recalls on functions of matrices and their approximation, we define a new arithmetic which we call Toeplitz-like allowing to execute simple operations on Toeplitz-like matrices with low complexity of order n log^2 n operations. With this arithmetic, we study the approximation to the square root and sign functions for which we implement the well-known Newton methods and its variants. Finally, we look at the rational approximation of the function of matrices f(A) when f is a Markov function and A is symmetric Toeplitz matrix. We then provide our main result which is an upper born to the relative interpolation error on the spectral set of A. This born is then optimized with a special choice of interpolation points giving a best rational interpolant to the Markov function and we discuss 3 ways to implement these rational interpolants, especially the Thiele continued fraction representation with positive coefficients. Several experiments are brought to confirm that these interpolants provide a small error for scalar argument but just one of them is retained to be used on symmetric Toeplitz matrices.Show less >
Show more >The numerical implementation of a function of matrices f(A) with A a square Toeplitz matrice of dimension n arises in many applications such as the semi-discretization of integral equations or filters systems. However, classical methods to compute these functions of matrices usually require a complexity of O(n^3) elementary operations if it doesn't take into account the special structure of the matrix. In this thesis, following the study of D. Kressner and R. Luce who worked on the calculus of the exponential of a Toeplitz matrix, we aim at decreasing the computation complexity to O(n^2) elementary operations or O(n log^2(n)) by exploiting the Toeplitz and Toeplitz-like structure of our matrices with help of rational approximation to functions.After giving some recalls on functions of matrices and their approximation, we define a new arithmetic which we call Toeplitz-like allowing to execute simple operations on Toeplitz-like matrices with low complexity of order n log^2 n operations. With this arithmetic, we study the approximation to the square root and sign functions for which we implement the well-known Newton methods and its variants. Finally, we look at the rational approximation of the function of matrices f(A) when f is a Markov function and A is symmetric Toeplitz matrix. We then provide our main result which is an upper born to the relative interpolation error on the spectral set of A. This born is then optimized with a special choice of interpolation points giving a best rational interpolant to the Markov function and we discuss 3 ways to implement these rational interpolants, especially the Thiele continued fraction representation with positive coefficients. Several experiments are brought to confirm that these interpolants provide a small error for scalar argument but just one of them is retained to be used on symmetric Toeplitz matrices.Show less >
Language :
Français
Collections :
Source :
Files
- document
- Open access
- Access the document
- These_BISCH_Joanna.pdf
- Open access
- Access the document
- document
- Open access
- Access the document
- These_BISCH_Joanna.pdf
- Open access
- Access the document