Metody numeryczne

obowiązkowe

Informatyka

I stopień

Celem przedmiotu jest zapoznanie studentów z podstawowymi zagadnieniami analizy numerycznej, własnościami arytmetyki zmiennopozycyjnej oraz metodami przybliżonego rozwiązywania wybranych zagadnień matematycznych.

II rok

Kursy: Algebra liniowa, Analiza matematyczna, Podstawy programowania.

Materiały przewidziane do publikacji na stronach www osób prowadzących kurs.

ECTS: 6

Wykłady:

1. Arytmetyka zmiennopozycyjna - reprezentacja zmiennopozycyjna liczb (podstawy teoretyczne i standard IEEE 754), arytmetyka i błędy zaokrągleń. Algorytm sumacyjny Kahana.

2. Błędy w obliczeniach, uwarunkowanie zadania, numeryczna stabilność algorytmów.

3. Algorytm Hornera - obliczanie wartości wielomianu w postaci naturalnej w punkcie, dzielenie wielomianu przez dwumian, obliczanie wartości pochodnych znormalizowanych w punkcie, obliczanie wartości wielomianu w postaci Newtona w punkcie.

4. Przypomnienie pojęcia przestrzeni metrycznej. Interpolacja wielomianowa - zadanie interpolacyjne Lagrange'a i Hermite'a, bazy Newtona, ilorazy róznicowe, błąd interpolacji, dobór węzłów interpolacji.

5. Interpolacja funkcjami sklejanymi.

6. Przypomnienie pojęcia całki Riemanna. Numeryczne obliczanie całek - kwadratury Newtona-Cotesa i Gaussa.

7. Metody iteracyjne rozwiązywania równań nieliniowych (metody bisekcji, siecznych i Newtona) i kryteria stopu. Idea metody Bairstowa. Rząd metody.

8. Rozwiązywanie układów liniowych równań algebraicznych - uwarunkowanie (normy wektorów i macierzy); metody bezpośrednie: eliminacja Gaussa z częściowym i pełnym wyborem elementu głównego, rozkład LU, rozkład Doolitle'a, rozkład Cholesky'ego-Banachiewicza (z wprowadzeniem pojęcia macierzy dodatnio określonej); iteracyjne poprawianie rozwiązań; metody iteracyjne rozwiązania układów liniowych równań algebraicznych.

9. Rozkład SVD.

Laboratoria:

1. Postać zmiennopozycyjna liczby w arytmetyce pojedynczej i podwójnej precyzji. Liczby maszynowe. Działania arytmetyczne w arytmetyce zmiennopozycyjnej. Epsilon maszynowy, wyrażenia specjalne: NaN i nieskończoność. Porównywanie rozwiązań zadania otrzymywanych różnymi algorytmami.

2. Utrata cyfr znaczących. Uwarunkowanie zadania obliczania wartości funkcji jednej zmiennej. Wskaźnik uwarunkowania zadania obliczania iloczynu skalarnego wektorów. Przykłady algorytmów niestabilnych numerycznie.

3. Zastosowanie algorytmu Hornera do obliczania wartości dziesiętnej liczby zapisanej w dowolnym liczbowym systemie pozycyjnym. Przykład obliczenia wartości wielomianu w postaci Newtona w zadanym punkcie.

4. Zasady wyboru postaci Lagrange'a lub Newtona wielomianu interpolacyjnego. Błąd interpolacji wielomianowej. Poprawa jakości wielomianu interpolacyjnego poprzez dobór węzłów Czebyszewa. Przykład zastosowania interpolacji Hermite'a.

5. Motywacja do stosowania funkcji sklejanych. Naturalne funkcje sklejane. Funkcje sklejane trzeciego stopnia.

6. Przybliżanie całek za pomocą sum Riemanna oraz prostych i złożonych kwadratur Newtona-Cotesa.

7. Sposoby unikania rozbieżności metod iteracyjnych. Porównanie szybkości zbieżności poznanych metod iteracyjnych.

8. Uwarunkowanie macierzy. Niestabilność metody eliminacji Gaussa bez wyboru elementu głównego, zalety częsciowego wyboru elementu głównego. Metoda Doolitle'a i Cholesky'ego-Banachiewicza. Metoda Jacobiego i Gaussa-Seidela. Metoda nadrelaksacji dla różnych wartości parametru relaksacji.

9 Zastosowanie rozkładu SVD do redukcji danych.

1. Cheney W., KincaidD., ,,Analiza numeryczna", WN-T, Warszawa 2006.

2. Dahlquist G., Bjorck A., „Metody numeryczne'', PWN Warszawa 1983.

3. Maćkiewicz A., ,,Algorytmy algebry liniowej. Metody bezpośrednie'', Wyd. Politechniki Poznańskiej Poznań 2002.

4. Krzyżanowski P., ,,Obliczenia inżynierskie i naukowe", Wyd. Naukowe PWN W-wa 2011.

5. Johansson R., ,,Numerical python", Apress 2015

1. E01- rozumie różnicę pomiędzy arytmetyką liczb rzeczywistych, a arytmetyką komputerową; potrafi wyjaśnić wpływ arytmetyki zmiennopozycyjnej na działanie algorytmu.

2. E02- potrafi wskazać, który z podanych algorytmów jest dla danego problemu bardziej efektywny.

3. E03 - zna metody pozwalające na przybliżone rozwiązanie wybranych zagadnień matematycznych.

4. E04 - rozumie rolę norm wektorów i macierzy w ocenie dokładności rozwiązań numerycznych podstawowych zadań algebry liniowej.

5. E05 - zna metody numeryczne rozwiązywania podstawowych zadań algebry liniowej

6. E06 - zna metody rozwiązywania układów nadokreślonych.

Egzamin końcowy ma postać testu obejmującego teorię i zadania. Do egzaminu mogą przystąpić tylko osoby, które otrzymają pozytywną ocenę z laboratoriów.

Ocena z laboratoriów wystawiana jest na podstawie kilku zapowiedzianych testów sprawdzających znajomość pojęć wprowadzonych na wykładach i laboratoriach oraz na podstawie zadań/projektów.

W obydwu przypadkach zastosowana skala ocen jest zgodna z paragrafem 22 Regulaminu Studiów UAM (obwieszczenie 6/2015 Senatu Uniwersytetu im. Adama Mickiewicza w Poznaniu).