El algoritmo de Remez o algoritmo de intercambio de Remez , publicado por Evgeny Yakovlevich Remez en 1934, es un algoritmo iterativo que se utiliza para encontrar aproximaciones simples a funciones, específicamente, aproximaciones por funciones en un espacio de Chebyshev que son las mejores en el sentido de la norma uniforme L ∞ . [1]
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 máxima diferencia absoluta 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 para ser aproximado y un conjunto de puntos de muestra en el intervalo de aproximación, generalmente los extremos del polinomio de Chebyshev mapeados linealmente en el intervalo. Los pasos son:
- Resuelve el sistema lineal de ecuaciones.
- (dónde ),
- por las incógnitas y E .
- Utilizar el como coeficientes para formar un polinomio .
- Encuentra el set de puntos de error máximo local .
- Si los errores en cada son de igual magnitud y de signo alterno, entonces es el polinomio de aproximación minimax. Si no, reemplácelo 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 aspectos técnicos de 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 mediante el interpolante de Lagrange L n ( f ), se puede demostrar que esta aproximación inicial está limitada por
siendo la norma o constante de Lebesgue del operador de interpolación de Lagrange L n de los nodos ( t 1 , ..., t n + 1 )
Siendo T 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 una t i única para cada L n , aunque no se conoce explícitamente para polinomios (ordinarios). Similar,, y la optimalidad de una elección de nodos se puede expresar como
Para los nodos de Chebyshev, que proporciona una elección subóptima, pero analíticamente explícita, el comportamiento asintótico se conoce como [5]
( γ es la constante de Euler-Mascheroni ) con
- por
y límite superior [6]
Lev Brutman [7] obtuvo el destino de, y siendo los ceros de los polinomios expandidos de Chebyshev:
Rüdiger Günttner [8] obtenido a partir de una estimación más precisa de
Discusión detallada
Esta sección proporciona más información sobre los pasos descritos anteriormente. En esta sección, el índice i va de 0 a n +1.
Paso 1: dado, resuelve el sistema lineal de n +2 ecuaciones
- (dónde ),
- por las incógnitas y E .
Debe quedar claro que en esta ecuación tiene sentido solo si los nodos están ordenados , estrictamente crecientes o estrictamente decrecientes. 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 de la biblioteca tomaría operaciones. Aquí está la prueba simple:
Calcule el interpolante estándar de n -ésimo grado a en los primeros n +1 nodos y también en el interpolante estándar de n -ésimo grado a las ordenadas
Para ello, utilice cada vez la fórmula de interpolación de Newton con las diferencias de orden divididas y operaciones aritmeticas.
El polinomio tiene su i -ésimo cero entre y , y por lo tanto no hay más ceros entre y : y tener el mismo signo .
La combinación lineal también es un polinomio de grado n y
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 están siempre bien definidos.
El error en los n +2 nodos ordenados dados es positivo y negativo a su vez porque
El teorema de De La Vallee Poussin establece que bajo esta condición sin polinomio de grado n existe con error menor que E . De hecho, si existiera tal polinomio, llámelo, entonces la diferencia seguiría siendo positivo / negativo en los n +2 nodosy por lo tanto tener al menos n +1 ceros lo cual es imposible para un polinomio de grado n . Por lo tanto, este 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. (Suponeren A , el cerca , y en B. ) No se requiere una 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] )
Dejar . Cada amplitudes mayor que o igual a E . El Teorema de La Vallée Poussin y su demostración también se aplican a con como el nuevo límite inferior para el mejor error posible con polinomios de grado n .
Es más, resulta útil como límite superior obvio para el 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 parada confiable: repita los pasos hasta es suficientemente pequeño o ya no disminuye. Estos límites indican el progreso.
Variantes
A veces, más de un punto de muestra se reemplaza 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, signo alterno, diferencias máximas. [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 punto flotante.
A veces, las restricciones de punto de error cero se incluyen en un algoritmo de intercambio de Remez modificado. [10]
Ver también
Referencias
- ^ E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Matemáticas. Jarkov 10 , 41 (1934);
"Sur un procédé convergent d'approximations sucesives 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). "Un estudio de métodos de cálculo de aproximaciones polinomiales Minimax y Near-Minimax para funciones de una sola variable independiente". J. ACM . 12 : 295. doi : 10.1145 / 321281.321282 .
- ^ Kilgore, TA (1978). "Una caracterización de la proyección de interpolación de Lagrange con norma mínima de Tchebycheff" . J. Aprox. Teoría . 24 : 273. doi : 10.1016 / 0021-9045 (78) 90013-8 .
- ^ de Boor, C .; Pinkus, A. (1978). "Prueba de las conjeturas de Bernstein y Erdös sobre los nodos óptimos para la interpolación polinomial" . Revista de teoría de la aproximación . 24 : 289. doi : 10.1016 / 0021-9045 (78) 90014-X .
- ^ Luttmann, FW; Rivlin, TJ (1965). "Algunos experimentos numéricos en la teoría de la interpolación polinomial". IBM J. Res. Dev . 9 : 187. doi : 10.1147 / rd.93.0187 .
- ^ T. Rivlin, "Las constantes de Lebesgue para la interpolación polinomial", en Proceedings of the Int. Conf. sobre análisis funcional y su aplicación , editado por HG Garnier et al. (Springer-Verlag, Berlín, 1974), pág. 422; Los polinomios de Chebyshev (Wiley-Interscience, Nueva York, 1974).
- ^ Brutman, L. (1978). "Sobre la función de Lebesgue para la interpolación polinómica". SIAM J. Numer. Anal . 15 : 694. doi : 10.1137 / 0715046 .
- ^ Günttner, R. (1980). "Evaluación de las constantes de Lebesgue". SIAM J. Numer. Anal . 17 : 512. doi : 10.1137 / 0717043 .
- ^ David G. Luenberger: Introducción a la programación lineal y no lineal , Addison-Wesley Publishing Company 1973.
- ^ a b 2/73 "La optimización de sistemas de banda limitada" - GC Temes, FC Marshall y V. Barcilon. Actas IEEE.
enlaces externos
- El método Remez , Boost Documentation
- Introducción a DSP
- Aarts, Ronald M .; Bond, Charles; Mendelsohn, Phil y Weisstein, Eric W. "Algoritmo Remez" . MathWorld .