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

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

${\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, έτσι ώστε p + q/2 = n - η διάσταση του τριδιαγώνου. Αν και ένας γενικός τριδιαγώνιος πίνακας δεν είναι απαραίτητα συμμετρικός ή ερμιτιανός, πολλοί από αυτούς που προκύπτουν κατά την επίλυση προβλημάτων γραμμικής άλγεβρας έχουν μία από αυτές τις ιδιότητες. Επιπλέον, εάν ένας πραγματικός τριδιαγώνιος πίνακας 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₁ = |a₁| = a₁ (δηλαδή, f₁ είναι η ορίζουσα του πίνακα 1 επί 1 που αποτελείται μόνο από το a₁) και έστω

$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₀ = 1 και f₋₁ = 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\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}$

όπου τα θ_i ικανοποιούν τη σχέση επανάληψης

$\theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n$

με αρχικές συνθήκες θ₀ = 1, θ₁ = a₁ 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 = 1 και ϕ_n = a_n.

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

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

${\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 = b for $b\in \mathbb {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}TD$ δίνει έναν συμμετρικό τρισδιάστατο πίνακα $J$ από:

$J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {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 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

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

• Μαυρογιάννης, Ν. Σ. (Μαΐου 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. 
• Gray, Lawrence F.; Flanigan, Francis J.; Kazdan, Jerry L.; Frank, David H.; Fristedt, Bert (1990), Calculus two: linear and nonlinear functions, Berlin: Springer-Verlag, σελ. 375, ISBN 0-387-97388-5, https://archive.org/details/calculustwolinea00flan/page/375 
• Adkins, William A.; Weintraub, Steven H. (1992), Algebra: An Approach via Module Theory, Graduate Texts in Mathematics, 136, Springer-Verlag, ISBN 3-540-97839-9, Zbl 0768.00003 
• Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
• Moawwad El-Mikkawy, Abdelrahman Karawia (2006). «Inversion of general tridiagonal matrices». Applied Mathematics Letters 19 (8): 712–720. doi:10.1016/j.aml.2005.11.012. http://app2.mans.edu.eg/eulc/Libraries/itemsAttach/IssueArticle/1037592/papermik.pdf. 
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Tridiagonal linear system solver in C++

Παραπομπές

• Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp. 97–108) (MSC (2000) 11A25)
• Iwaniec and Kowalski, Analytic number theory, AMS (2004).