Matricea Toeplitz

În algebra liniară , o matrice Toeplitz (după Otto Toeplitz ) sau matrice diagonală constantă este o matrice ai cărei coeficienți pe o diagonală descendentă de la stânga la dreapta sunt aceiași. De exemplu, următoarea matrice este o matrice Toeplitz:

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

Definiție

Orice matrice A cu n rânduri și n coloane ale formularului

{\ displaystyle 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_ {n-1} & \ ldots & \ ldots & a_ {2} & a_ {1} & a_ {0} \ end {pmatrix}}}

este o matrice Toeplitz. Dacă elementul situat la intersecția rândului i și coloanei j a lui A este notat A i, j , atunci avem:

{\ displaystyle A_ {i, j} = A_ {i + 1, j + 1} = a_ {ij}}

Proprietăți

În general, o ecuație matricială

Ax = b

corespunde unui sistem de n ecuații liniare de rezolvat. Dacă A este o matrice Toeplitz, atunci sistemul este particular: conține doar 2 n - 1 informații aranjate într-un mod foarte particular, în loc de n 2 în cazul general.

Această proprietate poate fi stabilită respectând matricea:

AU_ {n} -U_ {n} A

Aici este dat de $A}$

U_ {n} = {\ begin {pmatrix} 0 & \ cdots & 0 & 1 \\ 1 & 0 && 0 \\\ vdots & \ ddots & \ ddots & \ vdots \\ 0 & \ cdots & 1 & 0 \ sfârșit {pmatrix}}.

Înmulțirea cu un vector v deplasează toți coeficienții lui v un rând în jos, iar ultimul coeficient crește la primul rând. $A}$

Un calcul simplu oferă

D (A) = AU_ {n} -U_ {n} A = {\ begin {pmatrix} (a _ {{- 1}} - a _ {{m-1}}) & \ cdots & (a _ { {- n +1}} - a_ {1}) & 0 \\ 0 & \ cdots & 0 & (a_ {1} -a _ {{- n + 1}}) \\\ vdots & \ cdots & \ vdots & \ vdots \\ 0 & \ cdots & 0 & (a _ {{m-1}} - a _ {{- 1}}) \ end {pmatrix}}

Vedem că este de rang la 2. Noi spunem că D ( A ) este matricea de circulație A .

Dacă A este inversabil și al lui Toeplitz, inversul său nu este al lui Toeplitz, cu excepția cazului în care A este triunghiular . Cu toate acestea, inversul lui A are încă o proprietate interesantă: dacă înmulțim D ( A ) cu inversul lui A, obținem , care este, așadar, de cel mult 2. $-D (A ^ {{- 1}})$

Din acest motiv, dacă A este o matrice astfel încât să fie de rang r , vom spune că este de tip Toeplitz , de rang de deplasare r . O pereche de matrice de o asemenea dimensiune se numește generator de deplasare pentru matrice . Oferă un mod compact de a reprezenta o matrice de tip Toeplitz. $AU_ {n} -U_ {n} A$ $(G, H)$ $n \ ori r$ $AU_ {n} -U_ {n} A = G \ cdot ^ {t} H$ $LA$

Calcul cu matrice Toeplitz

Aceste matrice sunt foarte interesante din punct de vedere al complexității calculului. De exemplu, produsul unei matrice Toeplitz de către un vector poate fi realizat la fel de repede ca produsul a două polinoame de cel mult grade și , adică, în operații. $n-1$ $2n-2$ $O (n \ log n)$

Suma a două matrice Toeplitz este Toeplitz și poate fi efectuată în operații O ( n ) . Produsul a două matrice Toeplitz nu este Toeplitz, dar este totuși de tip Toeplitz. În reprezentarea prin generatoare de deplasare , produsul lor poate fi calculat în operațiuni. $O (n \ log n)$

Pentru rezoluția unui sistem liniar a cărui matrice este Toeplitz, intervenind de exemplu pentru calcularea coeficienților unui model autoregresiv pentru o serie de timp , se utilizează adesea algoritmul Levinson - Durbin (complexitate :) . Pentru n mare, rezoluția unor astfel de sisteme poate fi făcută foarte rapid - de obicei în operații, prin conjuncția mai multor metode algoritmice. Aceste metode se extind la matrici de tip Toeplitz și sunt interesante pentru o matrice de gradul de deplasare r mic în fața lui n , deoarece oferă algoritmi în operații, care trebuie comparate cu operații pentru orice matrice solidă. $O (n ^ 2)$ $O (n \ log (n) ^ {2})$ $O (nr ^ {2} \ log (n) ^ {2})$ $O (n ^ {3})$

Cu toate acestea, o matrice Toeplitz poate fi foarte prost condiționată și, prin urmare, soluția obținută cu o eroare relativă puternică dacă calculăm în virgulă mobilă sau cu fracții gigantice, dacă calculăm exact în numere raționale.

Aceste matrice sunt, de asemenea, strâns legate de seria Fourier, deoarece operatorul multiplicării (en) cu un polinom trigonometric , comprimat ( restricționat ) într-un spațiu de dimensiune finită, poate fi reprezentat printr-o astfel de matrice.

Dacă o matrice Toeplitz verifică în continuare , atunci este o matrice circulantă . $a_ {i} = a _ {{i + n}}$

Matrici Tridiagonal Toeplitz

Matricile triagiagonale Toeplitz, care au ca valori proprii numerele pentru , unde este ordinea matricei. De exemplu, pentru o matrice cu , valorile proprii sunt . ${\ displaystyle {\ begin {pmatrix} a & b & 0 & 0 & 0 \\ c & a & b & 0 & 0 \\ 0 & c & a & b & 0 \\ 0 & 0 & c & a & b \\ 0 & 0 & 0 & c & a \ end {pmatrix}},}$ ${\ displaystyle a + 2 {\ sqrt {bc}} \ cos (k \ pi / (n + 1))}$ ${\ displaystyle k = 1,2, ..., n}$ $nu$ $n = 2$ ${\ displaystyle a \ pm {\ sqrt {bc}}}$

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul din Wikipedia engleză intitulat „ Toeplitz matrix ” ( vezi lista autorilor ) .

(în) Dario Bini și Victor Pan, Calcule polinomiale și matriciale , vol. 1, Birkhäuser , Boston, MA, 1994.
(în) Georg Heinig și Karla Rost, Metode algebrice pentru matrici și operatori de tip Toeplitz, Birkhauser, Basel, 1984.
(în) Albrecht Böttcher și Bernd Silbermann Introducere în matricile mari trunchiate Toeplitz , Springer , New York, 1999.

Vezi și tu

Bibliografie

Nikolaï Nikolski, Matrice și operatori Toeplitz , Calvage și Mounet, 2017

Articole similare

Matricea Hankel
Matricea circulantă
Matricea centrosimetrică - matricile simetrice Toeplitz sunt centrosimetrice

Link extern

(ro) Toeplitz and Circulant Matrices: A review by Robert M. Gray (ro) , Universitatea Stanford