Recursión de Levinson

Saltar a navegación, búsqueda

La recursión 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 Θ(n²), una mejora considerable frente a la eliminación de Gauss-Jordan, cuyo costo es de Θ(n³).

Hay algoritmos nuevos, llamados asintóticamente rápidos o a menudo algoritmos de Toeplitz superrápidos, que pueden resolver con un costo de Θ(n log^pn) 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]).

El algoritmo de Levinson-Durbin fue propuesto por primera vez por Norman Levinson en 1947, mejorado por J. Durbin en 1960 y más tarde mejorado a 4n² y luego a 3n² 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.

Derivación

Contexto

Las ecuaciones matriciales tienen la siguiente forma:

$\vec y = \mathbf M \ \vec x$

El algoritmo de Levinson-Durbin puede usarse para tales ecuaciones, siempre y cuando M sea una matriz de Toeplitz conocida, con una diagonal principal no nula. En la ecuación, $\vec y$ es un vector conocido (en el sentido del álgebra lineal de lista de números) y $\vec x$ es un vector de valores x_i desconocidos y a ser determinados.

Llamaremos ê_i al vector compuesto de ceros, salvo en su i-ésimo lugar, que contiene el valor de la unidad. Su dimensión dependerá del contexto y estará implícita en éste. Con N nos referiremos al ancho de la matriz anterior, es decir, M es una matriz de N×N. Finalmente, los superindices se referirán a índices inductivos, mientras que subíndices denotarán simplemente índices. Por ejemplo, la matriz Tⁿ es una matriz de n×n que copia el bloque superior izquierdo de n×n de M, es decir, Tⁿ_ij = M_ij.

Tⁿ también es una matriz de Toeplitz, en el sentido de que puede escribirse como:

$\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}$

Pasos introductorios

El algoritmo se desarrolla en dos pasos. En el primero, se establecen dos conjuntos de vectores, llamados vectores de avance y de retroceso. Los vectores de avance sirven para obtener el conjunto de vectores de retroceso y pueden luego ser descartados. Los vectores de retroceso son necesarios para el segundo paso, donde se los usa para construir la solución.

La recursión de Levinson-Durbin define el n-ésimo "vector de avance", denotado $\vec f^n$ , como el vector de longitud n que satisface:

$\mathbf T^n \vec f^n = \hat e_1$

El n-ésimo "vector de retroceso" $\vec b^n$ se define de manera similar; es el vector de longitud n que satisface:

$\mathbf T^n \vec b^n = \hat e_n$

Una simplificación importante ocurre cuando M es una matriz simétrica: los dos vectores se relacionan mediante bⁿ_i = fⁿ_n+1-i; es decir, uno se obtiene invirtiendo el order de los elementos del otro. Esto puede ahorrar cálculos extra en ese caso en particular.

Obtención del vector de retroceso

Incluso si la matriz no es simétrica, los n-ésimos vectores de avance y retroceso pueden encontrarse a partir de los vectores de longitud n-1 de la siguiente manera. Primero, el vector de avance puede extenderse con un cero para obtener:

$\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 \\ \epsilon_f^n \\ \end{bmatrix}$

Al ir de T^n-1 a Tⁿ, la columna extra agregada a la matriz no altera el resultado cuando se usa un cero para extender el vector de avance. Sin embargo, la fila extra agregada a la matriz sí lo altera, creando un error indeseado ε_f en el último lugar. De la ecuación anterior:

$\epsilon_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}$

Volveremos a este error en un momento. Antes, extenderemos al vector de retroceso de manera similar (aunque invertida). Para el vector de retroceso:

$\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} \epsilon_b^n \\ 0 \\ \vdots \\ 0 \\ 1 \\ \end{bmatrix}$

Como antes, la columna extra agregada a la matriz no altera el resultado, pero sí lo hace la fila extra. Tenemos aquí, entonces, otro error indeseado ε_b, cuyo valor es:

$\epsilon_b^n \ = \ \sum_{i=2}^n \ M_{1i} \ b_{i-1}^{n-1} \ = \ \sum_{i=1}^{n-1} \ t_{-i} \ b_i^{n-1} \$

Podemos usar estos dos términos de error para eliminarlos en forma simultánea. Debido a la propiedad de linealidad de las matrices:

$\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 \\ \epsilon_f \\ \end{bmatrix} + \beta \begin{bmatrix} \epsilon_b \\ 0 \\ \vdots \\ 0 \\ 1 \\ \end{bmatrix}$

Si elegimos α y β de manera tal que el lado derecho dé como resultado ê₁ o ê_n, entonces el valor entre paréntesis va a satisfacer la definición del vector de avance o retroceso n-ésimo, respectivamente. Con esos valores de α y β, la suma de vectores entre paréntesis es simple y da el resultado esperado.

Para encontrar estos coeficientes, es decir, α_f, β_f, α_b, y β_b, nótese que todos los ceros en el medio de los dos vectores de arriba pueden ser ignorados y colapsados, dejando simplemente la ecuación:

$\begin{bmatrix} 1 & \epsilon_b \\ \epsilon_f & 1 \end{bmatrix} \begin{bmatrix} \alpha_f & \alpha_b \\ \beta_f & \beta_b \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$

Resolviendo este sistema (por ejemplo, con la fórmula de inversa para matrices de 2x2), los nuevos vectores de avance y retroceso son:

$\vec f^n = {1 \over { 1 - \epsilon_b^n \epsilon_f^n }} \begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix} - { \epsilon_f^n \over { 1 - \epsilon_b^n \epsilon_f^n }}\begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}$

$\vec b^n = {1 \over { 1 - \epsilon_b^n \epsilon_f^n }} \begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix} - { \epsilon_b^n \over { 1 - \epsilon_b^n \epsilon_f^n }}\begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}$

Realizando la suma de vectores, entonces, se obtienen los vectores de avance y retroceso n-ésimos, dados los anteriores. Lo único que resta es encontrar los vectores iniciales, para luego obtener los otros mediante simples sumas y multiplicaciones. Los vectores de avance y retroceso iniciales son simplemente:

$\vec f^1 = \vec b^1 = \begin{bmatrix}{1 \over M_{11}}\end{bmatrix} = \begin{bmatrix}{1 \over t_0}\end{bmatrix}$

Usando los vectores de retroceso

Los pasos anteriores dan los N vectores de retroceso para M. De ahí, una ecuación más arbitraria es:

$\vec y = \mathbf M \ \vec x$

La solución puede construirse de la misma manera iterativa en se construyeron los vectores de retroceso. Así, $\vec x$ debe generalizarse a la secuencia $\vec x^n$ , de la cual $\vec x^N = \vec x$ .

La solución se construye entonces de manera iterativa, notando que si:

$\mathbf T^{n-1} \begin{bmatrix} x_1^{n-1} \\ x_2^{n-1} \\ \dots \\ x_{n-1}^{n-1} \\ \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \dots \\ y_{n-1} \\ \end{bmatrix}$

Entonces, extendiendo con un cero nuevamente, y definiendo una constante de error donde corresponda:

$\mathbf T^{n} \begin{bmatrix} x_1^{n-1} \\ x_2^{n-1} \\ \dots \\ x_{n-1}^{n-1} \\ 0 \\ \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ \dots \\ y_{n-1} \\ \epsilon_x^{n-1} \end{bmatrix}$

Podemos usar entonces el vector de retroceso n-ésimo para eliminar el término de error y reemplazarlo con la fórmula deseada de la siguiente manera:

$\mathbf T^{n} \left ( \begin{bmatrix} x_1^{n-1} \\ x_2^{n-1} \\ \dots \\ x_{n-1}^{n-1} \\ 0 \\ \end{bmatrix} + (y_n - \epsilon_x^{n-1}) \ \vec b^n \right ) = \begin{bmatrix} y_1 \\ y_2 \\ \dots \\ y_{n-1} \\ y_n \\ \end{bmatrix}$

Extendiendo este método hasta n = N se obtiene la solución $\vec x$ .

En la práctica, estos pasos se hacen a menudo en forma concurrente con el resto del procedimiento, pero forman una unidad coherente y merecen ser tratados como pasos separados.

Referencias

Levinson, N. (1947). "The Wiener RMS error criterion in filter design and prediction," J. Math. Phys., v. 25, pp. 261-278.

Véase también

Recursión de Split-Levinson
Predicción lineal

Obtenido de "Recursi%C3%B3n de Levinson"

Categorías: Matrices | Análisis numérico

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

Levinson recursion — or Levinson Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in Θ(n2) time, which is a strong improvement over Gauss Jordan elimination, which… … Wikipedia
Levinson — is a surname, and may refer to:* André Levinson * Arthur D. Levinson * Barry Levinson * Dennis Levinson * Eric L. Levinson * Feodor Levinson Lessing * Gerald Levinson * Jonathan Levinson * Mark Levinson * Norman Levinson ** Levinson recursion (… … Wikipedia
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 … Wikipedia Español
Norman Levinson — (August 11, 1912, Lynn, Massachusetts – October 10, 1975, Boston) was an American mathematician. Some of his major contributions were in the study of Fourier transforms, complex analysis, non linear differential equations, number theory, and… … Wikipedia
Sistema de ecuaciones lineales — En matemáticas y álgebra lineal, un sistema de ecuaciones lineales, también conocido como sistema lineal de ecuaciones o simplemente sistema lineal, es un conjunto de ecuaciones lineales sobre un cuerpo o un anillo conmutativo. Un ejemplo de… … Wikipedia Español
Linear prediction — is a mathematical operation where future values of a discrete time signal are estimated as a linear function of previous samples.In digital signal processing, linear prediction is often called linear predictive coding (LPC) and can thus be viewed … Wikipedia
Deconvolution — In mathematics, deconvolution is an algorithm based process used to reverse the effects of convolution on recorded data.[1] The concept of deconvolution is widely used in the techniques of signal processing and image processing. Because these… … Wikipedia
List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… … Wikipedia
Ordinary differential equation — In mathematics, an ordinary differential equation (or ODE) is a relation that contains functions of only one independent variable, and one or more of their derivatives with respect to that variable. A simple example is Newton s second law of… … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia

Los diccionarios y las enciclopedias sobre el Académico

Recursión de Levinson

Recursión de Levinson

Contenido