Ren matematik, datamatematik och hur man kan lösa det olösliga

En betydande del av den nutida forskningen inom matematik använder datorer som hjälpmedel. Naturligtvis är användningen av datorer mest utspridd i tillämpad matematik och i statistik (bl.a. i form av Monte Carlo-metoder), men dataprogram kan även användas för att bevisa satser som känns väldigt teoretiska. Det mest välkända exemplet lär vara beviset på fyrfärgssatsen.

Datorer har dock ett antal begränsningar: man kan mekaniskt, genom att gå igenom fall ett för ett, bevisa något endast för ett ändligt antal fall. Beräkningar gjorda av en dator är dessutom inte exakta i alla fall. Detta beror på att det i de flesta fallen finns endast en begränsad mängd minne reserverat för decimaltal, och därmed tappar man i vissa fall precision då man utför beräkningar. Oftast är detta ej önskevärt, men i vissa specialfall kan man faktiskt utnyttja denna brist för att göra beräkningar som tekniskt sett inte borde vara möjliga!

Tänk dig att vi skulle i något sammanhang ha behov av en funktion som tar in två reella tal och ger som resultat dess summa, förutom om talen är lika. Ifall talen är lika ger den ut det ena av talen (vilket av dem spelar ingen roll eftersom de är lika). Uttryckt matematiskt är vi alltså intresserade av funktionen f\colon \mathbb{R}^2 \rightarrow \mathbb{R}, där

  • f(x, y) = x + y ifall x \neq y, och
  • f(x, y) = x ifall x = y.

På en dator kan ovanstående konstruktion i vanliga fall lätt implementeras med hjälp av en if-sats, men låt oss nu anta att vi av någon orsak inte kan använda oss av konditionaler. Istället måste vi uttrycka ovanstående funktion med hjälp av endast de fyra grundräknesätten. Först skulle vi säkert försöka skapa en multiplikation med noll i något skede för att få en av termerna att försvinna i fallet där de båda är lika:

x + (x-y)\cdot y \qquad \: (1).

Detta fungerar ifall x = y, men om x \neq y får vi x + xy - y^2, vilket vi inte ville. Vi borde alltså i fallet x \neq y lyckas få den tillagda överloppstermen x-y att försvinna. Ett sätt är att istället använda sig av formeln

x + \frac{x-y}{x-y} \cdot y \qquad \: (2).

Ifall x \neq y, så ger ovanstående formel det korrekta resultatet x + y. Tyvärr så fungerar den ej i fallet x = y, eftersom vi då stöter på problemet att dividera med noll.

Eftersom de första, mest uppenbara försöken att skapa formeln misslyckades, kan det löna sig att fundera en stund över orsaken på varför vårt tillvägagångssätt ej fungerade. Vi märker att funktionen f\colon \mathbb{R}^2 \rightarrow \mathbb{R} är definierad för alla par av reella tal. Därmed kan vi inte i något skede dela med ett uttryck som kan bli noll, eftersom vi då får till stånd ett par av reella tal där formeln ej är definierad.

Ifall vi undersöker funktionen f närmare märker vi även att den inte är kontinuerlig i hela \mathbb{R}^2. Problempunkterna är punkterna av typen (a,a) där a \neq 0. Om vi t.ex. slår fast x-koordinaten att vara 2, ser vi att det för gränsvärdena gäller att \lim\limits_{y \to 2^{+}} f(2,y) = \lim\limits_{y \to 2^{-}} f(2,y) = 4, men att f(2,2) = 2. Vårt mål var att beskriva funktionen f endast med hjälp av de fyra grundräknesätten. Det är välkänt att funktioner som är uppbyggda endast med hjälp av de fyra grundräknesätten är kontinuerliga i hela sin definitionsmängd. Därmed är det omöjligt att beskriva funktionen f endast med hjälp av grundräknesätten eftersom funktionen inte är kontinuerlig!

Det verkar alltså som vi skulle ha kört fast, eftersom det rent matematiskt är omöjligt att lösa problemet, givet de verktyg vi har. Detta är dock ett av de fall där vi kan utnyttja de begränsningar som datorer ställer på beräkningar av decimaltal. I vanliga fall beskrivs decimaltal av en dator på följande sätt:

signifikand \cdot bas^{exponent}.

Eftersom varje decimaltal ges en konstant mängd utrymme i datorns minne, finns det en gräns på storleken på signifikanden (dvs. hur många signifikanta siffror talet kan ha) och även en gräns på hur stor exponenten kan vara. Detta leder till att datorn kan representera tal som är nära noll mycket noggrant, medan precisionen (absolut sett) blir allt mindre ju större talet är. Ifall vi som exempel slår fast basen att vara 10 och antalet signifikanta siffror att vara 10 och jämför exponenterna -20 och 20, ser vi att vi kring talet 10^{-20} kan representera skillnader av storleksordningen 0.000000001 \cdot 10^{-20} = 10^{-11}, medan vi kring talet 10^{20} endast kan representera skillnader av storleksordningen 0.000000001 \cdot 10^{20} = 10^{11}! Därmed om vi t.ex. skulle göra beräkningnen 10^{20} + 1 skulle resultatet vara 10^{20}, eftersom vi ej kan representera tal så noggrant kring 10^{20}.

Hur kan vi då utnyttja detta fenomen för att lösa vårt ursprungliga problem? Vi hade tidigare skapat formeln (2), som fungerar bra förutom att vi kan tvingas dela med noll. För att undvika division med noll kan vi modifiera formeln på följande sätt:

x + \frac{x-y}{(x-y) + \varepsilon} \cdot y \qquad \: (2′),

där \varepsilon är ett till absolutbeloppet mycket litet positivt tal (storleken på talet beror på representationen av decimaltalen). Matematiskt sett gäller naturligtvis inte att (x-y) + \varepsilon = x-y, men p.g.a. bristerna i decimaltalsberäkningen kommer likheten att gälla ifall x och y är olika och är tillräckligt stora. Kvoten \frac{x-y}{(x-y) + \varepsilon} är alltså 1 ifall x \neq y, och därmed uppfyller formeln (2′) kravet att f(x,y) = x + y om x \neq y.

Å andra sidan ifall x = y, så är naturligtvis x - y = 0 och därmed är 0 + \varepsilon = \varepsilon, eftersom vi kan representera tal noggrant kring noll. Därmed undviker vi division med noll och kvoten \frac{x-y}{(x-y) + \varepsilon} blir 0. Alltså gäller det för formeln (2′) även att f(x,y) = x ifall x = y.

Vi har alltså lyckats trolla fram en formel som med hjälp av datorberäkningar löser ett matematiskt sett omöjligt problem. Dock har formeln sina begränsningar; t.ex. får talen x och y ej vara för små, för då skulle additionen av talet \varepsilon påverka det slutliga resultatet som formeln (2′) ger. I de flesta fallen är precisionsproblemen i decimaltalsräkningen något man försöker undvika (se t.ex. Wikipedia-artiklen om ämnet), men i vissa fall kan man faktiskt dra nytta av dem. Det är bra att komma ihåg att begränsningar som datorer ställer inte alltid är endast negativa; i vissa fall kan vi p.g.a. begränsningarna lösa problem som annars vore olösliga.

Jag vill till sist tacka Lasse för idén till artikeln! Den som är intresserad att lära sig mer om ämnet kan börja t.ex. med Wikipedia-sidan IEEE floating point.

 

Sebbe

Lämna ett svar

Din e-postadress kommer inte publiceras.