2D1220, Tillämpade numeriska metoder 1

Tilnum1, föreläsningsinnehåll vt-08, LE=Lennart Edsberg, GE=Gerd Eriksson

• Föreläsning 1, onsdag 23 jan (LE):
  Presentation av kursen och kursmaterialet.
  Kurslitteratur, kursregistrering, labbar.
  Förkunskaper (repetera linjär algebra!), kursinnehåll.
  1) Repetition av numerisk lösning av ekvationssystem:
  Gausselimination, LU-faktorisering, 2n^3/3 flops att lösa Ax=b, Matlabs lu(A)
  Permutationsmatriser P; multiplikation med matris från vänster, dvs PA,
  innebär radbyte,dvs matrisraderna permuteras; Matlabs [L,U,P]=lu(A)
  Hur reagerar Matlab för en singulär matris A, dvs det(A)=0?
  Viktiga specialfall: A är en tridiagonal matris,
  A är symmetrisk positivt definit med Cholesky-faktorisering A=LL^T.
  Lösning av icke-linjärt ekvationssystem med Newtons metod.
  Svårigheter som kan inträffa: a) Systemet har ingen (reell) lösning,
  b) svårt att hitta begynnelsevärdet,
  c) jacobianen blir singulär
  d) långsam konvergens
  2) Repetition av interpolation: global och lokal sådan
  a) styckvis linjär, b) styckvis kubisk (Hermite), c) spline
  TK kap 1.2, 1.3 (referens till NAM 3.3, 3.7)

• Föreläsning 2, fredag 25 jan (LE):
  1) Blandade problem 1: Tillämpning från hållfasthetslära, ex på tridiagonalt system, Matlabfunktionen tridiag.
  Matlabkod för lösningen (stodmomrita.m, stodmoment.m i kurskatalogen).
  2) Optimering av en funktion av flera variabler.
  Nödvändigt och tillräckligt villkor för lokalt minimum
  a) Newtons metod för lösning av grad f=0. Definition av Hessianen
  Sökmetoder: Steepest descent, CG, BFGS-metoden
  b) Steepest descent. Definition av sökriktning och linjesökning
  OH-bild (samma som i kompendiet) som visar hur metoden funkar.
  c) CG, speciellt tillämpad på ett kvadratiskt uttryck med A pos def.
  Konvergerar då i högst n iterationer (vid räkningar utan avr.fel)
  d) Matlab-kod för ett par metoder.
  Ovanstående metoder använder alla gradienten vid sökningen.
  Om funktionen har diskontinuiteter i derivatan är det bättre
  att använda gradientfria metoder, t ex Nelder-Meads algoritm, i Matlab heter den fminsearch.
  TK kap 2.2, 3.3

• Föreläsning 3, tisdag 29 jan (GE):
  Parameterkurvor: Cirkel på parameterform är bekant (vinkeln som parameter).
  Rät linje mellan två punkter p1 och p2: r(t)=(1-t)*p1 + t*p2 .
  Kvadratisk bézierkurva, en styrpunkt b:
  r(t)=(1-t)^2*p1 + 2t(1-t)*b + t^2*p2 .
  Kubisk bézierkurva, två styrpunkter b och c:
  r(t)=(1-t)^3*p1 + 3t(1-t)^2*b + 3t^2*(1-t)*c + t^3*p2 .
  Algoritmer för stora glesa system: Tridiagonalt system löses med tridia (hämta tridia.m från kurskatalogen).
  System med nästan tridiagonal matris löses effektivt med Sherman-Morrison 1 (SM1) eller Sherman-Morrison 2 (SM2), i båda algoritmerna växer antalet operationer prop mot antalet obekanta, komplexiteten är O(n). Glesa diagonaltunga system kan lösas med iterativa metoder: Jacobis metod, Gauss-Seidels metod. Filen shermplus.m visar lösning av ett stort nästantridiagonalt system med fem metoder (sparselösning, SM1, SM2, CG och Gauss-Seidels metod) med tidmätning tic-toc.
  TK kap 1.4, 3.2, 3.4.

• Föreläsning 4, torsdag 31 jan (LE):
  Egenvärdesproblem: definition av egenvärden och egenvektorer.
  Karakteristiska ekvationen, Matlabs eig(A) och [V,D]=eig(A)
  Några exempel: symmetrisk, osymmetrisk matris, defekt matris (matris med
  ofullständig egenvektoruppsättning), diagonalmatris, triangulär matris.
  Gerschgorincirklar, likformighetstransformation.
  Numeriska metoder: potensmetoden utan och med normering, inversa potensmetoden, potensmetoden med skift.
  TK kap 4.

• Föreläsning 5, fredag 1 feb (GE):
  Gyllenesnittet Fi=(sqrt(5)+1)/2=1.618034. Gyllenesnittetrektanglar innebär successiv bortklippning av kvadrater;
  långsida/kortsida = Fi/1 = 1/(Fi-1) => andragradsekvation: Fi^2-Fi-1=0.
  Inversen till Fi är enkel att beräkna, den är helt enkelt Fi-1 = 0.618034. (Matlabfiler: gyllrektangel.m, gyllkvrot.m, gyllfrac.m, gyllspiral.m).
  Gyllenesnittetsökning är effektiv derivatafri metod för minimering i EN variabel. Linjär modellanpassning med minstakvadratmetoden, allmänt om basfunktioner. Speciella basfunktioner: hattfunktioner (linjära splines) och bellsplines (kubiska splines); fallet ekvidistanta knutpunkter vanligast och enklast (fbelleq.m), bellsplines vid varierande knutpunktsavstånd (fbell.m) har knepigare rekursiv algoritm.
  TK kap 2.1, kap 5.

• Föreläsning 6, tisdag 5 feb (LE):
  QR-faktorisering. Ortogonal matris Q: Q^TQ=I. Householdermatris.
  Användning av QR vid linjära minsta-kvadratproblem.
  Hur QR-faktoriseringen erhålles: 1) I Matlab: [Q,R]=qr(A)
  2) Gram-Schmidt ortogonalisering av kolumnerna i A, som dock kan ge
  dålig noggrannhet pga av avrundningsfelens inverkan
  3) En svit Housholdertransformationer som tar A till triangulär form:
  H_nH_n-1 .... H_2H_1A=R, där H_1 transformerar första kolumnen i A
  till ke_1, där e_1 är enhetsvektorn (1,0,0...,0)^T, osv för H_2, ...
  Glöm inte res checkin tilnum1-08.
  TK kap 6.
  

• Föreläsning 7, torsdag 7 feb (LE):
  SVD-faktorisering: A=USV^T. användning av SVD för överbestämda
  och underbestämda linjära ekvationssystem. Dimensioner hos
  de ingående matriserna. Härledning av residualen för överbestämt
  och underbestämt system. För underbestämt system ger SVD minsta
  normlösningen. Trunkerad SVD: vad som händer med residualens norm
  och lösningens norm då SVD trunkeras, dvs 'små' singulära värden sätts
  till noll. Diagram som visar sambandet mellan lösningens norm (på x-axeln)
  och residualens norm (på y-axeln). SVD för datakomprimering.
  Visar hur en matris A med SVD kan utvecklas i en summa av enrangiga matriser.
  Visar att V-matrisen är egenvektorerna till A^TA och att U-matrisen
  är egenvektorerna till AA^T.
  

• Föreläsning 8, fredag 8 feb (GE):
  QR-metoden för egenvärdesbestämning, se qrmetoden.m (pröva också eigsvdgui.m som beskrivs i NCM 10.10).
  SVD-tillämpningar: Komprimering av bildmatriser (studera gärna prof P C Hansens SVD-applications). Fredholms integralekvation av första slaget; genom diskretisering och numerisk integration formuleras problemet som ett stort (ofta underbestämt) linjärt ekvationssystem, trunkerad SVD ger kandidatlösningar. Litet datortomografiproblem.
  Singulärvärdesfaktoriseringens minimalegenskap, ex B34 rektangelanpassning som löses via QR-faktorisering och SVD (se de två sista sidorna i Blandade problem).
  TK kap 6.2 - 6.4.

• Föreläsning 9, tisdag 12 feb (LE):
  Randvärdesproblem. TK kap 7. Problemformulering: 2:a ordningens icke-linjär
  ODE med Dirichletvillkor (dvs y(a)=y_0, y(b)=y_slut).
  Inskjutningsmetoden: skriv först om som ett system av 2 första ordningens
  ODEer. Inför lutningen i startpunkten som insljutningsparameter s.
  Bestäm s genom att med sekantmetoden lösa den ekvation som definierar
  det högra randvillkoret.
  Finita differensmetoden tillämpad på en linjär andra ordningens ODE.
  Centraldifferenser av andra ordningen ger en numerisk lösning O(h²).
  Diskretiseringen leder fram till ett tridiagonalt linjärt ekvationssystem
  Andra typer av randvillkor: Neumannvillkor (derivatorna givna i ändpunkterna)
  blandade randvillkor (Robins villkor). Diskretisering av randvillkor
  som innehåller derivator.
  Genomgång av problemet utböjning av cirkelplatta (TK 7.6),
  

• Föreläsning 10, torsdag 14 feb (LE):
  Fortsättning på cirkleplatteproblemet men med
  diskretisering av u'''(0)=0 med skev differensformel i stället för
  att utnyttja att u(r) är jämn. Härledning av den skeva formeln
  u'''(0)=(-u(-h)+3u(0)-3u(h)+u(2h))/6h^3 + O(h) vilket också förklarar
  varför konvergensen av utböjningen i centrum av cirkelplattan är linjär.
  Galerkins metod tillämpad på en andra ordningens linjär ODE med Dirichlet
  randvillkor. TK 7.9. Basfunktioner, ortogonalitet, hattfunktioner.
  Översiktlig genomgång av hur matrisen A och högerledet b bildas i Ac=b
  då en ansats av hattfunktioner används som basfunktioner. Varför A blir
  tridiagonal.

• Föreläsning 11, fredag 15 feb (LE):
  

• Föreläsning 12, tisdag 19 feb (LE):
  

• Föreläsning 13, torsdag 21 feb (LE):
  

• Föreläsning 14, fredag 22 feb (LE):
  

• Föreläsning 15, tisdag 26 feb (GE):
  Info om lab3-uppgiften, bokning görs på kurshemsidan!
  Periodiska förlopp. Interpolation och minstakvadratapproximation med trigonometriskt polynom, diskret fouriertransform DFT med reell ansats.
  DFT med komplex ansats, fouriermatrisen F.
  Ex: DFT på pulsvektorn y={1 1 1 0 0 0 0 0}. Komplexitet, uppsnabbning med algoritmen FFT. Matlabs fft och ifft.
  Ex: DFT på puls och dubbelpuls med många samplade punkter, approximation dels då höga frekvenser skippas, dels då små fourierkoefficienter nollställs. Tvådimensionell DFT, tillämpning på 8 x 8 matris och på större bildmatriser, dels med kapning av höga frekvenser (ett slags lågpassfilter) dels med små fourierkoefficienter satta till noll.
  Diskret cosinustransform DCT. Basfunktioner enbart cosinusfunktioner, beräkning av DCT-koefficienter i fallet n=3. DCT-matrisen C är en reell ortogonalmatris.
  TK kap 12, NCM kap 8, SB kap 10, 11.1.

• Föreläsning 16, fredag 29 feb (GE, LE):
  Mer om DFT (FFT) på matriser. Mer om DCT, härledning av DCT på matriser. Exempel på 8 x 8 bildmatris med komprimering via lågpassfilter. Effektivare komprimering fås med linjär kvantisering med hjälp av hilbertmatrisen hilb(8). I kurskatalogen finns dftodct.m, hundhussefft.m och hundhussedct.m.
  TK kap 12.6-12.7, SB 11.1-11.2.
  Elliptiska problem, forts. Först repetition av numerisk lösning
  av Poissons ekvation på en kvadrat med 5-punktsoperatorn. För generella
  polygonområden hänvisades till TK 10.1.2. Poissons ekvation i andra
  koordinatsystem, cylindriska, polära och sfäriska koordinater men i
  alla tre fallen reducerat till endast två oberoende variabler (r,z),
  (r,fi) resp (r,teta). Härledning av 5-punktsoperatorn för dessa tre
  Poissonekvationer, se TK 10.7.

  där matrisen A är samma som
  erhålles vid diskretisering av Poissons ekvation på ett kvadratiskt område.
  Med Gerschgorincirklarna visas att lambda<0, vilket ger egenfrekvenser genom
  sambandet lambda=-omega². Egenvärden och egenvektorer kan i Matlab bestämmas
  med eig och eigs, samt även förståss med inversa potensmetoden med skift.
  Vi återkom till vågekvationen, nu med sikte på att lösa den i egenskap av
  hyperbolisk PDE. Diskretisering i x- och t-led med centraldifferens.
  Stabiltetsegenskaper, se TK 11.1. Envägsvågekvationen (även kallad
  advektionsekvationen). Numerisk lösning med FTBS, FTCS, Lax-Friedrich
  samt Lax-Wendroff. Stabilitetsegenskaper. CFL-villkoret.