Toeplitzova matice - Toeplitz matrix

V lineární algebře , je Toeplitz matrice nebo diagonální-konstantní matice , pojmenoval Otto Toeplitzem , je matice , ve které každý sestupně úhlopříčka zleva doprava, je konstantní. Následující matice je například Toeplitzova matice:

${\ Displaystyle \ qquad {\ begin {bmatrix} 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 {bmatrix}}.}$

Libovolná n  ×  n matice A formuláře

${\ displaystyle A = {\ begin {bmatrix} a_ {0} & a _ {-1} & a _ {-2} & \ cdots & \ cdots & 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} & \ cdots & \ cdots & a_ {2} & a_ {1} & a_ { 0} \ end {bmatrix}}}$

je Toeplitzova matice . Je -li i ,  j prvek A označen A _{i ,  j,} pak máme

${\ Displaystyle A_ {i, j} = A_ {i+1, j+1} = a_ {ij}.}$

Toeplitzova matice nemusí být nutně čtvercová .

Řešení systému Toeplitz

Maticová rovnice tvaru

${\ Displaystyle Ax = b}$

se nazývá systém Toeplitz, pokud A je Toeplitzova matice. Pokud A je n  ×  n Toeplitzova matice, pak má systém pouze 2 n - 1 stupně volnosti , než n ² . Můžeme tedy očekávat, že řešení systému Toeplitz bude snazší, a ve skutečnosti tomu tak je.

Systémy Toeplitz lze vyřešit Levinsonovým algoritmem v čase O ( n ² ) . Ukázalo se, že varianty tohoto algoritmu jsou slabě stabilní (tj. Vykazují numerickou stabilitu pro dobře podmíněné lineární systémy). Algoritmus lze také použít k nalezení determinantu Toeplitzovy matice v čase O ( n ² ) .

Toeplitzovu matici lze také rozložit (tj. Rozložit) na čas O ( n ² ) . Algoritmus Bareiss pro rozklad LU je stabilní. Rozklad LU poskytuje rychlou metodu pro řešení systému Toeplitz a také pro výpočet determinantu.

Algoritmy, které jsou asymptoticky rychlejší než Bareiss a Levinson, byly popsány v literatuře, ale na jejich přesnost se nelze spoléhat.

Obecné vlastnosti

• An n  ×  n Toeplitzovu matici lze definovat jako matici A, kde A _{i ,  j} = c _{i - j} , pro konstanty c _{1− n} , ..., c _{n −1} . Sada z n  x  n Toeplitz matric je podprostor z vektorového prostoru z n  x  n matice (za přidání matice a skalární násobení).
• Dvě Toeplitzovy matice mohou být přidány v čase O ( n ) (uložením pouze jedné hodnoty každé úhlopříčky) a násobeny v čase O ( n ² ).
• Toeplitz matice jsou persymetrické . Symetrické Toeplitz matice jsou oba centrosymmetric a bisymmetric .
• Toeplitzovy matice jsou také úzce spojeny s Fourierovými řadami , protože multiplikační operátor pomocí goniometrického polynomu , komprimovaného do prostoru konečných rozměrů, může být reprezentován takovou maticí. Podobně lze lineární konvoluci reprezentovat jako násobení Toeplitzovou maticí.
• Matice Toeplitz dojíždějí asymptoticky . To znamená, že diagonalizují na stejném základě, když má rozměr řádků a sloupců tendenci k nekonečnu.
• Pozitivně semidefinitní n  x  n Toeplitz matice z hodnost r < n může být jedinečně factored${\ displaystyle A}$

${\ Displaystyle A = \ sum _ {k = 1}^{r} d_ {k} v (f_ {k}) v (f_ {k})^{\ operatorname {H}} = VDV^{\ operatorname { H}}}$

kde je r  ×  r pozitivní jednoznačná diagonální matice , je n  ×  r Vandermondova matice , takže sloupce jsou . Tady a je normalizován frekvence, a je Hermitian transpozice of . Pokud je hodnost r = n , pak rozklad Vandermonde není jedinečný.${\ Displaystyle D = \ mathrm {diag} (d_ {1}, \ ldots, d_ {r})}$ ${\ Displaystyle V = [v (f_ {1}), \ ldots, v (f_ {r})]}$ ${\ Displaystyle v (f) = [1, e^{i2 \ pi f}, \ ldots, e^{i2 \ pi (n-1) f}]^{\ operatorname {T}}}$${\ displaystyle i^{2} =-1}$${\ Displaystyle f_ {k} \ v [0,1]}$${\ displaystyle V^{\ operatorname {H}}}$${\ displaystyle V}$

• U symetrických Toeplitzových matic existuje rozklad

${\ displaystyle {\ frac {1} {a_ {0}}} A = GG^{\ operatorname {T}}-(GI) (GI)^{\ operatorname {T}}}$

kde je spodní trojúhelníková část .${\ displaystyle G}$${\ displaystyle {\ frac {1} {a_ {0}}} A}$

• Reprezentace je inverzní k nesingulární symetrické Toeplitzově matici

${\ displaystyle A^{-1} = {\ frac {1} {\ alpha _ {0}}} (BB^{\ operatorname {T}} -CC^{\ operatorname {T}})}$

kde a jsou nižší trojúhelníkové matice Toeplitz a je přísně nižší trojúhelníková matice.${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle C}$

Diskrétní konvoluce

Konvoluční operace může být konstruován jako maticové násobení, kde jeden ze vstupů je přeměněn na Toeplitz matrice. Konvoluce a může být například formulována jako: ${\ displaystyle h}$${\ displaystyle x}$

${\ Displaystyle y = h \ ast x = {\ begin {bmatrix} h_ {1} & 0 & \ cdots & 0 & 0 \\ h_ {2} & h_ {1} && \ vdots & \ vdots \\ h_ {3} & h_ {2} & \ cdots & 0 & 0 \\\ vdots & h_ {3} & \ cdots & h_ {1} & 0 \\ h_ {m-1} & \ vdots & \ ddots & h_ {2} & h_ {1} \\ h_ {m} & h_ { m-1} && \ vdots & h_ {2} \\ 0 & h_ {m} & \ ddots & h_ {m-2} & \ vdots \\ 0 & 0 & \ cdots & h_ {m-1} & h_ {m-2} \\\ vdots & \ vdots && h_ {m} & h_ {m-1} \\ 0 & 0 & 0 & \ cdots & h_ {m} \ end {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ {2} \\ x_ {3} \\\ vdots \\ x_ {n} \ end {bmatrix}}}$

${\ Displaystyle y^{T} = {\ begin {bmatrix} h_ {1} & h_ {2} & h_ {3} & \ cdots & h_ {m-1} & h_ {m} \ end {bmatrix}} {\ begin { bmatrix} x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} & 0 & 0 & 0 & \ cdots & 0 \\ 0 & x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} & 0 & 0 & \ cdots & 0 \\ 0 & 0 & x_ {1} & x_ {2} & x_ {3} & \ ldots & x_ {n} & 0 & \ cdots & 0 \\\ vdots && \ vdots & \ vdots & \ vdots && \ vdots & \ vdots && \ vdots \\ 0 & \ cdots & 0 & 0 & x_ {1} & \ cdots & x_ {n-2} & x_ {n-1} & x_ {n} & 0 \\ 0 & \ cdots & 0 & 0 & 0 & x_ {1} & \ cdots & x_ {n-2} & x_ {n-1} & x_ {n} \ end {bmatrix}}.}$

Tento přístup lze rozšířit o výpočet autokorelace , křížové korelace , klouzavého průměru atd.

Nekonečná matice Toeplitz

Bi-nekonečná Toeplitzova matice (tj. Položky indexované ) indukuje lineární operátor na . ${\ displaystyle \ mathbb {Z} \ times \ mathbb {Z}}$${\ displaystyle A}$${\ displaystyle \ ell ^{2}}$

${\ Displaystyle A = {\ begin {bmatrix} & \ vdots & \ vdots & \ vdots & \ vdots \\\ cdots & a_ {0} & a _ {-1} & a _ {-2} & a _ {-3} & \ cdots \ \\ cdots & a_ {1} & a_ {0} & a _ {-1} & a _ {-2} & \ cdots \\\ cdots & a_ {2} & a_ {1} & a_ {0} & a _ {-1} & \ cdots \\ \ cdots & a_ {3} & a_ {2} & a_ {1} & a_ {0} & \ cdots \\ & \ vdots & \ vdots & \ vdots & \ vdots \ end {bmatrix}}.}$

Indukovaný operátor je ohraničen právě tehdy, pokud jsou koeficienty Toeplitzovy matice Fourierovými koeficienty nějaké v podstatě ohraničené funkce . ${\ displaystyle A}$${\ displaystyle f}$

V takových případech se nazývá symbol Toeplitzovy matice a spektrální norma Toeplitzovy matice se shoduje s normou jejího symbolu. Důkaz lze snadno stanovit a lze jej nalézt jako větu 1.1 v odkazu na knihu Google: ${\ displaystyle f}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle L^{\ infty}}$

Viz také

• Cirkulační matice , Toeplitzova matice s další vlastností, která${\ displaystyle a_ {i} = a_ {i+n}}$
• Hankelova matice , „vzhůru nohama“ (tj. Řádky obrácené) Toeplitzova matice

Poznámky

Reference

• Bojanczyk, AW; Brent, RP; de Hoog, FR; Sweet, DR (1995), „O stabilitě Bareissových 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), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis , Birkhäuser, ISBN 978-3-0348-8395-5
• Brent, RP (1999), „Stabilita rychlých algoritmů pro strukturované lineární systémy“, v Kailath, T .; Sayed, AH (eds.), Fast Reliable Algorithms for Matrices with Structure , SIAM , pp. 103–116
• Chan, RH-F .; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers , SIAM
• Chandrasekeran, S .; Gu, M .; Slunce, 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, WW; Hurvich, CM; Lu, Y. (2006), „O korelační matici diskrétní Fourierovy transformace a rychlém ř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 Algorithm is slaly stable“ , SIAM Journal on Numerical Analysis , 30 (5): 1498–1508, doi : 10,1137/0730078
• Monahan, JF (2011), Numerical Methods of Statistics , Cambridge University Press
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), „O některých vlastnostech pozitivních jednoznačných Toeplitzových matric 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
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), Numerical Recipes: The Art of Scientific Computing (Third ed.), Cambridge University Press , ISBN 978-0-521-88068-8
• Stewart, M. (2003), „Superrychlý řešitel 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 dekompozice víceúrovňových matic Toeplitz s aplikací na vícerozměrné superrozlišení“, IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi : 10.1109/TIT.2016.2553041

Další čtení

• Bareiss, EH (1969), „Numerické řešení lineárních rovnic s Toeplitzovými a vektorovými Toeplitzovými maticemi“, Numerische Mathematik , 13 (5): 404–424, doi : 10,1007/BF02163269
• Goldreich, O .; Tal, A. (2018), „Matrix rigidity of random Toeplitz matrices“, Computational Complexity , 27 (2): 305–350, doi : 10,1007/s00037-016-0144-9
• Golub GH , van Loan CF (1996), Matrix Computations ( Johns Hopkins University Press ) §4.7 — Toeplitz a související systémy
• Gray RM, Toeplitz a Circulant Matrices: recenze ( nyní vydavatelé )
• Noor, F .; Morgera, SD (1992), „Konstrukce hermitovské Toeplitzovy matice z libovolné sady vlastních hodnot“, IEEE Transactions on Signal Processing , 40 (8): 2093–2094, Bibcode : 1992ITSP ... 40.2093N , doi : 10.1109/ 78,149978
• Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms , Birkhäuser , ISBN 978-0817642402
• Ano, Ke; Lim, Lek-Heng (2016), „Every matrix is ​​a product of Toeplitz matrices“, Foundations of Computational Mathematics , 16 (3): 577–598, arXiv : 1307.5132 , doi : 10.1007/s10208-015-9254-z