Matrice di Toeplitz

In algebra lineare , una matrice di Toeplitz (dopo Otto Toeplitz ) o una matrice diagonale costante è una matrice i cui coefficienti su una diagonale discendente da sinistra a destra sono gli stessi. Ad esempio, la seguente matrice è una 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}}.}

Definizione

Qualsiasi matrice A con n righe en colonne del modulo

{\ 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}}}

è una matrice di Toeplitz. Se l'elemento situato all'intersezione della riga i e della colonna j di A è indicato come A i, j , allora abbiamo:

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

Proprietà

In generale, un'equazione di matrice

Ax = b

corrisponde a un sistema di n equazioni lineari da risolvere. Se A è una matrice di Toeplitz, allora il sistema è particolare: contiene solo 2 n - 1 informazioni disposte in modo molto particolare, invece di n 2 nel caso generale.

Questa proprietà può essere stabilita osservando la matrice:

AU_ {n} -U_ {n} A

Qui è dato da $UN}$

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

Moltiplicando per un vettore v, tutti i coefficienti di v vengono spostati in basso di una riga e l'ultimo coefficiente sale nella prima riga. $UN}$

Un semplice calcolo dà

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}}

Vediamo è di rango al 2. Diciamo che D ( A ) è la matrice di movimento A .

Se A è invertibile e di Toeplitz, il suo inverso non è di Toeplitz, a meno che A non sia triangolare . Tuttavia, l'inverso di A ha ancora una proprietà interessante: se moltiplichiamo D ( A ) per l'inverso di A, otteniamo , che è quindi anche di rango al massimo 2. $-D (A ^ {{- 1}})$

Per questo motivo, se A è una matrice tale che è di rango r , diremo che è di tipo Toeplitz , di displacement rango r . Una coppia di matrici di tali dimensioni è chiamata generatore di spostamento per la matrice . Fornisce un modo compatto per rappresentare una matrice di tipo Toeplitz. $AU_ {n} -U_ {n} A$ $(G, H)$ $n \ volte r$ $AU_ {n} -U_ {n} A = G \ cdot ^ {t} H$ $A$

Calcolo con matrici di Toeplitz

Queste matrici sono molto interessanti dal punto di vista della complessità del calcolo. Ad esempio, il prodotto di una matrice di Toeplitz per un vettore può essere eseguito tanto rapidamente quanto il prodotto di due polinomi di massimo gradi e , cioè, in operazioni. $n-1$ $2n-2$ $O (n \ log n)$

La somma di due matrici di Toeplitz è Toeplitz e può essere eseguita in operazioni O ( n ) . Il prodotto di due matrici Toeplitz non è Toeplitz, ma è comunque di tipo Toeplitz. Nella rappresentazione dei generatori di spostamento , il loro prodotto può essere calcolato in operazioni. $O (n \ log n)$

Per la risoluzione di un sistema lineare la cui matrice è Toeplitz, intervenendo ad esempio per il calcolo dei coefficienti di un modello autoregressivo per una serie temporale , viene spesso utilizzato l'algoritmo di Levinson - Durbin (complessità :) . Per n grandi, la risoluzione di tali sistemi può essere resa molto veloce, tipicamente nelle operazioni, mediante la combinazione di diversi metodi algoritmici. Questi metodi si estendono a matrici di tipo Toeplitz, e sono interessanti per una matrice di rango di spostamento r piccolo davanti a n , perché forniscono algoritmi nelle operazioni, da confrontare con operazioni per qualsiasi matrice solida. $O (n ^ 2)$ $O (n \ log (n) ^ {2})$ $O (nr ^ {2} \ log (n) ^ {2})$ $O (n ^ {3})$

Tuttavia, una matrice di Toeplitz può essere molto mal condizionata , e quindi la soluzione ottenuta con un forte errore relativo se calcoliamo in numeri in virgola mobile , o con frazioni gigantesche, se calcoliamo esattamente in numeri razionali.

Queste matrici sono anche strettamente correlate alla serie di Fourier perché l' operatore di moltiplicazione (en) per un polinomio trigonometrico , compresso ( ristretto ) ad uno spazio di dimensione finita, può essere rappresentato da una tale matrice.

Se una matrice di Toeplitz verifica ulteriormente , allora è una matrice circolante . $a_ {i} = a _ {{i + n}}$

Matrici di Toeplitz tridiagonali

Matrici di Toeplitz tridiagonali, tali che abbiano come autovalori i numeri per , dove è l'ordine della matrice. Ad esempio, per una matrice con , gli autovalori sono . ${\ 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}$ $non$ $n = 2$ ${\ displaystyle a \ pm {\ sqrt {bc}}}$

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Toeplitz matrix " ( vedere l'elenco degli autori ) .

(a) Dario Bini e Victor Pan, Polynomial and Matrix Computations , Vol. 1, Birkhäuser , Boston, MA, 1994.
(in) Georg Heinig e Karla Rost, Metodi algebrici per matrici e operatori simili a Toeplitz , Birkhauser, Basilea 1984.
(in) Albrecht Böttcher e Bernd Silbermann Introduction to Large Truncated Toeplitz Matrices , Springer , New York, 1999.

Vedi anche

Bibliografia

Nikolaï Nikolski, Matrici e operatori di Toeplitz , Calvage e Mounet, 2017

Link esterno

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