NB! Mindre endringer kan forekomme.

Notatene det henvises til finner du under Notater, både som Jupyternotater og som pdf-filer. Notatene dekker pensum, med mindre noe annet er presisert her. Men du finner flere eksempler og mer motivasjon i læreboka til Sauer.

Notatene finnes både som Jupyternotater (ipynb) og som pdf, med tilhørende kode i python.

Alt i disse notatene er pensum.

• Introduction to Jupyter with Python: ipynb, nbviewer.
• Preliminaries: ipynb, pdf, py.
  Litt repetisjon fra Matematikk 1 og 3, samt noen begreper som blir brukt gjentatte ganger gjennom kurset.
• Numerical Solution of Nonlinear Equations: ipynb, pdf, py (oppdatert 11.02)
• Polynomial Interpolation: ipynb, pdf, py.
• Numerical Integration (komplett): ipynb, pdf, py.
• Numerical solution of ordinary differential equations: ipynb, pdf, py.
• Numerisk lineær algebra, del 1: Direkte metoder for Ax=b: pdf
  (Rev.18.03 Delen om skalert pivotering rettet.
  Rev.16.05. Feil om radvis pivotering rettet. Alle endringer er merket i rødt. )
  Numerisk lineær algebra, del 2: Matrise- og vektor-normer. Feilanalyse av lineære ligninger: pdf
  Numerisk lineær algebra, del 3: Lokalisering av egenverdier. Symmetrisk positive matriser: pdf
  Numerisk lineær algebra, del 4: Klassiske iterative metoder: pdf

Fil for finere layout: tma4320.css

(Oppdatert 22.04.2022)

Siden det stadig er spørsmål om hvilke bevis dere risikerer få på eksamen, er disse understreket i det etterfølgende.

Innhold

• Numerisk løsning av skalare ikke-lineære ligninger
• Intervallhalveringsmetoden, fikspunktiterasjon, Newtons metode
• Konvergens av fikspunktiterasjon
• Kvadratisk konvergens i Newtons metode
• Formulering av Newtons metode for systemer

Læringsmål.

• Forstå prinsippene bak intervallhalveringsmetoden, forstå og bruke startkriterier, kunne utlede feilestimat, og implementere metoden i en programkode inkludert stoppkriterium.
• Forstå hva en fikspunktformulering av en ikke-lineær ligning er, og den tilhørende fikspunktiterasjon. Være i stand til å omformulere en nullpunkt-ligning \(f(x) = 0\) til en fikspunktformulering \(x = g(x)\). Kunne utlede kriterium for konvergens av fikspunktiterasjon. Kunne utføre konvergensanalyse for konkrete skalare ikke-lineære ligninger. Vite om stoppkriterier. Kunne implementere fikspunktiterasjon med stoppkriterium i programkode.
• Huske eksakt hvordan Newtoniterasjonen ser ut generelt for \(f(x)=0\), og kunne anvende den på konkrete tilfeller. Forstå Newtons metode som en fikspunktiterasjon. Forstå begrepet kvadratisk konvergens, og kunne utlede at Newtons metode har dette. Kunne implementere Newtons metode med stoppkriterium.
• Kunne sette opp og anvende Newtons metode for systemer

Innhold

• Interpolasjonsbegrepet
• Lagrangeinterpolasjon
• Feilskranker i interpolasjon
• Runges fenomen
• Chebyshev interpolasjon

Læringsmål

• Forstå hva det vil si å interpolere et datasett eller interpolere en funksjon i et sett av noder
• Kjenne til Lagrange kardinalfunksjoner, deres egenskaper og hvordan de brukes til å sette opp interpolasjonspolynomet. Kunne bruke prinsippet med Lagrangeinterpolasjon til å utlede interpolasjonspoly- nomer ved håndregning, og forstå hvordan de kan implementeres i programkode.
• Kunne bevise at interpolasjonsproblemet har en entydig løsning (for \(n + 1\) datapunkter, og polynom av grad n).
• Kunne utlede et uttrykk for feilen i interpolasjon (når \(f \in C^{n+1}[a, b])\), og kunne bruke dette uttrykket til å utlede feilskranke for konkrete interpolasjonsproblemer.
• Kjenne til mulige farer ved polynominterpolasjon og spesielt kunne redegjøre for disse ved å ha kjennskap til Runges fenomen, å ha teo- retisk innsikt i dette fenomenet er ikke et læringsmål i dette emnet.
• Vite hvordan Chebyshevpolynomene er definert relativt til intervallet \([−1, 1]\). Kjenne til Chebyshevpolynomenes viktigste egenskaper i forbindelse med interpolasjon. Være i stand til å bestemme nullpunktene i Chebyshevpolynomer av vilkårlig grad, og forstå hvorfor disse punktene egner seg godt som abscisser i interpolasjonsproblemet. Kunne utføre eksempler med interpolasjon for slike Chebyshevpunk- ter. Vite hvordan en kan utnytte Chebyshevinterpolasjon også når intervallet ikke er \([−1, 1]\).

Innhold

• Numeriske integrasjonsformler (kvadratur)
• Feilformler og feilskranker
• Presisjonsgrad av integrasjonsformler
• Sammensatte kvadraturformler
• Adaptive kvadratur

Læringsmål

• Kunne konstruere integrasjonsformler vha. polynominterpolasjon.
• Kunne finne feilformler og feilskranker og presisjonsgraden, og forstå hvordan de brukes.
• Presisjonsgrad av numeriske integrasjonsformler.
• Forstå hvordan en integrasjonsformel overføres fra et intervall til et annet, og hvordan sammensatte formler konstrueres.
• Forstå hvordan prinsippet for adaptiv integrasjon fungerer. Være i stand til å utlede og implementere en slik metode med et gitt stoppkriterium.
• Ha en viss forståelse for eventuelle begrensninger i hva slags integraler som kan løses med disse formlene.

Innhold

• Bakgrunn for numerisk løsning av differensialligninger. Problemformulering, omskriving av høyere ordens ligninger til systemer av førsteordens ligninger. Lipschitz-konstant, eksistens og entydighet av løsning. Autonome systemer og omforming av ikke-autonomt system til autonomt system.
• Systemer av første ordens differensialligninger.
• Eksistens og entydighet av løsning for initialverdiproblemet for systemer av diffligninger.
• Eulers metode, Heuns metode, Runge–Kutta metoder.
• Lokal og global avbruddsfeil, konvergens og orden, stabilitet via modelligning
• Estimering av lokalfeil og skrittlengdekontroll
• Stive diffligninger og implisitte metoder som implisitt Euler, trapes-metoden og midtpunktmetoden

Læringsmål

• Forstå hvordan numerisk løsning av differensialligninger virker (oppdeling av x-aksen i delintervaller, suksessive tidsskritt osv), også forstå hvilke begrensninger dette innebærer (parametre i ligningen, uendelig tidsintervall etc). Forstå hva brukeren av en diffligningsløser gir som input og hva slags output løseren produserer.
• Være istand til å omforme diffligninger av orden 2 og høyere (orden er høyeste derivertgrad i ligningen) til et system av første ordens diffligninger. Være istand til å omforme ikke-autonomt system til autonomt system.
• Ha kjennskap til resultat om eksistens og entydighet av initialverdiproblemet, og forstå hva Lipschitz-konstanten er og hvorfor den er viktig.
• Forstå alle numeriske metoder som anvendbare på systemer av første ordens differensialligninger
• Forstå oppbygningen av Runge–Kutta metoder generelt, og ha spesiell forståelse for og huske formler for Eulers og Heuns metode. Må kunne implementere diffligningsløsere i programkode basert på disse metodene.
• Ha en grunnleggende forståelse for begreper som lokal og global avbruddsfeil i numeriske metoder, og hva forskjellen er. Kunne utlede estimat av lokal avbruddsfeil for skalare diffligninger opp til orden 2. Kunne utlede uttrykk for global avbruddsfeil i Eulers metode ved bruk av Lipschitz-konstant og rekursjonsformel for globalfeil i hvert skritt.
• Vite hva det betyr at en metode er konvergent.
• Være kjent med modelligningen for stabilitet, og kunne utlede stabilitetsfunksjon, \(R(z)\), for en Runge–Kutta metode, der \(y_{k+1} = R(hλ) y_k\).
• Ha kunnskaper om og kunne bruke innbygde par for estimering av lokalfeil og skrittlengdekontroll. Forstå hvordan lokalfeilen estimeres, og kunne utlede og forstå formel for skrittlengdejustering og pessimistfaktor. Være istand til å implementere slike variabel-tidsskritt metoder i programkode. Kunne vise til et eksempel på et innbygd par, og anvende oppgitte eksempler.
• Kunne peke på eksempler på stive problemer, og kunne redegjøre hvorfor eksplisitte Runge-Kutta metoder vil møte utfordringer med slike problemer. Kjenne til alternative implisitte metoder som kan bøte på disse problemene. Forstå hva en implisitt metode er, og hva det innebærer i form av at man må løse ikke-lineære ligninger i hvert skritt. Være istand til å skrive ned en algoritme som kombinerer en implisitt metode med ikke-lineær ligningsløser og implementere dette i programkode.

Innhold.

• Gauss-eliminasjon og LU-faktorisering, inkludert pivotering. Diagonaldominans.
• Kompleksitet av LU-faktorisering
• Grunnlagsteori i lineær algebra. Vektornormer, matrisenormer, tilordnet matrisenorm, normkompatibilitet, eksempler på vektor- og matrisenormer.
• Baklengs feilanalyse for Gausseliminasjon (LU-faktorisering)
• Egenverdier og spektralradius for matriser.
• Diagonaldominante og symmetrisk positive matriser.
• Gershgorins sirkelteorem
• Anvendelse fra differensialligninger. Glisne ligningssystemer.
• Iterative metoder, Jacobi, Gauss-Seidel og SOR
• Konvergensteori og feilanalyse for iterative metoder, diagonaldominans,

Læringsmål.

• Forstå og kunne utføre Gausseliminasjon som LU-faktorisering både manuelt og i programkode. Forstå hvordan LU-faktorisering brukes når man løser et system med flere ulike høyresider (\(Ax_i = b_ii\) for fiksert matrise A, og forskjellige valg av høyresidevektorer \(b_i\)).
• Forstå pivotering og hvordan man pivoterer i numerisk kontekst, det vil si pivotering som gir størst mulig pivot-element.
• Vite om kompleksitet i Gausseliminasjon og kunne bruke dette til å estimere tidsbruk i algoritmen sammenlignet med andre metoder.
• Ha en grunnleggende forståelse for vektorrom og normbegrepet. Forstå matriser som elementer i vektorrom og normer på disse. Forstå hvordan en kan utlede en tilordnet matrisenorm fra en vilkårlig vektornorm, og vite hva kompatibilitet mellom vektor- og matrisenormer innebærer. Ha kjennskap til, gjerne huske, definisjonen av 1-, 2- og ∞-norm for vektorer og matriser. Kjenne til de mest brukte ulikheter for vektor- og matrisenormer. Vite hva spektralradius er, dens relasjon til matrisenormer og dens betydning for begrensethet av potenser av en gitt matrise. Forstå hva det betyr og kriterier for at en matrise er SPD (Symmetrisk, positiv definitt). Vite om og kunne anvende Gerschgorins sirkelteorem for å estimere spektralradius.
• Kunne utlede uttrykk for relativ feil, forstå kondisjonstallets betydning for numerisk løsning av lineære ligninger.
• Forstå hvordan numerisk løsning av differensialligninger kan lede til lineære systemer av ligninger (som ofte er SPD og glisne).
• Forstå forskjellen på direktemetoder og iterative metoder for lineære ligninger.
• Kunne utlede et tilstrekkelig konvergenskriterium for generelle iterative metoder på formen \(x^{(k+1)}=Gx^{(k)}+c\), og kjenne til det nødvendige og tilstrekkelige kriteriet.
• Forstå oppbygning og virkemåte for Jacobi-, Gauss–Seidel- og SOR- metoden, og være i stand til å implementere disse i programkode.
• Kunne analysere konvergens og feilanalyse av disse tre metodene i teorien, og i spesielle tilfeller kunne utlede estimater for antall påkrevde iterasjoner for en gitt nøyaktighet.