CS Challenge 9, Error Calculation

Usikkerheder i beregninger på computer eller lommeregner har flere forskellige kilder:

I denne Challenge ser vi på, hvordan man kan holde styr på disse usikkerheder ved hjælp af intervalaritmetik. Her repræsenteres et tal som et interval [a,b], hvor a er en garanteret nedre grænse og b en garanteret øvre grænse for den faktiske værdi. Fx kan 1/3 repræsenteres som:

[0.333333333333,0.333333333334]
og tallet π som:
[3.14159265358,3.14159265359]
I intervalaritmetik generaliserer man alle regneoperationer til sådanne intervaller.
Helt konkret benytter vi Usikkerhedsløseren, der er en lommeregner tilpasset til intervaller. Den har to displays: det grønne vil altid indeholde en sund nedre grænse og det blå en sund øvre grænse. Indmaden af dette program kan ses i Error.java.

Usikkerhedsløseren implementerer helt nøjagtigt en decimal lommeregner med 12 betydende cifre (uden Scientific Notation). Forskellen fra en almindelig lommeregner er, at den altid med de to displays vil vise den præcise usikkerhed på den beregnede værdi.


Usikkerheder ved beregninger er subtile og vanskelige at overskue i hovedet. Mange programmører ignorerer dem, hvilket kan få fatale konsekvenser i form af unøjagtige eller sågar meningsløse resultater.
De fire regnearter generaliseres som følger:
[a,b]+[c,d] = [a+c,b+d]
[a,b]-[c,d] = [a-d,b-c]
[a,b]*[c,d] = [min{a*c,a*d,b*c,b*d},max{a*c,a*d,b*c,b*d}]
[a,b]/[c,d] = [a,b]*[1/d,1/c]
Efter en beregning skal resultatet i alle tilfælde repræsenteres i lommeregnerens talsystem, hvilket sker ved at transformere et interval [a,b] til [floor12(a),ceil12(b)], hvor de to funktioner finder det nærmeste lavere henholdsvis højere tal, der kan repræsenteres.

De fleste andre operationer på lommeregneren kan bestemmes ud fra to observationer. Hvis en funktion f er monotont voksende, så er:

f([a,b]) = [f(a),f(b)]
og hvis den er monotont aftagende, så er:
f([a,b]) = [f(b),f(a)]
Udnyttelsen af dette kan ses i klassen Interval i Error.java.

Lommeregneren er konservativ i forhold til mulige fejl, fx vil den gå i en fejltilstand, hvis man tager kvadratroden af et interval der indeholder et negativt tal, dividerer med et interval der indeholder tallet 0, eller hvis absolutværdien af et endepunkt i intervallet overstiger 12 decimale cifre.


Spørgsmål A

Lige potensfunktioner, som kvadrering, er lidt mere specielle. Vis med et eksempel, at x2 kan være mere præcis end x*x. Forklar, med udgangspunkt i metoden square i klassen Interval, hvorfor dette er tilfældet.
Alle, der har lavet fysikrapporter, har lært lidt om usikkerheder ved beregninger, fx at et resultat ikke kan angives med flere betydende cifre end argumenterne. Dette er et sundt princip, men virkeligheden er ofte meget værre. Antag, at vi har opmålt en swimming pool. Længden har vi fået til 14 meter ± 2 cm, bredden til 8 meter ± 2 cm, og dybden (der er lidt vanskeligere at måle) til 3 meter ± 5 cm. Hvor stor bliver nu usikkerheden, når vi beregner rumfanget? På Usikkerhedsløseren bliver regnestykket:
[13.98,14.02]*[7.98,8.02]*[2.95,3.05] = [329.103180000,342.943220000]
Vi har dermed reelt kun et enkelt betydende ciffer tilbage, selvom måleusikkerhederne måske ikke virker så slemme hver for sig.

Som et større eksempel kan man se en fysikrapport fra gymnaiset uden og med brug af Usikkerhedsløseren. Når usikkerhederne regnes med, skifter resultaterne fra succesfulde til meningsløse.


Beregninger kan også generere store usikkerheder, selv om vi kender argumenterne eksakt. Betragt andengradsligningen:
x2+200x-0.000000015 = 0
Den kan løses med den sædvanlige formel, og koden for dette kan ses i main metoden i Error.java, der jo også kan bruges som et programmeringssprog for intervalaritmetik. De to løsninger, der beregnes, er:
x1 = [-200.000000002,-200.000000000]
x2 = [0.000000000000,0.000000000500]
Den første er meget præcis, men den anden er rigtig dårlig - uden et eneste korrekt ciffer. Problemet er, at den anvendte formel ikke er numerisk stabil. Hvis vi i stedet benytter, at den anden rod kan findes som:
x2 = c/x1 = [0.000000000074,0.000000000075]
så har vi også en præcis værdi for denne. Hvis vi ikke brugte intervaller, ville vi måske have endt med at stole på den meningsløse værdi.

Det er i praksis ofte nødvendigt at omskrive regneudtryk til algebraisk ækvivalente former, der giver bedre numeriske resultater.


Spørgsmål B

Beregn udtrykket:
1/((355/113)-π)
på lommeregneren. Kommenter usikkerheden på resultatet. Omskriv udtrykket til en algebraisk ækvivalent form, der giver et mindre usikkert resultat (et mere snævert interval).
Generelt at programmere beregninger, så man er bevidst om at minimere usikkerhederne er forskningsområdet Numerisk Analyse.

Spørgsmål C

Koden i Error.java er ikke helt komplet. Udfyld kroppene til metoderne sin og cos i klassen Interval, så de beregner intervaludgaverne af sinus og cosinus (med argumenter i grader). Hint: overvej, hvordan graferne for disse funktioner ser ud, inden du laver den "oplagte" løsning. Hint: de to minder meget om hinanden.
BlueJ version: ErrorBlueJ.zip.
Du deltager i vores Challenge ved senest den 9. oktober at sende en e-mail til mis@cs.au.dk med subject Challenge 9 og svarene på spørgsmål A, B og C (i plain text) og koden til spørgsmål C i form af et attachment med en ny udgave af programmet Error.java.