Metody numeryczne

obowiązkowe

Algorytmy i struktury danych 1000-213bASD
Analiza matematyczna inf. II 1000-212bAM2
Geometria z algebrą liniową 1000-211bGAL

Wiele praktycznych zastosowań komputerów (symulacje zjawisk przyrodniczych, społecznych i innych, kodowanie MP3 i JPEG, systemy projektowania CAD, wyszukiwarki internetowe itp.) wymaga przeprowadzenia obliczeń na liczbach rzeczywistych lub zespolonych. W niniejszym wykładzie przedstawiamy metody numerycznego rozwiązywania podstawowych zagadnień matematycznych spotykanych w zastosowaniach. Nacisk kładziemy na efektywne łączenie teorii matematycznej i praktyki obliczeniowej, aby tworzyć skuteczne - a więc szybkie i dokładne (na ile to możliwe) algorytmy wyznaczania rozwiązań. Dyskutujemy własności i ograniczenia omawianych algorytmów, a także wskazujemy praktyczne aspekty ich implementacji. Pokazujemy, że niektóre zadania mogą być trudne w realizacji numerycznej - i że czasem można to sprytnie obejść.

1. Rozwiązywanie równań nieliniowych:

• Metoda Newtona

• Podstawowe pojęcia w numerycznym rozwiązywaniu równań (funkcja iteracyjna, kula zbieżności, wykładnik zbieżności, graniczna dokładność)

• Metoda siecznych

• Metoda Newtona dla układu równań

• Modyfikacje

• Kryteria stopu

2. Arytmetyka zmiennopozycyjna:

• Reprezentacja zmiennopozycyjna liczb

• Arytmetyka i błędy zaokrągleń

• Arytmetyka zmiennopozycyjna zespolona

3. Błędy w obliczeniach:

• Numeryczne uwarunkowanie zadania

• Błędy reprezentacji wektorów

• Numeryczna poprawność i stabilność algorytmu

4. Rozwiązywanie układów równań liniowych:

• Uwarunkowanie układu równań liniowych

• Metody bezpośrednie: metoda eliminacji Gaussa, metoda odbić Householdera, metoda Choleskiego, układy i algorytmy blokowe, szacowanie błędu i iteracyjne

poprawianie rozwiązania

• Metody iteracyjne: metody iteracji prostej, metoda sprzężonych gradientów, poprawianie uwarunkowania

5. Liniowe zadania najmniejszych kwadratów:

• Regularne LZNK

• Dualne LZNK

• Nieregularne LZNK

6. Algebraiczne zagadnienie własne:

• Sformułowanie problemu

• Metoda potęgowa

• Odwrotna metoda potęgowa

• Sprowadzanie macierzy symetrycznej do postaci trójdiagonalnej

• Algorytm QR

7. Interpolacja wielomianowa:

• Sformułowanie zadań interpolacji Lagrange’a i Hermite’a

• Bazy Newtona

• Różnice dzielone i ich własności

• Algorytm różnic dzielonych

• Reszta interpolacyjna

8. Interpolacja funkcjami sklejanymi

• Motywacja dla stosowania funkcji sklejanych

• Obcięte funkcje potęgowe

• Reprezentacja Hermite’a funkcji sklejanych trzeciego stopnia

• Kubiczne interpolacyjne funkcje sklejane klasy C2

• Twierdzenie Holladaya

• Funkcje B-sklejane

• Kubiczne funkcje interpolacyjne w reprezentacji B-sklejanej

• Twierdzenie Schoenberga-Whitney

9. Interpolacja trygonometryczna:

• Trygonometryczne zadanie interpolacji Lagrange’a

• Dyskretna transformata Fouriera

• Algorytm FFT

10. Aproksymacja funkcji:

• Aproksymacja jednostajna: wielomiany i węzły Czebyszewa, _alternans i algorytm Remeza, aproksymacja jednostajna przez funkcje sklejane

• Aproksymacja średniokwadratowa: wielomiany ortogonalne

11. Numeryczne obliczanie całek:

• Kwadratury interpolacyjne

• Zamiana zmiennych

• Kwadratury Gaussa

• Kwadratury złożone

• Ekstrapolacja Richardsona i metoda Romberga

• Uwagi o całkowaniu funkcji wielu zmiennych

12. Wybrane środowiska i biblioteki dla obliczeń numerycznych

1. D. Kincaid, W. Cheney, Analiza numeryczna, Wydawnictwa Naukowo-Techniczne, Warszawa 2006.

2. P. Krzyżanowski, Obliczenia inżynierskie i naukowe, PWN, Warszawa 2011

3. J. Jankowska, M. Jankowski, M. Dryja, Przegląd metod i algorytmów numerycznych cz. 1 i 2, WNT Warszawa 1988,

4. G. Dahlquist, A. Bjorck Metody numeryczne, PWN Warszawa 1983

Wiedza:

* Student zna w stopniu zaawansowanym podstawową wiedzę na temat architektury współczesnych systemów (logika układów cyfrowych i reprezentacja danych, architektura procesora, wejście-wyjście, pamięć, architektury wieloprocesorowe) (K_W06). W kontekście przedmiotu w szczególności:

+ Zna podstawowe możliwości i ograniczenia obliczeń numerycznych.

+ Zna i umie stosować algorytmy rozwiązywania typowych zadań numerycznych.

+ Zna pojęcia numerycznego uwarunkowania zadania oraz numerycznej poprawności i stabilności algorytmu.

+ Wie, na co zwracać uwagę podczas dobierania algorytmu do rozwiązania konkretnego zadania.

+ Zna wybrane biblioteki procedur numerycznych i środowiska do przeprowadzania obliczeń numerycznych dla typowych zadań.

Umiejętności:

* Umie zastosować wiedzę matematyczną do formułowania, analizowania i rozwiązywania związanych z informatyką zadań o średnim poziomie złożoności (K_U01).

* Umie pozyskiwać informacje z literatury, baz wiedzy, Internetu oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02).

* Umie posługiwać się przyjętymi formatami reprezentacji różnego rodzaju danych stosownie do sytuacji (liczby, tablice, tekst) pamiętając o ich ograniczeniach, np. związanych z arytmetyką komputera (K_U08).

* Umie samodzielnie planować i realizować własne uczenie się przez całe życie (K_U09).

Kompetencje społeczne:

* Student jest gotów do pracy z zachowaniem uczciwości intelektualnej w działaniach własnych i innych osób; przestrzegania zasad etyki zawodowej i wymagania tego od innych oraz dbałości o dorobek i tradycje zawodu informatyka (K_K02).

* Student jest gotów do uznawania znaczenia wiedzy w rozwiązywaniu problemów poznawczych i praktycznych oraz wyszukiwania informacji w literaturze oraz zasięgania opinii ekspertów (K_K03).

Zaliczenie ćwiczeń na podstawie prac domowych, aktywności na zajęciach i projektów komputerowych.

Egzamin pisemny i w wyjątkowych przypadkach ustny.