Τριδιαγώνιος πίνακας

Στη γραμμική άλγεβρα, ένας **Τριδιαγώνιος πίνακας** είναι ένας πίνακας που έχει μη μηδενικά στοιχεία μόνο στην κύρια διαγώνιο, στην υποδιαγώνιο/κατώτερη διαγώνιο (η πρώτη διαγώνιος κάτω από αυτήν) και στην υπερδιαγώνιο/άνω διαγώνιο (η πρώτη διαγώνιος πάνω από την κύρια διαγώνιο). Παραδείγματος χάριν, ο πίνακας είναι τριδιαγώνιος:

:\begin{pmatrix}
1 & 4 & 0 & 0 \\
3 & 4 & 1 & 0 \\
0 & 2 & 3 & 4 \\
0 & 0 & 1 & 3 \\
\end{pmatrix}.

Η Ορίζουσα ενός τριδιαγώνιου πίνακα δίνεται από τη *συνέχουσα* των στοιχείων του.

Ένας ορθογώνιος μετασχηματισμός ενός συμμετρικού (ή ερμητικού) πίνακα σε τριαδική μορφή μπορεί να γίνει με τον αλγόριθμο Λάντζος.

## Ιδιότητες

Ένας τριδιαγώνιος πίνακας είναι ένας πίνακας που είναι τόσο ανώτερος όσο και κατώτερος πίνακας Χέσενμπεργκ. Ειδικότερα, ένας τριδιαγώνιος πίνακας είναι ένα άμεσο άθροισμα *p* πινάκων 1 επί 1 και *q* πινάκων 2 επί 2, έτσι ώστε  - η διάσταση του τριδιαγώνου. Αν και ένας γενικός τριδιαγώνιος πίνακας δεν είναι απαραίτητα συμμετρικός ή ερμιτιανός, πολλοί από αυτούς που προκύπτουν κατά την επίλυση προβλημάτων γραμμικής άλγεβρας έχουν μία από αυτές τις ιδιότητες. Επιπλέον, εάν ένας πραγματικός τριδιαγώνιος πίνακας *A* ικανοποιεί την τιμή *a**k*,*k*+1 *a**k*+1,*k* > 0 για όλα τα *k*, έτσι ώστε τα πρόσημα των εγγραφών του να είναι συμμετρικά, τότε είναι παρόμοιος με έναν Ερμιτιανό πίνακα, μέσω μιας διαγώνιας αλλαγής του πίνακα βάσης. Συνεπώς, οι ιδιοτιμές του είναι πραγματικές. Αν αντικαταστήσουμε την αυστηρή ανισότητα με *a**k*,*k*+1 *a**k*+1,*k* ≥ 0, τότε λόγω συνέχειας, οι ιδιοτιμές εξακολουθούν να είναι εγγυημένα πραγματικές, αλλά ο πίνακας δεν χρειάζεται πλέον να είναι παρόμοιος με έναν ερμιτιανό πίνακα.

Το σύνολο όλων των τριδιαγώνιων πινάκων *n × n* σχηματίζει έναν διανυσματικό χώρο *3n-2* διαστάσεων.

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

### Ορίζουσα

Η Ορίζουσα ενός τριδιαγώνιου πίνακα *A* τάξης *n* μπορεί να υπολογιστεί από μια αναδρομική σχέση τριών όρων.. Ας γράψουμε*f*1&nbsp;=&nbsp;|*a*1|&nbsp;=&nbsp;*a*1 (δηλαδή, *f*1 είναι η ορίζουσα του πίνακα 1 επί 1 που αποτελείται μόνο από το *a*1) και έστω

:f_n = \begin{vmatrix}
a_1 & b_1 \\
c_1 & a_2 & b_2 \\
& c_2 & \ddots & \ddots \\
& & \ddots & \ddots & b_{n-1} \\
& & & c_{n-1} & a_n
\end{vmatrix}.

Η ακολουθία (*f**i*) ονομάζεται συνέχουσα και ικανοποιεί τη σχέση αναδρομής

:f_n = a_n f_{n-1} - c_{n-1}b_{n-1}f_{n-2}

με αρχικές τιμές *f*0&nbsp;=&nbsp;1 και *f*−1&nbsp;=&nbsp;0. Το κόστος υπολογισμού του καθοριστικού παράγοντα ενός τριδιαγώνιου πίνακα χρησιμοποιώντας αυτόν τον τύπο είναι γραμμικό ως προς το *n*, ενώ το κόστος είναι κυβικό για έναν γενικό πίνακα.

### Αντιστροφή

Ο αντιστρέψιμος πίνακας ενός μη-συνεχούς τριδιαγώνιου πίνακα *T*

:T = \begin{pmatrix}
a_1 & b_1 \\
c_1 & a_2 & b_2 \\
& c_2 & \ddots & \ddots \\
& & \ddots & \ddots & b_{n-1} \\
& & & c_{n-1} & a_n
\end{pmatrix}

Δίνεται από τη σχέση 

:(T^{-1})_{ij} = \begin{cases}
(-1)^{i+j}b_i \cdots b_{j-1} \theta_{i-1} \phi_{j+1}/\theta_n & \text{ if } i  j\\
\end{cases}

όπου τα *θ<sub>i</sub>* ικανοποιούν τη σχέση επανάληψης

:\theta_i = a_i \theta_{i-1} - b_{i-1}c_{i-1}\theta_{i-2} \qquad i=2,3,\ldots,n

με αρχικές συνθήκες *θ*0&nbsp;=&nbsp;1, *θ*1&nbsp;=&nbsp;*a*1 and the *ϕ**i* ικανοποιεί το

:\phi_i = a_i \phi_{i+1} - b_i c_i \phi_{i+2} \qquad i=n-1,\ldots,1

με αρχικούς όρους *ϕ**n*+1&nbsp;=&nbsp;1 και *ϕ**n*&nbsp;=&nbsp;*a<sub>n</sub>*.

Λύσεις κλειστής μορφής μπορούν να υπολογιστούν για ειδικές περιπτώσεις όπως συμμετρικοί πίνακες με όλα τα διαγώνια και εκτός διαγωνίου στοιχεία ίσα  ή πίνακες Τόεπλιτζ και για τη γενική περίπτωση επίσης.

Κατά κανόνα, ο αντίστροφος ενός τριδιαγώνιου πίνακα είναι ένας ημι-διαχωρίσιμος πίνακας και αντίστροφα. Ο αντίστροφος ενός συμμετρικού τριδιαγώνιου πίνακα μπορεί να γραφεί ως ένας πίνακας ενός ζεύγους (ή αλλιώς γεννήτρια-αντιπροσωπευτικός ημι-διαχωρίσιμος πίνακας) της μορφής.

\begin{pmatrix}
        \alpha_1 & -\beta_1 \\
        -\beta_1  & \alpha_2 & -\beta_2 \\
        & \ddots & \ddots & \ddots & \\
& & \ddots & \ddots & -\beta_{n-1} \\
& & & -\beta_{n-1} & \alpha_n
        \end{pmatrix}^{-1} = 
\begin{pmatrix}
        a_1 b_1 & a_1 b_2 & \cdots & a_1 b_n \\
        a_1 b_2 & a_2 b_2 & \cdots & a_2 b_n \\
        \vdots  & \vdots & \ddots & \vdots \\
        a_1 b_n & a_2 b_n & \cdots & a_n b_n
    \end{pmatrix}
= \left( a_{\min(i,j)} b_{\max(i,j)} \right)


όπου \begin{cases} \displaystyle a_i = \frac{\beta_{i} \cdots \beta_{n-1}}{\delta_i \cdots \delta_n\,b_n}
\\ \displaystyle
b_i = \frac{\beta_1 \cdots \beta_{i-1}}{d_1 \cdots d_i}\end{cases}
με \begin{cases}
        d_n = \alpha_n,\quad d_{i-1} = \alpha_{i-1} - \frac{\beta_{i-1}^2}{d_{i}}, & i = n, n-1, \cdots, 2,
        \\
        \delta_1 = \alpha_1, \quad
        \delta_{i+1} = \alpha_{i+1} - \frac{\beta_{i}^2}{\delta_{i}}, & i = 1, 2, \cdots, n-1.
    \end{cases}


### Λύση γραμμικού συστήματος

Ένα σύστημα εξισώσεων *Ax*&nbsp;=&nbsp;*b* for&nbsp;b\in \R^n μπορεί να επιλυθεί με μια αποτελεσματική μορφή απαλοιφής του Γκάους όταν το *A* είναι τρισδιάστατο και ονομάζεται αλγόριθμος τρισδιάστατων πινάκων, απαιτώντας *O*(*n*) πράξεις.

### Ιδιοτιμές

Όταν ένας τριδιαγώνιος πίνακας είναι επίσης Τόπλιτζ, υπάρχει μια απλή λύση κλειστής μορφής για τις ιδιοτιμές του, δηλαδή:

: a - 2 \sqrt{bc} \cos \left (\frac{k\pi}{n+1} \right ), \qquad k=1, \ldots, n. 

Ένας πραγματικός συμμετρικός τριδιαγώνιος πίνακας έχει πραγματικές ιδιοτιμές και όλες οι ιδιοτιμές είναι διακριτές (απλές) εάν όλα τα εκτός διαγωνίου στοιχεία είναι μη μηδενικά. Υπάρχουν πολυάριθμες μέθοδοι για τον αριθμητικό υπολογισμό των ιδιοτιμών ενός πραγματικού συμμετρικού τριδιαγώνιου πίνακα με αυθαίρετη πεπερασμένη ακρίβεια, που συνήθως απαιτούν O(n^2) πράξεις για έναν πίνακα μεγέθους n\times n, αν και υπάρχουν γρήγοροι αλγόριθμοι που (χωρίς παράλληλο υπολογισμό) απαιτούν μόνο O(n\log n).

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

### Ομοιότητα με συμμετρικό τριδιαγώνιο πίνακα

Για μη συμμετρικούς ή μη συμμετρικούς τριδιαγώνιους πίνακες μπορεί κανείς να υπολογίσει την **ιδιοαποσύνθεση** (eigendecomposition) χρησιμοποιώντας έναν μετασχηματισμό ομοιότητας. Δεδομένου ενός πραγματικού τριδιαγώνιου, μη συμμετρικού πίνακα

:
T = \begin{pmatrix}
a_1 & b_1 \\
c_1 & a_2 & b_2 \\
& c_2 & \ddots & \ddots \\
& & \ddots & \ddots & b_{n-1} \\
& & & c_{n-1} & a_n
\end{pmatrix}


όπου b_i \neq c_i .
Ας υποθέσουμε ότι κάθε γινόμενο των εκτός διαγωνίου εγγραφών είναι  θετικό b_i c_i > 0  και ορίστε έναν πίνακα μετασχηματισμού D ως εξής 

:
D := \operatorname{diag}(\delta_1 , \dots, \delta_n) 
\quad \text{for} \quad
\delta_i :=
\begin{cases}
1 & , \, i=1
\\
\sqrt{\frac{c_{i-1} \dots c_1}{b_{i-1} \dots b_1}} & , \, i=2,\dots,n \,.
\end{cases}


Ο μετασχηματισμός ομοιότητας D^{-1} T D  δίνει έναν *συμμετρικό* τρισδιάστατο πίνακα J από:
:
J:=D^{-1} T D 
= \begin{pmatrix}
a_1 & \sgn b_1 \,  \sqrt{b_1 c_1} \\
\sgn b_1 \, \sqrt{b_1 c_1} & a_2 & \sgn b_2 \, \sqrt{b_2 c_2} \\
& \sgn b_2 \,  \sqrt{b_2 c_2} & \ddots & \ddots \\
& & \ddots & \ddots & \sgn b_{n-1} \, \sqrt{b_{n-1} c_{n-1}} \\
& & & \sgn b_{n-1} \,  \sqrt{b_{n-1} c_{n-1}} & a_n
\end{pmatrix} \,.


Ας σημειωθεί ότι οι T και J έχουν τις ίδιες ιδιοτιμές.

## Προγραμματισμός υπολογιστών

Ένας μετασχηματισμός που ανάγει έναν γενικό πίνακα σε μορφή Χέσενμπεργκ θα ανάγει έναν ερμιτιανό πίνακα σε τριδιαγώνια μορφή. Έτσι, πολλοί αλγόριθμοι ιδιοτιμών, όταν εφαρμόζονται σε έναν ερμιτιανό πίνακα, ανάγουν τον ερμιτιανό πίνακα εισόδου σε (συμμετρική πραγματική) τριδιαγώνια μορφή ως πρώτο βήμα.

Ένας τριδιαγώνιος πίνακας μπορεί επίσης να αποθηκευτεί πιο αποτελεσματικά από έναν γενικό πίνακα με τη χρήση ενός ειδικού συστήματος αποθήκευσης. Παραδείγματος χάριν, η συσκευασία LAPACK Fortran αποθηκεύει έναν μη συμμετρικό τρισδιάστατο πίνακα τάξης *n* σε τρεις μονοδιάστατους πίνακες, έναν μήκους *n* που περιέχει τα διαγώνια στοιχεία και δύο μήκους *n* − 1 που περιέχουν τα υποδιαγώνια και υπερδιαγώνια στοιχεία.

## Εφαρμογές

Η διακριτοποίηση στο χώρο της μονοδιάστατης εξίσωσης διάχυσης ή θερμότητας

:
\begin{pmatrix}
\frac{\partial u_{1}(t)}{\partial t} \\
\frac{\partial u_{2}(t)}{\partial t} \\
\vdots \\
\frac{\partial u_{N}(t)}{\partial t}
\end{pmatrix}
 = \frac{\alpha}{\Delta x^2} \begin{pmatrix}
-2 & 1 & 0 & \ldots & 0 \\
1 & -2 & 1 & \ddots & \vdots  \\
0 & \ddots & \ddots & \ddots & 0 \\
\vdots  & & 1 & -2 & 1 \\
0 & \ldots & 0 & 1 & -2
\end{pmatrix}
\begin{pmatrix}
u_{1}(t) \\
u_{2}(t) \\
\vdots \\
u_{N}(t) \\
\end{pmatrix}


με σταθερά διακριτοποίησης \Delta x. Ο πίνακας είναι τρισδιάστατος με a_{i}=-2 και b_{i}=c_{i}=1. Σημείωση: εδώ δεν χρησιμοποιούνται συνοριακές συνθήκες.

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

* Field Arithmetic
* Πραγματικό προβολικό επίπεδο
* Εσωτερικό γινόμενο
* Φυσικός αριθμός
* Πίνακας (μαθηματικά)
* Τριγωνικός πίνακας
* Διάνυσμα
* Τρίγωνο του Πασκάλ
* Ταυτοτικός πίνακας

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

* English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
* Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
* Matrix calculator
* Matrix Analysis
* Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
* Symmetries, Lie Algebras and Representations: A Graduate Course for Physicists
* Introduction to Numerical Analysis
* Matrices, Moments and Quadrature with Applications
* An Introduction to Numerical Analysis
* Matrix Computations and Semiseparable Matrices: Linear Systems, Τόμος 1

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

* 
* 
* 
* 
* Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
* 
* High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
* Tridiagonal linear system solver in C++

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


* Janko Bračič, *Kolobar aritmetičnih funkcij* (*[[:en:Ring (algebra)|Ring]] of arithmetical functions*), (Obzornik mat, fiz. **49** (2002) 4, pp.&nbsp;97–108)  (MSC (2000) 11A25) 
* Iwaniec and Kowalski, *Analytic number theory*, AMS (2004).

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