Aritmética afín

La aritmética afín ( AA ) es un modelo de análisis numérico autovalidado . En la AA, las cantidades de interés se representan como combinaciones afines ( formas afines ) de ciertas variables primitivas, que representan fuentes de incertidumbre en los datos o aproximaciones realizadas durante el cálculo.

La aritmética afín pretende ser una mejora de la aritmética de intervalos (IA) y es similar a la aritmética de intervalos generalizada , la aritmética de Taylor de primer orden, el modelo de centro-pendiente y el cálculo elipsoidal, en el sentido de que es un método automático para derivar aproximaciones garantizadas de primer orden a fórmulas generales.

La aritmética afín es potencialmente útil en cualquier problema numérico en el que se necesiten recintos garantizados para suavizar funciones, como resolver sistemas de ecuaciones no lineales, analizar sistemas dinámicos , integrar funciones, ecuaciones diferenciales , etc. Las aplicaciones incluyen trazado de rayos , trazado de curvas , intersección de superficies implícitas y paramétricas , análisis de errores (matemáticas) , control de procesos , análisis del peor de los casos de circuitos eléctricos y más.

Definición

En aritmética afín, cada entrada o cantidad calculada x se representa mediante una fórmula donde son números de punto flotante conocidos y son variables simbólicas cuyos valores solo se sabe que están en el rango [-1, +1]. ${\displaystyle x=x_{0}+x_{1}\epsilon _{1}+x_{2}\epsilon _{2}+{}}$ ${\displaystyle \cdots }$ ${\displaystyle {}+x_{n}\epsilon _{n}}$ ${\displaystyle x_{0},x_{1},x_{2},}$ ${\displaystyle \dots ,}$ ${\displaystyle x_{n}}$ ${\displaystyle \epsilon _{1},\epsilon _{2},\dots ,\epsilon _{n}}$

Así, por ejemplo, una cantidad X que se sabe que se encuentra en el rango [3,7] se puede representar mediante la forma afín , para algún k . A la inversa, la forma implica que la cantidad correspondiente X se encuentra en el rango [3,17]. ${\displaystyle x=5+2\epsilon _{k}}$ ${\displaystyle x=10+2\epsilon _{3}-5\epsilon _{8}}$

El hecho de que dos formas afines compartan un símbolo implica que las cantidades correspondientes X , Y son parcialmente dependientes, en el sentido de que su rango conjunto es menor que el producto cartesiano de sus rangos separados. Por ejemplo, si y , entonces los rangos individuales de X e Y son [2,18] y [13,27], pero el rango conjunto del par ( X , Y ) es el hexágono con vértices (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) —que es un subconjunto propio del rectángulo [2,18]×[13,27]. ${\displaystyle \epsilon _{j}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x=10+2\epsilon _{3}-6\epsilon _{8}}$ ${\displaystyle y=20+3\epsilon _{4}+4\epsilon _{8}}$

Operaciones aritméticas afines

Las formas afines se pueden combinar con las operaciones aritméticas estándar o funciones elementales, para obtener aproximaciones garantizadas a las fórmulas.

Operaciones afines

Por ejemplo, dadas formas afines para X e Y , se puede obtener una forma afín para Z = X + Y simplemente sumando las formas, es decir, estableciendo para cada j . De manera similar, se puede calcular una forma afín para Z = X , donde es una constante conocida, estableciendo para cada j . Esto se generaliza a operaciones afines arbitrarias como Z = X + Y + . ${\displaystyle x,y}$ ${\displaystyle z}$ ${\displaystyle z_{j}}$ ${\displaystyle \gets }$ ${\displaystyle x_{j}+y_{j}}$ ${\displaystyle z}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle z_{j}}$ ${\displaystyle \gets }$ ${\displaystyle \alpha x_{j}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

Operaciones no afines

Una operación no afín , como la multiplicación o , no se puede realizar de forma exacta, ya que el resultado no sería una forma afín de . En ese caso, se debe tomar una función afín adecuada G que se aproxime a F en primer orden, en los rangos implicados por y ; y calcular , donde es un límite superior para el error absoluto en ese rango, y es una nueva variable simbólica que no aparece en ninguna forma anterior. ${\displaystyle Z}$ ${\displaystyle \gets }$ ${\displaystyle F(X,Y,}$ ${\displaystyle \dots }$ ${\displaystyle )}$ ${\displaystyle Z}$ ${\displaystyle \gets }$ ${\displaystyle XY}$ ${\displaystyle Z}$ ${\displaystyle \gets }$ ${\displaystyle \sin(X)}$ ${\displaystyle \epsilon _{i}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle \gets }$ ${\displaystyle G(x,y,}$ ${\displaystyle \dots }$ ${\displaystyle )+z_{k}\epsilon _{k}}$ ${\displaystyle z_{k}}$ ${\displaystyle |F-G|}$ ${\displaystyle \epsilon _{k}}$

La forma proporciona entonces un recinto garantizado para la cantidad Z ; además, las formas afines proporcionan conjuntamente un recinto garantizado para el punto ( X , Y ,..., Z ), que a menudo es mucho más pequeño que el producto cartesiano de los rangos de las formas individuales. ${\displaystyle z}$ ${\displaystyle x,y,}$ ${\displaystyle \dots }$ ${\displaystyle ,z}$

Operaciones de encadenamiento

El uso sistemático de este método permite reemplazar cálculos arbitrarios sobre cantidades dadas por cálculos equivalentes sobre sus formas afines, al tiempo que se preservan las correlaciones de primer orden entre la entrada y la salida y se garantiza el encierro completo del rango conjunto. Simplemente se reemplaza cada operación aritmética o llamada a función elemental en la fórmula por una llamada a la rutina de biblioteca AA correspondiente.

En el caso de funciones suaves, los errores de aproximación cometidos en cada paso son proporcionales al cuadrado h ² del ancho h de los intervalos de entrada. Por este motivo, la aritmética afín suele producir límites mucho más estrictos que la aritmética de intervalos estándar (cuyos errores son proporcionales a h ).

Errores de redondeo

Para proporcionar un cerramiento garantizado, las operaciones aritméticas afines deben tener en cuenta los errores de redondeo en el cálculo de los coeficientes resultantes . Esto no se puede hacer redondeando cada uno en una dirección específica, porque cualquier redondeo de ese tipo falsificaría las dependencias entre las formas afines que comparten el símbolo . En cambio, se debe calcular un límite superior para el error de redondeo de cada , y agregar todos ellos al coeficiente del nuevo símbolo (redondeando hacia arriba). Por lo tanto, debido a los errores de redondeo, incluso las operaciones afines como Z = X y Z = X + Y agregarán el término adicional . ${\displaystyle z_{j}}$ ${\displaystyle z_{j}}$ ${\displaystyle \epsilon _{j}}$ ${\displaystyle \delta _{j}}$ ${\displaystyle z_{j}}$ ${\displaystyle \delta _{j}}$ ${\displaystyle z_{k}}$ ${\displaystyle \epsilon _{k}}$ ${\displaystyle \alpha }$ ${\displaystyle z_{k}\epsilon _{k}}$

El manejo de errores de redondeo aumenta la complejidad del código y el tiempo de ejecución de las operaciones de AA. En aplicaciones donde se sabe que esos errores no son importantes (porque están dominados por incertidumbres en los datos de entrada y/o por los errores de linealización), se puede utilizar una biblioteca de AA simplificada que no implemente el control de errores de redondeo.

Modelo de proyección afín

La aritmética afín se puede ver en forma matricial de la siguiente manera. Sean todas las cantidades de entrada y calculadas en uso en algún punto durante un cálculo. Las formas afines para esas cantidades se pueden representar mediante una matriz de coeficiente único A y un vector b , donde elemento es el coeficiente de símbolo en la forma afín de ; y es el término independiente de esa forma. Entonces, el rango conjunto de las cantidades, es decir, el rango del punto , es la imagen del hipercubo por el mapa afín de a definido por . ${\displaystyle X_{1},X_{2},}$ ${\displaystyle \dots ,}$ ${\displaystyle X_{m}}$ ${\displaystyle A_{i,j}}$ ${\displaystyle \epsilon _{j}}$ ${\displaystyle X_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle (X_{1},X_{2},}$ ${\displaystyle \dots ,}$ ${\displaystyle X_{m})}$ ${\displaystyle U^{n}=[-1,+1]^{n}}$ ${\displaystyle U^{n}}$ ${\displaystyle R^{m}}$ ${\displaystyle \epsilon }$ ${\displaystyle \to }$ ${\displaystyle A\epsilon +b}$

El rango de este mapa afín es un zonotopo que limita el rango conjunto de las cantidades . Por lo tanto, se podría decir que AA es una "aritmética de zonotopos". Cada paso de AA suele implicar añadir una fila más y una columna más a la matriz A . ${\displaystyle X_{1},X_{2},}$ ${\displaystyle \dots ,}$ ${\displaystyle X_{m}}$

Simplificación de formas afines

Dado que cada operación AA generalmente crea un nuevo símbolo , la cantidad de términos en una forma afín puede ser proporcional a la cantidad de operaciones utilizadas para calcularla. Por lo tanto, a menudo es necesario aplicar pasos de "condensación de símbolos", donde dos o más símbolos se reemplazan por un conjunto más pequeño de nuevos símbolos. Geométricamente, esto significa reemplazar un zonotopo complicado P por un zonotopo más simple Q que lo encierra. Esta operación se puede realizar sin destruir la propiedad de aproximación de primer orden del zonotopo final. ${\displaystyle \epsilon _{k}}$ ${\displaystyle \epsilon _{k}}$

Implementación

Implementación de matriz

La aritmética afín se puede implementar mediante una matriz global A y un vector global b , como se describió anteriormente. Este enfoque es razonablemente adecuado cuando el conjunto de cantidades a calcular es pequeño y se conoce de antemano. En este enfoque, el programador debe mantener externamente la correspondencia entre los índices de fila y las cantidades de interés. Las variables globales contienen el número m de formas afines (filas) calculadas hasta el momento y el número n de símbolos (columnas) utilizados hasta el momento; estos se actualizan automáticamente en cada operación de aritmética afín.

Implementación de vectores

Como alternativa, cada forma afín se puede implementar como un vector de coeficientes independiente. Este enfoque es más conveniente para la programación, especialmente cuando hay llamadas a procedimientos de biblioteca que pueden usar AA internamente. A cada forma afín se le puede dar un nombre mnemotécnico; se puede asignar cuando sea necesario, pasar a procedimientos y recuperar cuando ya no se necesite. El código AA se parece mucho más a la fórmula original. Una variable global contiene la cantidad n de símbolos utilizados hasta el momento.

Implementación de vector disperso

En cálculos bastante largos, el conjunto de cantidades "vivas" (que se utilizarán en cálculos futuros) es mucho más pequeño que el conjunto de todas las cantidades calculadas; y lo mismo ocurre con el conjunto de símbolos "vivos" . En esta situación, las implementaciones matriciales y vectoriales son una pérdida de tiempo y espacio excesiva. ${\displaystyle \epsilon _{j}}$

En tales situaciones, se debe utilizar una implementación dispersa . Es decir, cada forma afín se almacena como una lista de pares (j, ), que contiene solo los términos con coeficiente distinto de cero . Para mayor eficiencia, los términos se deben ordenar en orden de j . Esta representación hace que las operaciones de AA sean algo más complicadas; sin embargo, el costo de cada operación se vuelve proporcional a la cantidad de términos distintos de cero que aparecen en los operandos, en lugar de la cantidad total de símbolos utilizados hasta ahora. ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$

Esta es la representación utilizada por LibAffa.

Referencias

• LH de Figueiredo y J. Stolfi (2004) "Aritmética afín: conceptos y aplicaciones". Algoritmos numéricos 37 (1–4), 147–158.
• JLD Comba y J. Stolfi (1993), "Aritmética afín y sus aplicaciones a los gráficos por computadora". Proc. SIBGRAPI'93 — VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (Recife, BR) , 9–18.
• LH de Figueiredo y J. Stolfi (1996), "Enumeración adaptativa de superficies implícitas con aritmética afín". Computer Graphics Forum , 15 5 , 287–296.
• W. Heidrich (1997), "Una compilación de versiones aritméticas afines de funciones comunes de bibliotecas matemáticas". Informe técnico 1997-3, Universität Erlangen-Nürnberg.
• M. Kashiwagi (1998), "Un algoritmo de solución total utilizando aritmética afín". NOLTA'98 — Simposio internacional de 1998 sobre teoría no lineal y sus aplicaciones (Crans-Montana, Suiza) , 14–17.
• L. Egiziano, N. Femia y G. Spagnuolo (1998), "Nuevos enfoques para la evaluación del peor caso real en el análisis de sensibilidad y tolerancia de circuitos — Parte II: Cálculo de la solución externa utilizando aritmética afín". Proc. COMPEL'98 — 6.º Taller sobre informática en electrónica de potencia (Villa Erba, Italia) , 19–22.
• W. Heidrich, Ph. Slusallek y H.-P. Seidel (1998), "Muestreo de sombreadores procedimentales utilizando aritmética afín". ACM Transactions on Graphics , 173 , 158–176.
• F. Messine y A. Mahfoudi (1998), "Uso de aritmética afín en algoritmos de optimización de intervalos para resolver problemas de escalamiento multidimensional". Proc. SCAN'98 — Simposio internacional IMACS/GAMM sobre computación científica, aritmética computacional y números validados (Budapest, Hungría) , 22–25.
• A. de Cusatis Jr., LH Figueiredo y M. Gattass (1999), "Métodos de intervalos para la proyección de rayos en superficies con aritmética afín". Proc. SIBGRAPI'99 — 12.º Simposio Brasileño sobre Procesamiento de Imágenes y Gráficos por Computadora , 65–71.
• K. Bühler y W. Barth (2000), "Un nuevo algoritmo de intersección para superficies paramétricas basado en estimaciones de intervalos lineales". Proc. SCAN 2000 / Interval 2000 — 9.º Simposio internacional GAMM-IMACS sobre computación científica, aritmética computacional y números validados , ???–???.
• I. Voiculescu, J. Berchtold, A. Bowyer, RR Martin y Q. Zhang (2000), "Aritmética de intervalos y afín para la localización de superficies de polinomios en forma de Bernstein y de potencia". Proc. Matemáticas de superficies IX , 410–423. Springer, ISBN  1-85233-358-8 .
• Q. Zhang y RR Martin (2000), "Evaluación polinómica utilizando aritmética afín para el dibujo de curvas". Actas de la Conferencia Eurographics UK 2000 , 49–56. ISBN 0-9521097-9-4 . 
• D. Michelucci (2000), "Cálculos fiables para sistemas dinámicos". Proc. SCAN 2000 / Interval 2000 — 9º Simposio internacional GAMM-IMACS sobre computación científica, aritmética informática y números validados , ???–???.
• N. Femia y G. Spagnuolo (2000), "Análisis de tolerancia de circuitos en el peor de los casos utilizando algoritmos genéticos y aritmética afín — Parte I". IEEE Transactions on Circuits and Systems , 47 9 , 1285–1296.
• R. Martin, H. Shou, I. Voiculescu y G. Wang (2001), "Una comparación de los métodos aritméticos de Bernstein hull y afines para el dibujo de curvas algebraicas". Proc. Uncertainty in Geometric Computations , 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X . 
• A. Bowyer, R. Martin, H. Shou y I. Voiculescu (2001), "Intervalos afines en un modelador geométrico CSG". Proc. Uncertainty in Geometric Computations , 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X . 
• T. Kikuchi y M. Kashiwagi (2001), "Eliminación de regiones de no existencia de la solución de ecuaciones no lineales utilizando aritmética afín". Proc. NOLTA'01 — Simposio internacional de 2001 sobre teoría no lineal y sus aplicaciones .
• T. Miyata y M. Kashiwagi (2001), "Evaluación de rangos de polinomios de aritmética afín". Proc. NOLTA'01 - Simposio internacional sobre teoría no lineal y sus aplicaciones 2001 .
• Y. Kanazawa y S. Oishi (2002), "Un método numérico para probar la existencia de soluciones para ecuaciones diferenciales ordinarias no lineales utilizando aritmética afín". Proc. SCAN'02 — 10.º Simposio internacional GAMM-IMACS sobre computación científica, aritmética informática y números validados .
• H. Shou, RRMartin, I. Voiculescu, A. Bowyer y G. Wang (2002), "Aritmética afín en forma matricial para evaluación polinómica y dibujo de curvas algebraicas". Progress in Natural Science , 12 1 , 77–81.
• A. Lemke, L. Hedrich y E. Barke (2002), "Dimensionamiento de circuitos analógicos basado en métodos formales utilizando aritmética afín". Proc. ICCAD-2002 — Conferencia internacional sobre diseño asistido por ordenador , 486–489.
• F. Messine (2002), "Extensiones de aritmética afín: aplicación a la optimización global sin restricciones". Journal of Universal Computer Science , 8 11 , 992–1015.
• K. Bühler (2002), "Estimaciones de intervalos lineales implícitos". Proc. 18th Spring Conference on Computer Graphics (Budmerice, Eslovaquia) , 123–132. ACM Press, ISBN 1-58113-608-0 . 
• LH de Figueiredo, J. Stolfi y L. Velho (2003), "Aproximación de curvas paramétricas con árboles de franjas utilizando aritmética afín". Computer Graphics Forum , 22 2 , 171–179.
• CF Fang, T. Chen y R. Rutenbar (2003), "Análisis de errores de punto flotante basado en aritmética afín". Proc. 2003 Conferencia internacional sobre procesamiento acústico, de voz y de señales .
• A. Paiva, LH de Figueiredo y J. Stolfi (2006), "Visualización robusta de atractores extraños utilizando aritmética afín". Computers & Graphics , 30 6 , 1020– 1026.

Enlaces externos

• [1] La página de Stolfi sobre AA.
• [2] LibAffa, una implementación LGPL de aritmética afín.
  • libaffa en GitHub
• [3] ASOL, un método de ramificación y poda para encontrar todas las soluciones a sistemas de ecuaciones no lineales utilizando aritmética afín
• [4] Archivado el 27 de enero de 2021 en Wayback Machine YalAA, una biblioteca de plantillas basada en C++ orientada a objetos para aritmética afín (AA).
• kv en GitHub ( biblioteca de C++ que puede utilizar aritmética afín)