Számítás garantált pontossággal II.

A számítógépeken használt eljárásoknak vannak olyan problémái, amik extrém esetben az eredményeket teljesen használhatatlanná tehetik. Ezt a technika jelenlegi fejlettségi fokán már többé nem kell eltűrnünk. Kifinomult eljárások a számítási eredményeket egy matematikai bizonyítás bizonyosságával tudják előállítani. A dupla cikk második része a skalárszorzással mint az ötödik alapművelettel, az intervallum-aritmetikával és hatékony iterációval foglalkozik.

A skalárszorzás: az ötödik alapművelet

A kivágási probléma megoldása az lenne, hogy minden számítást csak egy 600 decimális jegyes fixpontos számmal kell megoldani? Semmi esetre sem: ágyúval lőnénk verébre. A szorzás és az osztás eredményei pusztán a hosszú regiszter használata miatt nem lesznek jobbak; csak az összeadás és a kivonás a kritikus művelet. A közelebbi vizsgálatok során egyetlen  összetett  művelet adódik, amelynél az ágyú nemcsak hogy megfelelő eszköz, hanem a szokásos problémák nagy részét meg is oldja: ez a két vektor skalárszorzata.
Ez a művelet központi jelentőségű az egész numerikus matematikában. Nagy egyenletrendszerek megoldása végül is gyakorlatilag mindig a skalárszorzat többféle alkalmazására vezethető vissza. A művelet sok  1000 darab nem ritka  szorzat összeadásából áll, amelyek egyenként két-két lebegőpontos szám összeszorzásából adódnak. Ezen szorzatok nagyságrendje általában alig becsülhető. Emiatt sokat segít, hogy a hosszú regiszterben ezek összeadása (az ún. akkumulálás) mindenféle kerekítés nélkül történik (séma alul). Csak a teljes összeget kerekítjük, hogy a további számítás lebegőpontos formátumban történhessen. 
Elméletileg a hosszú fixpontos regiszter a szokásos hardverrel realizálható. A 600 számjegyet, amiből egy hosszú fixpontos szám áll, osszuk szét megfelelő hosszúságú részsorozatokra, és ezek mindegyikét tároljuk egy hagyományos fixpontos számban. Minden ilyen tárolóegység helye a hosszú számon belül rögzített; csak arról kell gondoskodni alkalmas programozással, hogy a lebegőpontos számot ennek a hosszú számnak a megfelelő pozíciójához adjuk.
Bár egy így összerakott (emulált) hosszú regiszter olyan hibamentesen működik, ahogy azt az elmélet állítja, mégis a gyakorlat számára nem alkalmas. A számítási munka a különben szükséges idő többszörösét igényli, úgy hogy egy felhasználó inkább a hagyományos, de sokkal gyorsabban megkapható eredményre szavazna.
Egy modern processzorban a lebegőpontos összeadás annyira optimalizált, hogy sokkal gyorsabban lehet végrehajtani, mint bármely logikailag ekvivalens, de explicit programozással kapott (azaz több egyedi utasításból összetett) alternatíváját. Emiatt kerül a már szoftverben megvalósított négyszeres pontosságú aritmetika közel négyszer annyi időbe, mint a konvencionális. Ha azonban az akkumulációt a hosszú fixpontos regiszterbe „bedrótozzuk”, a lapkába beépítjük, akkor a növelt pontosságot időveszteség nélkül kaphatjuk meg.
A Karlsruhei Egyetemen Kulisch professzor intézetének egy munkacsoportja, a Hamburg-Harburgi Műszaki Egyetem Informatikai Intézete és Stuttgarti Egyetem Mikroelektronikai Intézete 1995-ben egy ilyen mikrochipet fejlesztett ki: az XPA3233 vektoraritmetika-processzort. Ezzel egyidőben a szokásos programozási nyelveket is átírták, amikkel aztán a processzor új tulajdonságai kihasználhatók: ilyenek a PASCAL-XSC, C-XSC és Fortran-XSC. A fent említett szoftver-implementációval szemben a lapka százszoros számítási sebességet ért el, és ezzel megelőzte a négyszeres pontosságú aritmetikát mind minőségben, mind gyorsaságban.
A nagypontosságú aritmetika eredményei helyenként látványosak. Alfons Ams és Wolfram Klein a karlsruhei intézetben meghatározták a forgó turbina kilengéseit. Míg a hagyományos számítás a magasabb fordulatszám tartományban a sajátfrekvenciák szaporodását találja, a nagypontosságú aritmetika azt adja, hogy az állítólagos sajátfrekvenciák egy kivételével a számítási pontatlanságra vezethetők vissza, tehát a turbina ilyen fordulatszámon is biztonságosan üzemeltethető (ábra balra fenn).

1. Ábra. Egy turbina sajátfrekvenciái (felül egy keresztmetszet) egy f függvény zérushelyei, amelyhez egy sor trigonometrikus függvényt és számos skalárszorzást kell kiértékelni. A szokásos lebegőpontos számítással szemben (alul feketével) a nagypontosságú aritmetika (piros) a  garantált  információt adja, és így a turbina nagy fordulatszámon biztonságosan üzemeltethető. 

Az ábra feliratában: f sajátértékfüggvény; fordulatszám, ezer fordulat percenként.

Intervallum-aritmetika

Az is lehetséges, hogy ezt az eredményt olyan szintű garanciával mondhassuk ki, mint amilyenek a matematikai bizonyítások. A modern processzorokban a négy alapműveletet olyan alaposan implementálták, hogy a kerekítési hiba olyan kicsi, amilyen csak lehet az adott körülmények között, azaz legfeljebb egy fél helyiértéknyi az utolsó pozíción. Miután a skalárszorzás akkumulálásával egy jelentős pontosságot rontó tényezőt hatástalanítottunk, egy régi jó elv juthat megérdemelten érvényre: az intervallumokkal való számítás.
Amikor egy hosszabb számításhoz való kiindulási értékek mért adatok, akkor ezek természetükből adódóan bizonyos pontatlansággal rendelkeznek. Például ha egy hosszúságot 1.075 ± 0.002 miliméternek mérünk, akkor szokás az 1.075 számmal tovább számolni, mintha ez pontos lenne, és ignorálni azt, hogy a mérési hiba a teljes számításon végigvonul. Közben legalábbis elméletileg egyszerű a hibát végig követni a teljes eljárásban: nem csak egy számmal kell számolnunk, hanem egész intervallumokkal. Egy intervallumot az alsó és felső határa definiál: a fenti példában a mérési adatnak az [1,073, 1,077] intervallum felel meg. Bár ez a megadás lazább, mint a — látszólag — pontosabb 1,075 érték; de így azt a bizonyosságot nyertük, hogy a mérési érték az intervallum belsejébe esik. 
Ezt az elvet átvisszük a teljes számítási menetre. A továbbiakban nem egy számot adunk meg, ami — remélhetőleg — körülbelül egyenlő a számítás valódi eredményével, hanem egy olyan intervallumot, amelyben az eredmény bizonyosan benne van. Ha két a és b számot az [a1, a2] és az [b1, b2] intervallumokkal ábrázolunk, akkor az összeg biztosan az [a1+b1, a2+b2] intervallumban van. Itt az első összeadást lefelé, a másodikat felfelé kerekítéssel kell végrehajtani (ezeket a műveleteket szokás külön jelekkel is kiemelni). Analóg módon definiáljuk az intervallumok kivonását, szorzását és osztását is. 
Az elmélet továbbfejlesztése során aztán az intervallumok öntörvényű matematikai objektumokká válnak: az intervallumokkal való számolás matematikai törvényeit ismerjük fel, az intervallum fogalmát több dimenzióra általánosítjuk, — egy kétdimenziós intervallum egy téglalap, egy háromdimenziós egy téglatest, megfelelő objektumok léteznek magasabb dimenziós terekben is — és mindenek előtt olyan programozási nyelveket írunk, amely egy intervallumot egyetlen névvel jelöl, úgy mint különben a számokat. A klasszikus programozási nyelvek, mint a Fortran, Pascal, C fent említett kibővítései rendelkeznek ezzel a lehetőséggel. A programozó tehát ugyanolyan formula jellegű utasításokat adhat intervallumokkal való számolásra, mint különben a számokkal.
Az intervallumokkal való számolás koncepciója tehát kézzelfogható előnyöket kínál — és ennek alapjai évtizedek óta ismertek: Az ötletet először a japán matematikus Teruo Sunaga publikálta 1958-ban; 1967-ben Karlsruhéban már futott egy megfelelően kibővített Algol-60 programozási nyelv Zuse Z23-as számítógépén. Mégis az intervallum-aritmetika eddig nem terjedt el általánosan.
Túlságosan lassú, vetik ellen a kritikusok, és gyakran túl pesszimista abban az értelemben, hogy túl nagy intervallumokat ad meg, és így az eredményeknek sokkal nagyobb bizonytalanságot tulajdonít, mint ami a valóságnak megfelel. Sokszor az a hosszú és fáradságos számítás eredménye, hogy a megoldás - és + között van, amit amúgy is tudtunk.
Az első érv találó — legalábbis a jelen helyzetre, de nem az elvre. Az intervallumos számolás lassú, mert eddig — kényszerhelyzetben — olyan gépeken hajtjuk végre, amelyeket nem kifejezetten erre terveztek. Így már csak a kerekítési módok beállítása is sok időt visz el, mert ez a ma csaknem kizárólagosan követett IEEE-standardban a tényleges művelettől el van választva; persze a szokásos aritmetikában alig használják. Egy megfelelően megtervezett processzor, amely még a két végpontot is párhuzamosan számítja, ugyanolyan gyors intervallumokon, mint szokásos számokkal.
A második érv az intervallum-aritmetika naiv alkalmazásaira érvényes. Ha egy f függvényt az X = [a, b] intervallumra értékelünk ki, szintén egy intervallumot kapunk, amit aztán f(X)-el jelölünk, és ami minden a és b közötti x-re f(x)-et tartalmazza — de lehetőség szerint mást nem. Amikor az intervallum nagy, és az f függvényt ügyetlenül értékeljük ki, akkor valóban tekintélyesen túlbecsült intervallumot kaphatunk. Két számítási eljárás, amelyek számokra egyenértékűek, intervallumokra alkalmazva ugyanis teljesen más eredményeket adhatnak. De az elmélet megad egy olyan eljárást (az ún. középponti alakot), amely a túlbecslést minimálissá teszi.
Ezen túl mindig megvan a lehetőség egy intervallumot részintervallumokra bontani — ez a numerikus matematikában gyakori megoldás. Az említett optimális számítási móddal a túlbecslés még gyorsabban csökken, mint a részintervallumok mérete.
Általában arról van szó, hogy egy feladat több megoldása közül egy olyant találjunk, amely esetén az intervallumos számítás az erejét meg tudja mutatni. Ez a megoldási mód gyakran nem a különben is szokásos. Így egyes egyenletrendszerekre vannak explicit megoldó algoritmusok: olyan számítási lépéssor, amely egy előre adott véges számú lépés után a pontos megoldást szolgáltatja — ha tudnánk pontosan számolni. Ritkán fordul elő, hogy ilyen algoritmus rendelkezésre áll; többnyire csak iteratív eljárások vannak (lásd keretes írás), tehát olyanok, amelyek egy közelítő megoldásból egy — remélhetően — jobbat tudnak adni.

2. Ábra. A „System Trinks” mechanikus asztali számológép a Brunsviga cégtől, amely hosszú eredményregisztert használ.

A Newton-eljárás intervallum-aritmetikával

Zseblámpa helyett reflektor

A klasszikus Newton-eljárás egy lépése egy xk számból egy másik számot, xk+1-et ad, amely remélhetően az f függvény keresett zérushelyéhez közelebb van, mint xk (lásd a keretes szöveget az első cikkben). Az eljárás intervallum-aritmetikás formája értelemszerűen az Xk intervallumból egy Xk+1 intervallumot ad, amely a zérushelyet lehetőleg még szorosabban tartalmazza mint Xk+1. A Newton-eljárás xk+1 = xk – f(xk)/f’(xk) képletét egyszerűen számok helyett intervallumokra alkalmazhatnánk. De ez nem célravezető. Ehelyett válasszunk egy mk pontot az Xk intervallum belsejében, például az Xk középpontját, és határozzuk meg az új intervallumot az Xk+1 = mk – f(mk)/f’(Xk) képlettel. Itt az f’(Xk) az az intervallum, amely az f’(x) deriváltfüggvénynek az Xk intervallumra való alkalmazásával adódik, tehát f’(Xk) tartalmazza a legkisebb és a legnagyobb olyan értéket is f’(x)-re, ami Xk-ban előfordul. 
Míg a klasszikus Newton-eljárás egy fénysugárnak felel meg, amit az érintő irányában küldünk, és megkeressük, hogy hol találkozik az x tengellyel, addig az intervallumos Newton-eljárás széles fénynyalábbal dolgozik: megmutatja, hogy az adott pontból az x tengely mely pontjai érhetők el akkor, ha minden olyan érintőirányt figyelembe veszünk, amely Xk-ban előfordul. Egy kevés elmélet biztató világos kijelentést ad: Ha az Xk intervallumban már benne volt egy zérushely, akkor a fénynyaláb is el fogja találni. A megfordítás szerint tehát ha Xk–nak és Xk+1–nek nincs közös pontja, akkor ezzel bizonyított, hogy Xk-ban nincs zérushely, és ott a keresést befejezhetjük. Minden esetre elegendő Xk és Xk+1 metszetével tovább számolni, mivel a zérushely mindkettőben benne kell hogy legyen. Többnyire Xk+1 benne van Xk-ban, és lényegesen kisebb, mint elődje.
Az intervallumos Newton-eljárás különösen olyan helyzetben mutatja meg előnyeit, amikor a klasszikus Newton-eljárás eredményessége kétséges: nevezetesen amikor a függvény f’(xk) deriváltja a nulla közelébe kerül. Ez a helyzet egy nagyon lapos érintőnek felel meg. Annak zérushelye tehát nagyon távol esik, úgy hogy az eljárás bizonyos körülmények között hamis eredményre vezet.
Ez a probléma rendszeresen fellép akkor, amikor a függvény két zérushelye közel esik egymáshoz. Az egyik zérushelytől a függvény a másikig először nő, majd csökken, vagy fordítva. Minden esetre közben van egy horizontális érintője. Ebben a pontban f’(x) = 0, és ennek közelében a klasszikus Newton-eljárás könnyen hibázik. 
Az intervallum-aritmetika esetén ebben a helyzetben egy olyan intervallummal kell osztani, ami nullát tartalmaz. Ez a művelet a valós nullával való osztással ellentétben nem tiltott, csak az eredményhez hozzá kell szokni: ha x a [-0,5, 0,4] intervallumba esik, akkor 1/x vagy kisebb mint –2, vagy nagyobb, mint 2,5. Egy osztás eredménye két intervallumból áll: ]- , -2], illetve [2,5, +[.
Az intervallumos Newton-eljárás egy lépése során tehát ebben a speciális esetben egy intervallumból kettő lesz, amelyek ráadásul a végtelenig nyúlnak. Ez az első pillantásra nagy rosszabbodás. De van még az eredeti intervallum, amelyben a függvénynek bizonyosan legalább egy zérushelye benne kellett hogy legyen. A zérushelyek tehát mind a hagyományos, mind a kiterjesztett intervallumban benne vannak, amely egy szakasz kivételével minden valós számot tartalmaz. Tehát két szokásos intervallum marad. Általában ezek mindegyike egy zérushelyet tartalmaz, amelyeket aztán egyenként lehet megkeresni. 
 A közeli zérushelyek elkülönítése, ami a klasszikus Newton-eljárás számára a legnehezebbek egyike, intervallum-aritmetikával automatikusan megoldódik.

3. Ábra. Az X1 = [1,4, 3,4] intervallumból (zöld), amely az f függvény egy zérushelyét tartalmazza, az intervallumos Newton-eljárás a következő X2 intervallumot úgy határozza meg (piros), hogy az X1 intervallum m1 középpontját minden, X1-ben előforduló meredekséggel levetíti. A továbbiakban csak a két intervallum metszetével kell számolni.
 
4. Ábra. Ez a példa az X1 = [-0,4, 2,4] intervallum (zöld) a derivált egy zérushelyét tartalmazza; emiatt áll az X2 intervallum két részből, amelyek a - , illetve a +  felé tartanak. A továbbiakban azonban nem kell végtelen hosszú intervallumokkal számolni: X1 és X2 metszete két szokásos intervallumból áll, amelyek mindegyike egy-egy zérushelyet tartalmaz.

Inkább egy jó iterálás, mint egy rossz egzakt módszer 

Úgy tűnik, mintha egy iteratív eljárás csak szükségmegoldás lenne, amihez csak akkor nyúlunk, ha explicit módszer nem áll rendelkezésre. Azonban az explicit eljárások a hiba továbbterjedésével terheltek, ami a hiba növekedését is jelentheti. Kedvezőtlen körülmények között az intervallum aritmetika megoldásként egy használhatatlanul nagy intervallumot adhat (és a hagyományos számítás egy durván hibásat, anélkül hogy észrevennénk). Ezzel szemben az iteratív eljárásokat úgy alakítják ki, hogy azok a megoldást tartalmazó intervallumot általában csökkentsék: ha nem ezt tennék, egyáltalán nem működnének. Tehát van az eljáráson belül egy olyan mechanizmus, amely az intervallumok növekedése ellen hat. Ennek segítségével az intervallumos számítás azt a nagyobb pontatlanságot (illetve nagy, semmitmondó intervallumot), amely hosszabb kalkuláció során kialakult, ismét leépítheti.
Sajnos az iterációs eljárások nem mindig csökkentik az intervallumokat (nem kontrahálók). Inkább az fordul elő, hogy egy iterációs lépés nem csak átmenetileg téves irányba halad, hanem egy intervallumot is lényegesen megnagyobbít. A hagyományos aritmetika ekkor veszít a pontosságból, anélkül, hogy észrevennénk; az intervallum-aritmetika ezzel szemben az eddig elértet nem kell, hogy feladja. Az eddigi intervallum bizonyossággal tartalmazza a megoldást, az újonnan számított, nagyobb szintén: tehát átlagos esetben a megoldás a két intervallum metszetében van. Így az intervallumos módszer még információt is nyer ebből a helyzetből, amely különben az eljárás kudarcát jelenthetné (keretes szöveg). Az intervallum-aritmetika nyilvánvalóan jobban alkalmas akkor, ha valójában nem számot, hanem intervallumot keresünk. Például amikor van egy f(x) függvényünk, amely túl bonyolult ahhoz, hogy elméleti eszközökkel kezeljük, és azt szeretnénk tudni, hogy egy tartomány minden x értékére nagyobb-e mint nulla. (Például f(x) = 0 egy veszélyes helyzetnek felel meg, vagy a rendszer összeomlását jelenti.) 
Általában az f(x)–et sok helyen kiértékelnénk, habár a konkrét függvényértékek nem érdekelnek bennünket. Amikor a kiértékelési helyek sűrűn helyezkednek el, a függvényértékek minden ilyen helyen pozitívok, és a szomszédos helyeken nem mutatnak túl nagy ugrást, akkor nagyon is készek lennénk a pontokat egy sima, interpoláló görbével összekötni — de ez hamis lehet. A valódi görbének minden további nélkül lehet egy lelógó része (ábra fenn). Ezzel szemben az intervallumos számítás esetleg már egy kiértékelés után megadja, hogy f-nek a tekintett intervallumban nincs zérushelye.
A klasszikus analízis egy központi eljárása közelebbről megvizsgálva úgy működik, mintha az intervallum-aritmetika számára találták volna ki: a függvényeknek a Taylor polinomokkal való közelítése. Szinte minden jelentősebb függvény értékeit nagy pontossággal lehet közelítőleg meghatározni, éspedig olyan módon, amely csak összeadásokat és szorzásokat igényel. Mindenekelőtt azonban az approximációs hiba, tehát a valódi és a közelítő érték különbsége, megadható. Ez egy kis szám megszorozva egy bizonyos deriváltértékkel egy olyan helyen, ami szintén megadható intervallumban van.
Az elmélet tehát megad egy intervallumot a hibára, az intervallum-aritmetikának csak ki kell ezt számítania. Ugyanakkor ehhez egy magasrendű deriváltat kell kiértékelni. Ezt nehéz kézzel implementálni; de van már olyan módszer, az „automatikus differenciálás”, amellyel a programozó ezt a munkát a számítógépre bízhatja.
Ezzel az intervallum-aritmetikára egy hasonló kép alakul ki, mint a nagypontosságú számításra: egyik sem tud egyedül fejlődni egy olyan világban, amelyben minden másféle számítási módra van beállítva. Bár kölcsönösen támogatják egymást, de teljes kibontakozásukhoz mind illeszkedő hardverre, mind megfelelő elméletre és arra támaszkodó szoftverre is szükség van.
Az XPA 3233 lapka mégis jó példa ezen koncepciók működőképességére. Mint a gyakorlati alkalmazások számítási eszközét már meghaladta a gyorsan fejlődő technológia. A piacképességig való továbbfejlesztéséhez hiányzott annak idején az anyagi támogatás.
Mégis, John Gustafson, egy jelentős amerikai számítógépes szakember nemrég felhívást tett közzé, ráirányítva a figyelmet a garantált számítási eredményekre, és az intervallum-aritmetikára. Mindkét koncepció jövőjét illetően óvatos optimizmusra van okunk .

Irodalomjegyzék

Ulrich Kulisch: Advanced Arithmetic for the Digital Computer  Design of Arithmetic Units. Electronic Notes of Theoretical Computer Science, 1999. http://www.elsevier.nl/locate/entcs/volume24.html

John Gustafson: Computational Verifiability and Feasibility of the ASCI Program. IEEE Computational Science & Engineering 5 (1998) 36-45. 

Christoph Pöppe: Rechnen mit garantierter Genauigkeit. Spektrum der Wissenschaft, 2000 szeptember, 54-61.

A Spektrum der Wissenschaften nyomán