Weekly outline

  • General

  • Kvizi

    • 1. kviz: 26. november ob 14.30 v učilnicah 3.10 in 3.11

      2. kviz: 18. januar ob 14.00 v učilnicah 3.10 in 3.11

      Na kvizih lahko uporabljate zapiske s predavanj in vaj ter datoteke, ki ste si jih pripravili pri reševanju računalniških nalog.

    • Na kviz se lahko pripravite z reševanjem nalog z računalniških vaj (OneDrive repozitorij), predvsem tistih, ki so označene z D.

  • 4 October - 10 October

    Naredili bomo pregled matematičnih problemov, ki jih bomo numerično reševali. Povedali bomo, kaj je numerična metoda in kakšne so lastnosti dobrih numeričnih metod. Pri numeričnem računanju so ves čas prisotne napake, zato definiramo absolutno in relativno napako.

  • 11 October - 17 October

    Definirali smo, kaj je numerično stabilna numerična metoda in kaj sta obratna in direktna stabilnost oz. napaka. Za računanje skalarnega produkta smo pokazali, da je obratno stabilno, direktno pa ne. Pogledali smo nekaj poučnih numeričnih primerov, kjer pri uporabi formul, ki so sicer pravilne, pri nepazljivem numeričnem računanju hitro pridemo do nenatančnih rezultatov. 

    Zgledi v Matlabu

  • 18 October - 24 October

    Ukvarjali smo se z numeričnimi metodami za reševanje nelinearne enačbe. Kot prvo numerično metodo smo obravnavali bisekcijo. Nato smo obravnavali navadno iteracijo, kjer je pogoj za to, da je točka privlačna, ta, da je odvod iteracijske funkcije v negibni točki po absolutni vrednosti pod 1. Definirali smo red konvergence. 

    Zgledi v Matlabu

    • 25 October - 31 October

      Kot poseben primer navadne iteracije smo spoznali tangentno metodo, kjer si pomagamo tudi z odvodom. Tangentna metoda ima to lepo lastnost, da so (če je funkcija dvakrat zvezno odvedljiva) vse ničle privlačne, v splošnem primeru pa je konvergenca kvadratična.Kadar odvoda nimamo na voljo, lahko namesto tangentne uporabimo npr. sekantno metodo, Mullerjevo metodo ali inverzno interpolacijo. Pri kombiniranih metodah počasno a robustno bisekcijo kombiniramo z metodami višjega reda, kot sta npr. sekantna metoda in inverzna interpolacija. Primer je Brentova metoda, ki je uporabljena v Matlabovi funkciji fzero.

      Zgledi v Matlabu (ker je povezava vedno enaka in je objavljena na vrhu spletne učilnice, je v naslednjih poglavjih ne bom več ponavljal)

      • Kratek kviz iz reševanja nelinearnih enačb Quiz

        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.

    • 1 November - 7 November

      Začeli smo z naslednjim poglavjem, v katerem se bomo ukvarjali z reševanjem sistemov linearnih enačb. Najprej smo ponovili oznake in vektorske norme. Obravnavali smo operatorske matrične norme in pokazali nekaj uporabnih rezultatov, kot je npr. ta, da je matrika $I-X$, kjer je $\|X\|<1$, vedno obrnljiva.

      • 8 November - 14 November

        Obravavali smo občutljivost sistema linearnih enačb $Ax=b$ in ugotovili, da je odvisna od produkta $\|A\|\|A^{-1}\|$, kar smo poimenovali občutljivost ali pogojenostno število matrike $A$.

        S pomočjo elementarnih eliminacij smo izračunali LU razcep matrike. Prešteli smo število operacij, ki jih potrebuje algoritem za LU razcep matrike. LU razcep lahko izračunamo v 2/3 n^3 + O(n^2) operacijah. Stabilnejši varianti LU razcepa sta LU razcep z delnim ali kompletnim pivotiranjem, kjer je za obstoj razcepa dovolj, da je matrika A nesingularna.

        Programi:

        • 15 November - 21 November

          Raziskali smo obratno stabilnost reševanja linearnega sistema preko LU razcepa. Ugotovili smo, da je LU razcep brez pivotiranja nestabilen, LU z delnim pivotiranjem je v praksi stabilen, v teoriji ne, LU s kompletnim pivotiranjem pa je tudi teoretično obratno stabilen.

          Spoznali smo razcep Choleskega, s katerim rešujemo sisteme s simetričnimi pozitivno definitnimi matrikami. 

        • 22 November - 28 November

          Spoznali smo razcep Choleskega, s katerim rešujemo sisteme s simetričnimi pozitivno definitnimi matrikami. 

          V primeru simetrične nedefinitne matrike lahko uporabimo LDL^T razcep.

          V praksi se pri numeričnem reševanju parcialnih diferencialnih enačb ali drugih praktičnih problemov večkrat srečamo s tem, da je potrebno rešiti sistem z veliko in razpršeno matriko, kar pomeni, da je večina (razen O(n)) elementov enakih 0 in nimajo kakšne posebne strukture (kot jo npr. ima tridiagonalna matrika), ki bi jo lahko izkoristili. Velikost takih matrik je lahko tudi 100000 x 100000 ali še veliko več. Včasih lahko tak sistem vseeno učinkovito rešimo z razcepom, če matriko ustrezno preuredimo, da pri razcepu ne pride do pojava preveč novih neničelnih elementov, sicer pa se takšne sisteme rešuje iterativno. To obravnava predmet Iterativne numerične metode v linearni algebri na 2. stopnji.

          Obravnavali smo sisteme nelinearnih enačb. Spoznali smo posplošitev navadne iteracije, ki jo lahko izvajamo v Jacobijevi ali Seidelovi obliki. Za konverenco mora veljati, da je spektralni radij Jacobijeve matrike parcialnih odvodov v negibni točki manjši od 1. Preko razvoja v Taylorjevo vrsto smo izpeljali Newtonovo metodo, ki je posplošitev tangentne metode. Za reševanje nelinearnih sistemov imamo na voljo tudi metode, ki ne potrebujejo odvodov. Ena najbolj razširjenih je Broydenova metoda, ki se v primeru ene same enačbe ujema s sekantno metodo. 

          Programi:

          • 29 November - 5 December

            Začeli smo z obravnavo predoločenih linearnih sistemov, kjer imamo več enačb kot neznank. Ker točna rešitev v splošnem primeru ne obstaja, kot rešitev iščemo tisti vektor, ki minimizira normo ostanka. To rešitev imenujemo rešitev po metodi najmanjših kvadratov, dobimo pa jo kot rešitev t.i. normalnega sistema. Poleg normalnega sistema lahko predoločene sisteme rešujemo tudi s pomočjo QR razcepa. Za začetek smo spoznali računanje QR razcepa z uporabo Gram-Schmidtove ortogonalizacije.

            Programi:

            • Aproksimacija točk s kvadratnim polinomom: fit_parabola.m
            • QR razcep z uporabo Gram-Schmidtove ortogonalizacije:cgs.m, mgs.m

            • 6 December - 12 December

              Za računanje QR razcepa lahko uporabimo tudi ortogonalne transformacije, ki v matriki eliminirajo vse elemente pod diagonalo. Z Givensovimi rotacijami uničimo en po en element in matriko spravimo v zgornjo trapezno obliko. Tako pridemo do t.i. razširjenega QR razcepa. Še hitreje kot z Givensovimi rotacijami lahko podobno s Householderjevimi zrcaljenji uničimo vse elemente vektorja naenkrat in tako QR razcep izračunamo še hitreje. Seveda lahko QR razcep uporabimo tudi za reševanje navadnega linearnega sistema velikosti n x n namesto LU razcepa. Če npr. uporabimo Householderjeva zrcaljenja, porabimo dvakrat toliko operacij kot pri LU razcepu, a imamo zagotovljeno obratno stabilnost.

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


              Povezave:

              • Še močnejše orodje od QR je singularni razcep (SVD). Uporabljamo ga za reševanje zelo občutljivih sistemov, aproksimacijo matrik z matrikami nižjega ranga in mnogo drugih zadev. Obravnava se ga pri izbirnem predmetu Numerična linearna algebra v 2. semestru.

              • 13 December - 19 December

                Lotili smo se problema lastnih vrednosti. Pri samem problemu ločimo metode glede na to, kakšnega tipa je matrika in kaj potrebujemo. Pomembno je:

                • ali je matrika simetrična ali ne (oz. ima kakšno drugo strukturo, ki se jo da izkoristiti),
                • ali potrebujemo vse ali le nekaj lastnih vrednosti,
                • ali potrebujemo tudi lastne vektorje,
                • ali je matrika polna ali razpršena.


                Mi se bomo ukvarjali le z najbolj splošnim primerom, ko je matrika nesimetrična in polna. Naš cilj je izračunati Schurovo formo, iz katere lahko potem preberemo lastne vrednosti matrike. 

                Spoznali smo potenčno metodo, s pomočjo katere lahko izračunamo dominantno lastno vrednost. V metodi potrebujemo Rayleighov kvocient, ki nam za dani približek za lastni vektor vrne najboljši približek za lastno vrednost. Z inverzno iteracijo lahko izračunamo lastni vektor ki pripada numerično izračunani lastni vrednosti. Več dominantnih lastnih vrednosti skupaj lahko izračunamo z ortogonalno iteracijo, ki nas lahko pripelje tudi do Schurove forme. 

                Programi:

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


                • 20 December - 26 December

                  Še bolj učinkovito do Schurove forme pridemo s QR iteracijo. Pokazali smo, da je osnovna varianta QR iteracije ekvivalentna ortogonalni iteraciji, kjer začnemo z identiteto. Hessenbergova oblika se med QR iteracijo ohranja in s tem zmanjšamo zahtevnost enega koraka QR iteracije na  O(n2). Hitrost konvergence pospešimo s premiki. Enojni premik so dobri le za matrike, ki nimajo kompleksnih lastnih vrednosti, sicer pa so boljša izbira dvojni premiki.

                  Povezave:

                  • Do popolne QR iteracije nam manjka še en pomemben korak: kako narediti dvojni premik v času O(n2) samo s pomočjo realne aritmetike. Kako se to naredi s pomočjo implicitne QR iteracije, se obravnava v naslednjem semestru pri predmetu Numerična linearna algebra. Tam boste obravnavali tudi učinkovitejše algoritme za primer, ko je matrika simetrična.
                  • Če so matrike velike in razpršene, potem iščemo le nekaj lastnih vrednosti in za to uporabljamo iterativne metode (primer tovrstne metode je npr. potenčna metoda). To obravnava predmet Iterativne numerične metode v linearni algebri na 2. stopnji.



                  • 27 December - 2 January

                    Lotili smo se polinomske interpolacije. Definirali smo Lagrangeeve bazne polinome in pokazali, da lahko z njimi enolično zapišemo interpolacijski polinom. Zapisali smo tudi napako interpolacijskega polinoma. 

                    Bolj splošno orodje za polinomsko inerpolacijo so deljene diference, s katerimi lahko zapišemo interpolacijski polinom v t.i. Newtonovi obliki. Če dopustimo ujemanje točk, potem posplošimo interpolacijski polinom tako, da se v dani točki poleg v vrednosti s funkcijo ujema še v ustreznem številu odvodov. Izpeljali smo oceno napake v obliki z deljeno diferenco.


                    Povezave:

                    • 3 January - 9 January

                      Lotili smo se numeričnega integriranja. Najprej smo spoznali splošno kvadraturno formulo in ugotovili, da so koeficienti (uteži) določeni z integrali Lagrangeevih baznih polinomov. Nato smo obravnavali Newton-Cotesove formule, kjer vozle razdelimo ekvidistantno. Tu se pri večanju števila točk pojavi težava z neodstranljivo napako, saj uteži postanejo negativne, njihove absolutne vrednosti pa naraščajo. Rešitev so sestavljena pravila.

                      Pri Gaussovih kvadraturnih formulah lahko z izbiro ničel ortogonalnih polinomov za vozle dosežemo, da je formula točna za polinome stopnje 2n+1.

                      • 10 January - 16 January

                        Pogledali smo si uvod v numerične metode za reševanje navadnih diferencialnih enačb. Metode delimo na enokoračne in večkoračne, poleg tega pa še na eksplicitne in implicitne. Spoznali smo eksplicitno in implicitno Eulerjevo metodo, metodo razvoja v Taylorjevo vrsto in metode tipa Runge-Kutta. Definirali smo lokalno napako metode.

                        Pogledali smo, kako zgledajo veččlenske metode za reševanje začetnega problema in pristope za reševanje sistemov začetnih problemov in reševanje začetnih problemov višjega reda.

                        Programi:

                        • Primer v Matlabu za reševanje začetnega problema z Eulerjevo in R-K metodo: Zacetni.zip
                        • Programi za reševanje začetnega problema v Matlabu: ode.zip, kratek opis funkcij je v OdePreberiMe.txt
                        • Reševanje začetnega problema z enokoračnimi metodami: zacproblem1.zip (Mathematica)

                        Povezave:


                      • 17 January - 23 January

                        Pogledali smo, kako zgledajo veččlenske metode za reševanje začetnega problema in pristope za reševanje sistemov začetnih problemov in reševanje začetnih problemov višjega reda.

                        • Vaje