Topic outline

  • General

    Pri predmetu Numerična linearna algebra bomo poglobili znanje iz Uvoda v numerične metode na naslednjih področjih:

    1. Singularni razcep in uporaba
    2. Občutljivost lastnih vrednosti
    3. Implicitni QR algoritem za računanje lastnih vrednosti
    4. Računanje lastnih vrednosti za simetrične matrike
    5. Posplošeni problemi lastnih vrednosti
    6. Računanje s tenzorji

  • Domače naloge in kvizi in izpiti

    1. kviz: 26. 4. 2022 ob 10h v 3.12

    2. kviz: 27. 5. 2022 ob 14.30 v 3.10

    1. izpit: sreda, 8. 6. 2022, ob 10h v 3.05 

    2. izpit: ponedeljek, 22. 8. 2022 ob 9h v 3.06

    3. izpit: ponedeljek, 5. 9. 2022 ob 9h v 3.06

  • Predavanje 1

    Začeli smo s singularnim razcepom, ki je močno in uporabno orodje v numerični linearni algebri. Dokazali smo, da za vsako matriko obstaja singularni razcep (SVD), kjer realno matriko zapišemo kot produkt dveh ortogonalnih in diagonalne matrike. Definirali smo psevdoinverz in pogledali, kako lahko singularni razcep uporabimo za reševanje sistemov linearnih enačb po metodi najmanjših kvadratov. Produkt $x=A^+b$ vrne vekor $x$, ki minimizira ostanek $\|Ax-b\|_2$ in ima v primeru, ko je takih vektorjev več, med njimi minimalno normo $\|x\|_2$.

  • Predavanje 2

    Za reševanje nelinearnih problemov najmanjših kvadratov lahko uporabimo Gauss-Newtonovo metodo. S pomočjo SVD lahko najdemo matriko nižjega ranga, ki je po normi najbližja originalni matriki, to pa lahko uporabimo za aproksimacijo slik, tabeliranih vrednosti gladkih funkcij dveh spremenljivk, pa tudi za optimizacijo iskanja po internetu. 

    • Predavanje 3

      Ukvarjali smo se z regularizacijo, kjer npr. z uporabo odrezanega singularnega razcepa (TSVD) ali regularizacije Tihonova lahko pridemo do dovolj uporabnih rešitev inverznih oziroma slabo pogojenih problemov.

      Primeri v Matlabu:

      Če koga zanima še več:

      • Zgled za regularizacijo z enačbo prevajanja toplote je narejen s pomočjo paketa Regularization Tools za Matlab, ki ga je pripravil Per Christian Hansen. V tem paketu lahko najdete še dodatne metode za regularizacijo kakor tudi priročnik, ki lahko služi kot učbenik za regularizacijo. Domača stran je http://www2.imm.dtu.dk/~pch/Regutools/


      Primeri v Matlabu:

      Primeri v Matlabu:

    • Predavanje 4

      Obravnavali smo občutljivost lastnih vrednosti za splošno nesimetrično matriko. Videli smo, da je za enostavno lastno vrednost skalarni produkt med normiranima desnim in levim lastnim vektorjem merilo za občutljivost lastne vrednosti. Manjša, ko je absolutna vrednost skalarnega produkta, bolj je lastna vrednost občutljiva. Za izračunano lastno vrednost lahko v primeru, ko poznamo tudi približka za levi in desni lastni vektor, dobimo uporabno oceno napake iz norme ostanka in ocene za občutljivost.

      Pokazali smo izrek o implicitnem Q, pomembno orodje pri metodah tipa QR iteracije za računanje lastnih vrednosti.

      V Matlabu imate na voljo zglede, ki med drugim prikazujejo, kako lahko iz občutljivosti lastnih vrednosti dobimo praktične ocene za direktno napako izračunanih lastnih vrednosti. Na voljo imate:
      • PrimerBF1, PrimerBF2, PrimerBF3: trije zgledi Bauer-Fikeovih krogov in lastne vrednosti zmotenih matrik, ki prikazujejo, da res vse lastne vrednosti ležijo v uniji B-F krogov.
      • PrimerS1, PrimerS2, PrimerS3: za iste tri matrike kot zgoraj dobimo boljše ocene, če za vsako lastno vrednost upoštevamo njeno občutljivost.
      • PrimerG: zgled Gerschgorinovih krogov in prikaz, kako lahko še boljše ocene dobimo s pomočjo diagonalne transformacije.
      • PrimerG3, PrimerG5, PrimerGodunov: primeri celoštevilskih matrik s celoštevilskimi lastnimi vrednostmi, ki jih Matlab izračuna z različnimi natančnostmi. Iz zgledov je razvidno, da je obratna napaka vedno majhna, ocena za direktno napako iz občutljivosti pa se dobro ujema z dejansko napako izračunanih lastnih vrednosti.
      • Zgledi v Matlabu

    • Predavanje 5

      Obravnavali smo implicitno QR iteracijo. QR metoda je trenutno najprimernejša metoda za računanje lastnih vrednosti nesimetričnih matrik, izpeljanke pa se uporabljajo tudi za simetrični problem lastnih vrednosti, reševanje posplošenega problema lastnih vrednosti in singularnega razcepa. Ključnega pomena pri tem, da se da QR iteracijo narediti učinkovito, ima izrek o implicitnem Q. Pogledali smo si, kako preganjamo grbe v primeru enojnih in dvojnih premikov.

      Začeli smo se ukvarjali s simetričnim problemom lastnih vrednosti. Pogledali smo si nekaj pomembnih teoretičnih rezultatov o lastnih vrednostih simetričnih matrik. Tako smo dokazali Courant-Fischerjev minimaks izrek in nekaj posledic.

      Programi:

      • Različne metode za nesimetrični in simetrični lastni problem v Matlabu: lastni.zip

    • Predavanje 6

      Obravnavali smo Rayleighovo iteracijo, kjer iteracijo začnemo s približkom za lastni vektor, metoda pa v tem primeru konvergira k lastnemu vektorju in pripadajoči lastni vrednosti. Na grobo smo pokazali, da ima metoda za simetrično matriko v bližini enostavne lastne vrednosti kubično konvergenco, za nesimetrično matriko pa kvadratično. Obravnavali smo QR iteracijo za simetrične matrike. Zaradi povezave med Rayleighovo iteracijo in QR iteracijo z Rayleighovimi premiki ima QR iteracija za simetrične matrike v bližini enostavne lastne vrednosti kubično konvergenco. 

    • Predavanje 7

      Obravnavali smo še dve metodi za računanje lastnih vrednosti simetrične matrike. Pri prvi metodi uporabimo Sylvestrov izrek o ohranitvi inercije, s pomočjo katerega lahko lastne vrednosti tridiagonalne nerazcepne matrike računamo s pomočjo bisekcije. Tako lahko izračunamo k-to lastno vrednost simetrične matrike brez tega, da bi poznali ostale lastne vrednosti. Kot drugo smo obravnavali metodo deli in vladaj za računanje lastnih vrednosti simetrične tridiagonalne matrike. Metoda je za dovolj velike matrike (okvirno večje od 25x25) hitrejša od QR metode. 

    • Predavanje 8

      Obravnavali smo Jacobijevo metodo za računanje lastnih vrednosti simetrične matrike, kjer matrike na začetku na reduciramo na tridiagonalno obliko. Potem smo si pogledali še, kako lahko s tem algoritmom (z enostransko različico) izračunamo singularni razcep dane matike.

      Za simetrični problem lastnih vrednosti obstajajo še druge metode. Če imamo npr. tridiagonalno simetrično matriko, je bilo dolgo časa vprašanje, ali je možno za tako matriko v zahevnosti O(n^2) stabilno izračunati vse lastne vrednosti in lastne vektorje. Lastne vrednosti lahko izračunamo s QR iteracijo (brez računanja matrike Q z lastnimi vektorji, saj bi stalo O(n^3)) in potem vsak lastni vektor posebej izračunamo z inverzno iteracijo. Ta algoritem ima res zahtevnos O(n^2), a lastni vektorji za bližnje lastne vrednosti niso tako ortogonalni, kot bi morali biti. Rešitev je uporaba relativno robustnih reprezentacij, več lahko preberete na spodnjih prosojnicah.

    • Topic 10

      Ukvarjali smo se z računanjem singularnega razcepa. Pri računanju matriko najprej reduciramo na bidiagonalno obliko z ortogonalnimi transformacijami. Pri QR iteraciji nato implicitno izvajamo QR iteracijo na matriki $B^TB$, a popravljamo samo B. Pri metodi dqds pa si pomagamo z LR iteracijo in razcepom Choleskega. Na ta način porabimo manj operacij, smo pa omejeni pri izbiri premika, saj mora biti manjši od kvadrata najmanjše singularne vrednosti matrike.

    • Topic 11

      Lotili smo se posplošenih problemov lastnih vrednosti. Definirali smo matrični šop in končne in neskončne lastne vrednosti. Za reševanje posplošenega problema lastnih vrednosti za regularen matrični šop uporabimo QZ metodo, s katero lahko izračunamo posplošeno Schurovo formo.

    • Topic 12

      Obravnavali smo polinomske probleme lastnih vrednosti, še posebno kvadratni problem lastnih vrednosti. Če koga zanima še več o tovrstnih problemih in numeričnem reševanju, si lahko pogleda skripto za podiplomski predmet Nelinearni problemi lastnih vrednosti.

    • Topic 13

      Lotili smo se tenzorjev. Zaenkrat so to za nas večdimenzionalne tabele, v katerih hranimo npr. vrednosti neke gladke funkcije več spremenljivk v ekvidistantni mreži. Podobno kot lahko v primeru matrike to pogosto dobro aproksimiramo z matrikami nizkega ranga, bi to radi naredili tudi pri tenzorjih, kjer potrebujemo še več (pogosto toliko, da ni več prostora) podatkov za celoten tenzor.

    • Topic 14

      Obravnavali smo tenzorje in aproksimacijo s tenzorji nizkega ranga v obliki CP. Algoritma podobnega SVD za matrike nimamo, v večini primerov pa se uporablja algoritem ALS-CP, ki temelji na alternirajočih najmanjših kvadratih. Nato smo si pogledali Tuckerjevo obliko zapisa tenzorja.

    • Topic 15

      Pogledali smo HOSVD, ki je posplošitev SVD na tenzorje. Spoznali smo, kako so tenzorji povezani z multilinearnimi preslikavami in kako s pomočjo tenzorjev lahko razložimo ozadje Strassenovega množenja matrik, s katerim lahko dve matriki velikosti $n\times n$ zmnožimo hitreje kot v $O(n^3)$.

    • Vaje 1

      Izračunali smo SVD za dve manjši pravokotni matriki. Pogledali smo si še primer, kako lahko uporabimo SVD pri dokazu lastnosti, da je vsaka matrika P, za katero velja P=P^T in P^2= P, ortogonalna projekcija.

      • Vaje 2

        V naloge, povezane z SVD, smo vključili še psevdoinverz. Poiskali smo psevdoinverz za matriko oblike \( AB^\top \) in pokazali obstoj in enoličnost polarne dekompozicije za nesingularne matrike. Ogledali smo si lastnost psevdoinverza, da $X = A^+$ minimizira \( \| A X - I \|_F \).

        • Vaje 3

          Na računalniku smo si ogledali, kako izostriti fotografijo preko regularizacije. Dokončali smo nalogo iz prejšnjih vaj.

        • Vaje 4

          Totalni najmanjši kvadrati, pogojenostno število za bločno matriko, začetek poglavja o občutljivosti lastnih vrednosti.

        • Vaje 5

          Končali smo z nalogo o občultjivih lastnih vrednostih. Nato smo reševali naloge, povezane z Gerschgorinovimi krogi.

          • Vaje 6

            Pogledali smo si nekaj nalog, povezanih z/s (ne)simetričnim problemom lastnih vrednosti.

            1) Hotellingova in Householderjeva redukcija za potenčno metodo,

            2) zgled za kubično konvergenco za Rayleighovo iteracijo.


            • Vaje 7

              1) Trditev, ki povezuje QR iteracijo z Rayleighovimi premiki in Rayleighovo iteracijo in 

              2) Primer, kjer za simetrično 3x3 matriko pogledamo Rayleigove kvociente (določimo krožnici, kjer so kvocienti enaki $\lambda_2$), preko katerih bi lahko ocenili, kam bi Rayleighova iteracija skonvergirala za dani začetni vektor.

            • Vaje 8

              Nadaljevali smo z nalogami, povezanimi s simetričnim problemom lastnih vrednosti. Pogledali smo si podprobleme, ki se navezujejo na metodo bisekcije in metodo deli in vladaj.

              1) Na primeru smo pogledali, kako prešteti pozitivne d_i v LDL^T, ko pride do deljenja z 0.

              2) Posplošitev formule det(I+xy^T), ko imata X in Y nekaj stolpcev.

              3) Časovna zahtevnost metode deli in vladaj.


              • Vaje 9


                Nadaljevali smo z nalogami, povezanimi s simetričnim problemom lastnih vrednosti. 

                1) Na primeru smo naredili en korak Newtonove metode z racionalno funkcijo za iskanje ničle sekularne funkcije.

                2) Izračun lastnih vrednosti tridiagonalne matrike preko rekurzivne formule za izračun determinante.


                • Vaje 10

                  1) "Optimalnost" Rayleighovega kvocienta in posplošitev na problem z več matrikami.

                  2) Določitev Givensove rotacije, ki zamenja dva sosednja diagonalna elementa zgornje trikotne matrike (nesimetrični primer).

                  3) Spodnja ocena za $\|x-y\|_2^2$ preko najmanjše in največje lastne vrednosti spd matrike $A$, kjer je $x^\top A y = 0$.


                  • Vaje 11

                    Pisanje kviza in Matlab implementacija razpoznavanja števk preko SVD.

                  • Vaje 12

                    Rešili smo še nekaj nalog za simetrične probleme (Courant-Fisher izrek za sing. vrednosti, pretvorba računanja kompleksnega SVD na realni SVD), nato smo začeli s posplošitvijo problema lastnih vrednosti (definitni matrični šopi) in posplošeni Rayleighov kvocient.

                    • Vaje 13

                      Ogledali smo si kvadratične probleme lastnih vrednosti (hiperbolični, eliptični, nadkritično dušeni, žiroskopski).

                    • Vaje 14

                      Ogledali smo si primer PEP in NEP, ter pripadajoče metode za reševanje. Nato smo začeli s poglavjem o tenzorjih; primere osnovnih manipulacij smo izvedli tudi v Matlabu na primerih.

                      • Vaje 15

                        Algoritem ALS-CP


                        Testiramo za funkcijo

                        f = @(x,y,z) x.^2 .*y .* z.^3 + cos(x.^2 .*y .* z.^3);