Matrice de Toeplitz

Matrice de Toeplitz

En algèbre linéaire, une matrice de Toeplitz (d'après Otto Toeplitz) ou matrice à diagonales constantes est une matrice dont les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Par exemple, la matrice suivante est une matrice de Toeplitz :

\begin{pmatrix} a & b & c & d & e \\ f & a & b & c & d \\ g & f & a & b & c \\ h & g & f & a & b \\ j & h & g & f & a \end{pmatrix}.

Toute matrice A à m lignes et n colonnes de la forme

A = \begin{pmatrix} a_{0} & a_{-1} & a_{-2} & \ldots & \ldots &a_{-n+1} \\ a_{1} & a_0 & a_{-1} & \ddots & & \vdots \\ a_{2} & a_{1} & \ddots & \ddots & \ddots& \vdots \\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2}\\ \vdots & & \ddots & a_{1} & a_{0}& a_{-1} \\ a_{m-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{pmatrix}

est une matrice de Toeplitz. Si l'élément situé à l’intersection des ligne i et colonne j de A est noté Ai,j, alors on a :

Ai,j = ai − j.

Sommaire

Propriétés

En général, une équation matricielle

Ax = b

correspond à un système de n équations linéaires à résoudre. Si A est une matrice de Toeplitz, alors le système est particulier : il ne contient que 2n − 1 informations arrangées d'une manière bien particulière au lieu de n2 dans le cas général.

Cette propriété peut être établie en observant la matrice :

AUn − UnA,.

Ici Un est donnée par

U_n=\begin{pmatrix} 0 & \cdots & 0 & 1 \\ 1 & 0 & & 0 \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 1 & 0 \end{pmatrix}.

Si on effectue la multiplication de Un par un vecteur v, cela décale tous les coefficients de v d'une ligne vers le bas, et le dernier coefficient monte à la première ligne.

Un calcul simple donne

D(A)= AU_n-U_nA= \begin{pmatrix} a_{-1} & \cdots & a_{-n+1} & 0 \\ \vdots & & & -a_{-n+1} \\ \vdots & & & \vdots \\ 0 & \cdots & & -a_{n-n-1} \end{pmatrix}

où les cases vides peuvent être remplacées par des zéros. On voit qu'elle est de rang au plus 2. On dira que D(A) est la matrice de déplacement de A.

Si A est inversible et de Toeplitz, son inverse n'est pas de Toeplitz, sauf si A est triangulaire. Néanmoins, l'inverse de A a quand même une propriété intéressante : si on multiplie D(A) par l'inverse de A, on obtient − D(A − 1), qui est donc aussi de rang au plus 2.

Pour cette raison, si A est une matrice telle que AUn − UnA, soit de rang r, on dira qu'elle est de type Toeplitz, de rang de déplacement r[1].

Calcul avec des matrices de Toeplitz

Ces matrices sont très intéressantes du point de vue de la complexité du calcul : on montre que l'addition de deux matrices de Toeplitz peut être effectuée en O(n) opérations et le produit matriciel de deux matrices de Toeplitz en O(n log n) opérations.

La résolution de systèmes linéaires dont la matrice est de Toeplitz peut être rendue très rapide – typiquement en O(nlog(n)2) opérations, au moyen de la conjonction de plusieurs procédés algorithmiques. Ces procédés s'étendent aux matrices de type Toeplitz, et ils sont intéressants pour une matrice de rang de déplacement r petit devant n, car ils fournissent des algorithmes en O(nr2log(n)2) opérations, à comparer avec O(n3) opérations pour une matrice pleine quelconque[2].

Cependant, une matrice de Toeplitz peut être fort mal conditionnée, et donc la solution obtenue avec une erreur relative forte si on calcule en nombres flottants, ou avec des fractions gigantesques, si on calcule exactement en rationnels[3].

Ces matrices sont aussi étroitement liées aux séries de Fourier car l'opérateur de multiplication (en) par un polynôme trigonométrique, comprimé (restreint) à un espace de dimension finie, peut être représentée par une telle matrice.

Si une matrice de Toeplitz vérifie de plus ai = ai + n, alors c'est une matrice circulante.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « Toeplitz matrix » (voir la liste des auteurs)

  1. ↑ (en) Polynomial and matrix computations. Vol. 1, Dario Bini et Victor Pan, Birkhäuser Boston Inc., Boston, MA, 1994.
  2. ↑ (en) Algebraic methods for Toeplitz-like matrices and operators, Georg Heinig et Karla Rost, Birkhäuser Verlag, Bâle, 1984.
  3. ↑ (en) Introduction to large truncated Toeplitz matrices, Albrecht Böttcher et Bernd Silbermann, Springer-Verlag, New York, 1999.

Voir aussi

Liens externes

(en) Toeplitz and Circulant Matrices: A review par Robert M. Gray (en), université Stanford


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Matrice de Toeplitz de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Matrice De Toeplitz — En algèbre linéaire, une matrice de Toeplitz (d après Otto Toeplitz) ou matrice à diagonales constantes est une matrice dont les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Par exemple, la matrice suivante est une …   Wikipédia en Français

  • Matrice de toeplitz — En algèbre linéaire, une matrice de Toeplitz (d après Otto Toeplitz) ou matrice à diagonales constantes est une matrice dont les coefficients sur une diagonale descendant de gauche à droite sont les mêmes. Par exemple, la matrice suivante est une …   Wikipédia en Français

  • Matrice par blocs — Matrice par bloc En théorie des matrices, une matrice par bloc ou matrice partitionnée est une matrice pouvant être divisée en matrices rectangulaires de dimensions inférieures appelées blocs. On peut dire également que la matrice est écrite en… …   Wikipédia en Français

  • Matrice Circulante — En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients. Une matrice circulante de taille n est donc de la forme où… …   Wikipédia en Français

  • Matrice par bloc — En théorie des matrices, une matrice par bloc ou matrice partitionnée est une matrice pouvant être divisée en matrices rectangulaires de dimensions inférieures appelées blocs. On peut dire également que la matrice est écrite en termes de matrices …   Wikipédia en Français

  • Matrice circulante — En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients. Une matrice circulante de taille n est donc de la forme où… …   Wikipédia en Français

  • Toeplitz — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Toeplitz ou Töplitz peut faire référence à : Patronyme Kasper T. Toeplitz (né en 1960), un musicien français Otto Toeplitz (1881 1940), un… …   Wikipédia en Français

  • Matrice De Hankel — En algèbre linéaire une matrice de Hankel, du nom du mathématicien Hermann Hankel, est une matrice carrée dont les valeurs sont constantes le long des diagonales ascendantes, c est à dire dont les indices vérifient la relation ai,j = ai − 1,j + 1 …   Wikipédia en Français

  • Matrice de hankel — En algèbre linéaire une matrice de Hankel, du nom du mathématicien Hermann Hankel, est une matrice carrée dont les valeurs sont constantes le long des diagonales ascendantes, c est à dire dont les indices vérifient la relation ai,j = ai − 1,j + 1 …   Wikipédia en Français

  • Matrice (algèbre) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”