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

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

$\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$ टोएप्लिट्ज़ आव्यूह, तो प्रणाली में $n^{2}$ के अपेक्षाकृत केवल अधिकतम $2n-1$ अद्वितीय मान है। इसलिए हम आशा कर सकते हैं कि टोप्लिट्ज़ प्रणाली का समाधान आसान होगा, और वास्तव में यही कारक है।

टोप्लिट्ज़ प्रणाली को $O(n^{2})$समय में लेविंसन रिकर्सन द्वारा हल किया जा सकता है । इस एल्गोरिदम के परिवर्त्य को कमजोर रूप से स्थिर दिखाया गया है (अर्थात वे सुव्यवस्थित रैखिक प्रणालियों के लिए संख्यात्मक स्थिरता प्रदर्शित करते हैं)। एल्गोरिदम का उपयोग $O(n^{2})$समय में टोप्लिट्ज़ आव्यूह के निर्धारक को खोजने के लिए भी किया जा सकता है।

टोएप्लिट्ज़ आव्यूह को $O(n^{2})$समय में भी विघटित किया जा सकता है (अर्थात गुणनखंडित किया जा सकता है)।। LU अपघटन के लिए बेरिस एल्गोरिथ्मस्थिर है। 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$ निचले त्रिकोणीय टोएप्लिट्ज़ आव्यूह हैं और $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}$
• हैंकेल आव्यूह, एक उल्टा (अर्थात, पंक्ति-उलटा) टोप्लिट्ज़ आव्यूह
• स्ज़ेगो सीमा प्रमेय

संदर्भ

• 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