Aritmetica affine

L'Aritmetica Affine (AA) è un modello auto-validato di analisi numerica. In AA, le quantità vengono rappresentati come combinazioni affini (forme affini) di alcune variabili primitive che esprimono l'incertezza dell'approssimazione dei dati durante un calcolo.

L'aritmetica affine risulta particolarmente utile nei problemi in cui c'è necessità di garantire errori minimi dovuti ad arrotondamenti nei calcoli numerici a virgola mobile. Esempi tipici sono la risoluzione di sistemi di equazioni non lineari, l'analisi di sistemi dinamici, la risoluzione di equazioni differenziali, ecc.

Definizioni modifica

In Aritmetica Affine, un dato numerico x (sia esso un dato in ingresso o il risultato di un calcolo) è rappresentato dalla formula $x=x_{0}+x_{1}\varepsilon _{1}+x_{2}\varepsilon _{2}+{}$ $\cdots$ ${}+x_{n}\varepsilon _{n}$ dove $x_{0},x_{1},x_{2},$ $\dots ,$ $x_{n}$ sono numeri in virgola mobile e $\varepsilon _{1},\varepsilon _{2},\varepsilon _{n}$ sono variabili simboliche a valori nell'intervallo [-1,+1].

Ad esempio, una quantità X che si trova nell'intervallo [3,7] può essere rappresentata dalla forma affine $x=5+2\varepsilon _{k}$ , per qualche k. Viceversa, la forma affine $x=10+2\varepsilon _{3}-5\varepsilon _{8}$ rappresenta una quantità X che si trova nell'intervallo [3,17].

Il fatto che due forme affini $x$ e $y$ hanno in comune un simbolo $\varepsilon _{j}$ implica che le corrispondenti quantità X, Y sono parzialmente dipendenti, nel senso che l'intervallo comune (joint range) dei loro intervalli è contenuto nel Prodotto cartesiano dei singoli intervalli. Per esempio, se: $x=10+2\varepsilon _{3}-6\varepsilon _{8}$ e $y=20+3\varepsilon _{4}+4\varepsilon _{8}$ , gli intervalli individuali di X and Y sono [2,18] and [13,27], ma il loro intervallo comune della coppia (X,Y) è l'esagono di vertici (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) — che è un sottoinsieme proprio del rettangolo [2,18]×[13,27].

Bibliografia modifica

L. H. de Figueiredo and J. Stolfi (2004) "Affine arithmetic: concepts and applications." Numerical Algorithms 37 (1–4), 147–158.
J. L. D. Comba and J. Stolfi (1993), "Affine arithmetic and its applications to computer graphics". Proc. SIBGRAPI'93 — VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (Recife, BR), 9–18.
L. H. de Figueiredo and J. Stolfi (1996), "Adaptive enumeration of implicit surfaces with affine arithmetic". Computer Graphics Forum, 15 5, 287–296.
W. Heidrich (1997), "A compilation of affine arithmetic versions of common math library functions". Technical Report 1997-3, Universität Erlangen-Nürnberg.
M. Kashiwagi (1998), "An all solution algorithm using affine arithmetic". NOLTA'98 — 1998 International Symposium on Nonlinear Theory and its Applications (Crans-Montana, Switzerland), 14–17.
L. Egiziano, N. Femia, and G. Spagnuolo (1998), "New approaches to the true worst-case evaluation in circuit tolerance and sensitivity analysis — Part II: Calculation of the outer solution using affine arithmetic". Proc. COMPEL'98 — 6th Workshop on Computer in Power Electronics (Villa Erba, Italy), 19–22.
W. Heidrich, Ph. Slusallek, and H.-P. Seidel (1998), "Sampling procedural shaders using affine arithmetic". ACM Transactions on Graphics (TOG), 17 3, 158–176.
F. Messine and A. Mahfoudi (1998), "Use of affine arithmetic in interval optimization algorithms to solve multidimensional scaling problems". Proc. SCAN'98 — IMACS/GAMM International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (Budapest, Hungary), 22–25.
A. de Cusatis Jr., L. H. Figueiredo, and M. Gattass (1999), "Interval methods for ray casting surfaces with affine arithmetic". Proc. SIBGRAPI'99 — 12th Brazilian Symposium on Computer Graphics and Image Processing, 65–71.
K. Bühler and W. Barth (2000), "A new intersection algorithm for parametric surfaces based on linear interval estimations". Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, ???–???.
I. Voiculescu, J. Berchtold, A. Bowyer, R. R. Martin, and Q. Zhang (2000), "Interval and affine arithmetic for surface location of power- and Bernstein-form polynomials". Proc. Mathematics of Surfaces IX, 410–423. Springer, ISBN 1-85233-358-8.
Q. Zhang and R. R. Martin (2000), "Polynomial evaluation using affine arithmetic for curve drawing". Proc. of Eurographics UK 2000 Conference, 49–56. ISBN 0-9521097-9-4.
D. Michelucci (2000), "Reliable computations for dynamic systems". Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, ???–???.
N. Femia and G. Spagnuolo (2000), "True worst-case circuit tolerance analysis using genetic algorithm and affine arithmetic — Part I". IEEE Transactions on Circuits and Systems, 47 9, 1285–1296.
R. Martin, H. Shou, I. Voiculescu, and G. Wang (2001), "A comparison of Bernstein hull and affine arithmetic methods for algebraic curve drawing". Proc. Uncertainty in Geometric Computations, 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
A. Bowyer, R. Martin, H. Shou, and I. Voiculescu (2001), "Affine intervals in a CSG geometric modeller". Proc. Uncertainty in Geometric Computations, 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X.
T. Kikuchi and M. Kashiwagi (2001), "Elimination of non-existence regions of the solution of nonlinear equations using affine arithmetic". Proc. NOLTA'01 — 2001 International Symposium on Nonlinear Theory and its Applications.
T. Miyata and M. Kashiwagi (2001), "On range evaluation of polynomials of affine arithmetic". Proc. NOLTA'01 - 2001 International Symposium on Nonlinear Theory and its Applications.
Y. Kanazawa and S. Oishi (2002), "A numerical method of proving the existence of solutions for nonlinear ODEs using affine arithmetic". Proc. SCAN'02 — 10th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics.
H. Shou, R. R.Martin, I. Voiculescu, A. Bowyer, and G. Wang (2002), "Affine arithmetic in matrix form for polynomial evaluation and algebraic curve drawing". Progress in Natural Science, 12 1, 77–81.
A. Lemke, L. Hedrich, and E. Barke (2002), "Analog circuit sizing based on formal methods using affine arithmetic". Proc. ICCAD-2002 — International Conference on Computer Aided Design, 486–489.
F. Messine (2002), "Extensions of affine arithmetic: Application to unconstrained global optimization". Journal of Universal Computer Science, 8 11, 992–1015.
K. Bühler (2002), "Implicit linear interval estimations". Proc. 18th Spring Conference on Computer Graphics (Budmerice, Slovakia), 123–132. ACM Press, ISBN 1-58113-608-0.
L. H. de Figueiredo, J. Stolfi, and L. Velho (2003), "Approximating parametric curves with strip trees using affine arithmetic". Computer Graphics Forum, 22 2, 171–179.
C. F. Fang, T. Chen, and R. Rutenbar (2003), "Floating-point error analysis based on affine arithmetic". Proc. 2003 International Conf. on Acoustic, Speech and Signal Processing.
A. Paiva, L. H. de Figueiredo, and J. Stolfi (2006), "Robust visualization of strange attractors using affine arithmetic". Computers & Graphics, 30 6, 1020– 1026.

Collegamenti esterni modifica

[1] Archiviato il 23 maggio 2011 in Internet Archive. Stolfi's page on AA.
[2] LibAffa, an LGPL implementation of affine arithmetic.
[3] ASOL, a branch-and-prune method to find all solutions to systems of nonlinear equations using affine arithmetic

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica