Počítačové metody v teoretické fyzice - TMF057(ZS 2015-16)

Aktualiky: (15. ledna 2016)  zadání zápočtových úloh a doplnil jsem silabus a demostrační scripty v pythonu.

 (29. října 2015) Průběžně doplňuji aktuální sylabus a demonstrace z přednášek v PYTHONu.

LEKCE 1 - Zaokrouhlovací chyby a numerická stabilita:

• Reprezentace reálných čísel v pohyblivé řádové čárce a zaokrouhlovací chyba.
• Strojové epsilon, skládání chyb při základních aritmetických operacích. Problémy s odčítáním podobných čísel.
• Numerická stabilita a podmíněnost úlohy.

Demonstrace:

1. Zaokrouhlovací chyba (triviální příklad) ...................... demoL01.01_wrong_loop.py
2. Sčítání odpředu = sčítání odzadu? .............................. demoL01.02_suma.py
3. Zaokrouhlovací chyba při odčítání............................... demoL01.03_cancelation.py
4. Kvadratická rovnice (minimalizace zaokr. chyby)......... demoL01.04_quadratic.py
5. Proč nekonverguje absolutně konvergentní řada?......... demoL01.05_Taylor_exp.py

Cvičení: Určení čísla pi Archimedovou metodou. (pokus1-nestabilní, pokus2-funkční, pokus3-urychlení konvergence)

LEKCE 2 - Iterace a řešení nelineárních rovnic.

• Věta o pevném bodě kontrahujícího zobrazení a konvergence iterací.
• Odhad chyby, řád konvergence a její urychlování.
• Aitkenův a Aitkenův-Steffensenův algoritmus.
• Iterační řešení nelineárních rovnic. Newtonova metoda.

Demonstrace:

1. cos(cos(cos(...cos(1.0)...)))..................................demoL02.01_coscos.py
2. Babylonská metoda výpočtu odmocniny................demoL02.02_Babylon.py
3. Aitken na cos cos.................................................demoL02.03_Aitken.py
4. Aiten-Steffensen na cos cos..................................demoL02.04_AitkenSteffensen.py
5. Newtonův fraktál = odpověď na otázku: "Ke kterému kořenu rovnice z³-1=0 dokonverguje Newtonův algoritmus spuštěný z daného místa komplexní roviny?" dává obrázek https://en.wikipedia.org/wiki/Newton_fractal

LEKCE 3 - Interpolace a interpolační polynomy.

• Existence a jednoznačnost polynovmiální iterpolace.
• Lagrangeova interpolace, Aitkenovo-Nevillovo Schema.
• Chybový vzorec a jeho chování na rovnoměrné a Čebyševově síti.
• Hermiteova interpolace, chybový vzorec a souvislost s Taylorovou řadou.

Demonstrace: (používají metod knihovny Turtle graphics z Pythonu pro zobrazení dat)

1. Interpolace na rovnoměrné síti...............................demoL03.01_regular.py
2. Chování polynomu omega.....................................demoL03.02_omega.gnu (script pro gnuplot - testováno ve verzi 4.7)
3. Interpolace na Čebyševově síti..............................demoL03.03_chebychev.py

LEKCE 4 - Interpolace na rovnoměrné síti, diferenční rovnice.

• Operátory zpětné a dopředné diference. Funkce operátorů.
• Newtonova interpolační formule.
• Odvození vzorců pro derivaci interpolačních polynovů.
• Numerické integrování a Eulerova-Maclaurinova sumační formule.
• Lineární diferenční rovnice a jejich řešení. Explicitní formule pro Fibonacciho posloupnost.

LEKCE 5 - Numerická derivace derivace a integrace.

• Analýza chování zaokrohlovací a diskretizační chyby pro různé aproximace derivace funkce.
• Integrace pomocí Newtonových-Cotesových formulí.
• Použití Richardsonovy extrapolace a Rombergova integrace.
• Gaussova kvadratura a ortogonální polynomy.
• Diskuse různých přístupů k interaci, singularity integrandu, nevlastní integrály. Více dimenzí.

Cvičení: Numerické derivování, diskretizační a zaokrouhlovací chyba (výpis numerické derivace pro různé hodnoty h do souboru a zobrazení chyby výsledků pomocí gnuplotu).

Demonstrace: (Numerická derivace, diskretizační x zaokrouhlovací chyba)

1. Derivace různými diskretizačními formulemi .........demoL4.01_derivace.py
2. Zobrazení výsledků..............................................demoL4.01_derivace.gnu (script pro gnuplot)

LEKCE 6 - Numerická integrace diferenciálních rovnic.

• Formulace počáteční úlohy pro ODR. Převení rovnice vyššího řádu na soustavu rovnic prvního řádu.
• Příklady odvození jednoduchých diferenčních schémat.
• Formulace obecné lineární multikrokové formule (LIMUFO). Řád přesnosti a konzistence metody.
• Souvislost s aproximací funkce logaritmus, odvození metod pomocí Padého aproximace. Metody AB, BA a BD
• Charakteristické polynomy a stabilita metody. Stabilita Adamsových metod a zpětné diference.
• Dahlquistovy věty o konvergenci a bariéry stability, absolutní stability, oblasti stability.

Demonstrace: (Numerické řešení diferenciálních rovnic)

1. Výpočet řešení počáteční úlohy explicitními formulemi ...........demoL5.01_LIMUFO.py
2. Zobrazení řešení pro různé metody ....................................... reseni.gnu (script pro gnuplot, ukaze data z predchoziho *.py)
3. Testování rychlosti konvergence pro zmenšující se krok..........demoL5.02_global.py
4. Zobrazení rychlosti konvergence ........................................... konverg.gnu
5. Jako 1,2 ale implicitni.............................................................demoL6.01_implicit.py,    reseni.gnu
6. Jako 3,4 ale implicitni ............................................................demoL6.02_stiff.py,         kstif.gnu

LEKCE 7 - Numerická lineární algebra - faktorizace matic.

• O numerické algebře obecně: pojem faktorizace matice, charakterizace algoritmu pomocí asymptotické složitosti (FLOPs)
• Gram-Schmidtova ortogonalizace a QR-faktorizace. Stabilita, Hausholderova metoda, složitost algoritmu.
• SVD-faktorizace. Existence singulárního rozkladu a jeho použití.
• Řešení soustavy rovnic ve smyslu nejmeších čtverců. Normální rovnice a pseudoinverze, řešení pomocí faktorizací.
• Norma vektoru a matice. Příklady norem a jejich výpočet. Základní nerovnosti.
• Stabilita a zpětná stabilita. Zpětná stabilita QR faktorizace.

Demonstrace: (Faktorizace matice a její použití):

1. Nalezení vlastních fcí kvantového oscilátoru ..................DemoL8.01_QR_LHO.py
2. Zpetná stabilita QR faktorizace.....................................DemoL8.02_zpet_stabil.py
3. Hodnost matice pomocí QR.........................................DemoL8.03_Hello.py

LEKCE 8 - Numerická lineární algebra - Gaussova eliminace.

• Podmíněnost úlohy. Číslo podmíněnosti matice a jeho význam pro různé úlohy.
• Řešení soustavy rovnic a jeho souvislost s Gaussovou eliminací. LU rozklad.
• Stabilita LU rozkladu Gaussovou eliminací, pivotace.
• Použití LU rozkladu na řešení soustav, nalezení inverze, determinantu matice.
• Složitost Gaussovy eliminace. Tridiagonální a pásové matice. Symetrické matice (Choleského rozklad)
• Řešení soustav rovnic se špatně podmíněnou maticí. Použití SVD.

Demonstrace: (Gaussova eliminace a LU rozklad)

1. Gauss bez pivotace......................DemoL9.01_LU_nestab.py
2. Gauss s pivotaci...........................DemoL9.02_LU_pivot.py
3. LU rozklad z knihovny scipy.........DemoL9.03_LU_linalg.py

LEKCE 9 - Numerická lineární algebra - diagonalizace matic.

• Pojem diagonalizace. Vlastní čísla a jejich multiplicita. Levé a pravé vlastní vektory. Charakteristický polynom.
• Diagonalizace reálné symetrické matice Jacobiho metodou. Konvergence a asymptotická složitost metody.
• Přehled dalších metod. Převedení do tridiagonálního (Hessenbergova) tvaru.
• Princip QR algoritmu. Hledání kořenů charakteristického polynomu tridiagonální matice.

Demonstrace: (Diagonalizace Jacobiho metodou)

1. Pouziti diagonalizace z numpy..........................DemoL10.01_eigval.py
2. Jacobiho metoda se "speepy"..........................DemoL10.02_Jacobi.py
3. Jacobiho metoda s vyhledáním max. prvku......DemoL10.03_Jacobi_max.py

LEKCE 10 - Diskrétní Fourierova transformace (odpřednesl jsem zrychleně - nezkouším)

• FT, semiDFT a DFT, Nyquistova frekvence.
• Algoritmust rychlé Fourierovy transformace (FFT) a jeho složitost.
• Použití Fourierovy transformace na řešení problémů.

Letos přednáší Matin Čížek. Informace z loňských stránek Karla Houfka naleznete naleznete zde.

MOJE STRÁNKY ZE ZS 2013/14:

14.1. Vyrobil jsem konečné požadavky ke zkoušce, věnujte jim pozornost, budu podle nich volit otázky. Také jsem se snažil opravit drobné chyby a nepřesnosti v poznámkám k přednášce, které naleznete ZDE. Bohužel jsem nestihl dokončit v ucelené podobě lineární algebru a fourierovu trasformaci, tak se podívejte alespoň na odkazy a průběžně sledujte tuto stránku, možná se tu objeví ještě lepší verze.

Zápočtové úlohy:

Ze zápočtových úloh je potřeba vybrat jednu a tu vyřešit v nějakém vyšším programovacím jazyce (FORTRAN, Pascal, C, C++,...). Při řešení je možno používat podprogramy z Numerických receptů, které na požádání dodám ve Fortranu, Pascalu nebo C, ale protože jsou potřeba jen algoritmy, které jsme probrali na přednášce, doporučuji zkusit si je naprogramovat. Rozhodně nepovažuji za vypracované úlohy  v jazycích pro symbolické manipulace typu Maple/Mathematica, které mají vestavěné hotové numerické procedury pro řešení rovni, numerickou lineární algebru atd.  

Požadavky ke zkoušce (předběžné, upřesním v zápočtovém týdnu)

Zkouška sestává ze dvou otázek vybraných z následujících okruhů. Jedna otázka se týká teorie k zápočtové úloze, kterou jste si vybrali a jejíž řešení mi představíte a vysvětlíte.

1) Zaokrouhlovací chyby, diskretizační chyba, numerická nestabilita, podmíněnost úlohy. Stabilní výpočet kořenů kvadratické rovnice.

2) Iterace, rychlost konvergence a urychlování konvergence. Aitkenův vzorec. Řešení nelineárních rovnic: bisekce, převedení na iterace, Newtonova metoda. Zobecnění na systémy rovnic.

3) Polynomiální interpolace, Lagrangeův a Hermiteův interpolační polynom. Interpolace na rovnoměrné síti. Newtonův interpolační vzorce, integrace a derivace interpolačního polynomu. Řešení diferenčních rovnic. Numerická derivace, analýza velikosti chyby metody a zaokrouhlovací chyby, optimální volba kroku.

4) Numerická integrace:Newtonovy-Cotesovy vzorce, metoda Richarsonovy extrapolace a Rombergova metoda. Gaussovy kvadratury. Principy metod a oblast použitelnosti.

5) Integrace obyčejných diferenciálních rovnic. Převedení rovnice vyššího řádu na soustavu prvního řádu. Lineární mnohokrokové metody, jednokrokové metody vyššího řádu - Rungeovy-Kuttovy metody. Volba délky kroku. Řád metody a stabilita. Problematika silného tlumení a implicitní metody. Numerovova metoda pro rovnice druhého řádu.

6) Okrajové úlohy - standardní typy problémů. Metoda střelby. (Relaxační metody. Jiné principy řešení (rozklad do baze, převedení na integrální rovnici, variační metody)

7) Základy numerické lineární algebry: Singulární rozklad matice, QR faktorizace. Metody výpočtu QR faktorizace: Grammova-Schmidtova ortogonalizace, Hausholderova metoda. Řešení lineárních úloh v nejmenších čtvercích. Podmíněnost úloh lineární algebry a pojem zpětné stability.

8) Číslo podmíněnosti matice. Řešení soustav lineárních rovnic. Gaussova eliminace a zpětná substituce, pivotace, trojúhelníkový (LU) rozklad. Choleského rozklad. Tridiagonální a pásové matice. Rozklad do singulárních hodnot a jeho použití pro soustavy lineárních rovnic. Iterační zpřesňování řešení a iterační metody, projekční metody pro inverzi matic po částech nebo inverzi části matice.

4) Diagonalizace matic - Jakobiho metoda. Použití na reálné a na Hermitovské matice. Převedení na Hessenbergův tvar a nalezení kořenů charakteristického polynomu. Stručný přehled dalších metod.

8) Semidiskrétní a diskrétní Fourierova transformace, Nyquistova kritická frekvence, rychlá FT. Příklady použití FT.

9) Integrální rovnice: typy standardních úloh. Přímé metody pomocí kvadraturního vzorce a Richarsonova extrapolace. Další možnosti (stručně): rozvoj do baze, iterační metody, variační metody, poruchové metody.

10) Stučně o minimalizace funkcí jedné a více proměnných.

11) Aproximace Padé.

Doporučená literatura

[0] Moje poznámky k přednášce (neúplné).

[1] Press, Teukolsky, Vetterling, Flannery: Numerical Recipes in C, Fortran, ...(prakticky orientované s knihovnou podprogramů v různých programovacích jazycích), k dispozici online.

[2] L.N. Trefethen: Finite difference and spectral methods for ODE and PDE. Nedopsaná kniha přístupná online: http://web.comlab.ox.ac.uk/nick.trefethen/pdetext.html (Obsahuje přehledný výklad teorie lineárních mnohakrokových metod pro obyčejné diferenciální rovnice)

[3] L.N. Trefethen, D. Bau III: Numerical Linear Algebra. SIAM 1997. (Velice čtivý a pedagogický výklad numerické lineární algebry)

[4] Isaacson, Keller: Analysis of Numerical Methods....(Matematické, důkazy konvergence, stability).

[5] Koonin: Computational Physics....(Numerické algoritmy stručně s aplikací na fyzikální problémy).

[6] Henrici: Essentials of Numerical Analysis with Pocket Calculator Demonstrations...(Rozbor základních numerických algoritmů s demonstrací hlavních obtíží na spoustě jednoduchých příkladů).

[7] Vitásek: Numerické metody. (Snadno dostupné v češtině. Obsáhlá příručka algoritmů.)

[8] Segethová: Základy numerické matematiky.(Skriptum. Výběr základních numerických algoritmů s důkazy konvergence.)