Emnet går fra tall og beregningsfeil via lineær algebra til optimering. Vi bruker små regneeksempler, figurer og Python-forsøk til å utvikle og kontrollere metodene. Klikk på uken for å åpne undervisningssiden.
Tall og algoritmer
| Uke 1 |
Hvordan kan vi regne raskere, og hvorfor blir ikke 0,1 + 0,2 nøyaktig 0,3 på en datamaskin? |
Du lærer å måle hvor stor en feil er, og ser at en lur regnerekkefølge (Horners metode) gjør polynomer mye raskere å regne ut. Datamaskinen lagrer tall med et begrenset antall binære sifre; du finner ut når avrundingen ødelegger et resultat, og i prosjektet prøver du å lure en vanlig summering til å regne feil. |
| Uke 2 |
Kan vi finne løsningen av en likning ved å gjenta en enkel regneregel – og hvordan vet vi når svaret er nøyaktig nok? |
Mange likninger løses best ved å starte med et anslag og forbedre det steg for steg, og du lærer å se om en slik gjentakelse nærmer seg svaret, hvor fort det går og når det er trygt å stoppe. I prosjektet tegner du fargekart over hvilken løsning Newtons metode finner fra ulike startpunkter. |
Numerisk lineær algebra
| Uke 3 |
Kan et bilde av et sjakkbrett og et ensfarget bilde bli helt like når vi gjør dem mindre? |
Du skriver en bildeforminskning som en matrise og finner ut hvilken informasjon som går tapt og hvilken som kan gjenskapes – det er nettopp dette nullrom og rang måler. Ideene virker like godt for polynomer, og i prosjektet ser du at valget av byggesteiner og målepunkter avgjør om du kan finne et polynom igjen fra noen få verdier. |
| Uke 4 |
Hvordan finner vi linjen som ligger nærmest målingene når ingen linje treffer alle – og kan vi stole på regningen? |
Du lærer å måle hvor mye av en vektor som peker i en gitt retning, og bruker det til å lage vinkelrette retninger og finne linjen eller kurven som passer best til målinger (minste kvadraters metode). I prosjektet tilpasser du kurver til målinger med støy og vurderer om tilpasningen er til å stole på. |
| Uke 5 |
Hva skjer med retningen når vi ganger med den samme matrisen om og om igjen – og hvordan kan det rangere nettsider? |
Når vi ganger med den samme matrisen om og om igjen, tar noen spesielle retninger – egenvektorene – over. Du bruker dette til å rangere nettsider ut fra lenkene mellom dem (PageRank), og i prosjektet undersøker du hvor mye besøksmønsteret må endres før to sider bytter plass. |
| Uke 6 |
Kan vi løse tusenvis av likninger ved å begynne med et grovt svar og forbedre det litt om gangen? |
Store likningssett løses ofte ved å forbedre et grovt anslag litt om gangen, og du lærer å vurdere hvor nær et anslag er løsningen og hvorfor noen systemer er ekstra følsomme. Når vi ser løsningen som bunnen av en skål, får vi en rask metode (konjugert gradient), og i prosjektet sparer du arbeid ved å skalere om likningene først. |
| Uke 7 |
Hvilken informasjon bevares når vi forenkler et bilde – og kan vi fjerne støy uten å miste detaljene? |
Et bilde kan skrives som en sum av enkle mønstre, ordnet etter hvor mye de betyr (singulærverdidekomposisjonen, SVD). Ved å beholde bare de viktigste mønstrene kan du komprimere bilder og fjerne støy, og i prosjektet ser du hvorfor det er risikabelt å gjenskape et uskarpt signal fra unøyaktige målinger. |
Optimering
Vi bygger videre på minimum, gradient og linjesøk fra uke 6. Minste kvadraters metode fra uke 4 og uke 7 er et eksempel vi kan knytte de nye ideene til. De to siste ukene handler om optimering med krav: lineær programmering i uke 11 og Lagranges metode i uke 12.
| Uke 8 |
Når finnes det en beste tilpasning, og når kan vi stole på at en løser har funnet den? |
Før vi lar datamaskinen lete etter et minimum, spør vi om det finnes et beste svar i det hele tatt, og om punktet vi finner, er en bunn eller et sadelpunkt – her hjelper Hessianen, som beskriver krumningen. For konvekse funksjoner, som er formet som en skål, er enhver bunn også den laveste; denne uka er det ikke noe nytt prosjekt. |
| Uke 9 |
Hvor stort steg kan vi ta nedover, og hvorfor går gradientmetoden noen ganger så sakte? |
Du går nedover i den bratteste retningen og finner ut hvor langt hvert steg kan være og hvorfor metoden kryper i en smal dal; deretter velger du steget automatisk (Armijo-testen) og leter helt uten deriverte (kompassøk). I prosjektet bruker du Challenger-data til å undersøke hvordan koordinatvalg påvirker farten, og hva et automatisk steg kan og ikke kan rette opp. |
| Uke 10 |
Kan vi finne bunnen av en dal raskere ved å bruke både hvor bratt bakken er og hvordan helningen endrer seg? |
Newtons metode bruker både helningen og krumningen og kommer svært raskt fram: antall riktige sifre omtrent dobles for hvert steg. Den kan også havne i et sadelpunkt eller et toppunkt, så du lærer en enkel reparasjon som retter opp retningen og korter ned steget, og i prosjektet finner du posisjonen din fra målte avstander, slik en GPS gjør. |
| Uke 11 |
Et verksted lager to produkter med de samme maskinene. Hva bør det produsere, og hvor mye er én ekstra maskintime verdt? |
Du lærer å sette opp et produksjonsproblem med begrensede ressurser (lineær programmering) og ser hvorfor den beste planen ligger i et hjørne av området med tillatte planer. Ressurspriser beviser at planen er best og viser hva én ekstra maskintime er verdt, og i prosjektet bruker du samme idé til å forklare hvorfor strømprisen kan være så forskjellig i ulike deler av landet. |
| Uke 12 |
Hva erstatter \(\nabla f=0\) når svaret må ligge på en kurve? |
Når svaret må ligge på en kurve, er det ikke lenger nok å sette gradienten lik null, og Lagranges metode gir likningene som gjelder i stedet. Du lærer å finne og kontrollere slike løsninger både for hånd og med SciPy, og i prosjektet forklarer du formen på en hengende kjetting og ser at multiplikatorene i Lagranges metode er kreftene i leddene. |
Prosjekter i optimering
Hvert prosjekt skiller en kort, gitt innføring i anvendelsen fra arbeidet med numeriske metoder og lineær algebra. Formlene du trenger, er oppgitt; du bruker kode, små matriseeksempler og egne resultater til å trekke konklusjoner.
| Prosjekt 9 |
En kort innføring i statistikk |
Kondisjon, steglengde og arbeidsmengden med Armijo |
| Prosjekt 10 |
Avstander og ferdige formler |
Gauss–Newton, følsomhet og om et konvergert svar er troverdig |
| Prosjekt 11 |
Begreper og en enkel modell |
Produksjonsplan, ressurspriser og grensene for lokale anslag |
| Prosjekt 12 |
Den fysiske modellen og formlene |
Kravbrudd, multiplikatorer og straffemetodens kondisjon |