Numerical methods of linear algebra with applications

General data

Course ID:	17-DSPE-IP5
Erasmus code / ISCED:	(unknown) / (unknown)
Course title:	Numerical methods of linear algebra with applications
Name in Polish:	Metody numeryczne algebry liniowej z zastosowaniami
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) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	Polish
Module type:	compulsory
Major:	(in Polish) Technologie informatyczne.
Cycle of studies:	1st cycle
Module learning aims:	(in Polish) Kurs jest bardziej zaawansowaną kontynuacją wykładu „Algorytmy algebry liniowej”. Omawiane są metody i algorytmy stanowiące istotne komponenty współczesnych technik rozwiązywania zadań naukowych i inżynierskich. Szczególny nacisk położono na zastosowania algebry liniowej w informatyce (grafika komputerowa, zadanie kompresji i oczyszczania sygnału, rankowanie stron internetowych itp.) Wykładany materiał jest również wstępem do technik optymalizacyjnych rozwiązywania zadań liniowych i nieliniowych przy ograniczeniach. 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.
Course module conducted remotely (e-learning):	(in Polish) Nie dotyczy.
Pre-requisites in terms of knowledge, skills and social competences:	(in Polish) Umiejętność programowania w wybranym języku wysokiego poziomu (Python 3, Matlab lub jego równoważnik). Zaliczony wcześniejszy wykład „Algorytmy algebry liniowej”.
Information on where to find course materials:	(in Polish) Pliki PDF dostarczone przez wykładowcę( w tym wymagany podręcznik i zbiór zadań). Uzupełniające wykłady internetowe wskazane na zajęciach.
Methods of teaching for learning outcomes achievement:	(in Polish) Wykład (30h.) , laboratorium (30h.)
Student workload (ECTS credits):	(in Polish) Nakład pracy: 110 h. Punktów: 5
Short description:	(in Polish) T01. Przyczyny powstawania błędów w obliczeniach zmiennoprzecinkowych. T02. Zredukowany rozkład QR macierzy prostokątnych. T03. Zastosowanie zredukowanego rozkładu QR macierzy prostokątnych. T04. Ogólna charakterystyka macierzy ortogonalnych. Macierze obrotów. Odbicia Householdera. T05. Podstawowe informacje o macierzowych zadaniach własnych. T06. Metoda potęgowa. T07 Algorytm Jacobiego rozwiązywania symetrycznych zadań własnych. T08. Istnienie, właściwości i zastosowania rozkładu SVD. T09. Jednostronny algorytm Jacobiego wyznaczania rozkładu SVD. T10. Regularyzacja Tichonowa. T11. Liniowe zadania najmniejszych kwadratów z ograniczeniami liniowymi.
Full description:	(in Polish) T01. Różne rodzaje błędów w obliczeniach numerycznych Katastroficzna utrata cyfr znaczących Przybliżanie wartości pochodnych funkcji w punkcie za pomocą˛ ilorazów różnicowych różnego typu. Dyskretyzacja zadań brzegowych dla równań różniczkowych. Numeryczne różniczkowanie funkcji wielu zmiennych (gradient, jakobian, macierz Hessego itd.) Złożoność obliczeniowa . Błąd obcięcia dla ilorazów różnicowych Inne przykłady w których występuje utrata cyfr znaczących T02. Zredukowany rozkład QR macierzy prostokątnych Utrata ortogonalności w klasycznym algorytmie (cgs) Grama-Schmita. Zmodyfikowany algorytm Grama-Schmita (mgs). Algorytm Grama-Schmita z reortogonalizacją. Wnioski z doświadczalnych obliczeń numerycznych. T03. Zastosowanie zredukowanego rozkładu QR macierzy prostokątnych Rozwiązywanie regularnych, liniowych zadań najmniejszych kwadratów metodą QR. Porównanie z wynikami rozwiązania normalnego układu równań (dla analogicznych zadań) T04. Ogólna charakterystyka macierzy ortogonalnych. Odbicia Householdera. Pełen rozkład QR macierzy prostokątnej wyznaczany metodami Householdera i Givensa. Rozkład QR z wyborem kolumny i jego zastosowanie do rozwiązywania liniowych, nieregularnych zadań najmniejszych kwadratów. Badanie złożoności obliczeniowej. T05. Podstawowe informacje o macierzowych zadaniach własnych. Definicja wektorów własnych , wartości własnych i ich krotności algebraicznej oraz krotności geometrycznej. Twierdzenie o istnieniu rozkład spektralnego rzeczywistej macierzy symetrycznej. Uwarunkowanie symetrycznych i niesymetrycznych zadań własnych. Twierdzenie lokalizacyjne Gerschgorina. Relacja podobieństwa macierzy. O konieczności użycia metod iteracyjnych do rozwiązywania dużych zadań własnych. Wykorzystanie zadań własnych do badania rozwiązań liniowych równań różnicowych o stałych współczynnikach. T06. Metoda potęgowa Zbieżność metody potęgowej. Odwrotna metoda potęgowa. Zagadnienie PageRank. T07 Algorytm Jacobiego rozwiązywania symetrycznych zadań własnych. Różne strategie zerowania w algorytmie Jacobiego i porównanie ich efektywności. Dobór parametrów sterujących w algorytmie Jacobiego. Informacje o metodzie QR rozwiązywania zadań własnych. T08. Istnienie, właściwości i zastosowania rozkładu SVD Wartości szczególne macierzy prostokątnej , lewe wektory szczególne, prawe wektory szczególne (i relacje między nimi). Twierdzenie Bauera-Fike. Zastosowanie do kompresji obrazu. Pseudoodwrotność macierzy. Rozwiązywanie regularnych i nieregularnych liniowych zadań najmniejszych kwadratów z wykorzystaniem rozkładu SVD. T09. Jednostronny algorytm Jacobiego wyznaczania rozkładu SVD Dobór macierzy Givensa . Dlaczego stosujemy metodę jednostronną ? Informacja o metodzie składowych głównych. T10. Regularyzacja Tichonowa Czym jest regularyzacja ? Przykłady liniowych zadań najmniejszych kwadratów wymagających regularyzacji. Zastosowanie do czyszczenia forografii cyfrowej. T11. Liniowe zadania najmniejszych kwadratów z ograniczeniami liniowymi. Macierz KKT i jej odwracalność. Warunki istnienia i jednoznaczności rozwiązania zadań LLS z ograniczeniami. Numeryczne wyznaczanie rozwiązania zadania LLS z ograniczeniami. Zastosowania.
Bibliography:	(in Polish) Zalecana literatura podstawowa: ‒ S. Boyd, L. Vanderberghe , “Introduction to Applied Linear Algebra”, Cambridge Univ. Press 2018. ‒ Golub G.H, Van Loan Ch., Matrix Computation 4ed., J. Hopkins UP., 2013. ‒ Trefethen L.N. , Bau D. Numerical Linear Algebra., SIAM 1997. Zalecana literatura uzupełniająca: ‒ G. Allaire., S. Kaber S , Numerical Linear Algebra, Springer 2002 ‒ A. Kiełbasińsk, H. Schwetlick , Numeryczna algebra liniowa: wprowadzenie do obliczeń zautomatyzowanych, Warszawa : Wydaw. Nauk. -Techn., 1992 ‒ D.S. Watkins, Foundations of Matrix Computations 3ed., Wiley 2012.
Learning outcomes:	(in Polish) absolwent potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym InzP_U01-KPIN1_U05 E02 absolwent zna i rozumie zagadnienia matematyczne konieczne do zrozumienia podstawowych pojęć i zjawisk niezbędnych w pracy informatyka obejmujące m.in. podstawy analizy matematycznej, przybliżone metody opisu zjawisk ciągłych, metody numeryczne, podstawy algebry i algebry liniowej, podstawy logiki i matematyki dyskretnej KPIN1_W01 E03 absolwent potrafi projektować, analizować pod kątem poprawności i złożoności obliczeniowej oraz programować algorytmy; wykorzystywać podstawowe techniki algorytmiczne i struktury danych E04 absolwent zna i rozumie podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, metoda dziel i zwyciężaj, poprawność, metoda niezmienników, złożoność obliczeniowa) KPIN1_W05 E05 absolwent potrafi stosować techniki prowadzące do otrzymania oprogramowania wysokiej jakości InzP_U19-KPIN1_U25 E06 absolwent potrafi opracować, przeanalizować i zaimplementować wybrane metody numeryczne z wykorzystaniem pakietów i bibliotek numerycznych KPIN1_U28 E07 absolwent potrafi przygotowywać dokumentację, opracowania i raporty w języku polskim i języku obcym, w tym z wykorzystaniem Reprezentacja 64-bitowych liczb zmiennopozycyjnych w standardzie IEEE Podstawowe funkcje Matlaba i Pythona dotyczące arytmetyki zmiennopozycyjnej
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ą.
Practical placement:	(in Polish) Nie dotyczy.

Classes in period "Academic year 2020/2021, summer semester" (past)

Time span:	2021-03-01 - 2021-09-30	Selected timetable range: weekly course term Navigate to timetable
Type of class:	laboratory, 30 hours more information lecture, 30 hours more information
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	Selected timetable range: weekly course term Navigate to timetable
Type of class:	laboratory, 30 hours more information lecture, 30 hours more information
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	Selected timetable range: weekly course term Navigate to timetable
Type of class:	laboratory, 30 hours more information lecture, 30 hours more information
Coordinators:	Andrzej Maćkiewicz
Group instructors:	(unknown)
Students list:	(inaccessible to you)
Examination:	Course - Exam laboratory - Graded credit lecture - Exam

Classes in period "Academic year 2023/2024, summer semester" (in progress)

Time span:	2024-02-26 - 2024-09-30	Selected timetable range: weekly course term Navigate to timetable
Type of class:	laboratory, 30 hours more information lecture, 30 hours more information
Coordinators:	Andrzej Maćkiewicz
Group instructors:	(unknown)
Students list:	(inaccessible to you)
Examination:	Course - Exam laboratory - Graded credit lecture - Exam

Course descriptions are protected by copyright.
Copyright by Adam Mickiewicz University, Poznań.