Matriz de Toeplitz
En álgebra lineal , una matriz de Toeplitz o matriz de constante diagonal , llamada así por Otto Toeplitz , es una matriz en la que cada diagonal descendente de izquierda a derecha es constante. Por ejemplo, la siguiente matriz es una matriz de Toeplitz:
se llama sistema Toeplitz si A es una matriz Toeplitz. Si A es una matriz Toeplitz de n × n , entonces el sistema tiene solo 2 n − 1 grados de libertad , en lugar de n 2 . Por lo tanto, podríamos esperar que la solución de un sistema Toeplitz fuera más fácil y, de hecho, ese es el caso.
Los sistemas de Toeplitz se pueden resolver mediante el algoritmo de Levinson en tiempo O ( n 2 ) . [1] Se ha demostrado que las variantes de este algoritmo son débilmente estables (es decir, exhiben estabilidad numérica para sistemas lineales bien acondicionados ). [2] El algoritmo también se puede utilizar para encontrar el determinante de una matriz de Toeplitz en tiempo O ( n 2 ) . [3]
Matriz A Toeplitz también se puede descomponer (es decir factorizada) en O ( n 2 ) tiempo. [4] algoritmo El Bareiss para una descomposición LU es estable. [5] Una LU descomposición da un método rápido para resolver un sistema de Toeplitz, y también para calcular el determinante.
En la literatura se han descrito algoritmos que son asintóticamente más rápidos que los de Bareiss y Levinson, pero no se puede confiar en su precisión. [6] [7] [8] [9]
La operación de convolución se puede construir como una multiplicación de matrices, donde una de las entradas se convierte en una matriz de Toeplitz. Por ejemplo, la convolución de y se puede formular como:
