Algoritmo Remez
El algoritmo de Remez o algoritmo de intercambio de Remez, publicado por Evgeny Yakovlevich Remez en 1934, es un algoritmo iterativo utilizado para encontrar aproximaciones simples a funciones, específicamente, aproximaciones por funciones en un espacio Chebyshev que son las mejores en el sentido uniforme de la norma L ∞.[1]
Algoritmo Remez Algoritmo de intercambio de Remez | ||
---|---|---|
Tipo | Algoritmo iterativo | |
Problema que resuelve | Encontrar aproximaciones simples a ciertas funciones. | |
Creador | Evgeny Yakovlevich Remez | |
Fecha | 1934 | |
Un ejemplo típico de un espacio de Chebyshev es el subespacio de polinomios de Chebyshev de orden n en el espacio de funciones continuas reales en un intervalo, C[a,b ]. El polinomio de mejor aproximación dentro de un subespacio dado se define como el que minimiza la diferencia absoluta máxima entre el polinomio y la función. En este caso, la forma de la solución se precisa mediante el teorema de equioscilación .
Procedimiento
El algoritmo de Remez comienza con la función a ser aproximada y un conjunto de puntos de muestra en el intervalo de aproximación, generalmente los extremos del polinomio de Chebyshev se asignan linealmente al intervalo. Los pasos son:
- Resolver el sistema lineal de ecuaciones.
- (dónde ),
- para las incógnitas y E.
- Utilizar los como coeficientes para formar un polinomio .
- Encontrar el set de puntos de error local máximo .
- Si los errores en cada son de igual magnitud y se alternan en signo, entonces es el polinomio de aproximación minimax. Si no, reemplace con y repita los pasos anteriores.
El resultado se denomina polinomio de mejor aproximación o algoritmo de aproximación minimax .
W. Fraser ofrece una revisión de los tecnicismos en la implementación del algoritmo Remez.[2]
Sobre la elección de la inicialización
Los nodos de Chebyshev son una opción común para la aproximación inicial debido a su papel en la teoría de la interpolación polinómica. Para la inicialización del problema de optimización para la función f por el interpolante de Lagrange Ln(f), se puede demostrar que esta aproximación inicial está limitada por
con la norma o constante de Lebesgue del operador de interpolación de Lagrange Ln de los nodos (t1, ..., tn+1 ) sea:
T son los ceros de los polinomios de Chebyshev, y las funciones de Lebesgue son
Theodore A. Kilgore,[3] Carl de Boor y Allan Pinkus [4] demostraron que existe un ti único para cada Ln, aunque no se conoce explícitamente para polinomios (ordinarios). De manerasimilar, , y la optimalidad de una elección de nodos se puede expresar como
Para los nodos de Chebyshev que proporcionan una opción subóptima, pero analíticamente explícita, el comportamiento asintótico se conoce como [5]
(γ es la constante de Euler-Mascheroni) con
- para
y límite superior [6]
Lev Brutman [7] obtuvo el límite para y siendo los ceros de los polinomios de Chebyshev expandidos:
Rüdiger Günttner [8] obtuvo, de una estimación más precisa para
Discusión detallada
Esta sección proporciona más información sobre los pasos descritos anteriormente. En esta sección, el índice i se ejecuta de 0 a n +1.
Paso 1: dado , resolver el sistema lineal de n+2 ecuaciones
- (dónde ),
- por las incógnitas y E.
Debe quedar claro que en esta ecuación solo tiene sentido si los nodos se ordenan, ya sea de manera estrictamente creciente o estrictamente decreciente. Entonces este sistema lineal tiene una solución única (como es bien sabido, no todos los sistemas lineales tienen una solución). Además, la solución se puede obtener solo con operaciones aritméticas mientras que un solucionador estándar tomaría operaciones. Una prueba simple:
Calcule el interpolador estándar de n-ésimo grado a en los primeros n+1 nodos y también el grado interpolador estándar n-ésimo a las ordenadas
Para este fin, use cada vez la fórmula de interpolación de Newton con las diferencias divididas de orden y operaciones aritméticas.
El polinomio tiene su i-ésimo cero entre y y, por lo tanto, no hay más ceros entre y : y teniendo el mismo signo .
La combinación lineal también es un polinomio de grado ny
Esto es lo mismo que la ecuación anterior para y para cualquier elección de E. La misma ecuación para i = n +1 es
- y necesita un razonamiento especial: resuelto para la variable E, es la definición de E :
Como se mencionó anteriormente, los dos términos en el denominador tienen el mismo signo: E y por lo tanto siempre están bien definidos
El error en los nodos ordenados n +2 dados es positivo y negativo a su vez porque
El teorema de De La Vallée Poussin establece que bajo esta condición no existe un polinomio de grado n con un error menor que E. De hecho, si existiera tal polinomio, llámelo , entonces la diferencia seguiría siendo positivo/negativo en los n+2 nodos y por lo tanto tienen al menos n+ ceros lo que es imposible para un polinomio de grado n . Por lo tanto, esta E es un límite inferior para el error mínimo que se puede lograr con polinomios de grado n .
El paso 2 cambia la notación de a .
El paso 3 mejora los nodos de entrada y sus errores como sigue.
En cada región P, el nodo actual se reemplaza con el maximizador local y en cada N-región se reemplaza con el minimizador local. (Se espera en A, cerca y en B). No se requiere alta precisión aquí, la búsqueda de línea estándar con un par de ajustes cuadráticos debería ser suficiente. (Ver [9] )
Sea . Cada amplitud es mayor o igual que E. El teorema de de La Vallée Poussin y su prueba también se aplican a con como el nuevo límite inferior para el mejor error posible con polinomios de grado n .
Además, es útil como un límite superior obvio para ese mejor error posible.
Paso 4: con y como límite inferior y superior para el mejor error de aproximación posible, uno tiene un criterio de detención confiable: repite los pasos hasta que es suficientemente pequeño o ya no disminuye. Estos límites indican el progreso.
Variantes
A veces se reemplaza más de un punto de muestra es reemplazado al mismo tiempo con las ubicaciones de las diferencias absolutas máximas cercanas.
A veces todos los puntos de muestra se reemplazan en una sola iteración con las ubicaciones de todos las diferencias máximas, alternando los signos.[10]
A veces, el error relativo se usa para medir la diferencia entre la aproximación y la función, especialmente si la aproximación se usará para calcular la función en una computadora que usa aritmética de coma flotante.
A veces, las restricciones de punto de error cero se incluyen en un Algoritmo de intercambio Remez modificado.[10]
Véase también
Referencias
- E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
"Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
"Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934). - Fraser, W. (1965). «A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable». J. ACM 12: 295. doi:10.1145/321281.321282.
- Kilgore, T. A. (1978). «A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm». J. Approx. Theory 24: 273. doi:10.1016/0021-9045(78)90013-8.
- de Boor, C.; Pinkus, A. (1978). «Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation». Journal of Approximation Theory 24: 289. doi:10.1016/0021-9045(78)90014-X.
- Luttmann, F. W.; Rivlin, T. J. (1965). «Some numerical experiments in the theory of polynomial interpolation». IBM J. Res. Dev. 9: 187. doi:10.1147/rd.93.0187.
- T. Rivlin, "The Lebesgue constants for polynomial interpolation", in Proceedings of the Int. Conf. on Functional Analysis and Its Application, edited by H. G. Garnier et al. (Springer-Verlag, Berlin, 1974), p. 422; The Chebyshev polynomials (Wiley-Interscience, New York, 1974).
- Brutman, L. (1978). «On the Lebesgue Function for Polynomial Interpolation». SIAM J. Numer. Anal. 15: 694. doi:10.1137/0715046.
- Günttner, R. (1980). «Evaluation of Lebesgue Constants». SIAM J. Numer. Anal. 17: 512. doi:10.1137/0717043.
- David G. Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company 1973.
- 2/73 "The Optimization of Bandlimited Systems" – G. C. Temes, F. C. Marshall and V. Barcilon. Proceedings IEEE.
Enlaces externos
- El Método Remez , Documentación de Boost
- Introducción a DSP