Oversikt

Dette temaet handler om at en datamaskin ikke regner eksakt: den bruker et endelig antall bits (typisk 64-bits flyttall med 53 signifikante bits i mantissen). Tall som ikke kan skrives som en endelig binærbrøk, for eksempel \(2/3\) eller \(0.1\), får en liten avrundingsfeil allerede når de leses inn. Eksamen kombinerer dette med differenslikninger: du skal først løse likningen eksakt, og deretter forklare hvordan små avrundingsfeil vokser ved iterasjon.

Binær representasjon

Et tall på formen \(a/2^k\) (en dyadisk brøk) kan lagres eksakt. Derfor er for eksempel \(3/8 = 3\cdot 2^{-3}\), \(1/4\) og hele tall eksakte, mens \(1/3\), \(2/3\) og \(0.1\) ikke er det. Hvis en rekursjon deler på en potens av to, for eksempel \(x_{n+2} = (12x_{n+1}-x_n)/32\) der \(32=2^5\), introduserer selve regneoperasjonen ingen ny avrundingsfeil.

Feilforplantning i differenslikninger

Selv når regnestykket er eksakt, vil en eksakt løsning som krever stadig flere signifikante bits til slutt rundes av. Et typisk mønster: hvis den eksakte løsningen er en sum av to ledd der det ene avtar mot null og det andre vokser, vil avrundingsfeil aktivere det voksende leddet. Da kan løsningen som maskinen regner ut, til slutt drives mot \(\pm\infty\) (overflow) eller bli NaN (uttrykk av typen \(\infty-\infty\)), selv om den eksakte løsningen er liten og veloppdragen.

Restleddet i Taylors formel

Restleddet \(R_n f(x) = f(x) - T_n f(x)\) kan begrenses med Lagranges form: \(|R_n f(x)| \le \frac{M_{n+1}}{(n+1)!}|x-a|^{n+1}\), der \(M_{n+1}\) er en øvre grense for \(|f^{(n+1)}|\) på intervallet. Dette brukes til å finne minste grad \(n\) som garanterer en ønsket nøyaktighet.

Eksempel: feilgrense for Taylorpolynom

La \(f(x)=\cos(x)e^{x}\) og finn minste \(n\) slik at \(\max_{x\in[-1/2,1/2]}|f(x)-T_n f(x)| \le 0{,}03\) om \(a=0\).

De fire første deriverte tilfredsstiller på intervallet \(|f^{(k)}(x)| \le 4e^{1/2}\) (en romslig grense). Da er \(|R_n f(x)| \le \frac{4e^{1/2}}{(n+1)!}(1/2)^{n+1}\). Vi prøvre:

\(n=2\): \(\frac{4e^{1/2}}{6}(1/8) \approx 0{,}137\) -- for stort.
\(n=3\): \(\frac{4e^{1/2}}{24}(1/16) \approx 0{,}017\) -- under \(0{,}03\).

Første \(n\) som garantert holder er \(n=3\). Poenget er å prøve seg oppover til ulikheten holder, ikke å finne den minste teoretiske \(n\).

Eksempel: avrundingsfeil i differenslikning

Likningen \(32x_{n+2}-12x_{n+1}+x_n=0\) med \(x_0=2, x_1=3/8\) har eksakt løsning \(x_n = 4^{-n}+8^{-n}\) (røttene er \(1/4\) og \(1/8\)). Maskinen regner \(x_{n+2}=(12x_{n+1}-x_n)/32\) eksakt fordi \(32=2^5\). Men \(4^{-n}+8^{-n}\) krever omtrent \(n+1\) signifikante bits, så når \(n\) blir stor nok overstiger dette de 53 tilgjengelige bitsene og leddet rundes av. Siden begge ledd avtar mot null, vil maskinen til slutt regne alt til 0 -- noe før den eksakte løsningen faktisk er null.

Studieguide: Tallrepresentasjon og feil

Studieguide: Tallrepresentasjon og feil