Algorytmy algebry liniowej

obowiązkowe

Technologie informatyczne

I stopień

kurs traktuje o dwu podstawowych klasach problemów numerycznej algebry liniowej tj. o rozwiązywaniu układów równań liniowych (różnych typów) i liniowym zadaniu najmniejszych kwadratów. Omawiana jest teoretyczna analiza wspomnianych problemów oraz metody ich rozwiązania. Wykorzystuje się języki programowania wysokiego poziomu (Python 3, Matlab-Octave) do implementacji efektywnych algorytmów. Omawia się zagadnienie wpływu błędów zaokrągleń na końcowy wynik obliczeń, problem uwarunkowania zadania i poprawności numerycznej kodów.

Uzasadniony teoretycznie materiał jest ilustrowany przykładami i problemami (także z zakresu zastosowań) przeznaczonymi do samodzielnego rozpatrzenia.

II rok

Programowanie w językach wysokiego poziomu (Python, Matlab-Octave).

Teoretyczna algebra liniowa

Wskazane podręczniki.

Wskazane strony internetowe,

Pliki PDF dostarczone przez wykładowcę.

Zajęcia stacjonarne. Wykłady (30h.) i laboratoria (30h.).

Nakład pracy :110 h.

Punktów 5 pt.

Przyczyny powstawania błędów w obliczeniach zmiennoprzecinkowych.

Różnice między teoretyczną a numeryczną algebrą liniową.

Iloczyn skalarny.. Elementy geometrii euklidesowej przestrzeni n-wymiarowej.

O złożoności obliczeniowej algorytmów. Działania macierz x wektor i macierz x macierz. Podstawowe typy macierzy specjalnych. Układy równań liniowych o kwadratowych macierzach specjalnych.Metoda eliminacji Gaussa. Liniowe zadanie najmniejszych kwadratów. Algorytm Choleskiego dla symetrycznych macierzy dodatnio określonych. Podokreślone układy równań liniowych.

Normy macierzowe. Liczba uwarunkowania macierzy kwadratowych.

Przyczyny powstawania błędów w obliczeniach zmiennoprzecinkowych

Reprezentacja 64-bitowych liczb zmiennopozycyjnych w standardzie IEEE

Podstawowe funkcje Matlaba i Pythona dotyczące arytmetyki zmiennopozycyjnej

Różne rodzaje błędów w obliczeniach numerycznych

Katastroficzna utrata cyfr znaczących

Różnice między teoretyczną a numeryczną algebrą liniową.

Błąd bezwzględny i względny

Notacja "dużego O" i "małego o"

Iloczyn skalarny.

Norma euklidesowa, nierówność Cauchy-Schwarza, kąt i odległość między wektorami.

Współrzędne sferyczne.

Iteracyjny algorytm skupiskowania (z zastosowaniami).

Elementy geometrii euklidesowej przestrzeni n-wymiarowej

Nierówność trójkąta.

Twierdzenie Pitagorasa w n-wymiarach.

Prawidło równoległoboku.

Liniowa niezależność wektorów.

O złożoności obliczeniowej algorytmów

Podstawowe wzory sumacyjne

Algorytmy o stałym czasie realizacji (przykłady)

Algorytmy z złożoności logarytmicznej (przykłady)

Algorytmy o złożoności liniowej (przykłady)

Algorytmy logarytmiczno- liniowe (przykłady)

Algorytmy wielomianowe (przykłady)

Algorytmy wykładnicze (przykłady)

Działania macierz x wektor i macierz x macierz

Organizacja danych przy przetwarzaniu macierzy rzadkich.

Mnożenie macierzy zblokowanych.

Szybkie mnożenie macierz x wektor z użyciem strategii dziel i zwyciężaj.

Informacja o FFT i transformacjach falkowych.

Analiza złożoności podstawowych operacji numerycznej algebry liniowej

Algorytmy typu wektor-wektor.

Algorytmy typu macierz-wektor.

Algorytmy typu macierz-macierz.

Wektoryzacja.

Informacja o bibliotece BLAS.

Podstawowe typy macierzy specjalnych

Iloczyn zewnętrzny wektorów.

Aktualizacja macierzy składnikiem rzędu jeden.

Wzór Shermana-Morrisona.

Macierze Gaussa-Frobeniusa i ich odwracanie.

Uogólniony wzór Shermana-Morrisona

Macierze permutacyjne i ich komputerowa reprezentacja

Układy równań liniowych o kwadratowych macierzach specjalnych

Układy równań o macierzach trójkątnych

Kolumnowa i wierszowa orientacja algorytmu.

Wpływ błędów zaokrągleń na rozwiązanie układów o macierzach trójkątnych.

Metoda eliminacji Gaussa

Rozkład A=LU. Macierze o dominującej głównej przekątnej.

Różne strategie realizacji metody Gaussa wynikające z przeprowadzonej analizy błędów

Rozkład PA=LU.

Rozwiązywanie układów Ax=b i Ax=B. Informacje o uwarunkowaniu problemu.

Poprawianie rozwiązań numerycznych liniowych układów równań z wykorzystaniem arytmetyki poszerzonej precyzji.

Prosty algorytm kompresji danych macierzowych jako iteracyjna wersja metody Gaussa

Liniowe zadanie najmniejszych kwadratów (LLS)

Normalny układ równań. Macierze rzutowania prostopadłego, Lewa pseudoodwrotność „szczupłej” macierzy prostokątnej. Rzutowanie prostopadłe na podprzestrzeń o znanej bazie ortonormalnej. Współczynniki Fouriera.

Algorytm Choleskiego dla symetrycznych macierzy dodatnio określonych (spd.)

Rozkład Choleskiego A=L*L’ macierzy spd.. Rozwiązywanie zadań LLS z wykorzystaniem algorytmu Choleskiego. Interpolacja funkcjami sklejanymi (spline) 3-go stopnia jako przykład problemu z pasmową macierzą spd.

Organizacja danych dla układów równań liniowych o kwadratowych, pasmowych macierzach współczynników.

Podokreślone układy równań liniowych

Jednoznaczność rozwiązania o minimalnej normie. Prawa pseudoodwrotność „grubej” macierzy prostokątnej.

Normy macierzowe. Liczba uwarunkowania macierzy kwadratowych.

Macierzowe normy indukowane. Norma Frobeniusa. Liczba uwarunkowania macierzy

kwadratowej, nieosobliwej. Analiza przykładowych żle uwarunkowanych układów równań liniowych (macierze Hilberta, Vandermonde’a itp.)

Zalecana literatura podstawowa:

‒ G. Allaire, S. Kaber , Numerical Linear Algebra, Springer 2002.

‒ F. Bornemann, “Numerical Linear Algebra”, Springer 2018.

‒ S. Boyd, L. Vanderberghe “Introduction to Applied Linear Algebra”, Cambridge Univ. Press 2018. (bezpłatna wersja PDF dostępna w internecie).

Po odbyciu kursu student powinien orientować się w specyfice przedmiotu i mieć przekonanie o jego ważności dla technik informatycznych. Powinien też zapoznać się z omawianymi algorytmami oraz fragmentami bibliotek BLAS i Lapack.

Zaliczenie ćwiczeń.

Wszystkie elementy projektów są punktowane a punkty są sumowane. Uzyskanie

- 50%- 60% punktów - ocena dostateczny

- 60%- 70% punktów - ocena dostateczny plus

- 70%- 80% punktów - ocena dobry

- 80%- 90% punktów - ocena dobry plus

- 90%-100% punktów - ocena bardzo dobry

Warunkiem zaliczenia jest uzyskanie min. 60% obecności.

Egzamin.

Zaliczenie testu dotyczącego wiedzy na ocenę pozytywną.