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

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

[\begin{matrix} 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{matrix}] .

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

A = [\begin{matrix} a_{0} & a_{- 1} & a_{- 2} & \dots & \dots & a_{- (n - 1)} \\ a_{1} & a_{0} & a_{- 1} & ⋱ & ⋮ \\ a_{2} & a_{1} & ⋱ & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & ⋱ & a_{- 1} & a_{- 2} \\ ⋮ & ⋱ & a_{1} & a_{0} & a_{- 1} \\ a_{n - 1} & \dots & \dots & a_{2} & a_{1} & a_{0} \end{matrix}]

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

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

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

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

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

A x = b

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

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

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

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

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

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

όπου

G

είναι το κάτω τριγωνικό μέρος του

\frac{1}{a_{0}} A

.

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

A^{- 1} = \frac{1}{α_{0}} (B B^{T} - C C^{T})

όπου

B

και

C

είναι κατώτεροι τριγωνικοί πίνακες Τόεπλιτς και

C

είναι ένας αυστηρά κατώτερος τριγωνικός πίνακας.^[7]

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

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

y = h * x = [\begin{matrix} h_{1} & 0 & \dots & 0 & 0 \\ h_{2} & h_{1} & ⋮ & ⋮ \\ h_{3} & h_{2} & \dots & 0 & 0 \\ ⋮ & h_{3} & \dots & h_{1} & 0 \\ h_{m - 1} & ⋮ & ⋱ & h_{2} & h_{1} \\ h_{m} & h_{m - 1} & ⋮ & h_{2} \\ 0 & h_{m} & ⋱ & h_{m - 2} & ⋮ \\ 0 & 0 & \dots & h_{m - 1} & h_{m - 2} \\ ⋮ & ⋮ & h_{m} & h_{m - 1} \\ 0 & 0 & 0 & \dots & h_{m} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ x_{n} \end{matrix}]

y^{T} = [\begin{matrix} h_{1} & h_{2} & h_{3} & \dots & h_{m - 1} & h_{m} \end{matrix}] [\begin{matrix} x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & 0 & 0 & \dots & 0 \\ 0 & x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & 0 & \dots & 0 \\ 0 & 0 & x_{1} & x_{2} & x_{3} & \dots & x_{n} & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & \dots & 0 & 0 & x_{1} & \dots & x_{n - 2} & x_{n - 1} & x_{n} & 0 \\ 0 & \dots & 0 & 0 & 0 & x_{1} & \dots & x_{n - 2} & x_{n - 1} & x_{n} \end{matrix}] .

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