Teoría de la aproximación

En matemáticas, la teoría de la aproximación se refiere a cómo las funciones pueden ser aproximadas con otras funciones más simples, incluyendo la caracterización cuantitativa del error introducido. Debe tenerse en cuenta que lo que se entiende por mejor y más simple depende del uso que quiera darse a la aproximación, y de los recursos de cálculo necesarios.^[1]​

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

Un problema de particular interés es el de aproximar una función en una biblioteca matemática de una computadora, utilizando operaciones que pueden realizarse fácilmente en el dispositivo (por ejemplo, la suma y la multiplicación), de modo que el resultado sea lo más cercano posible a la función buscada. Esto normalmente se hace con aproximaciones polinómicas o racionales (relació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 en coma flotante de la computadora subyacente. Esto se logra mediante el uso de un polinomio de alto grado, y/o estrechando el dominio sobre el que el polinomio tiene que aproximar la función. La reducción del dominio a menudo se puede hacer mediante el uso de varias fórmulas de adición o escalado para la función que se aproxima. Las bibliotecas matemáticas modernas a menudo reducen el dominio en muchos segmentos pequeños y usan un polinomio de bajo grado para cada segmento.

Una vez que se elige el dominio (típicamente un intervalo) y el grado del polinomio, el polinomio en sí se elige de tal manera que se minimice 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 de la aproximación, f(x) es la función real, y x varía en el intervalo elegido. Para funciones con buen comportamiento, existe un polinomio de grado N-ésimo que conducirá a una curva de error que oscila entre ${displaystyle +varepsilon }$ y ${displaystyle -varepsilon }$ un total de N+2 veces, lo que da una cota del peor resultado del error ${displaystyle varepsilon }$. Se ve que existe un polinomio de grado N-ésimo que puede interpolar N+1 puntos en una curva. Tal polinomio es siempre óptimo. Es posible encontrar funciones artificiales f(x) para las cuales no existe tal polinomio, pero raramente se suelen dar en la práctica.^[3]​

Por ejemplo, los gráficos situados a la derecha muestran el error al aproximar log(x) y exp(x) para N = 4. Las curvas rojas, para el polinomio óptimo, establecen un nivel de referencia, es decir, oscilan entre ${displaystyle +varepsilon }$ y ${displaystyle -varepsilon }$ exactamente. Debe tenerse en cuenta que, en cada caso, el número de extremos 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, supóngase 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 podría ser esta función de error para N = 4. Supóngase que Q(x) (cuya función de error se muestra en azul a la derecha) es otro polinomio de grado N que es una mejor aproximación a f que P. En particular, Q está más cerca de f que P para cada valor x_i donde se sitúa un extremo de P-f, entonces

Cuando se produce un máximo de P-f en x_i, entonces

Y cuando se produce un mínimo de P-f en x_i , entonces

Entonces, como se puede ver en el gráfico, [P(x) - f(x)] - [ Q (x) - f(x)] debe alternar en el signo de 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 el signo al menos N+1 veces, por lo que, por el Teorema del valor intermedio, tiene N+1 ceros, lo que es imposible para un polinomio de grado N.^[4]​

Se pueden obtener polinomios muy cercanos al óptimo expandiendo la función dada en términos de los polinomios de Chebyshev y luego cortando la expansión en el grado deseado.^[5]​

Este enfoque 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:

y luego se corta la serie después del término ${displaystyle T_{N}}$, se obtiene un polinomio de grado N-ésimo que se aproxima a f(x).

La razón por la que este polinomio es casi óptimo es que, para funciones con series de potencias que convergen rápidamente, si la serie se corta después de un término, el error total que surge 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 otros tipos de polinomios. Si una expansión de Chebyshev se corta después de ${displaystyle T_{N}}$, el error tomará una forma cercana a un múltiplo de ${displaystyle T_{N+1}}$. Los polinomios de Chebyshev tienen la propiedad de que están nivelados: oscilan entre +1 y −1 en el intervalo [−1, 1]. ${displaystyle T_{N+1}}$ tiene N+2 niveles extremos. Esto significa que el error entre f(x) y su expansión de Chebyshev a ${displaystyle T_{N}}$ está cerca de una función de nivel con N+2 extremos, por lo que está cerca del polinomio óptimo de N-ésimo grado.

En los gráficos anteriores, debe tenerse en cuenta que la función de error azul es a veces mejor (está más próxima) que la función roja, pero a veces es peor, lo que significa que no es el polinomio óptimo. Téngase en cuenta también que la discrepancia es menos grave para la función exp, que tiene una serie de potencias convergente extremadamente rápida, que para la función de registro.

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

El algoritmo Remez (a veces escrito Remes) se usa para producir un polinomio óptimo P(x) que se aproxima a una función dada f(x) en un intervalo dado. Es un algoritmo iterativo que converge a un polinomio que tiene una función de error con N+2 niveles extremos. Según el teorema anterior, este polinomio es óptimo.^[7]​

El algoritmo de Remez utiliza el hecho de que se puede construir un polinomio de grado N-ésimo que conduce a niveles y valores de error alternos, dados los N+2 puntos de referencia.

Dados N+2 puntos de referencia ${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 deben resolverse:

Los lados de la derecha se alternan en señal, es decir

Dado que ${displaystyle x_{1}}$, ..., ${displaystyle x_{N+2}}$ son datos dados, todqs sus potencias son conocidas, y ${displaystyle f(x_{1})}$, ..., ${displaystyle f(x_{N+2})}$ también son conocidos. Eso significa que las ecuaciones anteriores son solo 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 referencia ${displaystyle x_{1}}$, ..., ${displaystyle x_{N+2}}$, se puede resolver este sistema para obtener el polinomio Py el número ${displaystyle varepsilon }$.

El siguiente gráfico muestra un ejemplo de esta configuración, produciendo un polinomio de cuarto grado que se aproxima a ${displaystyle e^{x}}$ sobre [−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 }$ es 4.43 × 10⁻⁴

Téngase en cuenta que el gráfico de error toma los valores ${displaystyle pm varepsilon }$ en los seis puntos de prueba, incluidos 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) tuviera máximos o mínimos 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 en aproximadamente −0.28. La forma de hacer esto en el algoritmo es usar un solo paso del método de Newton. Como se conoce la primera y la segunda derivada de P(x) − f(x), se puede calcular aproximadamente hasta qué punto se debe mover un punto de prueba para que la derivada sea cero.

Calcular las derivadas de un polinomio es sencillo. También se debe poder calcular la primera y la segunda derivada de f(x). El algoritmo de Remez requiere la capacidad de calcular ${displaystyle f(x),}$, ${displaystyle f'(x),}$ y ${displaystyle f''(x),}$ con una precisión extremadamente alta. 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 usa otra vez para mover los puntos de referencia nuevamente. Esta secuencia 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 con buen comportamiento: si los puntos de prueba están dentro de ${displaystyle 10^{-15}}$ del resultado correcto, estarán aproximadamente dentro de ${displaystyle 10^{-30}}$ del resultado correcto después de la siguiente iteración.

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