Algorytmy algebry liniowej 17-DSPE-IP6

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.)