algoritmo remez

Algoritmo para aproximar funciones

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 de Chebyshev que sean las mejores en el sentido de la norma uniforme L _∞ . ^[1] A veces se lo denomina algoritmo Remes o algoritmo Reme . ^{[ cita necesaria ]}

Un ejemplo típico de un espacio de Chebyshev es el subespacio de polinomios de Chebyshev de orden n en el espacio de funciones reales continuas en un intervalo , C [ a , b ]. El polinomio de mejor aproximación dentro de un subespacio dado se define como aquel que minimiza la máxima diferencia absoluta entre el polinomio y la función. En este caso, la forma de la solución viene precisada por el teorema de equioscilación .

Procedimiento

El algoritmo de Remez comienza con la función que se va a aproximar y un conjunto de puntos de muestra en el intervalo de aproximación, generalmente los extremos del polinomio de Chebyshev asignados linealmente al intervalo. Los pasos son: ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle n+2}$ ${\displaystyle x_{1},x_{2},...,x_{n+2}}$

• Resolver el sistema lineal de ecuaciones.

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$(dónde ), ${\displaystyle i=1,2,...n+2}$

para las incógnitas y E . ${\displaystyle b_{0},b_{1}...b_{n}}$

• Usa los coeficientes as para formar un polinomio . ${\displaystyle b_{i}}$ ${\displaystyle P_{n}}$
• Encuentre el conjunto de puntos de error máximo local . ${\displaystyle M}$ ${\displaystyle |P_{n}(x)-f(x)|}$
• Si los errores en cada son de igual magnitud y de signo alternativo, entonces es el polinomio de aproximación minimax. De lo contrario, reemplácelo y repita los pasos anteriores. ${\displaystyle m\in M}$ ${\displaystyle P_{n}}$ ${\displaystyle X}$ ${\displaystyle M}$

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]

Elección de inicialización

Los nodos de Chebyshev son una elecció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á acotada por

${\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert }$

siendo la norma o constante de Lebesgue del operador de interpolación de Lagrange L _n de los nodos ( t ₁ , ..., t _{n  + 1} )

${\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}$

siendo T los ceros de los polinomios de Chebyshev y siendo las funciones de Lebesgue

${\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.}$

Theodore A. Kilgore, ^[3] Carl de Boor y Allan Pinkus ^[4] demostraron que existe un ti _único para cada L _n , aunque no se conoce explícitamente para polinomios (ordinarios). De manera similar, y la optimización de una elección de nodos se puede expresar como ${\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$ ${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$

Para los nodos de Chebyshev, que proporcionan una elección subóptima, pero analíticamente explícita, el comportamiento asintótico se conoce como ^[5]

${\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}$

( siendo γ la constante de Euler-Mascheroni ) con

${\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}$para ${\displaystyle n\geq 1,}$

y límite superior ^[6]

${\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}$

Lev Brutman ^[7] obtuvo la cota para , y siendo los ceros de los polinomios expandidos de Chebyshev: ${\displaystyle n\geq 3}$ ${\displaystyle {\hat {T}}}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.}$

Rüdiger Günttner ^[8] obtuvo a partir de una estimación más precisa para ${\displaystyle n\geq 40}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}$

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 ${\displaystyle x_{0},x_{1},...x_{n+1}}$

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$(dónde ), ${\displaystyle i=0,1,...n+1}$

para las incógnitas y E . ${\displaystyle b_{0},b_{1},...b_{n}}$

Debe quedar claro que en esta ecuación sólo tiene sentido si los nodos están ordenados , ya sea 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 de la biblioteca tomaría operaciones. Aquí está la prueba simple: ${\displaystyle (-1)^{i}E}$ ${\displaystyle x_{0},...,x_{n+1}}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$

Calcule el interpolante estándar de n -ésimo grado en los primeros n +1 nodos y también el interpolante estándar de n -ésimo grado en las ordenadas ${\displaystyle p_{1}(x)}$ ${\displaystyle f(x)}$ ${\displaystyle p_{2}(x)}$ ${\displaystyle (-1)^{i}}$

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}$

Para ello se utiliza cada vez la fórmula de interpolación de Newton con las diferencias de orden divididas y operaciones aritméticas. ${\displaystyle 0,...,n}$ ${\displaystyle O(n^{2})}$

El polinomio tiene su i -ésimo cero entre y , y por lo tanto no hay más ceros entre y : y tienen el mismo signo . ${\displaystyle p_{2}(x)}$ ${\displaystyle x_{i-1}}$ ${\displaystyle x_{i},\ i=1,...,n}$ ${\displaystyle x_{n}}$ ${\displaystyle x_{n+1}}$ ${\displaystyle p_{2}(x_{n})}$ ${\displaystyle p_{2}(x_{n+1})}$ ${\displaystyle (-1)^{n}}$

La combinación lineal también es un polinomio de grado n y ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

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 ${\displaystyle i=0,...,n}$

${\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}$y necesita un razonamiento especial: resuelto para la variable E , es la definición de E :

${\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}$

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. ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$

El error en los n +2 nodos ordenados dados es positivo y negativo a su vez porque

${\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}$

El teorema de de La Vallée Poussin establece que bajo esta condición no existe ningún polinomio de grado n con error menor que E. De hecho, si tal polinomio existiera, llámelo , entonces la diferencia seguiría siendo positiva/negativa en los n +2 nodos y, por lo tanto, tendría al menos n +1 ceros, lo cual es imposible para un polinomio de grado n . Por tanto, este E es un límite inferior para el error mínimo que se puede lograr con polinomios de grado n . ${\displaystyle {\tilde {p}}(x)}$ ${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$ ${\displaystyle x_{i}}$

El paso 2 cambia la notación de a . ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$ ${\displaystyle p(x)}$

El paso 3 mejora los nodos de entrada y sus errores de la siguiente manera. ${\displaystyle x_{0},...,x_{n+1}}$ ${\displaystyle \pm E}$

En cada región P, el nodo actual se reemplaza con el maximizador local y en cada región N se reemplaza con el minimizador local. (Espere en A , el cercano y en B .) Aquí no se requiere alta precisión, la búsqueda de línea estándar con un par de ajustes cuadráticos debería ser suficiente. (Ver ^[9] ) ${\displaystyle x_{i}}$ ${\displaystyle {\bar {x}}_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle {\bar {x}}_{0}}$ ${\displaystyle {\bar {x}}_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle {\bar {x}}_{n+1}}$

Dejar . Cada amplitud es mayor o igual a E. El teorema de La Vallée Poussin y su demostración también se aplican como nuevo límite inferior para el mejor error posible con polinomios de grado n . ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$ ${\displaystyle |z_{i}|}$ ${\displaystyle z_{0},...,z_{n+1}}$ ${\displaystyle \min\{|z_{i}|\}\geq E}$

Además, resulta útil como límite superior obvio para lograr el mejor error posible. ${\displaystyle \max\{|z_{i}|\}}$

Paso 4: Con y como límite inferior y superior para el mejor error de aproximación posible, se tiene un criterio de parada fiable: repetir los pasos hasta que sea lo suficientemente pequeño o ya no disminuya. Estos límites indican el progreso. ${\displaystyle \min \,\{|z_{i}|\}}$ ${\displaystyle \max \,\{|z_{i}|\}}$ ${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$

Variantes

Algunas modificaciones del algoritmo están presentes en la literatura. ^[10] Estos incluyen:

• Reemplazar más de un punto de muestra con las ubicaciones de diferencias absolutas máximas cercanas. ^{[ cita necesaria ]}
• Reemplazar todos los puntos de muestra en una sola iteración con las ubicaciones de todos, signo alterno, diferencias máximas. ^[11]
• Usar el error relativo 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 ;
• Incluyendo restricciones de puntos de error cero. ^[11]
• La variante Fraser-Hart, utilizada para determinar la mejor aproximación racional de Chebyshev. ^[12]

Ver también

• Teoría de la aproximación

Referencias

1. E.Ya. Remez, "Sur la determinación de polinômes d'approximation de degré donnée", Comm. Soc. Matemáticas. Jarkov 10 , 41 (1934);
   "Sur un procédé convergent d'approximations sucesivas para determinar los polinômes d'approximation, Compt. Rend. Acad. Sc. 198 , 2063 (1934);
   "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Academia Sc. 199 , 337 (1934).
2. Fraser, W. (1965). "Un estudio de métodos de cálculo de aproximaciones polinómicas minimax y casi minimax para funciones de una única variable independiente". J. ACM . 12 (3): 295–314. doi : 10.1145/321281.321282 . S2CID  2736060.
3. Kilgore, TA (1978). "Una caracterización de la proyección interpoladora de Lagrange con norma mínima de Tchebycheff". J. Aprox. Teoría . 24 (4): 273–288. doi :10.1016/0021-9045(78)90013-8.
4. 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 (4): 289–303. doi : 10.1016/0021-9045(78)90014-X .
5. Luttmann, FW; Rivlin, TJ (1965). "Algunos experimentos numéricos en la teoría de la interpolación polinómica". IBM J. Res. Desarrollo . 9 (3): 187-191. doi :10.1147/rd.93.0187.
6. T. Rivlin, "Las constantes de Lebesgue para la interpolación polinomial", en Actas del 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).
7. Brutman, L. (1978). "Sobre la función de Lebesgue para la interpolación polinómica". SIAM J. Número. Anal . 15 (4): 694–704. Código bibliográfico : 1978SJNA...15..694B. doi :10.1137/0715046.
8. Günttner, R. (1980). "Evaluación de las constantes de Lebesgue". SIAM J. Número. Anal . 17 (4): 512–520. Código Bib : 1980SJNA...17..512G. doi :10.1137/0717043.
9. David G. Luenberger: Introducción a la programación lineal y no lineal , Addison-Wesley Publishing Company 1973.
10. Egidi, Nadaniela; Fatone, Lorella; Misici, Luciano (2020), Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.), "Un nuevo algoritmo tipo Remez para la mejor aproximación polinómica", Computaciones numéricas: teoría y algoritmos , vol. 11973, Cham: Springer International Publishing, págs. 56–69, doi :10.1007/978-3-030-39081-5_7, ISBN 978-3-030-39080-8, S2CID  211159177 , consultado el 19 de marzo de 2022
11. Temes, GC; Barcilón, V.; Marshall, FC (1973). "La optimización de sistemas de banda limitada". Actas del IEEE . 61 (2): 196–234. doi :10.1109/PROC.1973.9004. ISSN  0018-9219.
12. Dunham, Charles B. (1975). "Convergencia del algoritmo Fraser-Hart para la aproximación racional de Chebyshev". Matemáticas de la Computación . 29 (132): 1078-1082. doi : 10.1090/S0025-5718-1975-0388732-9 . ISSN  0025-5718.

enlaces externos

• Aproximaciones Minimax y el algoritmo Remez, capítulo de antecedentes en la documentación de Boost Math Tools, con enlace a una implementación en C++
• Introducción a DSP
• Aarts, Ronald M .; Vínculo, Carlos; Mendelsohn, Phil y Weisstein, Eric W. "Algoritmo Remez". MundoMatemático .