Algorytmy algebry liniowej
Informacje ogólne
Kod przedmiotu: | 17-DSPE-IP6 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Algorytmy algebry liniowej |
Jednostka: | Nadnotecki Instytut UAM w Pile |
Grupy: |
Moodle - przedmioty Innych jednostek |
Punkty ECTS i inne: |
0 LUB
5.00
(w zależności od programu)
|
Język prowadzenia: | język polski |
Rodzaj przedmiotu: | obowiązkowe |
Kierunek studiów: | Technologie informatyczne |
Poziom przedmiotu: | I stopień |
Cele kształcenia: | 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. |
Rok studiów (jeśli obowiązuje): | II rok |
Wymagania wstępne w zakresie wiedzy, umiejętności oraz kompetencji: | Programowanie w językach wysokiego poziomu (Python, Matlab-Octave). Teoretyczna algebra liniowa |
Informacja o tym, gdzie można zapoznać się z materiałami do zajęć: | Wskazane podręczniki. Wskazane strony internetowe, Pliki PDF dostarczone przez wykładowcę. |
Metody prowadzenia zajęć umożliwiające osiągnięcie założonych EK: | Zajęcia stacjonarne. Wykłady (30h.) i laboratoria (30h.). |
Nakład pracy studenta (punkty ECTS): | Nakład pracy :110 h. Punktów 5 pt. |
Skrócony opis: |
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. |
Pełny opis: |
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.) |
Literatura: |
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). |
Efekty uczenia się: |
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. |
Metody i kryteria oceniania: |
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ą. |
Zajęcia w cyklu "Semestr letni 2020/2021" (zakończony)
Okres: | 2021-03-01 - 2021-09-30 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Wykład, 30 godzin
Zajęcia laboratoryjne, 30 godzin
|
|
Koordynatorzy: | Andrzej Maćkiewicz | |
Prowadzący grup: | Andrzej Maćkiewicz | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2021/2022" (zakończony)
Okres: | 2022-02-24 - 2022-09-30 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Wykład, 30 godzin
Zajęcia laboratoryjne, 30 godzin
|
|
Koordynatorzy: | Andrzej Maćkiewicz | |
Prowadzący grup: | Andrzej Maćkiewicz | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2022/2023" (zakończony)
Okres: | 2023-02-27 - 2023-09-30 |
Przejdź do planu
PN WT ŚR CZ WYK
LAB
PT |
Typ zajęć: |
Wykład, 30 godzin
Zajęcia laboratoryjne, 30 godzin
|
|
Koordynatorzy: | Andrzej Maćkiewicz | |
Prowadzący grup: | Andrzej Maćkiewicz | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)
Okres: | 2024-02-26 - 2024-09-30 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Konwersatorium, 30 godzin
Zajęcia laboratoryjne, 30 godzin
|
|
Koordynatorzy: | Andrzej Maćkiewicz | |
Prowadzący grup: | Andrzej Maćkiewicz | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Konwersatorium - Egzamin Zajęcia laboratoryjne - Zaliczenie z notą |
Właścicielem praw autorskich jest Uniwersytet im. Adama Mickiewicza w Poznaniu.