Αναδρομή Λέβινσον

Η αναδρομή Λέβινσον ή αναδρομή Λέβινσον-Ντούρμπιν είναι μια διαδικασία στη γραμμική άλγεβρα για τον αναδρομικό υπολογισμό της λύσης μιας εξίσωσης που περιλαμβάνει έναν πίνακα Τόεπλιτς. Ο αλγόριθμος εκτελείται σε χρόνο Θ(n²)^[1], ο οποίος αποτελεί ισχυρή βελτίωση σε σχέση με την απαλοιφή Γκάους-Ζορντάν, η οποία εκτελείται σε χρόνο Θ(n³).

Ο αλγόριθμος Λέβινσον-Ντούρμπιν προτάθηκε για πρώτη φορά από τον Νόρμαν Λέβινσον το 1947, βελτιώθηκε από τον Τζέιμς Ντούρμπιν το 1960 και στη συνέχεια βελτιώθηκε σε 4n² και στη συνέχεια σε 3n² πολλαπλασιασμούς από τους Γ. Φ. Τρέντς και Σ. Ζοχάρ, αντίστοιχα.

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

Ο αλγόριθμος Μπάρεϊς για πίνακες Τόεπλιτς (που δεν πρέπει να συγχέεται με τον γενικό αλγόριθμο Μπάρεϊς) τρέχει περίπου τόσο γρήγορα όσο η αναδρομή Λεβινσον, αλλά χρησιμοποιεί χώρο O(n²), ενώ η αναδρομή Λεβινσον χρησιμοποιεί μόνο χώρο O(n). Ο αλγόριθμος Μπάρεϊς, όμως, είναι αριθμητικά σταθερός,^[2][3] ενώ η αναδρομή Λέβινσον είναι στην καλύτερη περίπτωση μόνο ασθενώς σταθερή (δηλ. παρουσιάζει αριθμητική ευστάθεια για καλά κλιμακωμένα γραμμικά συστήματα).^[4].

Οι νεότεροι αλγόριθμοι, που ονομάζονται ασυμπτωτικά γρήγοροι ή μερικές φορές υπερταχείς αλγόριθμοι Τόεπλιτς, μπορούν να λύσουν σε Θ(n log^pn) για διάφορα p (π.χ. p = 2,^[5][6] p = 3 ^[7]). Η αναδρομή Λέβινσον παραμένει δημοφιλής για διάφορους λόγους- αφενός, είναι σχετικά εύκολα κατανοητή σε σύγκριση- αφετέρου, μπορεί να είναι ταχύτερη από έναν υπερταχύ αλγόριθμο για μικρά n (συνήθως n < 256).^[8].

Παραγωγή

Ιστορικό

Οι εξισώσεις πινάκων ακολουθούν τη μορφή

${\displaystyle \mathbf {M} \,{\vec {x}}={\vec {y}}.}$

Ο αλγόριθμος Λέβινσον-Ντούρμπιν μπορεί να χρησιμοποιηθεί για οποιαδήποτε τέτοια εξίσωση, εφόσον ο Μ είναι ένας γνωστός πίνακας Τόεπλιτς με μη μηδενική κύρια διαγώνιο. Εδώ ${\displaystyle {\vec {y}}}$ είναι ένα γνωστό διάνυσμα, και ${\displaystyle {\vec {x}}}$ είναι ένα άγνωστο διάνυσμα αριθμών x_i που δεν έχει ακόμη προσδιοριστεί.

Για τις ανάγκες αυτού του άρθρου, το ê_i είναι ένα διάνυσμα που αποτελείται εξ ολοκλήρου από μηδενικά, εκτός από την iη θέση του, η οποία έχει την τιμή ένα. Το μήκος του θα καθορίζεται σιωπηρά από το περιβάλλον πλαίσιο. O όρος N αναφέρεται στο πλάτος του παραπάνω πίνακα - ο M είναι ένας N×N πίνακας. Τέλος, σε αυτό το άρθρο, οι άνω δείκτες αναφέρονται σε έναν επαγωγικό δείκτη, ενώ οι κάτω δείκτες υποδηλώνουν δείκτες. Παραδείγματος χάριν (και ορισμού), σε αυτό το άρθρο, ο πίνακας Tⁿ είναι ένας πίνακας n×n που αντιγράφει το άνω αριστερό τμήμα n×n' του μπλοκ από το M - δηλαδή, Tnij = Mij..

Ο Tⁿ είναι επίσης ένας πίνακας Τόεπλιτς, που σημαίνει ότι μπορεί να γραφεί ως εξής

${\displaystyle \mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}.}$

Εισαγωγικά βήματα

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

Η αναδρομή Λέβινσον-Ντέρμπιν ορίζει το n^th «προωθητικό διάνυσμα», που συμβολίζεται ${\displaystyle {\vec {f}}^{n}}$, ως το διάνυσμα μήκους n που ικανοποιεί:

${\displaystyle \mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}}_{1}.}$

Το n^th «αντίστροφο διάνυσμα» ${\displaystyle {\vec {b}}^{n}}$ ορίζεται ομοίως- είναι το διάνυσμα μήκους n που ικανοποιεί:

${\displaystyle \mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}}_{n}.}$

Μια σημαντική απλούστευση μπορεί να προκύψει όταν ο M είναι συμμετρικός πίνακας- τότε τα δύο διανύσματα συνδέονται με bⁿ_i = fⁿ_n+1−i-δηλαδή, είναι αντίστροφα στη σειρά το ένα του άλλου. Αυτό μπορεί να εξοικονομήσει μερικούς επιπλέον υπολογισμούς σε αυτή την ειδική περίπτωση.

Λήψη των διανυσμάτων προς τα πίσω

Ακόμη και αν ο πίνακας δεν είναι συμμετρικός, τότε το n^th εμπρόσθιο και το nοστό οπίσθιο διάνυσμα μπορούν να βρεθούν από τα διανύσματα μήκουςn − 1 ως εξής. Πρώτον, το εμπρόσθιο διάνυσμα μπορεί να επεκταθεί με ένα μηδέν για να προκύψει:

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\\\end{bmatrix}}={\begin{bmatrix}\ &\ &\ &t_{-n+1}\\\ &\mathbf {T} ^{n-1}&\ &t_{-n+2}\\\ &\ &\ &\vdots \\t_{n-1}&t_{n-2}&\dots &t_{0}\\\end{bmatrix}}{\begin{bmatrix}\ \\{\vec {f}}^{n-1}\\\ \\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}^{n}\end{bmatrix}}.}$

Κατά τη μετάβαση από το Tⁿ⁻¹ στο Tⁿ, η επιπλέον στήλη που προστίθεται στον πίνακα δεν διαταράσσει τη λύση όταν ένα μηδενικό χρησιμοποιείται για την επέκταση του διανύσματος προς τα εμπρός. Ωστόσο, η πρόσθετη γραμμή που προστέθηκε στον πίνακα έχει διαταράξει τη λύση- και έχει δημιουργήσει έναν ανεπιθύμητο όρο σφάλματος ε_f που εμφανίζεται στην τελευταία θέση. Η παραπάνω εξίσωση του δίνει την τιμή του:

${\displaystyle \varepsilon _{f}^{n}\ =\ \sum _{i=1}^{n-1}\ M_{ni}\ f_{i}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{n-i}\ f_{i}^{n-1}.}$

Αυτό το σφάλμα θα επιστραφεί σύντομα και θα εξαλειφθεί από το νέο εμπρόσθιο διάνυσμα- αλλά πρώτα, το αντίστροφο διάνυσμα πρέπει να επεκταθεί με παρόμοιο τρόπο (αν και αντίστροφα). Για το αντίστροφο διάνυσμα,

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}t_{0}&\dots &t_{-n+2}&t_{-n+1}\\\vdots &\ &\ &\ \\t_{n-2}&\ &\mathbf {T} ^{n-1}&\ \\t_{n-1}&\ &\ &\end{bmatrix}}{\begin{bmatrix}\ \\0\\\ \\{\vec {b}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\varepsilon _{b}^{n}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

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

${\displaystyle \varepsilon _{b}^{n}\ =\ \sum _{i=2}^{n}\ M_{1i}\ b_{i-1}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{-i}\ b_{i}^{n-1}.\ }$

Αυτοί οι δύο όροι σφάλματος μπορούν να χρησιμοποιηθούν για να σχηματίσουν διανύσματα υψηλότερης τάξης προς τα εμπρός και προς τα πίσω που περιγράφονται ως εξής. Χρησιμοποιώντας τη γραμμικότητα των πινάκων, η ακόλουθη ταυτότητα ισχύει για όλα τα ${\displaystyle (\alpha ,\beta )}$:

${\displaystyle \mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\varepsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

Εάν τα α και β επιλεγούν έτσι ώστε η δεξιά πλευρά να δίνει ê₁ ή ê_n, τότε η ποσότητα στην παρένθεση θα πληροί τον ορισμό του n^th διανύσματος προς τα εμπρός ή προς τα πίσω, αντίστοιχα. Με αυτά τα άλφα και βήτα επιλεγμένα, το άθροισμα των διανυσμάτων στην παρένθεση είναι απλό και δίνει το επιθυμητό αποτέλεσμα.

Για να βρεθούν αυτοί οι συντελεστές, ${\displaystyle \alpha _{f}^{n}}$, ${\displaystyle \beta _{f}^{n}}$ είναι τέτοιοι ώστε :

${\displaystyle {\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

και αντίστοιχα ${\displaystyle \alpha _{b}^{n}}$, ${\displaystyle \beta _{b}^{n}}$ είναι τέτοια ώστε :

${\displaystyle {\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.}$

Πολλαπλασιάζοντας και τις δύο προηγούμενες εξισώσεις με ${\displaystyle {\mathbf {T} }^{n}}$ προκύπτει η ακόλουθη εξίσωση:

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.}$

Τώρα, καθώς όλα τα μηδενικά στη μέση των δύο παραπάνω διανυσμάτων δεν λαμβάνονται υπόψη και καταρρέουν, απομένει μόνο η ακόλουθη εξίσωση:

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.}$

Με την επίλυση αυτών (χρησιμοποιώντας τον τύπο αντιστροφής του πίνακα 2×2 του Κράμερ), τα νέα διανύσματα προς τα εμπρός και προς τα πίσω είναι:

${\displaystyle {\vec {f}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\varepsilon _{f}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

${\displaystyle {\vec {b}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\varepsilon _{b}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.}$

Η εκτέλεση αυτών των διανυσματικών αθροισμάτων, λοιπόν, δίνει τα n^th εμπρός και πίσω διανύσματα από τα προηγούμενα. Το μόνο που απομένει είναι να βρεθεί το πρώτο από αυτά τα διανύσματα, και στη συνέχεια μερικά γρήγορα αθροίσματα και πολλαπλασιασμοί δίνουν τα υπόλοιπα. Τα πρώτα διανύσματα προς τα εμπρός και προς τα πίσω είναι απλά:

${\displaystyle {\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].}$

Αλγόριθμος μπλοκ Λέβινσον

Εάν ο M δεν είναι αυστηρά Τόεπλιτς, αλλά σύνθετος Τόεπλιτς, η αναδρομή Λέβινσον μπορεί να προκύψει με τον ίδιο τρόπο, θεωρώντας τον σύνθετο πίνακα Τόεπλιτς ως πίνακα Τόεπλιτς με στοιχεία πίνακα (Musicus 1988). Οι σύνθετοι πίνακες Τόεπλιτς προκύπτουν φυσικά σε αλγορίθμους επεξεργασίας σήματος όταν πρόκειται για πολλαπλές ροές σήματος (π.χ. σε συστήματα ΜΙΜΟ) ή κυκλικά στάσιμα σήματα.

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

Πηγές

• Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction." J. Math. Phys., v. 25, pp. 261–278.
• Durbin, J. (1960). "The fitting of time series models." Rev. Inst. Int. Stat., v. 28, pp. 233–243.
• Trench, W. F. (1964). "An algorithm for the inversion of finite Toeplitz matrices." J. Soc. Indust. Appl. Math., v. 12, pp. 515–522.
• Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for Toeplitz and Almost Toeplitz Matrices." RLE TR No. 538, MIT. [1]
• Delsarte, P. and Genin, Y. V. (1986). "The split Levinson algorithm." IEEE Transactions on Acoustics, Speech, and Signal Processing, v. ASSP-34(3), pp. 470–478.

Περαιτέρω εργασίες

• Bojanczyk, A.W.; Brent, R.P.; De Hoog, F.R.; Sweet, D.R. (1995). «On the stability of the Bareiss and related Toeplitz factorization algorithms». SIAM Journal on Matrix Analysis and Applications 16: 40–57. doi:10.1137/S0895479891221563. 
• Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
• Bunch, J. R. (1985). "Stability of methods for solving Toeplitz systems of equations." SIAM J. Sci. Stat. Comput., v. 6, pp. 349–364. [2]
• Krishna, H.; Wang, Y. (1993). «The Split Levinson Algorithm is weakly stable». SIAM Journal on Numerical Analysis 30 (5): 1498–1508. doi:10.1137/0730078. http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJNAAM000030000005001498000001&idtype=cvips&gifs=yes. 

Περιλήψεις

• Bäckström, T. (2004). "2.2. Levinson–Durbin Recursion." Linear Predictive Modelling of Speech – Constraints and Line Spectrum Pair Decomposition. Doctoral thesis. Report no. 71 / Helsinki University of Technology, Laboratory of Acoustics and Audio Signal Processing. Espoo, Finland. [3]
• Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." Fundamentals of Geophysical Data Processing. Palo Alto: Blackwell Scientific Publications. [4]
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.8.2. Toeplitz Matrices», Numerical Recipes: The Art of Scientific Computing (3rd έκδοση), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html?pg=96 
• Golub, G.H., and Loan, C.F. Van (1996). "Section 4.7 : Toeplitz and related Systems" Matrix Computations, Johns Hopkins University Press

Δείτε επίσης

• 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
• Signal Processing for Intelligent Sensor Systems
• Quantum Probability and Spectral Analysis of Graphs.
• Symplectic Methods in Harmonic Analysis and in Mathematical Physics...
• The Theory of Linear Prediction
• Linear Prediction Theory: A Mathematical Basis for Adaptive Systems...
• The Semicircle Law, Free Random Variables and Entropy....
• Symplectic Methods for the Symplectic Eigenproblem

Παραπομπές

1. Gerstein - University of Toronto, G. H. (Godfrey Harold) (1910). Orders of infinity, the 'Infinitärcalcül' of Paul Du Bois-Reymond. Cambridge University Press. 
2. Bojanczyk et al. (1995).
3. Brent (1999).
4. Krishna & Wang (1993).
5. «Archived copy» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 25 Μαρτίου 2012. Ανακτήθηκε στις 1 Απριλίου 2013. 
6. «Archived copy» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 15 Νοεμβρίου 2009. Ανακτήθηκε στις 28 Απριλίου 2009. 
7. «Archived copy» (PDF). saaz.cs.gsu.edu. Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 18 Απριλίου 2007. Ανακτήθηκε στις 12 Ιανουαρίου 2022. 
8. «Archived copy» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 5 Σεπτεμβρίου 2006. Ανακτήθηκε στις 15 Αυγούστου 2006. 

• Ozluk, A.E. (1982), Pair Correlation of Zeros of Dirichlet L-functions, Ph. D. Dissertation, Ann Arbor: Univ. of Michigan 
• Katz, Nicholas M.; Sarnak, Peter (1999), «Zeroes of zeta functions and symmetry», Bulletin of the American Mathematical Society, New Series 36 (1): 1–26, doi:10.1090/S0273-0979-99-00766-1, ISSN 0002-9904 
• Bernstein, Dennis S. (2009). Matrix Mathematics: Theory, Facts, and Formulas (2nd έκδοση). Princeton University Press. ISBN 978-0691140391 – μέσω Google Books. 
• Petersen, Kaare Brandt· Pedersen, Michael Syskind (15 Νοεμβρίου 2012). «The Matrix Cookbook» (PDF). σελίδες 17–23.