Algoritmo di Levinson-Durbin

L'algoritmo di Levinson-Durbin, in algebra lineare, serve per calcolare, con metodo ricorsivo, la soluzione di un'equazione che coinvolge una matrice di Toeplitz. L'algoritmo viene eseguito in passi, il che rappresenta un forte miglioramento rispetto al Metodo di eliminazione di Gauss, il quale richiede passaggi. L'algoritmo Levinson–Durbin fu proposto prima da Norman Levinson, nel 1947, e migliorato da James Durbin nel 1960; successivamente fu ulteriormente migliorato, portandolo da fino a moltiplicazioni, da W. F. Trench e S. Zohar, rispettivamente. Altri metodi per elaborare i dati, includono la decomposizione di Schur e la decomposizione di Cholesky. In confronto a questi, la ricorsione di Levinson (in particolare la ricorsione di Levinson suddivisa) tende a essere più veloce dal punto di vista computazionale, ma più sensibile a inesattezze computazionali come gli errori di arrotondamento. L'algoritmo di Bareiss per le matrici di Toeplitz (da non confondere con l'algoritmo di Bareiss generale) è veloce quanto la ricorsione di Levinson-Durbin, ma utilizza passaggi, mentre la ricorsione di Levinson-Durbin richiede solo passaggi. L'algoritmo di Bareiss, tuttavia, è numericamente stabile, mentre la ricorsione di Levinson-Durbin, nella migliore delle ipotesi, è solo debolmente stabile (cioè mostra stabilità numerica per sistemi lineari ben condizionati). Gli algoritmi più recenti, chiamati algoritmi di Toeplitz asintoticamente veloci o, in alcuni testi, superveloci, possono risolvere il problema in per vari (es. , ). La ricorsione di Levinson-Durbin rimane popolare per diversi motivi; primo, è relativamente facile da comprendere; inoltre, può essere più veloce di un algoritmo superveloce per piccoli (di solito ).