2010

Program wykładu 2007/2008

1. Wprowadzenie do metod numerycznych
2. Równania nieliniowe
3. Układy równań nieliniowych
4. Pamięć hierarchiczna a algorytmy numeryczne
5. Wielkie układy równań liniowych
6. Interpolacja i aproksymacja
7. Szybka transformacja Fouriera (FFT)
8. Funkcje sklejane (splajny)
9. Całkowanie i różniczkowanie
10. Równania różniczkowe zwyczajne
11. Równania różniczkowe cząstkowe

Podręczniki

• D. Kincaid and W. Cheney, Analiza numeryczna, WNT, Warszawa 2006. ISBN 83-204-3078-X
• A. Quarteroni, R. Sacco, F. Saleri, Numerical Mathematics, Springer
• M. Overton, Numerical Computing with IEEE Floating Point Arithmetic, SIAM

Na wykładzie będą omawiane także zagadnienia spoza podanej literatury... Na szczęście, są także dostępne on-line Materiały do (niektórych) wykładów i ćwiczeń (wersja eksperymentalna). Osobom zainteresowanym polecam także skrypt prof. K. Moszyńskiego Metody numeryczne dla informatyków.

Zaliczenie ćwiczeń

Na ćwiczeniach będą regularnie zadawane prace domowe oraz (czasem) przeprowadzane kartkówki, za co będzie można otrzymać 30 punktów przeliczeniowych. Ponadto, na jednym z wykładów zostanie zorganizowane jedno kolokwium, także warte 30 punktów. Jeśli oznaczyć C liczbę punktów uzyskanych przez studenta za pracę na ćwiczeniach, a K - liczbę punktów uzyskanych na kolokwium, to łączna liczba punktów z ćwiczeń Z wynosi

K+C

gdy K+C ≥ 25

min(K+C+P, 25)

w przeciwnym przypadku; tutaj 0 ≤ P ≤ 10 jest liczbą punktów uzyskanych z dodatkowego (ratunkowego?) mini-projektu komputerowego, indywidualnie zadanego studentowi przez prowadzącego ćwiczenia.

Do zaliczenia ćwiczeń wystarczy Z ≥ 25 punktów.

Egzamin

Egzamin będzie miał formę pisemną. Do egzaminu w pierwszym terminie mogą przystąpić jedynie osoby, które zaliczyły ćwiczenia. Z egzaminu pisemnego można będzie otrzymać maksymalnie 40 punktów przeliczeniowych. Ostateczna ocena z przedmiotu będzie oparta na sumie liczby punktów przeliczeniowych uzyskanych na egzaminie pisemnym E oraz z zaliczenia ćwiczeń Z. Egzamin ustny jest przewidziany tylko w wątpliwych wypadkach.

Na egzaminie pisemnym będzie można korzystać wyłącznie ze ściągawki: dwóch kartek papieru formatu A4 zapisanych dowolną czcionką. Egzamin pisemny będzie składać się z zadań oraz pytań dotyczących treści poruszanych na wykładach i ćwiczeniach, z wyjątkiem materiału z ostatniego wykładu. Na ustnym i na poprawkowym możliwe są pytania z całości przerobionego materiału.

Egzamin poprawkowy obejmie pełny zakres treści wykładu i ćwiczeń, zadania zaś będą uwzględniały także elementy zaliczenia ćwiczeń i laboratorium.

Archiwum

Program wykładu 2006/2007

1. Wprowadzenie do metod numerycznych
2. Równania nieliniowe
3. Układy równań nieliniowych
4. Pamięć hierarchiczna a algorytmy numeryczne
5. Wielkie układy równań liniowych
6. Interpolacja i aproksymacja
7. Szybka transformacja Fouriera (FFT)
8. Funkcje sklejane (splajny)
9. Całkowanie i różniczkowanie
10. Równania różniczkowe zwyczajne
11. Równania różniczkowe cząstkowe

...tydzień po tygodniu

Fragmenty zaznaczone kursywą zostały oddelegowane na ćwiczenia.

• Wprowadzenie do metod numerycznych. Języki programowania i najprostsze pułapki. Metoda bisekcji i Newtona dla równań skalarnych.Wyznaczanie pierwiastka i odwrotności metodą Newtona (także w arytmetyce zmiennoprzecinkowej)
• Inne metody dla równań skalarnych: siecznych i Steffensena. Wykładnik zbieżności omawianych metod. Wielowymiarowa metoda Banacha dla zadania punktu stałego i jej rząd zbieżności. Wykorzystanie tego wyniku do dowodu zbieżności m.in. metody Newtona dla zer wielokrotnych. Kryteria stopu i ich ograniczenia.
• Układy równań nieliniowych. Metody: Newtona, cięciw i z pochodną przybliżoną ilorazami różnicowymi oraz ich rząd zbieżności. Zależność błędu od residuum poprzez wskaźnik uwarunkowania macierzy pochodnej. Skuteczna implementacja omawianych metod wielowymiarowych.
• Elementy optymalizacji programów numerycznych dla architektur z pamięcią hierarchiczną. Mnożenie macierzy na różne sposoby. Blokowanie algorytmów algebry liniowej jako sposób na skuteczne wykorzystanie pamięci podręcznej. BLAS, LAPACK i ATLAS. Macierze w Fortranie i w C. Mieszanie kodu w C z biblioteką fortranowską.
• Podstawy dyskretyzacji równania dyfuzji w dwóch wymiarach: metoda różnic skończonych. Macierze rzadkie i sposoby ich reprezentacji: po współrzędnych oraz CSC/CSR; ich wady i zalety. Informacja kłopotach i o narzędziach bezpośredniego rozwiązywania układów z macierzami rzadkimi: UMFPACK, PARDISO i taśmowymi: DGBSV (LAPACK). Stacjonarne metody iteracyjne i warunki ich zbieżności. Przykłady: metoda Richardsona, metoda Jacobiego. Ich zbieżność. Inne metody stacjonarne.
• Metody przestrzeni Kryłowa na przykładzie metody gradientów sprzężonych (CG). Implementacja CG. CG jako metoda bezpośrednia i jako metoda iteracyjna. Informacja o metodzie GMRES. Ściskanie macierzy: cel i strategia. Przykłady macierzy ściskających: jeden krok metody klasycznej, niepełny rozkład, macierze oparte na specjalnych własnościach układu (na przykładzie równań różniczkowych, w tym - informacja o metodzie wielosiatkowej). Spektralna równoważność i optymalność ściskania macierzą spektralnie równoważną.
• Interpolacja wielomianowa. Istnienie i jednoznaczność. Znaczenie doboru bazy dla reprezentacji wielomianu. Algorytm różnic dzielonych. Błąd interpolacji, w szczególności na węzłach równoodległych. Zjawisko Rungego.
• Aproksymacja w przestrzeniach unormowanych. Motywacje, istnienie. Jednoznaczność i charakteryzacja elementu najlepszej aproksymacji w przestrzeni z iloczynem skalarnym. Rozwinięcie w bazie ortogonalnej. Przykłady. Wielomiany ortogonalne i formuła trójczłonowa. Przykłady wielomianów ortogonalnych (Legendre'a, Czebyszewa, Hermite'a, Lagrange'a) i ich własności. Własność minimaksu dla wielomianów Czebyszewa.
• Kolokwium (08.12.2006)
• Szybka transformacja Fouriera i jej zastosowania. Koszt FFT w porównaniu do naiwnego algorytmu. Biblioteka FFTW.
• Splajny. Zadanie interpolacji splajnowej. Splajn interpolacyjny liniowy i kubiczny (naturalny), w tym oszacowanie błędu interpolacji. Wyznaczanie splajnu interpolacyjnego kubicznego. Informacja o B-splajnach. Porównanie interpolacji splajnowej i wielomianowej.
• Całkowanie funkcji jednej zmiennej. Kwadratury interpolacyjne: przykłady (prostokątów, trapezów, Simpsona) i oszacowania błędu. Kwadratury złożone i ich zbieżność. Złożone kwadratury prostokątów i trapezów: wzory na błąd i porównanie. Informacja o kwadraturach Gaussa. Informacja o kwadraturach adaptacyjnych. QUADPACK.
• Równania różniczkowe zwyczajne - zadanie początkowe. Warunki istnienia i jednoznaczności. Schematy różnicowe: Eulera otwarty i zamknięty, schemat trapezów. Zbieżność schematu. Rząd schematu. Twierdzenie o zbieżności schematów jednokrokowych (bez dowodu).
• Informacja o schematach Rungego-Kutty. Schematy wielokrokowe. Twierdzenie Dahlquista o zbieżności (bez dowodu). Porównania metod R-K i wielokrokowych. Sztywność i kiedy schematy zamknięte mogą być lepsze od otwartych. Przegląd podstawowych typów równań różniczkowych cząstkowych i metod ich rozwiązywania.

Egzamin 2007

Zobacz, czy trudne były zadania z egzaminu pisemnego!