Numeryczna algebra liniowa

Tematyka wykładu jest związana z typowymi zadaniami obliczeniowymi algebry liniowej (dla macierzy rozrzedzonych), spotykanymi w zastosowaniach. Jednym ze źródeł takich zadań są łańcuchy Markowa, innym są równania różniczkowe cząstkowe.

Wykład może być szczególnie interesujący dla osób, które uczęszczały, uczęszczają lub będą uczęszczać na wykłady: Numeryczne metody równań różniczkowych cząstkowych oraz Algorytmy równoległe rozwiązywania RRCz.

Podręczniki

• Andrzej Kiełbasiński i Hubert Schwetlick, Numeryczna algebra liniowa. Wydawnictwa Naukowo-Techniczne, Warszawa 1992.
• Gene Golub and Charles Van Loan, Matrix Computations. Johns Hopkins University Press, 1996.
• Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia 1996.
• Wolfgang Hackbusch, Iterative Solution of Large Sparse Systems. Springer, 1994.
• Yousef Saad, Iterative methods for sparse linear systems oraz Numerical Methods for Large Eigenvalue Problems. SIAM, Poprzednia wersja dostępna on-line: http://www-users.cs.umn.edu/~saad/books.html
• James W. Demmel, Applied Numerical Linear Algebra. SIAM, Philadelphia 1997.

Interesujące mogą być także wybrane rozdziały z podręcznika D. Kincaid and W. Cheney Analiza numeryczna. WNT, 2006.

2006/07

Program

• Zadania i algorytmy gęstej algebry liniowej
  • Układy równań
  • Zagadnienie własne
  • SVD
• Algorytmy rozwiązywania układów równań z macierami rozrzedzonymi
  • Iteracyjne metody stacjonarne
  • Metody przestrzeni Kryłowa
  • Ściskanie i imadła

Egzamin

Egzamin pisemny

Zadania i pytania o treści wykładu, wymienione poniżej. Dowody (zaznaczone poniżej) mogą być wymagane na ocenę bardzo dobrą. Zadania rozwiązujemy z możliwością wspomożenia się notatkami, na pytania odpowiadamy bez żadnych pomocy naukowych.

Egzamin ustny

Egzamin dla chętnych, w terminie ustalonym po ogłoszeniu wyników pisemnego.

...tydzień po tygodniu

• Obszary zainteresowań numerycznej algebry liniowej. Ile można zyskać, gdy wie się coraz więcej o macierzy. Normy macierzowe i wektorowe oraz ich własności, z dowodami. Lemat von Neumanna. Uwarunkowanie zadania rozwiązywania układu równań liniowych, z dowodem.
• Numeryczne kryterium NP z dowodem. Wykonalność eliminacji Gaussa. Numeryczna poprawność eliminacji Gaussa z dowodem. Narzędzia do dowodu numerycznej poprawności eliminacji Gaussa: numeryczna realizacja iloczynu skalarnego i rozwiązywania układu z macierzą trójkątną.
• Wskaźnik wzrostu. Dokończenie dowodu praktycznej numerycznej poprawności eliminacji Gaussa. Górne oszacowanie wskaźnika wzrostu: przykład macierzy patologicznej. Informacja o typowo spotykanych wskaźnikach wzrostu. Rozkład LU macierzy rozszerzonej i kryterium jej odwracalności.
• Wzór Sherman-Morrison-Woodbury. Wykonalność rozkładu LU bez wyboru i wskaźnik wzrostu dla macierzy diagonalnie dominującej i symetrycznej dodatnio określonej. Algorytm Cholesky'ego i jego wariant bez pierwiastków. Elementy optymalizacji programów numerycznych dla architektur z pamięcią hierarchiczną. Blokowanie algorytmów algebry liniowej jako sposób na skuteczne wykorzystanie pamięci podręcznej. BLAS, LAPACK i ATLAS.
• Metody iteracyjne klasyczne - stacjonarne. Ogólna teoria zbieżności z dowodem. Metody: Richardsona (dobór optymalnego parametru), Jacobiego (zbieżność dla diag. dom.), SOR (zbieżność w zależności od parametru). Warianty twierdzeń o zbieżności dla macierzy niesymetrycznych w/g Hackbuscha z dowodami.
• Twierdzenie Ostrowskiego. Metoda CG: jej wyprowadzenie, implementacja, własności z dowodem. CG jako metoda bezpośrednia i jako metoda iteracyjna.
• Algorytm PCG. Spektralna równoważność macierzy. Przykład dla zadania dyfuzji ze zmiennym współczynnikiem. Własności spektralne macierzy jednowymiarowego laplasjanu. Metoda FFT rozwiązywania zadania Laplace'a na kwadracie.
• Metoda GMRES. Kolokwium (08.12.2006)
• Dyskusja kolokwium. Algorytm FFT. Informacja o bibliotece FFTW. Parzysta i nieparzysta sprzężoność i skutki dla FFT. Wersje FFT: do wektorów rzeczywistych, itp. Wybrane zastosowania FFT.
• Numeryczne zagadnienie własne. Uwarunkowanie wartości własnych i wektorów własnych. Twierdzenia Courant-Fischer oraz Bauer-Fike z dowodami. Metoda potęgowa i odwrotna potęgowa. Transformacje spektrum. Iloraz Rayleigh i RQI.
• Aproksymacja wektora własnego przy zadanej wartości własnej i aproksymacja wartości własnej przy zadanym wektorze własnym. Dlaczego RQI nie przeszkadza patologiczne uwarunkowanie rozwiązywanych układów równań. Transformacja ortogonalna do postaci Hessenberga (trójdiagonalnej, gdy macierz jest symetryczna). Pełne zagadnienie własne: metoda dziel i rządź oraz metoda QR - lektura.
• Eksponens dla macierzy symetrycznej. Uzupełnienie o transformacjach ortogonalnych: obroty Givensa i ich zastosowania (m.in. dla macierzy Hessenberga w metodzie GMRES). Porównanie z przekształceniem Householdera. Rozkład SVD macierzy. Istnienie i własności SVD z dowodem. Wykorzystanie SVD do wyznaczania uwarunkowania macierzy, jądra i rzędu macierzy.
• Nieregularnego zadania najmniejszych kwadratów: charakteryzacja rozwiązań z dowodem. SVD dla nieregularnego zadania najmniejszych kwadratów. Wyznaczanie SVD.