MAT-INF1100

Cheat Sheet

Formler, begreper og oppsummering

Modellering og beregninger

eksamenssett.no

Formler

Taylorpolynom og restledd

• $T_n f(x) = \sum_{k=0}^{n} \frac{f^{(k)}(a)}{k!}(x-a)^k$

Nøkkelformler per tema

Tallrepresentasjon og feil

•Lagranges restledd: $R_n f(x) = \frac{f^{(n+1)}(c)}{(n+1)!}(x-a)^{n+1}, \quad c \text{ mellom } a \text{ og } x$

Vanlige feil å unngå

Tallrepresentasjon og 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.

Interpolasjon

•Å sette opp Newtons form med feil 'neste'-faktorer -- ledd k må inneholde $(x-x_0)\cdots(x-x_{k-1})$, altså alle foregående knutepunkter.
•Å glemme å gange ut til standardform før integrasjon, slik at integralet blir feil.
•Å løse et fullt lineært system når Newtons form gir koeffisientene direkte og raskere.
•Å forveksle interpolasjon (går eksakt gjennom punktene) med minste kvadraters tilpasning (nær punktene).

Numerisk derivasjon og integrasjon

•Å glemme halveringen av endepunktene i trapesmetoden -- de teller med vekt 1/2, indre punkter med vekt 1.
•Å bruke delepunktene i stedet for midtpunktene i midtpunktsmetoden.

Eksamenstips

Tallrepresentasjon og feil

•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.

Interpolasjon

•Oppgaven kommer nesten hver eksamen -- tren på å skrive Newtons form og løse koeffisientene rekursivt på under to minutter.
•Les nøye om de ber om p'(a), integralet av p, eller selve polynomet -- det er ofte siste steg som gir poeng.
•Sjekk svaret ved å sette inn ett av interpolasjonspunktene i ferdig polynom.

Numerisk derivasjon og integrasjon

•Når du skal vise eksakthet: sjekk basisfunksjonene og nevn eksplisitt at linearitet gir resten -- det er det sensor poengsetter.
•Tegn opp delepunkter og (for midtpunkt) midtpunkter før du regner, så du ikke bommer på antallet.
•Husk at Simpsons metode er eksakt helt opp til tredjegradspolynomer -- nyttig snarvei når integranden er et polynom.

Differensiallikninger

•

R_n f(x) = \frac{f^{(n+1)}(c)}{(n+1)!}(x-a)^{n+1}, \; c \text{ mellom } a,x

•Feilgrense:

|R_n f(x)| \le \frac{M_{n+1}}{(n+1)!}|x-a|^{n+1}

Interpolasjon

•Newtons form: $p(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+\dots$
•Entydig polynom av grad $\le n$ gjennom $n+1$ punkter
•Simpsons punktformel: $\int_a^b f \approx \frac{h}{3}(f(a)+4f(m)+f(b))$ (eksakt grad $\le 3$)

Numerisk derivasjon

•Forlengs: $f'(a)\approx \frac{f(a+h)-f(a)}{h} \; (O(h))$
•Sentral: $f'(a)\approx \frac{f(a+h)-f(a-h)}{2h} \; (O(h^2))$
•Andrederivert: $f''(a)\approx \frac{f(a+h)-2f(a)+f(a-h)}{h^2}$

Numerisk integrasjon

•Trapes: $h\Big(\tfrac{f(x_0)+f(x_n)}{2}+\sum_{k=1}^{n-1}f(x_k)\Big)$
•Midtpunkt: $h\sum_k f(m_k), \; m_k=\text{midtpunkt}$

Nullpunktsmetoder

•Newton: $x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$
•Sekant: $x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k)$
•Halvering: behold halvdelen med fortegnsskifte, $m=\tfrac{a+b}{2}$

Differensiallikninger

•Karakteristisk: $r^2+br+c=0$ gir $y_h=Ce^{r_1x}+De^{r_2x}$ (eller $(C+Dx)e^{rx}$)
•Integrerende faktor: $\mu=e^{ax}, \; (\mu y)'=\mu g$
•Separabel: $\int g(x)\,dx=\int f(t)\,dt$
•System: $y=x' \Rightarrow x'=y,\; y'=(\text{løst for } x'')$

Differenslikninger

•Homogen: $ar^2+br+c=0 \Rightarrow x_n^h=Cr_1^n+Dr_2^n$
•Partikulær: gjett samme form som $g(n)$
•Generell: $x_n = x_n^p + x_n^h$, bestem C,D fra $x_0,x_1$

Numeriske ODE-metoder

•Euler: $x_{k+1}=x_k+h f(t_k,x_k)$
•Euler midtpunkt: $x_{k+1}=x_k+h f(t_{k+1/2},x_{k+1/2})$
•med $x_{k+1/2}=x_k+\tfrac{h}{2}f(t_k,x_k), \; t_{k+1/2}=t_k+\tfrac{h}{2}$

Minste kvadrater

• $\hat\beta_1=\frac{\sum(x_i-\bar x)(y_i-\bar y)}{\sum(x_i-\bar x)^2}, \; \hat\beta_0=\bar y-\hat\beta_1\bar x$
•Normallikninger: $A^TA\beta=A^Ty$

Flyttall og feil

•Eksakt i flyttall: tall på formen $a\cdot 2^{-k}$
•64-bits flyttall: 53 signifikante bits, maskinepsilon $\approx 1{,}1\cdot 10^{-16}$

•Feilgrense:

|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}$

Interpolasjon

•Newtons form (3 punkter): $p(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1)$
•Rekursiv løsning: $c_0 = y_0,\quad c_1 = \frac{y_1-c_0}{x_1-x_0}, \quad \dots$
•Entydighet: gjennom $n+1$ punkter med ulike $x_i$ finnes ett polynom av grad $\le n$
•Simpsons punktformel (eksakt for grad $\le 3$): $\int_a^b f \approx \frac{h}{3}\big(f(a)+4f(m)+f(b)\big), \; h=\frac{b-a}{2}$

Numerisk derivasjon og integrasjon

•Forlengsdifferanse: $f'(a)\approx \frac{f(a+h)-f(a)}{h} \quad (O(h))$
•Sentraldifferanse: $f'(a)\approx \frac{f(a+h)-f(a-h)}{2h} \quad (O(h^2))$
•Trapesmetoden: $\int_a^b f \approx h\Big(\tfrac{f(x_0)+f(x_n)}{2}+\sum_{k=1}^{n-1}f(x_k)\Big)$
•Midtpunktsmetoden: $\int_a^b f \approx h\sum_{k} f(m_k), \quad m_k = \text{midtpunkt}$

Differensiallikninger

•Karakteristisk likning: $r^2+br+c=0 \Rightarrow y_h = Ce^{r_1 x}+De^{r_2 x}$ (eller $(C+Dx)e^{rx}$ ved dobbeltrot)
•Integrerende faktor for $y'+ay=g$: $\mu=e^{ax}, \quad (\mu y)' = \mu g$
•Separabel: $g(x)\,x' = f(t) \Rightarrow \int g(x)\,dx = \int f(t)\,dt$
•Omskriving til system: $y=x' \Rightarrow x'=y, \; y'=(\text{løst for } x'')$
•Resonansregel: hvis 0 er rot og $g$ er polynom, øk graden i $y_p$ med 1

Newtons metode

•Newtons metode: $x_{k+1}=x_k - \frac{f(x_k)}{f'(x_k)}$
•Sekantmetoden: $x_{k+1}=x_k - \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k)$
•Halveringsmetoden: behold halvdelen med fortegnsskifte; tilnærming $m_k=\tfrac{a_k+b_k}{2}$
•Konvergens: Newton kvadratisk (typisk), halvering lineær men garantert

Minste kvadraters metode

•Mål: minimer $S(\beta) = \sum_i (y_i - \hat y_i)^2$
•Stigningstall: $\hat\beta_1 = \frac{\sum (x_i-\bar x)(y_i-\bar y)}{\sum (x_i-\bar x)^2}$
•Konstantledd: $\hat\beta_0 = \bar y - \hat\beta_1 \bar x$
•Normallikninger (matriseform): $A^T A \beta = A^T y$

Python-programmering

•Iterasjonsløkke: for k in range(N): x += h*f(t,x); t += h
•Faktorial: from math import factorial -- factorial(k) gir $k!$
•Testkonvensjon: funksjon test_*() med assert abs(computed-exact) <= tol
•Sekant trenger to forrige verdier: hold xpp og xp i løkken

Matematisk modellering

•Induksjon: vis $P_{n_0}$ (basis), anta $P_n$, vis $P_{n+1}$
•Differenslikning, homogen: $ar^2+br+c=0 \Rightarrow x_n^h = C r_1^n + D r_2^n$
•Partikulær løsning: gjett samme form som $g(n)$ (konstant, lineær $An+B$, osv.)
•Euler for ODE-modell: $x_{k+1}=x_k+h f(t_k,x_k)$
•Euler midtpunkt: $x_{k+1}=x_k+h f(t_{k+1/2}, x_{k+1/2}), \; x_{k+1/2}=x_k+\tfrac{h}{2}f(t_k,x_k)$

Å ikke begrunne lineariteten når man viser eksakthet -- å sjekke 1, x, x^2 alene holder ikke uten dette argumentet.

•Å regne med feil antall delintervaller (n delintervaller gir n+1 delepunkter).

Differensiallikninger

•Å glemme å gå opp en grad i partikulærgjettet når 0 er en rot i den karakteristiske likningen.
•Fortegnsfeil ved omskriving til førstordenssystem -- flytt alle ledd unntatt x'' over før du setter y'=...
•Å bestemme integrasjonskonstanten før den generelle løsningen er ferdig, eller å bruke feil initialbetingelse på y'(0).
•Å glemme den homogene løsningen og bare oppgi partikulærløsningen.

Newtons metode

•Å glemme å derivere f, eller bruke feil f' i Newtons formel.
•I sekantmetoden: forveksle hvilket punkt som er $x_k$ og hvilket som er $x_{k-1}$ i differansene.
•I halveringsmetoden: beholde feil halvdel -- behold alltid den der funksjonsverdiene har motsatt fortegn.
•Å runde av for tidlig når oppgaven ønsker eksakt brøksvar.

Minste kvadraters metode

•Å forveksle minste kvadrater (nær punktene) med interpolasjon (gjennom punktene).
•Å glemme å trekke fra gjennomsnittene $\bar x, \bar y$ i formelen for stigningstallet.
•Å tro at residualene må være null -- de er normalt ikke det, og summen deres skal være null, ikke kvadratsummen.

Python-programmering

•Å glemme å oppdatere både x og t inne i løkken (Euler).
•Feil indeksering i range -- range(N) gir 0..N-1, så N steg.
•Å skrive testfunksjonen uten assert eller uten navn på formen test_*().
•Å bruke factorial(k) der det skal være factorial(k-1) (eller motsatt) i Taylorsummer.

Matematisk modellering

•Å hoppe over basissteget eller induksjonshypotesen i et induksjonsbevis -- begge må stå eksplisitt.
•Å glemme partikulærløsningen når differenslikningen er inhomogen ($g(n)\neq 0$).
•Å bestemme C og D før den generelle løsningen (homogen + partikulær) er komplett.
•Å blande sammen Euler og Euler midtpunkt -- midtpunkt krever et halvsteg først.

DE dukker opp både i flervalg og Del 2 -- behersk separabel, lineær første/andre orden og systemomskriving.

•I flervalg kan du ofte teste alternativene ved innsetting i likningen + initialbetingelsen i stedet for å løse fra bunnen.

•Skriv alltid: homogen løsning, partikulær løsning, generell løsning, og DERETTER bestem konstantene fra initialbetingelsene.

Newtons metode

•Skriv opp iterasjonsformelen med innsatt f og f' før du regner -- det reduserer regnefeil.
•Hold svaret som brøk hvis startverdiene er rasjonale; alternativene i flervalg er ofte brøker.
•Kjenn forskjellen på Newton (krever f'), sekant (to punkter, ingen f') og halvering (intervall med fortegnsskifte).

Minste kvadraters metode

•Husk at regresjonslinjen alltid går gjennom tyngdepunktet $(\bar x,\bar y)$ -- en rask kontroll.
•Sett opp gjennomsnittene først; resten er innsetting i to formler.
•Forklar gjerne den geometriske tolkningen (projeksjon) hvis oppgaven ber om begrunnelse.

Python-programmering

•Følg konvensjonen: test_-prefiks og assert -- sensor sjekker dette eksplisitt.
•Bruk from math import * for å slippe lange prefikser på exp, sin, sqrt.
•Skriv løkken slik at den lett kan leses linje for linje; korrekt struktur teller mer enn elegant kode.

Matematisk modellering

•Induksjon og en differenslikning kommer nesten alltid som de to første Del 2-oppgavene -- tren på målstrukturen for begge.
•Skriv induksjonen ryddig: 'Basis', 'Antagelse', 'Induksjonssteg', 'Konklusjon'.
•Etter eksakt løsning av differenslikning: ha klar en standardforklaring på numerisk oppførsel (eksakte/ueksakte initialverdier, voksende/avtagende ledd).