Teoría de la aproximación

En matemáticas, la teoría de la aproximación se ocupa de cómo se pueden aproximar mejor las funciones con funciones más simples y de caracterizar cuantitativamente los errores introducidos por ellas. Lo que se entiende por mejor y más simple dependerá de la aplicación.

Un tema estrechamente relacionado es la aproximación de funciones mediante series de Fourier generalizadas, es decir, aproximaciones basadas en la suma de una serie de términos basados en polinomios ortogonales.

Un problema de particular interés es el de aproximar una función en una biblioteca matemática de computadora, usando operaciones que se pueden realizar en la computadora o calculadora (por ejemplo, suma y multiplicación), de modo que el resultado sea lo más cercano posible a la función real. posible. Esto generalmente se hace con aproximaciones polinomiales o racionales (proporción de polinomios).

El objetivo es hacer que la aproximación sea lo más cercana posible a la función real, generalmente con una precisión cercana a la de la aritmética de coma flotante subyacente de la computadora. Esto se logra usando un polinomio de alto grado y/o reduciendo el dominio sobre el cual el polinomio tiene que aproximarse a la función. A menudo se puede reducir el dominio mediante el uso de varias fórmulas de suma o escala para la función que se aproxima. Las bibliotecas matemáticas modernas a menudo reducen el dominio en muchos segmentos pequeños y utilizan un polinomio de bajo grado para cada segmento.

Polinomios óptimos

Una vez que el dominio (típicamente un intervalo) y el grado del polinomio son elegidos, el polinomio mismo es elegido de tal manera que minimiza el error del peor de los casos. Es decir, el objetivo es minimizar el valor máximo de ${displaystyle mid P(x)-f(x)mid }$, donde P()x) es el polinomio aproximado, f()x) es la función real, y x varía según el intervalo elegido. Para las funciones bien interpretadas, existe un NT- polinomio de grado que conducirá a una curva de error que oscila entre ${displaystyle +varepsilon }$ y ${displaystyle -varepsilon$ un total de N+2 veces, dando un peor error de caso ${displaystyle varepsilon }$. Se ve que existe NT- polinomio de grado que puede interpolar N+1 puntos en una curva. Que tal polinomio es siempre óptimo es afirmado por el teorema de equioscillación. Es posible realizar funciones contrincadas f()x) para el cual no existe tal polinomio, pero estos ocurren raramente en la práctica.

Por ejemplo, los gráficos mostrados a la derecha muestran el error en el registro aproximado(x) y exp(x) para N= 4. Las curvas rojas, para el polinomio óptimo, son nivel, es decir, oscilan entre ${displaystyle +varepsilon }$ y ${displaystyle -varepsilon$ exactamente. En cada caso, el número de extrema es N+2, es decir, 6. Dos de los extremos están en los puntos finales del intervalo, en los bordes izquierdo y derecho de los gráficos.

Para demostrar que esto es cierto en general, supongamos que P es un polinomio de grado N que tiene la propiedad descrita, es decir, da lugar a una función de error que tiene N + 2 extremos, de signos alternos y magnitudes iguales. El gráfico rojo a la derecha muestra cómo se vería esta función de error para N = 4. Supongamos que Q(x) (cuya función de error es (que se muestra en azul a la derecha) es otro polinomio de N grado que es una mejor aproximación a f que P. En particular, Q está más cerca de f que de P para cada valor x_i donde ocurre un extremo de P−f, entonces

${displaystyle SilencioQ(x_{i})-f(x_{i}) eternamenteP(x_{i})-f(x_{i})$

Cuando ocurre un máximo de P−f en x_i, entonces

${displaystyle Q(x_{i})-f(x_{i})leq SilencioQ(x_{i})-f(x_{i})$

Y cuando un mínimo P−f ocurre en x_iEntonces

${displaystyle f(x_{i})-Q(x_{i})leq SilencioQ(x_{i})-f(x_{i}) }$

Entonces, como se puede ver en el gráfico, [P(x) − f(x)] − [Q(x) − f(x)] debe alternar el signo para N + 2 valores de x_i. Pero [P(x) − f(x)] − [Q (x) − f(x)] se reduce a P(x) − Q(x) que es un polinomio de grado N. Esta función cambia de signo al menos N+1 veces, por lo que, según el teorema del valor intermedio, tiene N+1 ceros, lo cual es imposible para un polinomio de grado . N.

Aproximación de Chebyshev

Se pueden obtener polinomios muy cercanos al óptimo expandiendo la función dada en términos de polinomios de Chebyshev y luego cortando la expansión en el grado deseado. Esto es similar al análisis de Fourier de la función, utilizando los polinomios de Chebyshev en lugar de las funciones trigonométricas habituales.

Si se calculan los coeficientes en la expansión de Chebyshev para una función:

${displaystyle f(x)sim sum ¿Qué? }c_{i}T_{i}(x)}$

y luego corta la serie después de la ${displaystyle T_{N}$ término, uno tiene un NT- polinomio de grado aproximándose f()x).

La razón por la que este polinomio es casi óptima es que, para funciones con series de potencia convergentes rápidamente, si la serie se corta después de algún término, el error total resultante del corte está cerca del primer término después del corte. Es decir, el primer término después del corte domina todos los términos posteriores. Lo mismo es cierto si la expansión es en términos de polinomios bucking. Si una expansión Chebyshev se corta después ${displaystyle T_{N}$, el error tomará un formulario cerca de un múltiple de ${displaystyle T_{N+1}$. Los polinomios Chebyshev tienen la propiedad que son de nivel – oscilan entre +1 y −1 en el intervalo [−1, 1]. ${displaystyle T_{N+1}$ tiene N+2 nivel extrema. Esto significa que el error entre f()x) y su expansión Chebyshev ${displaystyle T_{N}$ está cerca de una función de nivel con N+2 extrema, por lo que está cerca de la óptima NT- polinomio de grado.

En los gráficos anteriores, la función de error azul es a veces mejor que (dentro de) la función roja, pero a veces peor, lo que significa que no es bastante el polinomio óptimo. La discrepancia es menos grave para la función exp, que tiene una serie de potencia convergente muy rápidamente, que para la función log.

La aproximación de Chebyshev es la base de la cuadratura de Clenshaw-Curtis, una técnica de integración numérica.

Algoritmo de Remez

El algoritmo Remez (a veces escrito Remes) se utiliza para producir un polinomio óptimo P(x) que se aproxima a una función dada f(< i>x) durante un intervalo dado. Es un algoritmo iterativo que converge a un polinomio que tiene una función de error con extremos de nivel N+2. Según el teorema anterior, ese polinomio es óptimo.

Remez utiliza el hecho de que se puede construir un polinomio de grado Nésimo que conduce a nivel y valores de error alternos, dados N+2 puntos de prueba.

Dado N+2 puntos de prueba ${displaystyle x_{1}}$, ${displaystyle x_{2}$,... ${displaystyle x_{N+2}$ (donde) ${displaystyle x_{1}}$ y ${displaystyle x_{N+2}$ son presumiblemente los puntos finales del intervalo de aproximación), estas ecuaciones necesitan ser resueltos:

${fnMicrosoft Sans Serif} {cnMicrosoft Sans Serif} {cnMicrosoft Sans Serif} {f}cnMicrosoft Sans Serif} {cnMicrosoft Sans Serif} {cH0} {ccH0} {ccH00cH0cH00cH0cH00cH00cH00cH00cH00}cH00cH00cH00cH00cH00cH00}$

Los lados derechos se alternan en signo.

Es decir,

${displaystyle {begin{aligned}P_{0}+P_{1}x_{1}+P_{2}x_{1}{2}+P_{3}x_{1}{3}+dots +P_{N}x_{1} {N}-f(x_{1}) ################################################################################################################################################################################################################################################################ +P_{N}x_{2} {N}-f(x_{2}) sensible=-varepsilon \\\\ vdots end{aligned}}$

Desde ${displaystyle x_{1}}$,... ${displaystyle x_{N+2}$ fueron dados, todos sus poderes son conocidos, y ${displaystyle f(x_{1}}$,... ${displaystyle f(x_{N+2}}$ son también conocidos. Eso significa que las ecuaciones anteriores son sólo N+2 ecuaciones lineales en las N+2 variables ${displaystyle P_{0}$, ${displaystyle P_{1}$,... ${displaystyle P_{N}$, y ${displaystyle varepsilon }$. Dados los puntos de prueba ${displaystyle x_{1}}$,... ${displaystyle x_{N+2}$, se puede resolver este sistema para conseguir el polinomio P y el número ${displaystyle varepsilon }$.

El gráfico de abajo muestra un ejemplo de esto, produciendo una aproximación polinomio de cuarto grado ${displaystyle e^{x}$ [ - 1, 1]. Los puntos de prueba se establecieron en 1, 0,7, 0, 1, +0, 4, +0,9 y 1. Esos valores se muestran en verde. El valor resultante de ${displaystyle varepsilon }$ 4.43 × 10⁻⁴

El gráfico de error realmente toma los valores ${displaystyle pm varepsilon }$ en los seis puntos de prueba, incluyendo los puntos finales, pero que esos puntos no son extremos. Si los cuatro puntos de prueba interiores hubieran sido extremos (es decir, la función P()x)f()x) tenía maxima o minima allí), el polinomio sería óptimo.

El segundo paso del algoritmo de Remez consiste en mover los puntos de prueba a las ubicaciones aproximadas donde la función de error tenía sus máximos o mínimos locales reales. Por ejemplo, al observar el gráfico se puede decir que el punto en −0,1 debería haber estado aproximadamente en −0,28. La forma de hacer esto en el algoritmo es utilizar una sola ronda del método de Newton. Dado que se conocen la primera y segunda derivada de P(x) − f(x), se puede calcular aproximadamente qué tan lejos se debe mover un punto de prueba para que la derivada sea cero.

Calcular los derivados de un polinomio es directo. Uno también debe ser capaz de calcular los derivados primero y segundo de f()x). El algoritmo de Remez requiere una habilidad para calcular ${displaystyle f(x),}$, ${displaystyle f'(x),}$, y ${displaystyle f''(x),}$ a alta precisión. Todo el algoritmo debe llevarse a cabo con mayor precisión que la precisión deseada del resultado.

Después de mover los puntos de prueba, se repite la parte de la ecuación lineal, obteniendo un nuevo polinomio, y el método de Newton se utiliza de nuevo para mover los puntos de prueba de nuevo. Esta secuencia se continúa hasta que el resultado converge a la precisión deseada. El algoritmo converge muy rápidamente. La convergencia es cuadrática para funciones bien interpretadas, si los puntos de prueba están dentro ${displaystyle 10^{-15}$ del resultado correcto, estarán aproximadamente dentro ${displaystyle 10^{-30}$ del resultado correcto después de la siguiente ronda.

El algoritmo de Remez se inicia típicamente eligiendo los extremos del polinomio Chebyshev ${displaystyle T_{N+1}$ como los puntos iniciales, ya que la función de error final será similar a ese polinomio.

Principales revistas

• Journal of Approximation Teoría
• Aproximación constructiva
• East Journal on Approximations