MAT-INF1100 · UiO

Studieguide for MAT-INF1100 Modellering og beregninger

Komplett pensumoversikt for modellering og beregninger ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

MAT-INF1100 Modellering og beregninger er et grunnemne ved Universitetet i Oslo som binder sammen kalkulus, numeriske metoder og programmering. Emnet handler om hvordan vi beskriver fenomener matematisk og løser dem -- både eksakt og ved hjelp av en datamaskin -- samtidig som vi forstår begrensningene som ligger i numerisk regning.

Eksamen varer fire timer og består av to deler. Del 1 er flervalgsoppgaver (totalt 30 poeng, typisk 10 oppgaver a 3 poeng) som tester rask og presis regning på Taylorpolynomer, interpolasjon, numerisk integrasjon, nullpunktsmetoder og differensiallikninger. Del 2 (totalt 70 poeng, syv delspørsmål) krever fulle begrunnelser, og inneholder nesten alltid et induksjonsbevis, en lineær differenslikning med numerisk drøfting, en numerisk derivasjons- eller integrasjonsoppgave, og en differensiallikning som skal løses eksakt og deretter tilnærmes med Eulers metode.

Denne studieguiden dekker alle de sentrale temaene i emnet, forankret i oppgavetypene som går igjen. Hver seksjon inneholder fagstoff, sentrale formler, vanlige feil og eksamenstips. Prioriter differensiallikninger, interpolasjon, numerisk integrasjon, induksjon og feilanalyse -- disse utgjør hoveddelen av poengene.

Tallrepresentasjon og feil

Eksamensrelevant

Hvordan tall lagres i flyttall (binært), avrundingsfeil, og hvordan slike feil forplanter seg når man simulerer differenslikninger på en datamaskin. Restleddet i Taylors formel brukes til å garantere feilgrenser.

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.

Nøkkelformler

•Lagranges restledd: $ $\displaystyle R_n f(x) = \frac{f^{(n+1)}(c)}{(n+1)!}(x-a)^{n+1}, \quad c \text{ mellom } a \text{ og } x$ $
•Feilgrense: $ $\displaystyle |R_n f(x)| \le \frac{M_{n+1}}{(n+1)!}|x-a|^{n+1}, \quad M_{n+1}=\max|f^{(n+1)}|$ $
•Eksakt i flyttall: tall på formen $a\cdot 2^{-k}$ (dyadiske brøker); 64-bits flyttall har 53 signifikante bits
•Maskinepsilon: relativ avrundingsfeil ved avrunding er $\le 2^{-53}\approx 1{,}1\cdot 10^{-16}$

Vanlige feil

⚠️Å lete etter den teoretisk minste n i feilgrenser i stedet for å prøve seg oppover med restleddsulikheten til den først holder.
⚠️Å tro at en rekursjon som deler på en potens av to gir avrundingsfeil -- den gjør ikke det; feilen kommer fra at løsningen krever for mange bits eller fra initialverdier som 2/3.
⚠️Å glemme at en initialverdi som 1/3 eller 0.1 ikke kan lagres eksakt, slik at feilen er der allerede før første iterasjon.
⚠️Å bruke feil M (maks av den deriverte) -- velg en gyldig øvre grense på hele intervallet, ikke verdien i ett punkt.

Eksamenstips

💡I Del 2-oppgaven om differenslikninger: først løs eksakt (karakteristisk likning + partikulær løsning), DERETTER drøft numerisk oppførsel.
💡Argumenter konkret: hvilket ledd vokser, hvilket avtar, og når slår avrundingsfeilen inn? Sensor ser etter at du knytter det til antall signifikante bits.
💡Nevn eksplisitt om initialverdiene kan representeres eksakt -- det avgjør om feilen starter umiddelbart.

Laster...

Laster…