Algoritmo de Levinson

El algoritmo de Levinson o de Levinson-Durbin es un algoritmo del álgebra lineal para calcular en forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz. El costo computacional es de Θ(n2), una mejora considerable frente a la eliminación de Gauss-Jordan, cuyo costo es de Θ(n3). Hay algoritmos nuevos, llamados asintóticamente rápidos o a menudo algoritmos de Toeplitz superrápidos, que pueden resolver con un costo de Θ(n logpn) para varios p (por ejemplo, para p = 2, p = 3). La recursión de Levinson sigue siendo popular por distintas razones; por un lado, es relativamente simple de comprender en comparación; por otro lado, puede ser más rápida que un algoritmo superrápido para n pequeño (normalmente para n < 256 [1] Archivado el 5 de septiembre de 2006 en Wayback Machine.). El algoritmo de Levinson-Durbin fue propuesto por primera vez por en 1947, mejorado por J. Durbin en 1960 y más tarde mejorado a 4n2 y luego a 3n2 multiplicaciones por W. F. Trench y S. Zohar, respectivamente. Otros métodos para procesar datos incluyen la descomposición de Schur y la descomposición de Cholesky. En comparación a estos, la recursión de Levinson (particularmente la recursión de Split-Levinson) tiende a ser más rápida computacionalmente, aunque más sensible a imperfecciones computacionales como errores de redondeo.