Matematyka obliczeniowa*

obowiązkowe

Oczekuje się dobrej znajomości zagadnień ujętych w sylabusie przedmiotu Wstęp do Informatyki I.

Wykład zawiera: elementy rachunku błędu zaaokrągleń, interpolacje wielomianową i splajnową, elementy aproksymacji, kwadratury złożone i kwadratury Gaussa, numeryczne metody rozwiązywania układów równań liniowych, rozwiązywanie równań nieliniowych, numeryczne zadanie własne. Ponadto wykład porusza kwestie złożoności obliczeniowej omawianych zadań i optymalności algorytmów.

Jest to wersja rozszerzona przedmiotu 1000-114bMOBa.

Wykład skierowany jest do studentów zainteresowanych głębszym poznaniem przedmiotu. Program jest nieco rozszerzoną wersją programu wykładu podstawowego. Materiał przekazany jest w szerszym kontekście, z uwzględnieniem złożoności obliczeniowej omawianych zadań i optymalności algorytmów. Dlatego, oprócz poniższych treści, obecne są ogólne pojęcia związane z optymalnością algorytmów liniowych, algorytmami adaptacyjnymi, metodami niedeterministycznymi, przekleństwem wymiaru.

Równania nieliniowe skalarne. Metody: bisekcji, stycznych, siecznych i ich rząd zbieżności. Kryteria stopu. Inne metody. (1--2 wykłady)

Arytmetyka zmiennopozycyjna. Kryteria oceny zadań numerycznych (uwarunkowanie) oraz algorytmów numerycznych (błąd, złożoność, stabilność, poprawność). (1--2 wykłady)

Układy równań liniowych. Rozkład LU metodą eliminacji Gaussa i jego zastosowanie do rozwiązywania układów równań. Numeryczna poprawność eliminacji z wyborem elementu głównego w kolumnie. Rozkłady specjalne: Cholesky'ego-Banachiewicza, macierzy trójdiagonalnej i inne. Zastosowania rozkładów. Normy wektorowe i macierzowe oraz ich własności. Uwarunkowanie zadania Ax=b. Residualne kryterium numerycznej poprawności. Liniowe zadanie najmniejszych kwadratów. Rozkład QR. Metoda Householdera i metoda Givensa wyznaczania rozkładu QR. (4--5 wykładów)

Zadanie własne. Metody: potęgowa i odwrotna potęgowa. Iloraz Rayleigh'a. (1 wykład)

Interpolacja Lagrange'a i Hermite'a. Algorytm różnic dzielonych. Błąd interpolacji. Wielomiany Czebyszewa. Algorytm Hornera. Funkcje sklejane. (1--2 wykłady)

Aproksymacja średniokwadratowa. Istnienie i charakteryzacja elementu najlepszej aproksymacji. Wielomiany ortogonalne i ich zastosowanie do wyznaczania wielomianu optymalnego. Reguła trójczłonowa. Aproksymacja jednostajna wielomianami. Algorytm Remeza. (2--3 wykłady)

Kwadratury interpolacyjne. Błąd w przypadku ogólnym i dla kwadratur prostokątów, trapezów i Simpsona. Kwadratury złożone i ich błąd. Kwadratury adaptacyjne. Metoda Romberga. Rząd kwadratury. Kwadratury Gaussa. (2--3 wykłady).

Praca z komputerem (w ramach laboratorium).

Efekty kształcenia:

Wiedza i umiejętności:

1. Zna pojęcie wykładniczego rzędu zbieżności metody rozwiązywani równania liniowego.

2. Zna metody bisekcji, Newtona i siecznych rozwiązywania równania nieliniowego; wie przy jakich założeniach metody są zbieżne; zna metodę Newtona rozwiązywania układu równań nieliniowych; zna twierdzenie o lokalnej zbieżności tej metody.

3. Zna podstawowe własności arytmetyki zmiennopozycyjnej w komputerze; wie co to uwarunkowanie zadania ze względu na zaburzenia danych w arytmetyce zmiennopozycyjnej; zna pojęcie numerycznej poprawności i numerycznej stabilności algorytmu.

4. Zna algorytm i koszt metod bezpośredniego rozwiązywania układów równań liniowych poprzez rozkład LU, metodę Cholesky'ego, poprzez rozkład QR uzyskany metodą Householdera.

5. Zna definicje i podstawowe własności norm wektorowych i macierzowych; zna wzory na podstawowe wzory na normy p-te wektorowe i macierzowe; zna pojęcie współczynnika uwarunkowania macierzy i jego związek z błędami zaokrągleń w algorytmach bezpośrednich rozwiązywania układów równań liniowych.

6. Zna definicję liniowego zadania najmniejszych kwadratów (LZNK); wie co oznacza, że LZNK jest regularne; zna twierdzenie o istnieniu i jednoznaczności regularnego LZNK (RLZNK); wie jak rozwiązać RLZNK znając rozkład QR macierzy; zna algorytm Householdera znajdowania rozkładu QR macierzy kolumnami regularnej; zna metodę rozwiązywania RLZNK poprzez sprowadzenie go układu liniowego równań normalnych.

7. Wie co to numeryczne symetryczne zadanie własne; zna algorytm i jego koszt sprowadzania macierzy symetrycznej do macierzy podobnej trójdiagonalnej przy pomocy przekształceń Householdera.

8. Zna metodę potęgową i odwrotną potęgową; wie przy jakich założeniach metody te są zbieżne.

9. Wie co to zadanie interpolacji Lagrange; zna twierdzenie o tym kiedy takie zadanie ma jednoznaczne rozwiązanie; zna pojęcie bazy Lagrange'a wielomianów określonego stopnia; zna definicję w własności różnicy dzielonej; zna algorytmy Newtona i różnic dzielonych znajdowania współczynników wielomianu interpolacyjnego Lagrange'a w bazie Newtona; zna wzór na błąd interpolacji Lagrange'a; wie co to optymalne węzły interpolacji; potrafi oszacować błąd interpolacji znając oszacowania odpowiednich pochodnych funkcji.

10. Wie co to zadanie interpolacji Hermite'a; zna twierdzenie o tym kiedy takie zadanie ma jednoznaczne rozwiązanie; zna definicję i własności uogólnionej różnicy dzielonej z węzłami wielokrotnymi; zna algorytm różnic dzielonych znajdowania współczynników wielomianu interpolacyjnego Hermite'a w bazie Newtona; zna wzór na błąd interpolacji Hermite'a.

11. Zna definicję przestrzeni splajnów dla ustalonych węzłów; w szczególności wie co to przestrzeń splajnów liniowych i przestrzeń splajnów kubicznych; wie jak znaleźć splajn interpolacyjny liniowy i zna błąd interpolacji splajnami liniowymi; zna zadanie interpolacji splajnami kubicznymi z różnymi warunkami brzegowymi; zna algorytm znajdowania splajnu kubicznego z warunkami brzegowymi naturalnymi; zna wzór na błąd interpolacji splajnami kubicznymi naturalnymi; zna twierdzenie Holladay'a.

12.Wie co to są kwadratury; zna definicję rzędu kwadratury; zna definicję kwadratury interpolacyjnej; zna wzór na błąd kwadratury interpolacyjnej; zna wzór na kwadratury złożone trapezów i Simpsona; zna oszacowanie błędu kwadratury trapezów; wie jak skonstruować kwadraturę Gaussa; zna twierdzenie o rzędzie kwadratury Gaussa i o dodatniości jej współczynników; zna twierdzenie o zbieżności kwadratur Gaussa.

13. Zna podstawowe fakty dotyczące złożoności obliczeniowej omawianych na wykładzie zadań numerycznych.

14. Zna i rozumie ogólne pojęcia związane z optymalnością algorytmów liniowych, algorytmami adaptacyjnymi, metodami niedeterministycznymi, przekleństwem wymiaru.

Kompetencje społeczne:

1. Rozumie znaczenie matematyki obliczeniowej jako narzędzia służącego konstrukcji i analizy metod obliczeniowych pozwalających rozwiązywać zadania powstające przy modelowaniu zjawisk przyrody i techniki.

Na końcową ocenę składają się oceny częściowe z: ćwiczeń, laboratorium, kolokwium i egzaminu końcowego.