Πίνακας ταινία

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

Πίνακας ταινιών

Εύρος ή πλάτης ζώνης

Επίσημα, θεωρούμε έναν πίνακα n×n A=(a_i,j ). Αν όλα τα στοιχεία του πίνακα είναι μηδέν εκτός μιας διαγωνίως οριοθετημένης ταινίας, το εύρος της οποίας καθορίζεται από τις σταθερές k₁ και k₂:

$a_{i,j}=0\text{if}j<i-k_1\text{ or }j>i+k_2;k_1,k_2\ge 0.$

τότε οι ποσότητες k₁ και k₂ ονομάζονται κατώτερο εύρος ταινίας και ανώτερο εύρος ζώνης, αντίστοιχαΠρότυπο:Sfn Το εύρος ζώνης (Πρότυπο:Visible anchor) του πίνακα είναι το μέγιστο των k₁ και k₂- με άλλα λόγια, είναι ο αριθμός k τέτοιος ώστε $a_{i,j}=0$ αν $|i-j|>k$.Πρότυπο:Sfn

Παραδείγματα

• Ένας πίνακας ταινία με k₁ = k₂ = 0 είναι ένας διαγώνιος πίνακας
• Ένας πίνακας ταινία με k₁ = k₂ = 1 είναι ένας τριγωνικός πίνακας
• Για k₁ = k₂ = 2 έχουμε έναν πενταδιαγώνιο πίνακα κ.ο.κ.
• Τριγωνικοί πίνακες
  • Για k₁ = 0, k₂ = n−1, προκύπτει ο ορισμός ενός άνω τριγωνικού πίνακα
  • Ομοίως, για k₁ = n−1, k₂ = 0 προκύπτει ένας κάτω τριγωνικός πίνακας.
• Ανώτεροι και κατώτεροι πίνακες Έσενμπεργκ
• Πίνακες Τόεπλιτς όταν το εύρος ζώνης είναι περιορισμένο.
• Διαγώνιοι Σύνθετοι πίνακες
• Πίνακες μετατόπισης και πίνακες διάτμησης
• Πίνακες στην κανονική μορφή του Ζορντάν
• Πίνακας skyline, που ονομάζεται επίσης «πίνακας μεταβλητής ταινίας» - μια γενίκευση του πίνακα ταινίας
• Οι αντίστροφοι των πινάκων Λέμερ είναι σταθεροί τριαδιαγώνιοι πίνακες, και επομένως είναι πίνακες ζώνης.

Εφαρμογές

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

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

Αποθήκευση ταινίας

Οι πίνακες ταινιών αποθηκεύονται συνήθως με την αποθήκευση των διαγωνίων στη ζώνη- οι υπόλοιποι είναι σιωπηρά μηδενικοί.

Παραδείγματος χάριν, ένας τριδιαγώνιος πίνακας έχει εύρος ζώνης 1. Ο πίνακας 6 επί 6

$\left[\begin{array}{cccccc}{B}_{11}& B_{12}& 0& \cdots & \cdots & 0\\ B_{21}& B_{22}& B_{23}& \ddots & \ddots & ⋮\\ 0& B_{32}& B_{33}& B_{34}& \ddots & ⋮\\ ⋮& \ddots & B_{43}& B_{44}& B_{45}& 0\\ ⋮& \ddots & \ddots & B_{54}& B_{55}& B_{56}\\ 0& \cdots & \cdots & 0& B_{65}& B_{66}\end{array}\right]$

αποθηκεύεται ως ο πίνακας 6 επί 3

$\left[\begin{array}{ccc}0& B_{11}& B_{12}\\ B_{21}& B_{22}& B_{23}\\ B_{32}& B_{33}& B_{34}\\ B_{43}& B_{44}& B_{45}\\ B_{54}& B_{55}& B_{56}\\ B_{65}& B_{66}& 0\end{array}\right].$

Μια περαιτέρω εξοικονόμηση είναι δυνατή όταν ο πίνακας είναι συμμετρικός. Παραδείγματος χάριν, ας θεωρήσουμε έναν συμμετρικό πίνακα 6 επί 6 με ανώτερο εύρος ζώνης 2:

$\left[\begin{array}{cccccc}{A}_{11}& A_{12}& A_{13}& 0& \cdots & 0\\ & A_{22}& A_{23}& A_{24}& \ddots & ⋮\\ & & A_{33}& A_{34}& A_{35}& 0\\ & & & A_{44}& A_{45}& A_{46}\\ & sym& & & A_{55}& A_{56}\\ & & & & & A_{66}\end{array}\right].$

Αυτός ο πίνακας αποθηκεύεται ως πίνακας 6 επί 3:

$\left[\begin{array}{ccc}{A}_{11}& A_{12}& A_{13}\\ A_{22}& A_{23}& A_{24}\\ A_{33}& A_{34}& A_{35}\\ A_{44}& A_{45}& A_{46}\\ A_{55}& A_{56}& 0\\ A_{66}& 0& 0\end{array}\right].$

Μορφή ταινίας αραιών πινάκων

Από υπολογιστική άποψη, η εργασία με πίνακες ταινίας είναι πάντα προτιμότερη από την εργασία με τετραγωνικούς πίνακες παρόμοιας διάστασης. Ένας πίνακας ταινία

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

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

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

Το πρόβλημα της εύρεσης μιας αναπαράστασης ενός πίνακα με ελάχιστο εύρος ζώνης μέσω μεταθέσεων των γραμμών και των στηλών είναι NP-Δύσκολα Πρότυπο:Sfn.

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Citation
• 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) Πρότυπο:Doi
• Πρότυπο:Citation
• Πρότυπο:Citation
• Πρότυπο:Citation

Δείτε επίσης

• 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
• Large Random Matrices: Lectures on Macroscopic Asymptotics: École d'Été de .....
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Random Matrices, Random Processes and Integrable Systems
• Random Matrices
• Toeplitz and Circulant Matrices: A Review

Παραπομπές

• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.