टोएप्लिट्ज़ मैट्रिक्स

रैखिक बीजगणित में, एक टोएप्लिट्ज़ मैट्रिक्स या विकर्ण-स्थिर मैट्रिक्स, जिसका नाम ओटो टोप्लिट्ज़ के नाम पर रखा गया है, एक मैट्रिक्स (गणित) है जिसमें बाएं से दाएं प्रत्येक अवरोही विकर्ण स्थिर है। उदाहरण के लिए, निम्नलिखित मैट्रिक्स एक Toeplitz मैट्रिक्स है:

$\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}}.$

कोई $n\times n$ आव्यूह $A$ रूप का

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

एक Toeplitz मैट्रिक्स है। यदि $i,j$ का तत्व $A$ निरूपित किया जाता है $A_{i,j}$ तो हमारे पास हैं

$A_{i,j}=A_{i+1,j+1}=a_{i-j}.$

टोएप्लिट्ज़ मैट्रिक्स आवश्यक रूप से वर्ग मैट्रिक्स नहीं है।

Toeplitz प्रणाली को हल करना

प्रपत्र का एक मैट्रिक्स समीकरण

$Ax=b$

यदि टोप्लिट्ज़ प्रणाली कहलाती है $A$ एक Toeplitz मैट्रिक्स है। अगर $A$ एक $n\times n$ Toeplitz मैट्रिक्स, तो सिस्टम में केवल अधिकतम है

$2n-1$ इसके बजाय, अद्वितीय मूल्य $n^{2}$. इसलिए हम उम्मीद कर सकते हैं कि टोप्लिट्ज़ प्रणाली का समाधान आसान होगा, और वास्तव में यही मामला है।

टोप्लिट्ज़ सिस्टम को बिग ओ नोटेशन में लेविंसन रिकर्सन द्वारा हल किया जा सकता है#बैचमैन-लैंडौ नोटेशन का परिवार|$O(n^{2})$समय। इस एल्गोरिदम के वेरिएंट को कमजोर रूप से स्थिर दिखाया गया है (यानी वे स्थिति संख्या | अच्छी तरह से वातानुकूलित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करते हैं)। एल्गोरिदम का उपयोग बिग ओ नोटेशन में टोप्लिट्ज़ मैट्रिक्स के निर्धारक को खोजने के लिए भी किया जा सकता है$O(n^{2})$समय। टोएप्लिट्ज़ मैट्रिक्स को बिग ओ नोटेशन में भी विघटित किया जा सकता है (अर्थात गुणनखंडित किया जा सकता है)।$O(n^{2})$समय। बेरिस एल्गोरिथ्म LU के लिए अपघटन स्थिर है। एलयू अपघटन टोप्लिट्ज़ प्रणाली को हल करने और निर्धारक की गणना के लिए एक त्वरित विधि प्रदान करता है।

साहित्य में ऐसे एल्गोरिदम का वर्णन किया गया है जो बेरिस और लेविंसन की तुलना में असम्बद्ध रूप से तेज़ हैं, लेकिन उनकी सटीकता पर भरोसा नहीं किया जा सकता है।

सामान्य गुण

• एक $n\times n$ Toeplitz मैट्रिक्स को एक मैट्रिक्स के रूप में परिभाषित किया जा सकता है $A$ कहाँ $A_{i,j}=c_{i-j}$, स्थिरांक के लिए $c_{1-n},\ldots ,c_{n-1}$. का समुच्चय (गणित)। $n\times n$ टोएप्लिट्ज़ मैट्रिसेस सदिश समष्टि का एक रैखिक उपसमष्टि है $n\times n$ आव्यूह (मैट्रिक्स जोड़ और अदिश गुणन के अंतर्गत)।
• बिग ओ नोटेशन में दो टोप्लिट्ज़ मैट्रिसेस जोड़े जा सकते हैं|$O(n)$समय (प्रत्येक विकर्ण का केवल एक मान संग्रहीत करके) और मैट्रिक्स गुणन $O(n^{2})$ समय।
• टोएप्लिट्ज़ मैट्रिसेस पर्सिमेट्रिक मैट्रिक्स हैं। सममित टोप्लिट्ज़ मैट्रिक्स सेंट्रोसिमेट्रिक मैट्रिक्स और द्विसममितीय मैट्रिक्स दोनों हैं।
• टोप्लिट्ज़ मैट्रिसेस भी फूरियर श्रृंखला के साथ निकटता से जुड़े हुए हैं, क्योंकि एक त्रिकोणमितीय बहुपद द्वारा गुणन ऑपरेटर, एक परिमित-आयामी स्थान पर संपीड़न (कार्यात्मक विश्लेषण), ऐसे मैट्रिक्स द्वारा दर्शाया जा सकता है। इसी प्रकार, कोई टोप्लिट्ज़ मैट्रिक्स द्वारा गुणन के रूप में रैखिक कनवल्शन का प्रतिनिधित्व कर सकता है।
• टोएप्लिट्ज़ मैट्रिसेस कम्यूटेटर एसिम्प्टोटिक विश्लेषण। इसका मतलब यह है कि जब पंक्ति और स्तंभ का आयाम अनंत की ओर जाता है तो वे एक ही आधार (रैखिक बीजगणित) में विकर्ण मैट्रिक्स होते हैं।

• सममित टोप्लिट्ज़ मैट्रिसेस के लिए, अपघटन होता है

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

कहाँ $G$ का निचला त्रिकोणीय भाग है ${\frac {1}{a_{0}}}A$.

• एक गैर-एकवचन सममित टोप्लिट्ज़ मैट्रिक्स के व्युत्क्रम का प्रतिनिधित्व होता है

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

कहाँ $B$ और $C$ निचले त्रिकोणीय Toeplitz matrices हैं और $C$ एक सख्ती से निचला त्रिकोणीय मैट्रिक्स है।

असतत कनवल्शन

कनवल्शन ऑपरेशन का निर्माण मैट्रिक्स गुणन के रूप में किया जा सकता है, जहां एक इनपुट को टोप्लिट्ज़ मैट्रिक्स में परिवर्तित किया जाता है। उदाहरण के लिए, का कनवल्शन $h$ और $x$ इस प्रकार तैयार किया जा सकता है:

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

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

इस दृष्टिकोण को ऑटोसहसंबंध, क्रॉस-सहसंबंध, चलती औसत आदि की गणना करने के लिए बढ़ाया जा सकता है।

अनंत टोप्लिट्ज़ मैट्रिक्स

Main article: Toeplitz operator

एक द्वि-अनंत टोप्लिट्ज़ मैट्रिक्स (अर्थात अनुक्रमित प्रविष्टियाँ $\mathbb {Z} \times \mathbb {Z}$) $A$ एक रैखिक ऑपरेटर को प्रेरित करता है $\ell ^{2}$.

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

प्रेरित ऑपरेटर परिबद्ध ऑपरेटर है यदि और केवल यदि Toeplitz मैट्रिक्स के गुणांक हैं $A$ कुछ आवश्यक श्रेणी फ़ंक्शन के फूरियर गुणांक हैं $f$.

इस तरह के मामलों में, $f$ टोएप्लिट्ज़ मैट्रिक्स का प्रतीक कहा जाता है $A$, और Toeplitz मैट्रिक्स का वर्णक्रमीय मानदंड $A$ के साथ मेल खाता है $L^{\infty }$ इसके प्रतीक का आदर्श. प्रमाण स्थापित करना आसान है और इसे प्रमेय 1.1 के रूप में पाया जा सकता है:

यह भी देखें

• सर्कुलेट मैट्रिक्स, अतिरिक्त संपत्ति के साथ एक वर्ग टोप्लिट्ज़ मैट्रिक्स $a_{i}=a_{i+n}$
• हैंकेल मैट्रिक्स, एक उल्टा (यानी, पंक्ति-उलटा) टोप्लिट्ज़ मैट्रिक्स
• Szegő limit theorems

संदर्भ

• Bojanczyk, A. W.; Brent, R. P.; de Hoog, F. R.; Sweet, D. R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137/S0895479891221563, S2CID 367586
• Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5
• Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H. (eds.), Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116, doi:10.1137/1.9781611971354.ch4, hdl:1885/40746, S2CID 13905858
• Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM, doi:10.1137/1.9780898718850, ISBN 978-0-89871-636-8
• Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", 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), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series", Journal of the American Statistical Association, 101 (474): 812–822, CiteSeerX 10.1.1.574.4394, doi:10.1198/016214505000001069, S2CID 55893963
• Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", SIAM Journal on Numerical Analysis, 30 (5): 1498–1508, doi:10.1137/0730078
• Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications" (PDF), Linear Algebra and Its Applications, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (Third ed.), Cambridge University Press, ISBN 978-0-521-88068-8
• Stewart, M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25 (3): 669–693, doi:10.1137/S089547980241791X, S2CID 15717371
• Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution", IEEE Transactions on Information Theory, 62 (6): 3685–3701, arXiv:1505.02510, doi:10.1109/TIT.2016.2553041, S2CID 6291005

अग्रिम पठन

• Bareiss, E. H. (1969), "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices", Numerische Mathematik, 13 (5): 404–424, doi:10.1007/BF02163269, S2CID 121761517
• Goldreich, O.; Tal, A. (2018), "Matrix rigidity of random Toeplitz matrices", Computational Complexity, 27 (2): 305–350, doi:10.1007/s00037-016-0144-9, S2CID 253641700
• Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems
• Gray R. M., Toeplitz and Circulant Matrices: A Review (Now Publishers) doi:10.1561/0100000006
• Noor, F.; Morgera, S. D. (1992), "Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues", 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
• Ye, 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, S2CID 254166943