Πίνακας Τόεπλιτς

Στη γραμμική άλγεβρα, ένας πίνακας Τόεπλιτς ή πίνακας με διαγώνιο σταθερό, που πήρε το όνομά του από τον Ότο Τόεπλιτς, είναι ένας πίνακας στον οποίο κάθε φθίνουσα διαγώνιος από αριστερά προς τα δεξιά είναι σταθερή. Παραδείγματος χάριν, ο ακόλουθος πίνακας είναι ένας πίνακας Τόεπλιτς:

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

Κάθε ${\displaystyle n\times n}$ πίνακας ${\displaystyle A}$ της μορφής

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

είναι ένας πίνακας Τόεπλιτς. Αν το στοιχείο ${\displaystyle i,j}$ του ${\displaystyle A}$ συμβολίζεται ${\displaystyle A_{i,j}}$ τότε έχουμε

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

Ένας πίνακας Τόεπλιτς δεν είναι απαραίτητα τετραγωνικός.

Λύση ενός συστήματος Τόεπλιτς

Μια εξίσωση πίνακα της μορφής

${\displaystyle Ax=b}$

ονομάζεται σύστημα Τόεπλιτς αν ${\displaystyle A}$ είναι ένας πίνακας Τόεπλιτς. Αν ${\displaystyle A}$ είναι ένας ${\displaystyle n\times n}$ πίνακας Τόεπλιτς, τότε το σύστημα έχει το πολύ μόνο ${\displaystyle 2n-1}$ μοναδιαίες τιμές, αντί για ${\displaystyle n^{2}}$. Θα μπορούσαμε επομένως να περιμένουμε ότι η επίλυση ενός συστήματος Τόεπλιτς θα ήταν ευκολότερη, και πράγματι αυτό συμβαίνει.

Τα συστήματα Τόεπλιτς μπορούν να επιλυθούν με αλγορίθμους όπως ο αλγόριθμος Σουρ ή ο αλγόριθμος Λέβινσον σε χρόνο ${\displaystyle O(n^{2})}$.^[1][2] Παραλλαγές των τελευταίων έχουν αποδειχθεί ότι είναι ασθενώς σταθεροί (δηλαδή παρουσιάζουν αριθμητική ευστάθεια για καλά εξαρτημένα γραμμικά συστήματα).^[3] Οι αλγόριθμοι μπορούν επίσης να χρησιμοποιηθούν για την εύρεση της ορίζουσας ενός πίνακα Τόεπλιτς σε χρόνο ${\displaystyle O(n^{2})}$.^[4]

Ένας πίνακας Τόεπλιτς μπορεί επίσης να αναλυθεί (δηλ. να παραγοντοποιηθεί) σε χρόνο ${\displaystyle O(n^{2})}$.^[5] Ο αλγόριθμος Μπαρέις για μια LU παραγοντοποιήση είναι σταθερός^[6]. Η LU παραγοντοποιήση δίνει μια γρήγορη μέθοδο για την επίλυση ενός συστήματος Τόεπλιτς, καθώς και για τον υπολογισμό της ορίζουσας.

Γενικές ιδιότητες

• Ένας ${\displaystyle n\times n}$ πίνακας Τόεπλιτς μπορεί να οριστεί ως ένας πίνακας ${\displaystyle A}$ όπου ${\displaystyle A_{i,j}=c_{i-j}}$, για σταθερές ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$. Το σύνολο των ${\displaystyle n\times n}$ πινάκων Τόεπλιτς είναι ένας υποχώρος του διανυσματικού χώρου των ${\displaystyle n\times n}$ πινάκων (υπό πρόσθεση πινάκων και κλιμακωτό πολλαπλασιασμό).
• Δύο πίνακες Τόεπλιτς μπορούν να προστεθούν σε ${\displaystyle O(n)}$ χρόνο (αποθηκεύοντας μόνο μία τιμή κάθε διαγωνίου) και πολλαπλασιασμός σε ${\displaystyle O(n^{2})}$ χρόνο.
• Οι πίνακες Τόεπλιτς είναι προσωσυμμετρικοί. Οι συμμετρικοί πίνακες Τόεπλιτς είναι τόσο κεντροσυμμετρικοί όσο και δισυμμετρικοί.
• Οι πίνακες Τόεπλιτς είναι επίσης στενά συνδεδεμένοι με τις σειρές Fourier, επειδή ο τελεστής πολλαπλασιασμού με ένα τριγωνομετρικό πολυώνυμο, συμπιεσμένος σε ένα χώρο πεπερασμένων διαστάσεων, μπορεί να αναπαρασταθεί από έναν τέτοιο πίνακα. Ομοίως, μπορεί κανείς να αναπαραστήσει τη γραμμική συνέλιξη ως πολλαπλασιασμό με έναν πίνακα Τόεπλιτς.
• Οι πίνακες Τόεπλιτς αντιμετατίθενται ασυμπτωτικά. Αυτό σημαίνει ότι διαγωνοποιούνται στην ίδια βάση όταν η διάσταση γραμμής και στήλης τείνει στο άπειρο.
• Για συμμετρικούς πίνακες Τόεπλιτς, υπάρχει η παραγοντοποιήση

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

όπου ${\displaystyle G}$ είναι το κάτω τριγωνικό μέρος του ${\displaystyle {\frac {1}{a_{0}}}A}$.

• Ο αντίστροφος ενός αντιστρέψιμου συμμετρικού πίνακα Τόεπλιτς έχει την παράσταση

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

όπου ${\displaystyle B}$ και ${\displaystyle C}$ είναι κατώτεροι τριγωνικοί πίνακες Τόεπλιτς και ${\displaystyle C}$ είναι ένας αυστηρά κατώτερος τριγωνικός πίνακας.^[7]

Διακριτή συνέλιξη

Η πράξη συνέλιξη μπορεί να κατασκευαστεί ως πολλαπλασιασμός πινάκων, όπου μία από τις εισόδους μετατρέπεται σε πίνακα Τόεπλιτς. Παραδείγματος χάριν, η συνέλιξη των ${\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}}.}$

Η προσέγγιση αυτή μπορεί να επεκταθεί για τον υπολογισμό της αυτοσυσχέτισης, της διασταυρούμενης συσχέτισης, του κινητού μέσου όρου κ.λπ.

Πίνακας Τόεπλιτς άπειρου μεγέθους

Ένας δι-πεπερασμένος πίνακας Τόεπλιτς (δηλ. καταχωρήσεις με δείκτη ${\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}}.}$

Ο επαγόμενος τελεστής είναι δεσμευμένος εάν και μόνο εάν οι συντελεστές του πίνακα Τόεπλιτς ${\displaystyle A}$ είναι οι συντελεστές Φουριέ κάποιας ουσιαστικά δεσμευμένης συνάρτησης ${\displaystyle f}$.

Σε τέτοιες περιπτώσεις, το ${\displaystyle f}$ ονομάζεται σύμβολο του πίνακα Τόεπλιτς ${\displaystyle A}$, και η φασματική νόρμα του πίνακα Τόεπλιτς ${\displaystyle A}$ συμπίπτει με την ${\displaystyle L^{\infty }}$ νόρμα του συμβόλου του. Η απόδειξη είναι απλή και μπορεί να βρεθεί ως Θεώρημα 1.1 του.^[8]

Δημοσιεύσεις

• Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf. 
• Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9. 
• Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244. 
• 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 
• 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 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, 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, doi:10.1007/s10208-015-9254-z 

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Πραγματικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Ταυτοτικός πίνακας
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Διανυσματικός χώρος
• Αντιμεταθέσιμοι πίνακες
• Πολλαπλασιασμός πινάκων
• Τριγωνικός πίνακας
• Διακριτός μετασχηματισμός Φουριέ
• Αντιστρέψιμος πίνακας
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Information Security and Privacy: 13th Australasian Conference, ACISP 2008 ...
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Toeplitz Matrices and Singular Integral Equations: The Bernd Silbermann ..
• Toeplitz Matrices and Operators
• Toeplitz and Circulant Matrices: A Review

Παραπομπές

1. Press και άλλοι 2007, §2.8.2—Toeplitz matrices
2. Hayes 1996, Chapter 5.2.6
3. Krishna & Wang 1993
4. Monahan 2011, §4.5—Toeplitz systems
5. Brent 1999
6. Bojanczyk και άλλοι 1995
7. Mukherjee & Maiti 1988
8. Böttcher & Grudsky 2012

• 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, 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, https://books.google.com/books?id=Dmr0BwAAQBAJ&pg=PA1 
• Brent, R. P. (1999), «Stability of fast algorithms for structured linear systems», στο: Kailath, T.; Sayed, A. H., επιμ., Fast Reliable Algorithms for Matrices with Structure, SIAM, σελ. 103–116, doi:10.1137/1.9781611971354.ch4 
• 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, 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, doi:10.1198/016214505000001069 
• Hayes, Monson H. (1996), Statistical digital signal processing and modeling, John Wiley & Son, ISBN 0-471-59431-8 
• 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, http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes 
• Monahan, J. F. (2011), Numerical Methods of Statistics, en:Cambridge University Press 
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), «On some properties of positive definite Toeplitz matrices and their possible applications», Linear Algebra and Its Applications 102: 211–240, doi:10.1016/0024-3795(88)90326-6, https://core.ac.uk/download/pdf/82070573.pdf 
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (Third έκδοση), 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 
• 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, doi:10.1109/TIT.2016.2553041