Teoría de la aproximación

Teoría de cómo acercarse aceptablemente a cálculos matemáticos inexactos

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 ello. Lo que se entiende por mejor y más sencillo 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. 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 punto flotante de la computadora subyacente . 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 se eligen el dominio (normalmente un intervalo) y el grado del polinomio, el polinomio en sí se elige de tal manera que se minimice el error en el peor de los casos. Es decir, el objetivo es minimizar el valor máximo de , donde P ( x ) es el polinomio aproximado, f ( x ) es la función real y x varía en el intervalo elegido. Para funciones que se comportan bien, existe un polinomio de grado N que conducirá a una curva de error que oscila hacia adelante y hacia atrás entre y un total de N +2 veces, dando un error en el peor de los casos de . Se ve que existe un polinomio de grado N que puede interpolar N +1 puntos en una curva. El teorema de equioscilación afirma que tal polinomio es siempre óptimo . Es posible crear funciones artificiales f ( x ) para las cuales no existe tal polinomio, pero rara vez ocurren en la práctica. ${\displaystyle \mid P(x)-f(x)\mid }$ ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$ ${\displaystyle \varepsilon }$

Por ejemplo, los gráficos que se muestran a la derecha muestran el error al aproximar log(x) y exp(x) para N  = 4. Las curvas rojas, para el polinomio óptimo, son de nivel , es decir, oscilan entre y exactamente. 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 las gráficas. ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$

Error P ( x ) −  f ( x ) para el polinomio de nivel (rojo) y para el supuesto polinomio mejor (azul)

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 se muestra en azul a la derecha) es otro polinomio de N grados que es una mejor aproximación a f que PAG . En particular, Q está más cerca de f que P para cada valor x _i donde ocurre un extremo de P − f , por lo que

${\displaystyle |Q(x_{i})-f(x_{i})|<|P(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 |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),}$

Y cuando ocurre un mínimo de P − f en x _i , entonces

${\displaystyle f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).}$

Entonces, como se puede ver en el gráfico, [ P ( x ) −  f ( x )] − [ Q ( x ) −  f ( x )] debe alternar en signo para los 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 _{i=0}^{\infty }c_{i}T_{i}(x)}$

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

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 algún 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 límite domina todos los términos posteriores. Lo mismo ocurre si la expansión se realiza en términos de polinomios contrapuestos. Si se corta una expansión de Chebyshev después de , el error tomará una forma cercana a un múltiplo de . Los polinomios de Chebyshev tienen la propiedad de ser nivelados: oscilan entre +1 y −1 en el intervalo [−1, 1]. tiene extremos de nivel N +2. Esto significa que el error entre f ( x ) y su expansión de Chebyshev está cerca de una función de nivel con N +2 extremos, por lo que está cerca del polinomio óptimo de N ésimo grado. ${\displaystyle T_{N}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N}}$

En los gráficos anteriores, la función de error azul a veces es mejor que (dentro de) la función roja, pero a veces es peor, lo que significa que no es el polinomio óptimo. La discrepancia es menos grave para la función exp, que tiene una serie de potencias que converge extremadamente 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 de Remez (a veces escrito Remes) se utiliza para producir un polinomio óptimo P ( x ) que se aproxima a una función dada f ( x ) en un intervalo determinado. 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.

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

Dados N +2 puntos de prueba , , ... (donde y son presumiblemente los puntos finales del intervalo de aproximación), es necesario resolver estas ecuaciones: ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$

${\displaystyle {\begin{aligned}P(x_{1})-f(x_{1})&=+\varepsilon \\P(x_{2})-f(x_{2})&=-\varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2})&=\pm \varepsilon .\end{aligned}}}$

Los lados derechos se alternan en signo.

Eso es,

${\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})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\&\ \ \vdots \end{aligned}}}$

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

El siguiente gráfico muestra un ejemplo de esto, produciendo un polinomio de cuarto grado que se aproxima 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 es 4,43 × 10 ⁻⁴ ${\displaystyle e^{x}}$ ${\displaystyle \varepsilon }$

Error del polinomio producido por el primer paso del algoritmo de Remez, aproximando e ^x en el intervalo [−1, 1]. Las divisiones verticales son 10 ⁻⁴ .

De hecho, el gráfico de error toma los valores en los seis puntos de prueba, incluidos los puntos finales, pero 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. ${\displaystyle \pm \varepsilon }$

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 . Como se conocen las derivadas primera y segunda 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 segunda derivada de f ( x ). El algoritmo de Remez requiere la capacidad de calcular , y con una precisión extremadamente alta. Todo el algoritmo debe llevarse a cabo con una precisión mayor que la precisión deseada del resultado. ${\displaystyle f(x)\,}$ ${\displaystyle f'(x)\,}$ ${\displaystyle f''(x)\,}$

Después de mover los puntos de prueba, se repite la parte de la ecuación lineal, obteniendo un nuevo polinomio, y se usa nuevamente el método de Newton para mover los puntos de prueba 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 que se comportan bien: si los puntos de prueba están dentro del resultado correcto, estarán aproximadamente dentro del resultado correcto después de la siguiente ronda. ${\displaystyle 10^{-15}}$ ${\displaystyle 10^{-30}}$

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

Revistas principales

• Revista de teoría de la aproximación
• Aproximación constructiva
• Revista Este sobre Aproximaciones

Ver también

• Teoría de la estimación
• series de Fourier
• Aproximación de funciones
• Base ortonormal
• Padé aproximante
• base de Schauder
• filtro de kalman

Referencias

• NI Achiezer (Akhiezer) , Teoría de la aproximación, Traducido por Charles J. Hyman Frederick Ungar Publishing Co., Nueva York 1956 x+307 págs.
• AF Timan, Teoría de la aproximación de funciones de una variable real , 1963 ISBN  0-486-67830-X
• C. Hastings, Jr. Aproximaciones para computadoras digitales . Prensa de la Universidad de Princeton, 1955.
• JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Aproximaciones informáticas . Wiley, 1968, Lib. Cong. 67–23326.
• L. Fox e IB Parker. "Polinomios de Chebyshev en análisis numérico". Oxford University Press Londres, 1968.
• Presione, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (2007), "Sección 5.8. Aproximación de Chebyshev", Recetas numéricas: el arte de la informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8, archivado desde el original el 10 de abril de 2020 , consultado el 9 de agosto de 2011
• WJ Cody Jr., W. Waite, Manual de software para funciones elementales . Prentice-Hall, 1980, ISBN 0-13-822064-6 . 
• E. Remes [Remez] , "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 CR Acad. Ciencia. , París, 199 , 337–340.
• KG. Steffens, "La historia de la teoría de la aproximación: de Euler a Bernstein", Birkhauser, Boston 2006 ISBN 0-8176-4353-2 . 
• T. Erdélyi , "Extensiones del teorema de Bloch-Pólya sobre el número de ceros reales distintos de polinomios", Journal de théorie des nombres de Bordeaux 20 (2008), 281–287.
• T. Erdélyi, "La desigualdad de Remez para combinaciones lineales de gaussianas desplazadas", Math. Proc. Camb. Fil. Soc. 146 (2009), 523–530.
• LN Trefethen , "Teoría de la aproximación y práctica de la aproximación", SIAM 2013. [1]

enlaces externos

• Historia de la teoría de la aproximación (HAT)
• Encuestas en Teoría de Aproximación (SAT)