Macierz Toeplitza

Macierz Toeplitza - macierz mająca te same wartości na poszczególnych przekątnych, tj. macierz postaci

$A={\begin{bmatrix}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{bmatrix}}$$A={\begin{bmatrix}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{bmatrix}}$

Przykład

$A={\begin{bmatrix}2&4&7&5\\-6&2&4&7\\0&-6&2&4\\8&0&-6&2\\\end{bmatrix}}$$A={\begin{bmatrix}2&4&7&5\\-6&2&4&7\\0&-6&2&4\\8&0&-6&2\\\end{bmatrix}}$

Rozwiązywanie

Równanie macierzy w formie $\mathrm {A} {\text{x}}=b$$\mathrm {A} {\text{x}}=b$ jest nazywane układem Toeplitza jeżeli $\mathrm {A}$$\mathrm {A}$ jest macierzą Toeplitza. Jeśli $\mathrm {A}$$\mathrm {A}$  to macierz Toepliza $n*n$$n*n$ to układ ma tylko $2n-1$$2n-1$ stopnie swobody zamiast $n^{2}$$n^2$. Można więc oczekiwać, że rozwiązanie układu Toeplitza jest łatwiejsze.

Układy Toeplitza można rozwiązać algorytmem Levinsona w czasie $\Theta (n^{2})$$\Theta(n^2)$. Warianty tego algorytmu są niestabilne (np. wykazują stabilność numeryczną dla dobrze uwarunkowanych systemów linearnych). Algorytm może również zostać wykorzystany do znalezienia wyznacznika macierzy Toeplitza w czasie $O(n^{2})$$O(n^{2})$.

Macierz Toeplitza może również być rozłożona w czasie $O(n^{2})$$O(n^{2})$ Algorytm Bareissa dla rozkładu LU jest stabilny.

Rozkład LU daje szybki sposób na rozwiązanie układu Toeplitza, jak i obliczenie wskaźnika.

Algorytmy asymptotycznie szybsze niż Bareissa i Levinsona były opisywane, ale ich dokładność nie jest wiarygodna.

Właściwości

Macierz Toeplitza można zdefiniować jako macierz $\mathrm {A}$$\mathrm {A}$, gdzie $A_{i,j}=c_{i-j}$$A_{i,j}=c_{i-j}$, dla stałych $c_{1-n}...c_{n-1}$$c_{1-n}...c_{n-1}$. Zestaw $n*n$$n*n$ macierzy Toeplitza jest podprzestrzenią przestrzeni wektorowej $n*n$$n*n$ macierzy utworzonej z ciała $K(V,+,\circ )$$K(V,+,\circ )$, gdzie $V$$V$ jest przestrzenią wektorową. Dwie macierze Toeplitza można dodać w czasie $O(n)$$O(n)$ i pomnożyć w czasie $O(n^{2})$$O(n^{2})$. Macierze Toeplitza są persymetryczne, natomiast symetryczne macierze Toeplitza są zarówno centrosymetryczne, jak i bisymetryczne.

Macierze Toeplitza są też blisko powiązane z szeregami Fouriera, ponieważ operator mnożenia przez wielomian trygonometryczny, skompresowany do przestrzeni o skończonej liczbie wymiarów, może być reprezentowany właśnie przez taką macierz. Podobnie, można przedstawić skręt liniowy jako mnożenie przez macierz Toeplitza.

Macierze Toeplitza komutują asymptotycznie. To oznacza, że diagonalizują one na tej samej bazie gdy wymiar wiersza i kolumny zmierza do nieskończoności.

Zobacz też

• Macierz Vandermonde'a

Linki zewnętrzne

• Macierz Toeplitza (ang.) w encyklopedii MathWorld