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

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

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

είναι ένας **πίνακας Τόεπλιτς**. Αν το στοιχείο i,j του A συμβολίζεται 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 παραγοντοποιήση είναι σταθερός. Η 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) χρόνο.
* Οι πίνακες Τόεπλιτς είναι προσωσυμμετρικοί. Οι συμμετρικοί πίνακες Τόεπλιτς είναι τόσο κεντροσυμμετρικοί όσο και δισυμμετρικοί.
* Οι πίνακες Τόεπλιτς είναι επίσης στενά συνδεδεμένοι με τις σειρές Fourier, επειδή ο τελεστής πολλαπλασιασμού με ένα τριγωνομετρικό πολυώνυμο, συμπιεσμένος σε ένα χώρο πεπερασμένων διαστάσεων, μπορεί να αναπαρασταθεί από έναν τέτοιο πίνακα. Ομοίως, μπορεί κανείς να αναπαραστήσει τη γραμμική συνέλιξη ως πολλαπλασιασμό με έναν πίνακα Τόεπλιτς.
* Οι πίνακες Τόεπλιτς αντιμετατίθενται ασυμπτωτικά. Αυτό σημαίνει ότι διαγωνοποιούνται στην ίδια βάση όταν η διάσταση γραμμής και στήλης τείνει στο άπειρο.
* Για συμμετρικούς πίνακες Τόεπλιτς, υπάρχει η παραγοντοποιήση 

::\frac{1}{a_0} A = G G^\operatorname{T} - (G - I)(G - I)^\operatorname{T}

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

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

::A^{-1} = \frac{1}{\alpha_0} (B B^\operatorname{T} - C C^\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}.


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

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

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

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

* 
* 
* 
*
*
*Golub G. H., van Loan C. F. (1996), *Matrix Computations* (Johns Hopkins University Press) §4.7&mdash;Toeplitz and Related Systems
*Gray R. M., *[http://ee.stanford.edu/~gray/toeplitz.pdf Toeplitz and Circulant Matrices: A Review]* (Now Publishers) 
*
*
*

## Δείτε επίσης

* 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

## Παραπομπές

*
*
*
*
*
*
*
*
*
*
*
*
*

 

Κατηγορία:Αριθμητική γραμμική άλγεβρα 
Κατηγορία:Γραμμική άλγεβρα 
Κατηγορία:Πίνακες (μαθηματικά) 
Κατηγορία:Θεωρία πινάκων 
Κατηγορία:Αλγόριθμοι