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 _∞.

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 $f$ y un conjunto $X$ de $n+2$ puntos de muestra $x_1,x_2,...,x_{n+2}$ 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.

$b_0+b_1{x}_i+...+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (dónde $i=1,2,...n+2$ ),

para las incógnitas $b_0,b_1...b_n$ y E.

• Utilizar los $b_i$ como coeficientes para formar un polinomio $P_n$ .
• Encontrar el set $M$ de puntos de error local máximo $|P_n(x)-f(x)|$ .
• Si los errores en cada $m\in M$ son de igual magnitud y se alternan en signo, entonces $P_n$ es el polinomio de aproximación minimax. Si no, reemplace $X$ con $M$ 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.

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 L_n(f), se puede demostrar que esta aproximación inicial está limitada por

$\Vert f-L_n(f){\Vert }_{\mathrm{\infty }}\le (1+\Vert L_n{\Vert }_{\mathrm{\infty }})\underset{p\in P_n}{\inf }\Vert f-p\Vert$

con la norma o constante de Lebesgue del operador de interpolación de Lagrange L_n de los nodos (t₁, ..., t_n+1 ) sea:

$\Vert L_n{\Vert }_{\mathrm{\infty }}={\bar{\mathrm{\Lambda }}}_n(T)=\underset{-1\le x\le 1}{\max }{\lambda }_n(T;x),$

T son los ceros de los polinomios de Chebyshev, y las funciones de Lebesgue son

${\lambda }_n(T;x)=\sum _{j=1}^{n+1}|l_j(x)|,l_j(x)=\prod _{\stackrel{i=1}{i\ne j}}^{n+1}\frac{(x-t_i)}{(t_j-t_i)}.$

Theodore A. Kilgore, Carl de Boor y Allan Pinkus demostraron que existe un t_i único para cada L_n, aunque no se conoce explícitamente para polinomios (ordinarios). De manerasimilar, ${\underset{\_}{\mathrm{\Lambda }}}_n(T)=\underset{-1\le x\le 1}{\min }{\lambda }_n(T;x)$, y la optimalidad de una elección de nodos se puede expresar como ${\bar{\mathrm{\Lambda }}}_n-{\underset{\_}{\mathrm{\Lambda }}}_n\ge 0.$

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

${\bar{\mathrm{\Lambda }}}_n(T)=\frac{2}{\pi }\log (n+1)+\frac{2}{\pi }(\gamma +\log \frac{8}{\pi })+{\alpha }_{n+1}$

(Plantilla:Math es la constante de Euler-Mascheroni) con

$0<{\alpha }_n<\frac{\pi }{72n^2}$ para $n\ge 1,$

y límite superior

${\bar{\mathrm{\Lambda }}}_n(T)\le \frac{2}{\pi }\log (n+1)+1$

Lev Brutman obtuvo el límite para $n\ge 3$ y $\hat{T}$ siendo los ceros de los polinomios de Chebyshev expandidos:

${\bar{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\Lambda }}}_n(\hat{T})<{\bar{\mathrm{\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 obtuvo, de una estimación más precisa para $n\ge 40$

${\bar{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\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 se ejecuta de 0 a n +1.

Paso 1: dado $x_0,x_1,...x_{n+1}$, resolver el sistema lineal de n+2 ecuaciones

$b_0+b_1{x}_i+...+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (dónde $i=0,1,...n+1$),

por las incógnitas $b_0,b_1,...b_n$ y E.

Debe quedar claro que $(-1{)}^{i}E$ en esta ecuación solo tiene sentido si los nodos $x_0,...,x_{n+1}$ 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 $O(n^2)$ operaciones aritméticas mientras que un solucionador estándar tomaría $O(n^3)$ operaciones. Una prueba simple:

Calcule el interpolador estándar de n-ésimo grado $p_1(x)$ a $f(x)$ en los primeros n+1 nodos y también el grado interpolador estándar n-ésimo $p_2(x)$ a las ordenadas $(-1{)}^i$

$p_1(x_i)=f(x_i),p_2(x_i)=(-1{)}^i,i=0,...,n.$

Para este fin, use cada vez la fórmula de interpolación de Newton con las diferencias divididas de orden $0,...,n$ y $O(n^2)$ operaciones aritméticas.

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

La combinación lineal $p(x):=p_1(x)-p_2(x)\cdot E$ también es un polinomio de grado ny

$p(x_i)=p_1(x_i)-p_2(x_i)\cdot E=f(x_i)-(-1{)}^{i}E,i=0,\dots ,n.$

Esto es lo mismo que la ecuación anterior para $i=0,...,n$ y para cualquier elección de E. La misma ecuación para i = n +1 es

$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 :

$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 $p(x)\equiv b_0+b_{1}x+\dots +b_n{x}^n$ siempre están bien definidos

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

$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 un polinomio de grado n con un error menor que E. De hecho, si existiera tal polinomio, llámelo $\tilde{p}(x)$, entonces la diferencia $p(x)-\tilde{p}(x)=(p(x)-f(x))-(\tilde{p}(x)-f(x))$ seguiría siendo positivo/negativo en los n+2 nodos $x_i$ 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 $b_0+b_{1}x+...+b_n{x}^n$ a $p(x)$ .

El paso 3 mejora los nodos de entrada $x_0,...,x_{n+1}$ y sus errores $\pm E$ como sigue.

En cada región P, el nodo actual $x_i$ se reemplaza con el ${\overline{x}}_i$ maximizador local y en cada N-región $x_i$ se reemplaza con el minimizador local. (Se espera ${\overline{x}}_0$ en A, ${\overline{x}}_i$ cerca $x_i$ y ${\overline{x}}_{n+1}$ 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 )

Sea $z_i:=p({\overline{x}}_i)-f({\overline{x}}_i)$ . Cada amplitud $|z_i|$ es mayor o igual que E. El teorema de de La Vallée Poussin y su prueba también se aplican a $z_0,...,z_{n+1}$ con $\min \{|z_i|\}\ge E$ como el nuevo límite inferior para el mejor error posible con polinomios de grado n .

Además, $\max \{|z_i|\}$ es útil como un límite superior obvio para ese mejor error posible.

Paso 4: con $\min \{|z_i|\}$ y $\max \{|z_i|\}$ 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 $\max \{|z_i|\}-\min \{|z_i|\}$ 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.

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.

Véase también

• Teoría de la aproximación

Enlaces externos

• El Método Remez , Documentación de Boost
• Introducción a DSP