Affin aritmetik

Affin aritmetik ( AA ) är en modell för självvaliderad numerisk analys . I AA representeras de intressanta kvantiteterna som affina kombinationer ( affina former ) av vissa primitiva variabler, som står för källor till osäkerhet i data eller approximationer som görs under beräkningen.

Affin aritmetik är tänkt att vara en förbättring av intervallaritmetik (IA), och liknar generaliserad intervallaritmetik, första ordningens Taylor-aritmetik, centrumlutningsmodellen och ellipsoidkalkyl – i den meningen att det är en automatisk metod att härleda första ordningens garanterade approximationer till allmänna formler.

Affin aritmetik är potentiellt användbar i alla numeriska problem där man behöver garanterade inneslutningar för att jämna ut funktioner, såsom att lösa system av icke-linjära ekvationer, analysera dynamiska system , integrera funktioner, differentialekvationer , etc. Tillämpningar inkluderar strålspårning , plottning av kurvor , korsande implicita system och parametriska ytor , felanalys (matematik) , processtyrning , värsta tänkbara analys av elektriska kretsar , med mera.

Definition

I affin aritmetik representeras varje indata eller beräknad kvantitet x av en formel $x=x_{0}+x_{1}\epsilon _{1}+ x_{2}\epsilon _{2}+{}$$\cdots$${}+x_{n}\epsilon _{n}$ där $x_{0},x_{1},x_{2},$$\dots ,$$x_{n}$ är kända flyttal, och $\epsilon _{1},\epsilon _{2},\dots ,\epsilon _{n}$ är symboliska variabler vars värden endast är kända för att ligga i intervallet [- 1,+1].

Således kan till exempel en storhet X som är känd för att ligga i området [3,7] representeras av den affina formen $x=5+2\epsilon _{k}$ , för några k . Omvänt innebär formen $x=10+2\epsilon _{3}-5\epsilon _{8}$ att motsvarande kvantitet X ligger i intervallet [3 ,17].

Att dela en symbol $\epsilon _{j}$ mellan två affina former $x$ , $y$ innebär att motsvarande storheter X , Y är delvis beroende, i den meningen att deras gemensamma sortiment är mindre än den kartesiska produkten i deras separata sortiment. Till exempel, om $x=10+2\epsilon _{3}-6\epsilon _{8}$ och ${\displaystyle y=20+3\epsilon _{4}+4\epsilon _{8}} ,$ då är de individuella intervallen för X och Y [2,18] och [13,27], men det gemensamma intervallet för paret ( X , Y ) är hexagonen med hörn (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) - vilket är en riktig delmängd av rektangeln [2,18]×[13,27].

Affina aritmetiska operationer

Affina former kan kombineras med aritmetiska standardoperationer eller elementära funktioner för att erhålla garanterade approximationer till formler.

Affina operationer

Till exempel, givet affina former $x,y$ för X och Y , kan man få en affin form $z$ för Z = X + Y helt enkelt genom att lägga till formerna - det vill säga ställa in $z_{j}$$\gets$$x_{j}+y_{j}$ för varje j . På liknande sätt kan man beräkna en affin form $z$ för Z = $\alpha$ X , där $\alpha$ är en känd konstant, genom att sätta $z_{j}$$\gets$$\alpha x_{j}$ för varje j . Detta generaliserar till godtyckliga affina operationer som Z = $\alpha$ X + $\beta$ Y + $\gamma$ .

Icke-affin verksamhet

En icke-affin operation $Z$$\gets$$F(X,Y,$$\dots$$)$ , som multiplikation $Z$$\gets$$XY$ eller $Z$$\gets$$\sin(X)$ , kan inte utföras exakt, eftersom resultatet inte skulle vara en affin form av $\epsilon _{i}$ . I så fall bör man ta en lämplig affin funktion G som approximerar F till första ordningen, i intervallen som impliceras av $x$ och $y$ ; och beräkna $z$$\gets$$G(x,y,$$\dots$$)+z_ {k}\epsilon _{k}$ , där $z_{k}$ är en övre gräns för det absoluta felet $|FG|$ i det intervallet, och $\epsilon _{k}$ är en ny symbolisk variabel som inte förekommer i någon tidigare form.

Formen $z$ ger då en garanterad inneslutning för kvantiteten Z ; dessutom ger de affina formerna $x,y,$$\dots$$,z$ tillsammans en garanterad inneslutning för punkten ( X , Y ,..., Z ), som ofta är mycket mindre än den kartesiska produkten av de individuella formernas intervall.

Kedjeoperationer

Systematisk användning av denna metod gör att godtyckliga beräkningar av givna kvantiteter kan ersättas med likvärdiga beräkningar på deras affina former, samtidigt som första ordningens korrelationer mellan inmatning och utdata bevaras och garanterar fullständig inneslutning av det gemensamma området. Man ersätter helt enkelt varje aritmetisk operation eller elementär funktionsanrop i formeln med ett anrop till motsvarande AA-biblioteksrutin.

För jämna funktioner är approximationsfelen som görs vid varje steg proportionella mot kvadraten h ² av bredden h för inmatningsintervallen. Av denna anledning kommer affin aritmetik ofta att ge mycket snävare gränser än standardintervallaritmetik (vars fel är proportionella mot h ).

Avrundningsfel

För att tillhandahålla garanterad inneslutning måste affina aritmetiska operationer ta hänsyn till avrundningsfelen vid beräkningen av de resulterande koefficienterna $z_{j}$ . Detta kan inte göras genom att avrunda varje $z_{j}$ i en specifik riktning, eftersom varje sådan avrundning skulle förfalska beroenden mellan affina former som delar symbolen $\epsilon _{j}$ . Istället måste man beräkna en övre gräns $\delta _{j}$ till avrundningsfelet för varje $z_{j}$ , och lägga till alla dessa $\delta _{ j}$ till koefficienten $z_{k}$ för den nya symbolen $\epsilon _{k}$ (avrundning uppåt). På grund av avrundningsfel kommer alltså även affina operationer som Z = $\alpha$ X och Z = X + Y att lägga till den extra termen $z_{k}\epsilon _{k}$ .

Hanteringen av avrundningsfel ökar kodkomplexiteten och exekveringstiden för AA-operationer. I applikationer där dessa fel är kända för att vara oviktiga (eftersom de domineras av osäkerheter i indata och/eller av linjäriseringsfel), kan man använda ett förenklat AA-bibliotek som inte implementerar avrundningsfelkontroll.

Affin projektionsmodell

Affin aritmetik kan ses i matrisform enligt följande. Låt $X_{1},X_{2},$$\dots ,$$X_{m}$ vara alla indata och beräknade kvantiteter som används vid vissa punkt under en beräkning. De affina formerna för dessa kvantiteter kan representeras av en enda koefficientmatris A och en vektor b , där element $A_{i,j}$ är koefficienten för symbolen $\epsilon _{ j}$ i den affina formen av $X_{i}$ ; och $b_{i}$ är den oberoende termen för den formen. Sedan det gemensamma intervallet för kvantiteterna — det vill säga intervallet för punkten $(X_{1},X_{2},$$\dots ,$$X_{m})$ — är bilden av hyperkuben $U^{n}=[-1,+1]^{n}$ av affin karta från $U^{n}$ till $R^{m}$ definierad av $\epsilon$$\to$$A \epsilon +b$ .

Området för denna affina karta är en zonotop som begränsar det gemensamma området för storheterna $X_{1},X_{2},$$\dots ,$$X_{m}$ . Man skulle alltså kunna säga att AA är en "zonotoparitmetik". Varje steg i AA innebär vanligtvis att man lägger till ytterligare en rad och ytterligare en kolumn till matrisen A .

Affin formförenkling

Eftersom varje AA-operation i allmänhet skapar en ny symbol ${\displaystyle \epsilon _{k}} ,$ kan antalet termer i en affin form vara proportionell mot antalet operationer som används för att beräkna det. Därför är det ofta nödvändigt att tillämpa "symbolkondenseringssteg", där två eller flera symboler $\epsilon _{k}$ ersätts med en mindre uppsättning nya symboler. Geometriskt innebär detta att man ersätter en komplicerad zonotop P med en enklare zonotop Q som omsluter den. Denna operation kan göras utan att förstöra första ordningens approximationsegenskap för den slutliga zonotopen.

Genomförande

Matrisimplementering

Affin aritmetik kan implementeras av en global matris A och en global vektor b , såsom beskrivits ovan. Detta tillvägagångssätt är tämligen adekvat när mängden kvantiteter som ska beräknas är liten och känd i förväg. I detta tillvägagångssätt måste programmeraren externt upprätthålla överensstämmelsen mellan radindexen och kvantiteterna av intresse. Globala variabler innehåller antalet m affina former (rader) som hittills beräknats och antalet n symboler (kolumner) som hittills använts; dessa uppdateras automatiskt vid varje AA-operation.

Vektor implementering

Alternativt kan varje affin form implementeras som en separat vektor av koefficienter. Detta tillvägagångssätt är mer praktiskt för programmering, särskilt när det finns anrop till biblioteksprocedurer som kan använda AA internt. Varje affin form kan ges ett mnemoniskt namn; det kan tilldelas när det behövs, skickas till procedurer och återkrävs när det inte längre behövs. AA-koden ser då mycket närmare den ursprungliga formeln. En global variabel innehåller antalet n symboler som hittills använts.

Gles vektorimplementering

På ganska långa beräkningar är uppsättningen av "live" kvantiteter (som kommer att användas i framtida beräkningar) mycket mindre än uppsättningen av alla beräknade kvantiteter; och dito för uppsättningen "live"-symboler $\epsilon _{j}$ . I den här situationen är matris- och vektorimplementeringarna för slöseri med tid och utrymme.

I sådana situationer bör man använda en sparsam implementering. Varje affin form lagras nämligen som en lista med par (j, $x_{j}$ ), som endast innehåller termer med koefficient som inte är noll $x_{j}$ . För effektivitetens skull bör termerna sorteras i ordningen j . Denna representation gör AA-verksamheten något mer komplicerad; kostnaden för varje operation blir dock proportionell mot antalet termer som inte är noll som förekommer i operanderna, istället för antalet totala symboler som hittills använts.

Detta är representationen som används av LibAffa.

• LH de Figueiredo och J. Stolfi (2004) "Affin aritmetik: begrepp och tillämpningar." Numeriska algoritmer 37 (1–4), 147–158.
• JLD Comba och J. Stolfi (1993), "Affin aritmetik och dess tillämpningar för datorgrafik". Proc. SIBGRAPI'93 — VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens (Recife, BR) , 9–18.
• LH de Figueiredo och J. Stolfi (1996), "Adaptiv uppräkning av implicita ytor med affin aritmetik". Computer Graphics Forum , 15 5 , 287–296.
• W. Heidrich (1997), "En sammanställning av affina aritmetiska versioner av vanliga matematiska biblioteksfunktioner". Teknisk rapport 1997-3, Universität Erlangen-Nürnberg.
• M. Kashiwagi (1998), "En algoritm för alla lösningar som använder affin aritmetik". NOLTA'98 — 1998 Internationellt symposium om icke-linjär teori och dess tillämpningar (Crans-Montana, Schweiz), 14–17.
• L. Egiziano, N. Femia och G. Spagnuolo (1998), "Nya tillvägagångssätt för den verkliga värsta tänkbara utvärderingen i kretstolerans- och känslighetsanalys - Del II: Beräkning av den yttre lösningen med affin aritmetik". Proc. COMPEL'98 — 6:e workshopen om dator i kraftelektronik (Villa Erba, Italien), 19–22.
• W. Heidrich, Ph. Slusallek och H.-P. Seidel (1998), "Sampling av procedurella shaders med affin aritmetik". ACM Transactions on Graphics , 17 3 , 158–176.
• F. Messine och A. Mahfoudi (1998), "Användning av affin aritmetik i intervalloptimeringsalgoritmer för att lösa flerdimensionella skalningsproblem". Proc. SCAN'98 — IMACS/GAMM International Symposium on Scientific Computing, Computer Aritmetic and Validated Numerics (Budapest, Ungern), 22–25.
• A. de Cusatis Jr., LH Figueiredo och M. Gattass (1999), "Intervallmetoder för strålgjutningsytor med affin aritmetik". Proc. SIBGRAPI'99 — 12:e brasilianska symposiet om datorgrafik och bildbehandling, 65–71.
• K. Bühler och W. Barth (2000), "En ny skärningsalgoritm för parametriska ytor baserad på linjära intervalluppskattningar". Proc. SCAN 2000 / Intervall 2000 — 9:e GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, ???–??? .
•   I. Voiculescu, J. Berchtold, A. Bowyer, RR Martin och Q. Zhang (2000), "Intervall och affin aritmetik för ytplacering av polynom i kraft- och Bernsteinform". Proc. Ytornas matematik IX , 410–423. Springer, ISBN 1-85233-358-8 .
•   Q. Zhang och RR Martin (2000), "Polynomial evaluation using affin aritmetic for curve drawing". Proc. av Eurographics UK 2000 Conference , 49–56. ISBN 0-9521097-9-4 .
• D. Michelucci (2000), "Tillförlitliga beräkningar för dynamiska system". Proc. SCAN 2000 / Intervall 2000 — 9:e GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics, ???–??? .
• N. Femia och G. Spagnuolo (2000), "True worst-case circuit tolerance analysis using genetisk algoritm och affin aritmetik — Del I". IEEE Transactions on Circuits and Systems , 47 9 , 1285–1296.
•   R. Martin, H. Shou, I. Voiculescu och G. Wang (2001), "En jämförelse mellan Bernsteins skrov och affina aritmetiska metoder för algebraisk kurvritning". Proc. Osäkerhet i geometriska beräkningar , 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X .
•   A. Bowyer, R. Martin, H. Shou och I. Voiculescu (2001), "Affina intervaller i en CSG geometrisk modellering". Proc. Uncertainty in Geometric Computations , 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X .
• T. Kikuchi och M. Kashiwagi (2001), "Eliminering av icke-existensregioner av lösningen av olinjära ekvationer med affin aritmetik". Proc. NOLTA'01 — 2001 Internationellt symposium om icke-linjär teori och dess tillämpningar .
• T. Miyata och M. Kashiwagi (2001), "Om intervallutvärdering av polynom av affin aritmetik". Proc. NOLTA'01 - 2001 Internationellt symposium om icke-linjär teori och dess tillämpningar .
• Y. Kanazawa och S. Oishi (2002), "En numerisk metod för att bevisa existensen av lösningar för icke-linjära ODEs med affin aritmetik". Proc. SCAN'02 — 10:e GAMM-IMACS internationella symposium om vetenskaplig beräkning, datoraritmetik och validerad numerik .
• H. Shou, RRMartin, I. Voiculescu, A. Bowyer och G. Wang (2002), "Affin aritmetik i matrisform för polynomutvärdering och algebraisk kurvritning". Progress in Natural Science , 12 1 , 77–81.
• A. Lemke, L. Hedrich och E. Barke (2002), "Analog kretsstorlek baserad på formella metoder med affin aritmetik". Proc. ICCAD-2002 — Internationell konferens om datorstödd design , 486–489.
• F. Messine (2002), "Extensions of affin aritmetic: Application to unconstrained global optimization". Journal of Universal Computer Science , 8 11 , 992–1015.
•   K. Bühler (2002), "Implicita linjära intervalluppskattningar". Proc. 18:e vårkonferensen om datorgrafik (Budmerice, Slovakien) , 123–132. ACM Press, ISBN 1-58113-608-0 .
• LH de Figueiredo, J. Stolfi och L. Velho (2003), "Approximering av parametriska kurvor med remsor med affin aritmetik". Datorgrafikforum , 22 2 , 171–179.
• CF Fang, T. Chen och R. Rutenbar (2003), "Flytpunktsfelanalys baserad på affin aritmetik". Proc. 2003 International Conf. om akustisk, tal och signalbehandling .
• A. Paiva, LH de Figueiredo och J. Stolfi (2006), "Robust visualisering av konstiga atttraktorer med affin aritmetik". Computers & Graphics , 30 6 , 1020– 1026.

externa länkar

• [1] Stolfis sida om AA.
• [2] LibAffa, en LGPL-implementering av affin aritmetik.
  • libaffa på GitHub
• [3] ASOL, en gren-och-beskärningsmetod för att hitta alla lösningar på system av olinjära ekvationer med hjälp av affin aritmetik
• [4] YalAA, ett objektorienterat C++-baserat mallbibliotek för affin aritmetik (AA).
• kv på GitHub ( C++ -bibliotek som kan använda affin aritmetik)