Matematyka obliczeniowa II

monograficzne

Metody numerycznego rozwiązywania ważnych zadań obliczeniowych matematyki stosowanej: zagadnienia własnego, wielkich układów równań liniowych, układów równań nieliniowych oraz całkowaniu wielowymiarowemu.

* Zagadnienie własne. Uwarunkowanie zadania własnego. Metoda potegowa, odwrotna potegowa i Rayleigh. Iteracja QR. Zbieżność tych metod w przypadku symetrycznym. Sprowadzanie do prostszej postaci przez przekształcenia ortogonalne. Informacja o metodach: Jacobiego oraz ?dziel i rzadź?. Oszacowania kosztu tych metod i ich własności numeryczne. (3 wykłady)

* Rozkład SVD i jego zastosowanie do nieregularnego zadania najmniejszych kwadratów. (1 wykład)

* Metody iteracyjne rozwiazywania wielkich układów równań liniowych. Metody CG i GMRES, ich zbieżność i implementacja. Przykłady metod stacjonarnych i warunek dostateczny zbieżności. Przeglad innych metod iteracyjnych (CGT, PCR, BiCG, wielosiatkowe, itp). Możliwości prowadzenia obliczeń na komputerach równoległych. Ściskanie macierzy na przykładzie macierzy spektralnie równoważnych. (4 wykłady)

* Układy równań nieliniowych. Metoda Banacha. Metoda Newtona, z przybliżona pochodna, przybliżona metoda Newtona, Broydena. Twierdzenia o zbieżności tych metod. Informacja o twierdzeniu Kantorowicza. Kryteria stopu. Informacja o metodzie kontynuacji. (4 wykłady)

* Numeryczne obliczanie całek wielowymiarowych. Kwadratury jednowymiarowe (Newtona?Cotesa, Gaussa, złożone). Niskowymiarowe kwadratury na siatkach gestych. Przekleństwo wymiaru. Metoda całkowania Monte Carlo z dowodem. Informacja o metodach redukcji wariancji i o QMC. (3 wykłady)

J. Demmel, Numerical Linear Algebra

T. Kelley, Iterative Solution of Linear and Nonlinear Equations

P. Davis and P. Rabinovitz, Methods of numerical integration

Efekty uczenia

Wiedza i umiejętności

1. Zna podstawowe formaty macierzy rzadkich. Zna kilka przykładów zadań w których takie macierze się pojawiają.

2. Wie co to jest iteracyjna metoda rozwiązywania układów równań liniowych

3. Zna metody iteracyjne typu Jakobi, Gauss, Seidel i Richardsona. Wie przy jakich założeniach te metody są zbieżne. Zna twierdzenie o warunku dostatecznym i koniecznym zbieżności prostych metod iteracyjnych.

4. Zna zasadę konstrukcji prostych metod gradientowych. Zna metodę najszybszego spadku i minimalnych residuów oraz zna twierdzenia mówiące o szybkości zbieżności tych metod.

5. Zna zasadę ogólną konstrukcji metod typu Kryłowa. Zna konstrukcję metod sprzężonych gradientów i GMRES. Wie przy jakich założeniach metody te są zbieżne i jaka jest oszacowanie szybkości zbieżności tych metod.

6. Wie na czym polega ściskanie macierzy (preconditioning) i zna kilka prostych technik konstrukcji prekonditionerów.

7. Zna wielowymiarowe metodę Newtona i metodę Banacha rozwiązywania układów równań nieliniowych. Wie kiedy te metody są zbieżne i co oznacza wykłądniczy rząd zbieżności metody iteracyjnej rozwiązywania układów równań nieliniowych.

8. Zna metodę Broydena. Wie jak praktycznie obliczać na komputerze kolejne iteracje tej metody.

9. Zna metody globalizacji zbieżności metod rozwiązywania układów równań nieliniowych

10. Wie na czym polega symetryczne numeryczne zadanie własne. Zna metodę sprowadzenia macierzy symetrycznej do macierzy podobnej trójdiagonalnej przy pomocy macierzy Householdera. Wie ile wynosi koszt tej operacji.

11. Zna metody potęgową i odwrotną potęgową. Wie przy kiedy te metody są zbieżne.

12. Zna wyprowadzenie metody QR i jej podstawowe własności.

13. Zna metodę dziel i rządź znajdowania par własnych dla macierzy trójdiagonalnej.

14. Zna metodę Hymana.

15. Wie na czym polega tzw. przeklęństwo wymiaru na przykładzie zadania wielowymiarowego całkowania.

16. Zna metody Monte Carlo i Quasi-Monte Carlo. Zna podstawowe własności tych metod.

Kompetencje społeczne:

1. Rozumie znaczenie metod rozwiązywania przybliżonego układów równań, zadania własnego i całkowania wielowymiarowego jako narzędzi służących do modelowania praw przyrody.