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

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

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

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

Ο αλγόριθμος Μπάρεϊς για πίνακες Τόεπλιτς (που δεν πρέπει να συγχέεται με τον γενικό αλγόριθμο Μπάρεϊς) τρέχει περίπου τόσο γρήγορα όσο η αναδρομή Λεβινσον, αλλά χρησιμοποιεί χώρο , ενώ η αναδρομή Λεβινσον χρησιμοποιεί μόνο χώρο O(n). Ο αλγόριθμος Μπάρεϊς, όμως, είναι αριθμητικά σταθερός,Bojanczyk et al. (1995).Brent (1999). ενώ η αναδρομή Λέβινσον είναι στην καλύτερη περίπτωση μόνο ασθενώς σταθερή (δηλ. παρουσιάζει αριθμητική ευστάθεια για καλά κλιμακωμένα γραμμικά συστήματα).Krishna & Wang (1993)..

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

 Παραγωγή 

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



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

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

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



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

Η αναδρομή Λέβινσον-Ντέρμπιν ορίζει το nth «προωθητικό διάνυσμα», που συμβολίζεται , ως το διάνυσμα μήκους n που ικανοποιεί:

Το nth «αντίστροφο διάνυσμα»  ορίζεται ομοίως- είναι το διάνυσμα μήκους n που ικανοποιεί:

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

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

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

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



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

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

Αυτοί οι δύο όροι σφάλματος μπορούν να χρησιμοποιηθούν για να σχηματίσουν διανύσματα υψηλότερης τάξης προς τα εμπρός και προς τα πίσω που περιγράφονται ως εξής. Χρησιμοποιώντας τη γραμμικότητα των πινάκων, η ακόλουθη ταυτότητα ισχύει για όλα τα :

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

Για να βρεθούν αυτοί οι συντελεστές, ,  είναι τέτοιοι ώστε :

και αντίστοιχα ,  είναι τέτοια ώστε :

Πολλαπλασιάζοντας και τις δύο προηγούμενες εξισώσεις με  προκύπτει η ακόλουθη εξίσωση:


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



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





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



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

Εάν ο 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. 
 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.
Περαιτέρω εργασίες

 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. 

Περιλήψεις
 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. 
 Claerbout, Jon F. (1976). "Chapter 7 – Waveform Applications of Least-Squares." Fundamentals of Geophysical Data Processing. Palo Alto: Blackwell Scientific Publications. 

 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

 Παραπομπές 






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