Toeplitzova matice - Toeplitz matrix
v lineární algebra, a Toeplitzova matice nebo matice diagonální konstanty, pojmenoval podle Otto Toeplitz, je matice ve kterém je každá sestupná úhlopříčka zleva doprava konstantní. Například následující matice je Toeplitzova matice:
Žádný n×n matice A formuláře
je Toeplitzova matice. Pokud i,j prvek A je označen Ai,j, pak máme
Toeplitzova matice nemusí být nutně náměstí.
Řešení systému Toeplitz
Maticová rovnice tvaru
se nazývá a Toeplitzův systém -li A je Toeplitzova matice. Li A je Toeplitzova matice, pak má systém pouze 2n−1 stupně svobody, spíše než n2. Můžeme tedy očekávat, že řešení Toeplitzova systému bude jednodušší, a to je pravda.
Toeplitzovy systémy lze vyřešit pomocí Levinsonův algoritmus v Ó(n2) čas.[1] Ukázalo se, že varianty tohoto algoritmu jsou slabě stabilní (tj. Vykazují numerická stabilita pro dobře podmíněný lineární systémy).[2] Algoritmus lze také použít k vyhledání určující Toeplitzovy matice v Ó(n2) čas.[3]
Toeplitzovu matici lze také rozložit (tj. Zohlednit) v Ó(n2) čas.[4] Algoritmus Bareiss pro LU rozklad je stabilní.[5] Rozklad LU poskytuje rychlou metodu pro řešení Toeplitzova systému a také pro výpočet determinantu.
Algoritmy, které jsou asymptoticky rychlejší než algoritmy Bareisse a Levinsona, byly popsány v literatuře, ale nelze se na ně spolehnout.[6][7][8][9]
Obecné vlastnosti
- An n×n Toeplitzovu matici lze definovat jako matici A kde Ajá, j = Ci − j, pro konstanty C1−n ... Cn−1. Sada n×n Toeplitzovy matice jsou a podprostor z vektorový prostor z n×n matice pod sčítáním matice a skalární násobení.
- Mohou být přidány dvě Toeplitzovy matice Ó(n) čas (uložením pouze jedné hodnoty každé úhlopříčky) a znásobeno v Ó(n2) čas.
- Toeplitzovy matice jsou persymetrický. Symetrické Toeplitzovy matice jsou obě centrosymmetrický a bisymetrický.
- Toeplitzovy matice jsou také úzce spojeny s Fourierova řada, protože operátor násobení podle a trigonometrický polynom, stlačený do konečně-dimenzionálního prostoru, může být představována takovou maticí. Podobně lze představovat lineární konvoluci jako násobení Toeplitzovou maticí.
- Toeplitzovy matice dojíždět asymptoticky. To znamená, že diagonalizovat ve stejné základ když kóta řádků a sloupců má sklon k nekonečnu.
- A pozitivní semi-definitivní n×n Toeplitzova matice hodnosti r < n může být jedinečně započítáno jako
- kde je r×r pozitivní určitá úhlopříčná matice, je n×r Vandermondeova matice takové, že sloupce jsou . Tady a je normalizovaná frekvence a je Hermitian transponovat z . Pokud hodnost r = n, pak rozklad Vandermonde není jedinečný.[10]
- U symetrických Toeplitzových matic dochází k rozkladu
- kde je spodní trojúhelníková část .
- Znázornění má inverzní funkce nesingulární symetrické Toeplitzovy matice
- kde a jsou nižší trojúhelníkové Toeplitzovy matice a je přísně nižší trojúhelníková matice.[11]
Diskrétní konvoluce
The konvoluce operaci lze zkonstruovat jako násobení matice, kde se jeden ze vstupů převede na Toeplitzovu matici. Například konvoluce a lze formulovat jako:
Tento přístup lze rozšířit na výpočet autokorelace, vzájemná korelace, klouzavý průměr atd.
Nekonečná Toeplitzova matice
Bi-nekonečná Toeplitzova matice (tj. Položky indexované pomocí ) vyvolá lineární operátor .
Indukovaný operátor je omezen právě tehdy, pokud jsou koeficienty Toeplitzovy matice jsou Fourierovy koeficienty některých v podstatě omezený funkce .
V takových případech, se nazývá symbol Toeplitzovy matice a spektrální norma Toeplitzovy matice se shoduje s norma jeho symbolu. Důkaz lze snadno zjistit a lze jej najít jako Theorem 1.1 v odkazu na knihu Google:[12]
Viz také
- Oběžná matice, Toeplitzova matice s další vlastností, která
- Hankelova matice, „vzhůru nohama“ (tj. řádkově obrácená) Toeplitzova matice
Poznámky
- ^ Press et al. 2007, §2.8.2 - Toeplitzovy matice
- ^ Krishna & Wang 1993
- ^ Monahan 2011, §4.5 - Toeplitzovy systémy
- ^ Brent 1999
- ^ Bojanczyk a kol. 1995
- ^ Stewart 2003
- ^ Chen, Hurvich a Lu 2006
- ^ Chan & Jin 2007
- ^ Chandrasekeran a kol. 2007
- ^ Yang, Xie & Stoica 2016
- ^ Mukherjee a Maiti 1988
- ^ Böttcher & Grudsky 2012
Reference
- Bojanczyk, A. W .; Brent, R. P .; de Hoog, F. R .; Sweet, D. R. (1995), „O stabilitě Bareisse a souvisejících Toeplitzových faktorizačních algoritmů“, SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137 / S0895479891221563
- Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitzovy matice, asymptotická lineární algebra a funkční analýza, Birkhäuser, ISBN 978-3-0348-8395-5
- Brent, R. P. (1999), „Stabilita rychlých algoritmů pro strukturované lineární systémy“, v Kailath, T .; Sayed, A. H. (eds.), Rychlé spolehlivé algoritmy pro matice se strukturou, SIAM, str. 103–116
- Chan, R. H.-F .; Jin, X.-Q. (2007), Úvod do iterativních Toeplitz Solvers, SIAM
- Chandrasekeran, S .; Gu, M .; Sun, X .; Xia, J .; Zhu, J. (2007), „Superrychlý algoritmus pro Toeplitzovy systémy lineárních rovnic“, SIAM Journal on Matrix Analysis and Applications, 29 (4): 1247–1266, CiteSeerX 10.1.1.116.3297, doi:10.1137/040617200
- Chen, W. W .; Hurvich, C. M .; Lu, Y. (2006), „Korelační matice diskrétní Fourierovy transformace a rychlé řešení velkých Toeplitzových systémů pro časové řady s dlouhou pamětí“, Journal of the American Statistical Association, 101 (474): 812–822, CiteSeerX 10.1.1.574.4394, doi:10.1198/016214505000001069
- Krishna, H .; Wang, Y. (1993), „Split Levinsonův algoritmus je slabě stabilní“, Časopis SIAM o numerické analýze, 30 (5): 1498–1508, doi:10.1137/0730078
- Monahan, J. F. (2011), Numerické metody statistiky, Cambridge University Press
- Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), „O některých vlastnostech pozitivních konečných Toeplitzových matic a jejich možných aplikacích“ (PDF), Lineární algebra a její aplikace, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
- Press, W. H .; Teukolsky, S. A .; Vetterling, W. T .; Flannery, B. P. (2007), Numerické recepty: Umění vědecké práce na počítači (Třetí vydání.), Cambridge University Press, ISBN 978-0-521-88068-8
- Stewart, M. (2003), „Superrychlý řešič Toeplitz se zlepšenou numerickou stabilitou“, SIAM Journal on Matrix Analysis and Applications, 25 (3): 669–693, doi:10.1137 / S089547980241791X
- Yang, Zai; Xie, Lihua; Stoica, Petre (2016), „Vandermondeův rozklad víceúrovňových Toeplitzových matic s aplikací na vícerozměrné superrozlišení“, Transakce IEEE na teorii informací, 62 (6): 3685–3701, arXiv:1505.02510, doi:10.1109 / TIT.2016.2553041
Další čtení
- Bareiss, E. H. (1969), „Numerické řešení lineárních rovnic s Toeplitzovou a vektorovou Toeplitzovou maticí“, Numerische Mathematik, 13 (5): 404–424, doi:10.1007 / BF02163269
- Goldreich, O.; Tal, A. (2018), „Matrix rigidity of random Toeplitz matrices“, Výpočetní složitost, 27 (2): 305–350, doi:10.1007 / s00037-016-0144-9
- Golub G. H., van půjčka C. F. (1996), Maticové výpočty (Johns Hopkins University Press ) §4.7 — Toeplitz a související systémy
- Gray R. M., Toeplitz a Circulant Matrices: Recenze (Nyní vydavatelé )
- Noor, F .; Morgera, S. D. (1992), „Konstrukce matice Hermitian Toeplitz z libovolné sady vlastních čísel“, Transakce IEEE při zpracování signálu, 40 (8): 2093–2094, Bibcode:1992ITSP ... 40.2093N, doi:10.1109/78.149978
- Pan, Victor Y. (2001), Strukturované matice a polynomy: sjednocené superrychlé algoritmy, Birkhäuser, ISBN 978-0817642402
- Ye, Ke; Lim, Lek-Heng (2016), „Every matrix is a product of Toeplitz matrices“, Základy výpočetní matematiky, 16 (3): 577–598, arXiv:1307.5132, doi:10.1007 / s10208-015-9254-z