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

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

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

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

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

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

टोएप्लिट्ज़ प्रणाली को हल करना

प्रपत्र का एक आव्यूहसमीकरण

$Ax=b$

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

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

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

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

सामान्य गुण

• एक $n\times n$ टोएप्लिट्ज़मैट्रिक्स को एक आव्यूहके रूप में परिभाषित किया जा सकता है $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$ निचले त्रिकोणीय टोएप्लिट्ज़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}}.$

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

इस तरह के मामलों में, $f$ टोएप्लिट्ज़ आव्यूहका प्रतीक कहा जाता है $A$, और टोएप्लिट्ज़मैट्रिक्स का वर्णक्रमीय मानदंड $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—टोएप्लिट्ज़and Related Systems
• Gray R. M., टोएप्लिट्ज़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