Linear algebra algorithms
General data
Course ID: | 17-DSPE-IP6 |
Erasmus code / ISCED: | (unknown) / (unknown) |
Course title: | Linear algebra algorithms |
Name in Polish: | Algorytmy algebry liniowej |
Organizational unit: | AMU Nadnotecki Institute in Piła |
Course groups: |
(in Polish) Moodle - przedmioty Innych jednostek |
ECTS credit allocation (and other scores): |
0 OR
5.00
(depends on study program)
|
Language: | Polish |
Module type: | compulsory |
Major: | (in Polish) Technologie informatyczne |
Cycle of studies: | 1st cycle |
Module learning aims: | (in Polish) 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. |
Year of studies (where relevant): | Year 2 |
Pre-requisites in terms of knowledge, skills and social competences: | (in Polish) Programowanie w językach wysokiego poziomu (Python, Matlab-Octave). Teoretyczna algebra liniowa |
Information on where to find course materials: | (in Polish) Wskazane podręczniki. Wskazane strony internetowe, Pliki PDF dostarczone przez wykładowcę. |
Methods of teaching for learning outcomes achievement: | (in Polish) Zajęcia stacjonarne. Wykłady (30h.) i laboratoria (30h.). |
Student workload (ECTS credits): | (in Polish) Nakład pracy :110 h. Punktów 5 pt. |
Short description: |
(in Polish) 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. |
Full description: |
(in Polish) 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.) |
Bibliography: |
(in Polish) 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). |
Learning outcomes: |
(in Polish) 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. |
Assessment methods and assessment criteria: |
(in Polish) 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ą. |
Classes in period "Academic year 2020/2021, summer semester" (past)
Time span: | 2021-03-01 - 2021-09-30 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
laboratory, 30 hours
lecture, 30 hours
|
|
Coordinators: | Andrzej Maćkiewicz | |
Group instructors: | Andrzej Maćkiewicz | |
Students list: | (inaccessible to you) | |
Examination: | Exam |
Classes in period "Academic year 2021/2022, summer semester" (past)
Time span: | 2022-02-24 - 2022-09-30 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
laboratory, 30 hours
lecture, 30 hours
|
|
Coordinators: | Andrzej Maćkiewicz | |
Group instructors: | Andrzej Maćkiewicz | |
Students list: | (inaccessible to you) | |
Examination: | Exam |
Classes in period "Academic year 2022/2023, summer semester" (past)
Time span: | 2023-02-27 - 2023-09-30 |
Navigate to timetable
MO TU W TH WYK
LAB
FR |
Type of class: |
laboratory, 30 hours
lecture, 30 hours
|
|
Coordinators: | Andrzej Maćkiewicz | |
Group instructors: | Andrzej Maćkiewicz | |
Students list: | (inaccessible to you) | |
Examination: | Exam |
Classes in period "Academic year 2023/2024, summer semester" (in progress)
Time span: | 2024-02-26 - 2024-09-30 |
Navigate to timetable
MO TU W TH FR |
Type of class: |
discussion seminar, 30 hours
laboratory, 30 hours
|
|
Coordinators: | Andrzej Maćkiewicz | |
Group instructors: | Andrzej Maćkiewicz | |
Students list: | (inaccessible to you) | |
Examination: |
Course -
Exam
discussion seminar - Exam laboratory - Graded credit |
Copyright by Adam Mickiewicz University, Poznań.