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

Κάθε πίνακας της μορφής

είναι ένας πίνακας Τόεπλιτς. Αν το στοιχείο του συμβολίζεται τότε έχουμε

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

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

Επεξεργασία

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

 

ονομάζεται σύστημα Τόεπλιτς αν   είναι ένας πίνακας Τόεπλιτς. Αν   είναι ένας   πίνακας Τόεπλιτς, τότε το σύστημα έχει το πολύ μόνο   μοναδιαίες τιμές, αντί για  . Θα μπορούσαμε επομένως να περιμένουμε ότι η επίλυση ενός συστήματος Τόεπλιτς θα ήταν ευκολότερη, και πράγματι αυτό συμβαίνει.

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

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

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

Επεξεργασία
  • Ένας   πίνακας Τόεπλιτς μπορεί να οριστεί ως ένας πίνακας   όπου  , για σταθερές  . Το σύνολο των   πινάκων Τόεπλιτς είναι ένας υποχώρος του διανυσματικού χώρου των   πινάκων (υπό πρόσθεση πινάκων και κλιμακωτό πολλαπλασιασμό).
  • Δύο πίνακες Τόεπλιτς μπορούν να προστεθούν σε   χρόνο (αποθηκεύοντας μόνο μία τιμή κάθε διαγωνίου) και πολλαπλασιασμός σε   χρόνο.
  • Οι πίνακες Τόεπλιτς είναι προσωσυμμετρικοί. Οι συμμετρικοί πίνακες Τόεπλιτς είναι τόσο κεντροσυμμετρικοί όσο και δισυμμετρικοί.
  • Οι πίνακες Τόεπλιτς είναι επίσης στενά συνδεδεμένοι με τις σειρές Fourier, επειδή ο τελεστής πολλαπλασιασμού με ένα τριγωνομετρικό πολυώνυμο, συμπιεσμένος σε ένα χώρο πεπερασμένων διαστάσεων, μπορεί να αναπαρασταθεί από έναν τέτοιο πίνακα. Ομοίως, μπορεί κανείς να αναπαραστήσει τη γραμμική συνέλιξη ως πολλαπλασιασμό με έναν πίνακα Τόεπλιτς.
  • Οι πίνακες Τόεπλιτς αντιμετατίθενται ασυμπτωτικά. Αυτό σημαίνει ότι διαγωνοποιούνται στην ίδια βάση όταν η διάσταση γραμμής και στήλης τείνει στο άπειρο.
  • Για συμμετρικούς πίνακες Τόεπλιτς, υπάρχει η παραγοντοποιήση
 
όπου   είναι το κάτω τριγωνικό μέρος του  .
 
όπου   και   είναι κατώτεροι τριγωνικοί πίνακες Τόεπλιτς και   είναι ένας αυστηρά κατώτερος τριγωνικός πίνακας.[7]

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

Επεξεργασία

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

 
 

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

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

Επεξεργασία

Ένας δι-πεπερασμένος πίνακας Τόεπλιτς (δηλ. καταχωρήσεις με δείκτη  )   επάγει έναν γραμμικό τελεστή στο  .

 

Ο επαγόμενος τελεστής είναι δεσμευμένος εάν και μόνο εάν οι συντελεστές του πίνακα Τόεπλιτς   είναι οι συντελεστές Φουριέ κάποιας ουσιαστικά δεσμευμένης συνάρτησης  .

Σε τέτοιες περιπτώσεις, το   ονομάζεται σύμβολο του πίνακα Τόεπλιτς  , και η φασματική νόρμα του πίνακα Τόεπλιτς   συμπίπτει με την   νόρμα του συμβόλου του. Η απόδειξη είναι απλή και μπορεί να βρεθεί ως Θεώρημα 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)
  • 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 

Δείτε επίσης

Επεξεργασία

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

Επεξεργασία

Παραπομπές

Επεξεργασία