Tedenski povzetek

  • Splošno

  • Evidenca prisotnosti

  • Izpiti

    Za pristop k izpitu je obvezna prijava v VISu vsaj tri dni pred izpitnim rokom!

    1. pisni izpit: 25. 1. 2022 ob 10.00 v 2.01

    2. pisni izpit:   3. 6. 2022 ob 10.00 v 3.05

    3. pisni izpit: 26. 8. 2022 ob 10.00 v 3.05

  • Kvizi

    Na kvizih je dovoljena uporaba datotek, pripravljenih na vajah in v okviru priprav na kvize.

    1. kviz: torek, 23. november, ob 8.00.
    2. kviz: petek, 7. januar, ob 10.00.

  • 11. oktober - 17. oktober

    Prvi teden se bomo seznanili z režimom in na kratko pregledali probleme, ki jih bomo numerično reševali pri tem predmetu. Ukvarjali se bomo z linearnimi, nelinearnimi in predoločenimi sistemi.

    Na kratko bomo pogledali, kako so števila predstavljena v premični piki. Ker imamo na voljo le končno mnogo predstavljivih števil, se pri računanju pojavijo zaokrožitvene napake. 

    Predavanja bodo prva dva tedna potekala s pomočjo prosojnic, potem pa večinoma s pisanjem na tablo in prikazovanjem zgledov v Matlabu.

    Na vajah boste pogledali osnove Matlaba. Naslednjič bomo nadaljevali z osnovami Matlaba in rešili nekaj nalog iz vira Matlab delo z matrikami, risanje.

  • 18. oktober - 24. oktober

    Spoznali smo tri vrste napak, ki se pojavijo pri numeričnem računanju: neodstranljivo napako, napako metode in zaokrožitveno napako. Povedali smo, kdaj je numerična metoda stabilna in kako to lahko ugotovimo preko analize zaokrožitvenih napak. Tako smo na primer videli, da je računanje produkta n+1 števil direktno in obratno stabilno.


  • 25. oktober - 31. oktober

    Pokazali smo, da je računanje skalarnega produkta v splošnem samo obratno stabilno. Na nekaj poučnih primerih smo videli, na kaj moramo paziti pri numeričnem računanju.

    Lotili smo se numeričnega reševanja nelinearnih enačb. 

    Zgledi v Matlabu

  • 1. november - 7. november

    Pri reševanju nelinearnih enačb smo spoznali prvi numerični metodi - bisekcijo in navadno iteracijo. Pri navadni iteraciji smo videli, da je pogoj za konvergenco ta, da je absolutna vrednost odvoda v negibni točki manjša od 1. 

    Zgledi v Matlabu

    • 8. november - 14. november

      Definirali smo red konvergence. Kot poseben primer navadne iteracije smo obravnavali tangentno metodo. Pri tangentni metodi smo pokazali, da ima za enostavne ničle vsaj kvadratno konvergenco. 

      • 15. november - 21. november

        Sekantna metoda ne uporablja odvodov in je velikokrat učinkovitejša od tangentne metode, čeprav ima nižji red konvergence. Na predavanjih smo spoznali Mullerjevo metodo, inverzno inerpolacijo in glavno idejo kombiniranih metod (kot je npr. Brentova metoda v fzero v Matlabu).

        Zgledi v Matlabu

        • Kratek kviz iz reševanja nelinearnih enačb

          To je kratek kviz iz numeričnega reševanja nelinearnih enačb. Tako kot vsi ostali kvizi ne vpliva na končno oceno. Z reševanjem boste utrdili snov in spotoma izvedeli še kaj novega, če nič drugega pa lahko služi tudi za razvedrilo.

      • 22. november - 28. november

        Začeli smo z obravnavo reševanja linearnih sistemov. Najprej smo ponovili oznake in definicije iz linearne algebre, potem pa smo obravnavali vektorske norme.

      • 29. november - 5. december

        Dokončali smo matrične norme in pokazali, od česa je odvisna občutljivost nesingularnega linearnega sistema. 

        Programi:

        • Zgled zelo občutljivega sistema: Računanje polinoma v standardni bazi, ki aproksimira sin(x) na [0,1]: zgledEnakApr.m

        • 6. december - 12. december

          Z uporabo elementarnih eliminacij smo izračunali LU razcep matrike in pokazali, kako s pomočjo matrik L in U rešimo linearni sistem. Pokazali smo, kdaj obstaja LU razcep brez pivotiranja. Ker to ni vedno možno oziroma takrat ko je možno, ni nujno stabilno, moramo vključiti še pivotiranje. Tako pri delnem pivotiranju dobimo razcep PA=LU, kjer je P permutacijska matrika, L spodnja trikotna matrika z enicami na diagonali, U pa zgornja trikotna matrika. 

          Programi:

          • 13. december - 19. december

            Analizirali smo obratno stabilnost reševanja linearnih sistemov preko LU razcepa in ugotovili, da je pri delnem pivotiranju metoda v praksi stabilna, teoretično pa obstajajo matrike, kjer bo napaka prevelika.

            • 20. december - 26. december

              Začeli smo z obravnavo predoločenih sistemov. Za sistem $Ax=b$, kjer je matrika $A$ polnega ranga in ima več vrstic kot stolpcev, lahko poiščemo rešitev po metodi najmanjših kvadratov, ki minimizira normo ostanka $\|Ax-b\|_2$. Pokazali smo, da mora za rešitev veljati, da je ostanek $b-Ax$ pravokoten na sliko matrike $A$, kar nas pripelje do normalnega sistema $A^TAx=A^Tb$, ki ga lahko učinkovito rešimo z uporabo razcepa Choleskega. Pokazali smo, da za vsako simetrično pozitivno definitno matriko obstaja razcep Choleskega.

              Programi:

              • Programi v Matlabu za računanje QR razcepa (CGS, MGS, Givens, Householder): QRrazcep.zip

              • 27. december - 2. januar

                 Predoločeni sistem lahko rešimo bolj zanesljivo, če uporabimo QR razcep. Spoznali smo dve metodi za računanje QR razcepa: Gram-Schmidtovo ortogonalizacijo in Givensove rotacije.

                Programi:

                • Programi v Matlabu za računanje QR razcepa (CGS, MGS, Givens, Householder): QRrazcep.zip

                • 3. januar - 9. januar

                  Spoznali smo še Householderjeva zrcaljenja, ki jih lahko uporabimo za računanje QR razcepa. QR razcep lahko za polno matriko najbolj učinkovito izračunamo preko Householderjevih zrcaljenj. QR razcep lahko seveda izračunamo tudi za kvadratne matrike in ga uporabimo za reševanje navadnega linearnega sistema. Tako porabimo dvakrat več operacij kot pri LU razcepu, a imamo zagotovljeno obratno stabilnost. Pokazali smo, da za vsako matriko obstaja singularni razcep.

                  • 10. januar - 16. januar

                    Za vsako matriko obstaja singularni razcep. To je zelo uporabno orodje, ki ga lahko med drugim uporabimo za reševanje predoločenih sistemov in iskanje matrik nižjega ranga, ki dobro aproksimirajo matriko. Kot primer uporabe smo omenili možnost aproksimacij slik in delovanje spletnih brskalnikov.

                    Programi:

                  • Vaje

                    Vaje 1 (6. oktober). Ogledali smo si osnovne ukaze v Matlabu.

                    Vaje 2 (13. oktober).  Ponovili smo pretvarjanje števil med različnimi bazami. Ogledali smo si format zapisa v premični piki P(b,t,L,u). Nekaj matematičnih izrazov smo pretvorili v bolj stabilno obliko. 

                    Vaje 3 (20. oktober). Ogledali smo si, kako stabilno izračunati e^(-x), x>0, preko Taylorjeve vrste, in da je lahko analitičen izračun določenega integrala nestabilen. Videli smo, da je računanje člena preko tričlenske rekurzivne formule lahko zelo občutljiv problem glede na začetne podatke (parazitski člen). Pogledali smo si dokaz izreka iz predavanj, ki govori o zgornji oceni relativne napake predstavitve števila, (ocena u/(1+u)).

                    Vaje 4 (27. oktober), 1 ura. Dokončali smo dokaz iz prejšnjih vaj. Nato smo začeli z direktno/obratno stabilnostjo za algoritem za izračun x^2-y^2.

                    Vaje 5 (3. november). Dokončali smo analizo stabilnosti za x^2 - y^2. Začeli smo z nelinearnimi enačbami, ogledali smo si babilonsko metodo za računanje korena števila.

                    Vaje 6 (10. november). Ogledali smo si še nekaj primerov navadne iteracije. Določili smo tudi red konvergence in ocenili napako izračuna do negibne točke preko dveh zaporednih približkov.

                    Vaje 7 (17. november). Ogledali smo si nalogo, kjer poiščemo optimalne parametre za navadno iteracijo. Rešili smo nalogi, kjer smo uporabili tangentno metodo (ničle za e^x + x^2 - 3) in sekantno metodo (problem stanovanj).

                    Vaje 8 (24. november). Dokazali smo red konvergence tangentne metode za večkratno ničlo. Pokazali smo, kako bi tangentno metodo uporabili za izračun inverza funkcije. Omenili smo Halleyjevo iteracijo in nakazali, kako bi preverili, da ima 3. red konvergence za enostavno ničlo (funkcije $x^n-a$). Začeli smo z matričnimi normami.

                    Vaje 9 (1. december). Ponovili smo dokaz s predavanj za enakost $\| \|_1$ in največje norme stolpca matrike. Dokazali smo zvezo $1/\sqrt n  \| A\|_\infty \leq  \|A_2\| \leq \sqrt m \| A\|_\infty$. Pokazali smo, da je $A^\top A$ spsd in da so njene lastne vrednosti nenegativne. Izračunali smo 2-normo za $3\times3$ matriko. Ogledali smo si norme matrike $A = u v^\top$.

                    Vaje 10 (8. december). Dokončali smo naloga za $A = u v^\top$. Začeli smo z reševanjem linearnih sistemov preko LU razcepa in rešitve dveh trikotnih sistemov. Ogledali smo si daljši postopek LU razcepa preko vmesnih matrik $L_i$ in kompakten način v eni matriki.

                    Vaje 11 (15. december). Izračunali smo časovno zahtevnost LU za zg. Hessenbergovo matriko. Ogledali smo si Thomasov algoritem za reševanje 3-diag sistemov in prešteli št. računskih operacij. Rešili smo linearen sistem preko LU z delnim pivotiranjem.

                    Vaje 12 (22. december). Končali smo primer LU z delnim pivotiranjem. Poiskali smo postopek iz izračun inverza matrike preko LU in prešteli št. računskih operacij. Ponovili smo, kako izračunamo razcep Choleskega.

                    Vaje 13 (29. december). Ogledali smo si dva zgleda za razcep Choleskega. Rešili smo predoločen sistem po metodi najmanjših kvadratov.

                    Vaje 14 (5. januar). Ogledali smo si še en zgled predoločenega sistema. Preko modificiranega Gram-Schmidtovega postopka smo izračunali QR razcep.

                    Vaje 15 (12. januar). Ogledali smo si Householderjeva zrcaljenja in Givensove rotacije, preko katerih lahko izračunamo razširjeni QR razcep. Dodaten primer za QR preko Householderja: https://unilj-my.sharepoint.com/:b:/g/personal/tadej_kanduc_fmf_uni-lj_si/EUJNW6vmP9hEordKCINjiOIBdmzhR1Es_ObvQ-ZuBEJ0Zg?e=hh51UD.

                  • Računalniške vaje

                    Vaje potekajo ob petkih od 10:15 do 12:00 v učilnici 3.10. Vsaka skupina ima vaje vsak drugi teden (alternirajoče se izmenjujeta).