MATEMÁTICAS - EPÓNIMOS

La factorización de curva elíptica de Lenstra o método de factorización de curva elíptica ( del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas. Para una factorización de propósito general, ECM es el tercer método más rápido conocido de factorización. El segundo más rápido es la criba cuadrática de múltiples polinomios y el más rápido es la criba general del cuerpo de números. La factorización de curva elíptica de Lenstra es llamada así en honor a Hendrik Lenstra.

En la práctica, ECM es considerado un algoritmo de factorización de propósito especial así como el más adecuado para encontrar factores pequeños. A fecha de 2012, es todavía el mejor algoritmo para divisores que no superen los 20 a 25 dígitos decimales (64 a 83 bits respectivamente), así como su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar de por el tamaño del número n a ser factorizado. Frecuentemente, ECM se usa para eliminar factores pequeños de un entero muy grande con muchos factores; si el entero resultante todavía es compuesto, entonces solo tiene factores grandes y es factorizado mediante el uso de técnicas de propósito general. El factor más grande encontrado usando ECM cuenta con 75 dígitos y fue descubierto el 2 de agosto de 2012 por Samuel Wagstaff.¹​ Incrementando el número de curvas probadas se mejoran las posibilidades de encontrar un factor, pero no son lineales con el incremento en el número de dígitos.

La factorización de formas cuadradas de Shanks es un método para factorizar enteros inventado por Daniel Shanks como una mejora del método de factorización de Fermat.

El éxito del método depende de encontrar números enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}-y^{2}=N}$, donde ${\displaystyle N}$ es el entero a ser factorizado. Una mejora (indicada por Kraitchik) es buscar enteros ${\displaystyle x}$ e ${\displaystyle y}$ tales que ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$. Encontrando un par adecuado ${\displaystyle (x,y)}$ no se garantiza una factorización de ${\displaystyle N}$, pero esto implica que ${\displaystyle N}$ es un factor de ${\displaystyle x^{2}-y^{2}=(x-y)(x+y)}$, y hay una buena posibilidad de que los divisores primos de ${\displaystyle N}$ estén distribuidos entre esos dos factores, así que el cálculo del máximo común divisor de ${\displaystyle N}$ y ${\displaystyle x-y}$ dará un factor no trivial de ${\displaystyle N}$.

Un algoritmo práctico para encontrar pares ${\displaystyle (x,y)}$ que satisfagan ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$ fue desarrollado por Shanks, que lo llamó Factorización de formas cuadradas (en inglés Square Forms Factorization o SQUFOF). El algoritmo puede ser expresado en términos de fracciones continuas, o en términos de formas cuadráticas. A pesar de que ahora existen métodos de factorización más eficientes disponibles, SQUFOF tiene la ventaja de que es lo suficientemente pequeño para ser implementado en una calculadora programable.

El filtro de Hodrick-Prescott es un método para extraer el componente secular o tendencia de una serie temporal, propuesto en 1980 por Robert J. Hodrick y Edward C. Prescott.¹​ Descompone la serie observada en dos componentes, uno tendencial y otro cíclico. El ajuste de sensibilidad de la tendencia a las fluctuaciones a corto plazo es obtenido modificando un multiplicador λ. Es actualmente una de las técnicas más ampliamente utilizada en las investigaciones sobre ciclos económicos para calcular la tendencia de las series de tiempo, pues brinda resultados más consistentes con los datos observados que otros métodos.

Utilidad[editar]

En los estudios sobre las fluctuaciones cíclicas, es importante eliminar de la serie observada el efecto de los componentes estacional, irregular y tendencial y trabajar únicamente con los cíclicos. Por consiguiente, se requieren métodos de descomposición de series de tiempo, de manera que puedan establecerse los ciclos, en tanto "fluctuaciones recurrentes en la actividad real respecto a una tendencia".²​ Se logra distinguir la tendencia del ciclo. Kydland y Prescott justifican el empleo de este filtro, por su linealidad, por estar bien definido sin elementos subjetivos, independiente de la serie a la cual se aplica y ser fácil de replicar para extraer "la tendencia que uno podría dibujar a mano alzada".³​ Recientemente se han desarrollado también otros métodos con el mismo objetivo, tal como el denominado "tendencia lineal estocástica".

Origen[editar]

Según sus propios autores.¹​ el filtro de Hodrick-Prescott tiene su origen en el método de "Whittaker-Henderson de tipo A", que fue usado primero por actuarios para suavizar las tablas de mortalidad, pero además ha sido útil en estudios de astronomía y balística. Los analistas han encontrado antecedentes en formulaciones de John von Neumann.

Fórmula[editar]

La serie ${\displaystyle y_{t}\,}$ para ${\displaystyle t=1,2,...,T\,}$ denota los logaritmos de una serie variable. ${\displaystyle y_{t}\,}$ está conformada por un componente tendencial, representado por ${\displaystyle \tau \,}$ y un componente cíclico, representado por ${\displaystyle c\,}$ tales que ${\displaystyle y_{t}\ =\tau _{t}\ +c_{t}\,}$⁴​ Dado un valor positivo ${\displaystyle \lambda }$, adecuadamente escogido, se calcula el componente tendencial resolviendo el siguiente problema:

min ${\displaystyle \sum _{t=1}^{T}{(y_{t}-\tau _{t})^{2}}+\lambda \sum _{t=2}^{T-1}{[(\tau _{t+1}-\tau _{t})-(\tau _{t}-\tau _{t-1})]^{2}}.\,}$

Según Hodrick y Prescott el componente tendencia de una serie es el que minimiza tal ecuación.

Siempre:

${\displaystyle \sum _{t=1}^{T}{(y_{t}-\tau _{t})}=0\,}$

es decir, que la tendencia calculada pasa por el "centro" de la serie básica.

El primer término de la ecuación representa la suma de las desviaciones de la serie respecto a la tendencia al cuadrado ${\displaystyle c_{t}\ =y_{t}\ -\tau _{t}\,}$ y es una medida del grado de ajuste las cuales penalizan el componente cíclico. El segundo término es una múltiple ${\displaystyle \lambda }$ de la suma de los cuadrados de las segundas diferencias de los componentes de tendencia, y es una medida del grado de suavidad. Este segundo termino penaliza variaciones en la tasa de crecimiento del componente tendencial. Cuanto más grande sea el valor de ${\displaystyle \lambda }$, más alta es la penaltidad. La elección de λ es aleatoria, pero Hodrick y Prescott estiman que, para datos trimestrales, un valor de ${\displaystyle \lambda =1600}$es razonable, bajo el supuesto de que cualquier perturbación que tiene efectos durante 8 o más años tiene carácter permanente. Para series mensuales se suele utilizar 14400 y para series anuales se recomienda un valor igual a 100.⁵​

La medida de las fluctuaciones cíclicas está dada por ${\displaystyle c_{t}\,}$:

${\displaystyle c_{t}=y_{t}-\tau _{t}\,}$.

Existe una pequeña subrutina de FORTRAN.⁶​ que calcula eficientemente los componentes de tendencia y las desviaciones.

Límites[editar]

La aplicación del filtro de Hodrick-Prescott sólo será óptima⁷​ si:

• Los datos componen una tendencia un I(2): que elimina los choques o rupturas extraeconómicos o casuales, que pueden interpretarse como variaciones tendenciales que realmente no existen de las que se deduzcan ciclos espurios.
• El ruido en los datos es aproximadamente Normal~(0,σ²) (ruido blanco).

El filtro de Kalman es un algoritmo desarrollado por Rudolf E. Kalmanen 1960 que sirve para poder identificar el estado oculto (no medible) de un sistema dinámico lineal, al igual que el observador de Luenberger, pero sirve además cuando el sistema está sometido a ruido blancoaditivo.¹​ La diferencia entre ambos es que en el observador de Luenberger, la ganancia K de realimentación del error debe ser elegida "a mano", mientras que el filtro de Kalman es capaz de escogerla de forma óptima cuando se conocen las varianzas de los ruidos que afectan al sistema. Ya que el Filtro de Kalman es un algoritmo recursivo, este puede correr en tiempo real usando únicamente las mediciones de entrada actuales, el estado calculado previamente y su matriz de incertidumbre, no requiere ninguna otra información adicional.

El filtro de Kalman tiene numerosas aplicaciones en tecnología. Una aplicación común es la guía, navegación y control de vehículos, especialmente naves espaciales. Además el filtro es ampliamente usado en campos como procesamiento de señales y econometría.

Sistema lineal en el espacio de estado[editar]

Se entiende como espacio de estado todos los posibles estados de un sistema dinámico. Cada estado corresponde a un punto del espacio de estado.

Caso de tiempo discreto:

Se tiene un sistema representado en el espacio de estado:

${\displaystyle \quad x_{k}=A_{k-1}x_{k-1}+B_{k-1}u_{k-1}+w_{k-1}}$

${\displaystyle \quad z_{k}=H_{k}x_{k}+v_{k}}$

donde:

${\displaystyle \quad w_{k}}$ es ruido blanco de valor promedio igual a cero y con varianza ${\displaystyle \quad Q_{k}}$ en el instante k.

${\displaystyle \quad v_{k}}$ es ruido blanco de valor promedio igual a cero y con varianza ${\displaystyle \quad R_{k}}$ en el instante k.

El filtro de Kalman permite estimar el estado ${\displaystyle \quad x_{k}}$ a partir de las mediciones anteriores de ${\displaystyle \quad u_{k-i}}$, ${\displaystyle \quad z_{k-i}}$, ${\displaystyle \quad Q_{k-i}}$, ${\displaystyle \quad R_{k-i}}$ y las estimaciones anteriores de ${\displaystyle \quad x_{k-i}}$.

Caso de tiempo continuo:

Se tiene un sistema representado en el espacio de estado:

${\displaystyle \quad {\frac {d}{dt}}x(t)=A(t)x(t)+B(t)u(t)+w(t)}$

${\displaystyle \quad z(t)=C(t)x(t)+v(t)}$

donde:

${\displaystyle \quad w(t)}$ es ruido blanco de valor promedio igual a cero y con varianza ${\displaystyle \quad Q(t)}$ en el intervalo de tiempo descrito como t.

${\displaystyle \quad v(t)}$ es ruido blanco de valor promedio igual a cero y con varianza ${\displaystyle \quad R(t)}$ en el intervalo de tiempo descrito como t.

El filtro de Kalman permite estimar el estado ${\displaystyle \quad x(t+dt)}$ a partir de las mediciones anteriores de ${\displaystyle \quad u(t)}$, ${\displaystyle \quad z(t)}$, ${\displaystyle \quad Q(t)}$, ${\displaystyle \quad R(t)}$ y las estimaciones anteriores de ${\displaystyle \quad x(t)}$.

Algoritmo del Filtro discreto de Kalman[editar]

El Filtro de Kalman es un algoritmo recursivo en el que el estado ${\displaystyle \quad x_{k}}$ es considerado una variable aleatoria Gaussiana. El filtro de Kalman suele describirse en dos pasos: Predicción y Corrección.

Predicción

Estimación a priori	${\displaystyle {\hat {\textbf {x}}}_{k|k-1}=\mathbf {\Phi } _{k}\ {\textbf {x}}_{k-1|k-1}}$
Covarianza del error asociada a la estimación a priori	${\displaystyle {\textbf {P}}_{k|k-1}=\mathbf {\Phi } _{k}{\textbf {P}}_{k-1|k-1}\mathbf {\Phi } _{k}^{\text{T}}+{\textbf {Q}}_{k}}$

Corrección

Actualización de la medición	${\displaystyle {\tilde {\textbf {y}}}_{k}={\textbf {z}}_{k}-{\textbf {H}}_{k}{\hat {\textbf {x}}}_{k|k-1}}$
Ganancia de Kalman	${\displaystyle {\textbf {K}}_{k}={\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{\text{T}}({\textbf {H}}_{k}{\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{\text{T}}+{\textbf {R}}_{k})^{-1}}$
Estimación a posteriori	${\displaystyle {\hat {\textbf {x}}}_{k|k}={\hat {\textbf {x}}}_{k|k-1}+{\textbf {K}}_{k}{\tilde {\textbf {y}}}_{k}}$
Covarianza del error asociada a la estimación a posteriori	${\displaystyle {\textbf {P}}_{k|k}=(I-{\textbf {K}}_{k}{\textbf {H}}_{k}){\textbf {P}}_{k|k-1}}$

donde:

${\displaystyle \mathbf {\Phi } _{k}:}$ Matriz de Transición de estados. Es la matriz que relaciona ${\displaystyle {\textbf {x}}_{k|k-1}}$ con ${\displaystyle {\textbf {x}}_{k-1|k-1}}$ en la ausencia de funciones forzantes (funciones que dependen únicamente del tiempo y ninguna otra variable).

${\displaystyle {\textbf {x}}_{k|k-1}:}$ El estimado apriori del vector de estados.

${\displaystyle {\textbf {P}}_{k|k-1}:}$ Covarianza del error asociada a la estimación a priori.

${\displaystyle {\textbf {z}}_{k}:}$ Vector de mediciones al momento k.

${\displaystyle {\textbf {H}}_{k}:}$ La matriz que indica la relación entre mediciones y el vector de estado al momento k en el supuesto ideal de que no hubiera ruido en las mediciones.

${\displaystyle {\textbf {R}}_{k}:}$ La matriz de covarianza del ruido de las mediciones (depende de la resolución de los sensores).

Extensibilidad[editar]

En el caso de que el sistema dinámico sea no lineal, es posible usar una modificación del algoritmo llamada "Filtro de Kalman Extendido", el cual linealiza el sistema en torno al ${\displaystyle {\hat {x}}(t)}$ identificado realmente, para calcular la ganancia y la dirección de corrección adecuada. En este caso, en vez de haber matrices A, B y C, hay dos funciones ${\displaystyle f(x,u,w)}$ y ${\displaystyle h(x,v)}$ que entregan la transición de estado y la observación (la salida contaminada) respectivamente. El modelo lineal dinámico con observación no lineal y no Gaussiano se estudia en este caso. Se extiende el teorema de Masreliez (ver. C. Johan Masreliez, 1975) como una aproximación de filtrado no Gaussiano con ecuación de estado lineal y ecuación de observaciones también lineal, al caso en que la ecuación de observaciones no lineal pueda aproximarse mediante el desarrollo en serie de Taylor de segundo orden. ²​

Primeras aplicaciones[editar]

Kalman encontró una audiencia receptiva de su filtro en el verano de 1960 en una visita de Stanley F. Schmidt del Ames Research Center de NASA en Mountain View (California). Kalman describió su resultado y Schmidt reconoció su potencial aplicativo - la estimación de la trayectoria y el problema del control del programa Apolo. Schmidt comenzó a trabajar inmediatamente en lo que fue probablemente la primera implementación completa del filtro de Kalman. Entusiasmado sobre el éxito del mismo, Schmidt impulsó usar el filtro en trabajos similares. A comienzos de 1961, Schmidt describió sus resultados a Richard H. Battin del laboratorio de instrumentación del MIT (llamado más tarde el Charles Stark Draper Laboratory). Battin estuvo usando métodos de espacio de estado para el diseño y la implementación de sistemas de navegación astronáutica, y él hizo al filtro de Kalman parte del sistema de guía del Apollo, el cual fue diseñado y desarrollado en el laboratorio de instrumentación. A mediados de la década de 1960, influenciado por Schmidt, el filtro de Kalman se hizo parte del sistema de navegación del transporte aéreo C5A, siendo diseñado por Lockheed Aircraft Company. El filtro de Kalman resolvió el problema de la fusión de datos asociado con la combinación de los datos del radar con los datos del sensor inercial al lograr una aproximación global de la trayectoria de la aeronave. Desde entonces ha sido parte integral de la estimación de trayectorias a bordo de las aeronaves y del diseño de sistemas de control.³​

Impacto del filtro de Kalman en la tecnología[editar]

Desde el punto de vista de los problemas que involucran control y estimación, el Filtro de Kalman ha sido considerado el gran logro en la teoría de estimación del siglo XX. Muchos de los logros desde su introducción no hubiesen sido posibles sin éste. Se puede decir que el filtro de Kalman fue una de las tecnologías que permitió la era espacial ya que la precisión y eficiencia en la navegación de las naves espaciales a través del sistema solar puede no haber sido hecha sin éste. El principal uso del filtro de Kalman ha sido en los sistemas de control modernos, en el seguimiento y navegación de todo tipo de vehículos, y en el diseño predictivo de estimación de los mismos.