Algoritmo de Remez

En matemáticas, el algoritmo de Remez, llamado así por su inventor Eugène Yakovlevitch Remez, tiene como objetivo construir la mejor aproximación polinomial de una función continua sobre un intervalo acotado, dado el grado máximo del polinomio .

Este algoritmo es el cálculo práctico vinculado al teorema de equi-oscilación de Tchebychev (cf. Teoría de aproximación ). Ver también polinomios de Chebyshev .

Algoritmo

El objetivo es encontrar el polinomio de grado $n$ que mejor se aproxime a una función continua $f$ dada en un intervalo, en el sentido de que el máximo de la diferencia entre el polinomio y la función debe ser mínimo: $P_n (x)$ $[a, b]$

{\ Displaystyle P_ {n} = {\ textrm {arg}} \ min \ left (\ sup _ {a \ leq x \ leq b} | P_ {n} (x) -f (x) | \ right)}

Esto implica que la diferencia entre el polinomio y la función llegará a extremos, de la misma amplitud y que se alternarán. $n + 2$

Tenga en cuenta el polinomio buscado.

{\ Displaystyle P_ {n} (x) = a_ {0} + a_ {1} \ cdot x + a_ {2} \ cdot x ^ {2} + a_ {3} \ cdot x ^ {3} + .. . + a_ {n} \ cdot x ^ {n}}

Por tanto, existen incógnitas que son: $n + 1$

{\ Displaystyle a_ {0}; a_ {1}; a_ {2}; a_ {3}; ...; a_ {n}}

Primera etapa :

Un posible comienzo es elegir los ceros del polinomio de grado de Chebyshev y determinar el polinomio que coincide con la función en estos puntos. Es necesario hacer una homotecia de los ceros para tener en cuenta los límites del intervalo. Los valores a tener en cuenta son: $n + 1$ $P_n (x)$

{\ Displaystyle z_ {k} = {\ frac {a + b} {2}} + {\ frac {ba} {2}} \ cdot \ cos \ left ({\ frac {(2k-1) \ pi} {2n + 2}} \ right)}

, para

{\ Displaystyle k \ in \ {1, \ ldots, n + 1 \}.}

Por tanto, es necesario resolver:

{\ Displaystyle P_ {n} (z_ {k}) = f (z_ {k})}

para

{\ Displaystyle k \ in \ {1, \ ldots, n + 1 \}.}

Explícitamente, si buscamos los coeficientes del polinomio, esto da: $P_n (x)$

{\ Displaystyle \ forall k \ in [\! [1; n + 1] \!], \, a_ {0} + a_ {1} \ cdot z_ {k} + a_ {2} \ cdot z_ {k} ^ {2} + a_ {3} \ cdot z_ {k} ^ {3} + ... + a_ {n} \ cdot z_ {k} ^ {n} = f (z_ {k})}

En forma de matriz, esto da:

{\ Displaystyle {\ begin {pmatrix} 1 & z_ {1} & z_ {1} ^ {2} & ... & z_ {1} ^ {n} \\ 1 & z_ {2} & z_ {2} ^ {2} & ... & Z_ {2} ^ {n} \\ ... & ... & ... & ... & ... \\ 1 & z_ {n + 1} & z_ {n + 1} ^ {2} &. .. & z_ {n + 1} ^ {n} \\\ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ ... \\ a_ {n} \ end {pmatrix}} = {\ begin {pmatrix} f (z_ {1}) \\ f (z_ {2}) \\ ... \\ f (z_ {n + 1}) \\\ end {pmatrix}}}

Primer paso, mejor comienzo:

Un mejor comienzo es elegir los extremos del polinomio de grado de Chebyshev, incluidos los límites. $n + 1$

{\ Displaystyle x_ {k} = {\ frac {a + b} {2}} + {\ frac {ba} {2}} \ cdot \ cos \ left ({\ frac {(k-1) \ pi} {n + 1}} \ right), \, \ forall k \ in \ {1, \ ldots, n + 2 \}.}

Segundo paso :

Una vez que se haya encontrado un primer polinomio que se aproxime a la función, busque los n +2 extremos de la diferencia entre el polinomio y la función. En general, los dos terminales y son parte de estos extremos. Esto debería dar puntos . $a$ $B$ $n + 2$ ${\ Displaystyle x_ {1}, x_ {2}, ..., x_ {n + 2}}$

Generalmente es el primer extremo, luego los otros extremos alternan entre "mínimos" y "máximos", hasta . ${\ Displaystyle x_ {1} = a}$ ${\ Displaystyle x_ {n + 2} = b}$

Tercer paso :

Determine el polinomio de grado que satisface: $P_n (x)$ $no$

{\ Displaystyle P_ {n} (x_ {k}) + (- 1) ^ {k} \ cdot e = f (x_ {k}), \, \ forall k \ in \ {1, \ ldots, n + 2 \}.}

donde $e$ es la n + 2 ^nd desconocido.

Si la aproximación encontrada no es lo suficientemente buena, regrese al paso 2. En general, una iteración es suficiente, la convergencia es muy rápida.

En forma de matriz, la ecuación a resolver es:

${\ displaystyle {\ begin {pmatrix} 1 & x_ {1} & x_ {1} ^ {2} & ... & x_ {1} ^ {n} & - 1 \\ 1 & x_ {2} & x_ {2} ^ {2} & ... & x_ {2} ^ {n} & (- 1) ^ {2} \\ ... & ... & ... & ... & ... \\ 1 & x_ {n + 1} & x_ {n + 1} ^ {2} & ... & x_ {n + 1} ^ {n} & (- 1) ^ {n + 1} \\ 1 & x_ {n + 2} & x_ {n + 2} ^ {2} & ... & x_ {n + 2} ^ {n} & (- 1) ^ {n + 2} \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ ... \\ a_ {n} \\ e \ end {pmatrix}} = {\ begin {pmatrix} f (x_ {1}) \\ f (x_ {2}) \\ ... \\ f (x_ {n + 1}) \\ f (x_ {n + 2}) \ end {pmatrix}}}$

El valor absoluto da una buena estimación de la diferencia máxima entre el polinomio y la función en el intervalo dado. $| e |$ $[a, b]$

Nota

Una ligera mejora final sería escribir el polinomio en la forma:

{\ Displaystyle P_ {n} (x) = c_ {0} + c_ {1} \ cdot T_ {1} (x) + c_ {2} \ cdot T_ {2} (x) + c_ {3} \ cdot T_ {3} (x) + ... + c_ {n} \ cdot T_ {n} (x)}

donde es el n- ésimo polinomio de Chebyshev . ${\ Displaystyle T_ {n} (x)}$

Luego evaluamos eficientemente este polinomio por $X$

{\ Displaystyle d_ {n + 1} = 0; \ quad d_ {n} = c_ {n};}

{\ Displaystyle d_ {j} = 2 \ cdot x \ cdot d_ {j + 1} -d_ {j + 2} + c_ {j}}

para ${\ Displaystyle j = n-1, n-2, n-3, ..., 3,2,1}$

{\ Displaystyle P_ {n} (x) = x \ cdot d_ {1} -d_ {2} + c_ {0}}

Los coeficientes generalmente disminuirán rápidamente. ${\ Displaystyle c_ {k}}$

Artículo relacionado

Polinomio de Chebyshev

Bibliografía

J.-M. Muller, Funciones elementales: algoritmos e implementación . ed. Birkhäuser (1997, reed.2005 ), ( ISBN 0-8176-4372-9 ), pág. 41–47
Recetas numéricas, El arte de la informática científica, segunda o tercera edición, William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, eds. Cambridge University Press, 1992 o 2007. Capítulo 5, "Aproximación de Chebyshev" a "Aproximación de Chebyshev racional".

enlaces externos

(en) Eric W. Weisstein, " Remez Algorithm ", en MathWorld
Aproximación polinomial de funciones en el lenguaje SciLab, con implementación del algoritmo Remez. Vea la Serie 4 y la clave de respuestas que sigue.

Diseño Electrónico

lunes, 28 de noviembre de 2022