University of Warsaw - Central Authentication System
Strona główna

Selected topics in numerical analysis

General data

Course ID: 1000-135AN
Erasmus code / ISCED: 11.183 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Mathematics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title: Selected topics in numerical analysis
Name in Polish: Analiza numeryczna
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: (in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Elective courses for 2nd stage studies in Mathematics
ECTS credit allocation (and other scores): 6.00 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: English
Type of course:

elective courses
Short description:

Numerical solution of important computational problems of applied mathematics: the eigenproblem, large sparse linear systems, systems of nonlinear equations and multidimensional quadrature.
Full description:

* Matrix eigenvalue problem. Conditioning of eigenvalues and eigenvectors. Power method, inverse iteration and Rayleigh quotient iteration (RQI). QR method. Convergence in the symmetric case. Orthogonal transformations. Jacobi and "divide and conquer" methods. Computational cost and numerical properties.

* SVD decomposition and irregular least squares problem.

* Iterative solution of large sparse systems of linear equations. CG and GMRES methods, their convergence and implementation. Examples of stationary iterations and their convergence condition. Short survey on other iterative methods (CGT, PCR, BiCG, multigrid, etc). Issues of parallel implementation and efficiency. Preconditioning and spectral equivalence.

* Iterative solution of systems of nonlinear equations. Banach's fixed point iteration. Newton's method and its variants. Convergence of these methods. Information on Kantorowich theorem. Stopping criteria. Information on continuation methods.

* Numerical quadrature in many dimensions. One dimensional quadratures. Tensor product quadratures in low dimension. Curse of dimensionality. Mone Carlo quadratures. Information on variance reduction and QMC.
Bibliography:

J. Demmel, Numerical Linear Algebra

T. Kelley, Iterative Solution of Linear and Nonlinear Equations

P. Davis and P. Rabinovitz, Methods of numerical integration
Learning outcomes: (in Polish)

Wiedza i umiejętności

1. Zna podstawowe formaty macierzy rzadkich. Zna kilka przykładów zadań w których takie macierze się pojawiają.

2. Wie co to jest iteracyjna metoda rozwiązywania układów równań liniowych

3. Zna metody iteracyjne typu Jakobi, Gauss, Seidel i Richardsona. Wie przy jakich założeniach te metody są zbieżne. Zna twierdzenie o warunku dostatecznym i koniecznym zbieżności prostych metod iteracyjnych.

4. Zna zasadę konstrukcji prostych metod gradientowych. Zna metodę najszybszego spadku i minimalnych residuów oraz zna twierdzenia mówiące o szybkości zbieżności tych metod.

5. Zna zasadę ogólną konstrukcji metod typu Kryłowa. Zna konstrukcję metod sprzężonych gradientów i GMRES. Wie przy jakich założeniach metody te są zbieżne i jaka jest oszacowanie szybkości zbieżności tych metod.

6. Wie na czym polega ściskanie macierzy (preconditioning) i zna kilka prostych technik konstrukcji prekonditionerów.

7. Zna wielowymiarowe metodę Newtona i metodę Banacha rozwiązywania układów równań nieliniowych. Wie kiedy te metody są zbieżne i co oznacza wykłądniczy rząd zbieżności metody iteracyjnej rozwiązywania układów równań nieliniowych.

8. Zna metodę Broydena. Wie jak praktycznie obliczać na komputerze kolejne iteracje tej metody.

9. Zna metody globalizacji zbieżności metod rozwiązywania układów równań nieliniowych

10. Wie na czym polega symetryczne numeryczne zadanie własne. Zna metodę sprowadzenia macierzy symetrycznej do macierzy podobnej trójdiagonalnej przy pomocy macierzy Householdera. Wie ile wynosi koszt tej operacji.

11. Zna metody potęgową i odwrotną potęgową. Wie przy kiedy te metody są zbieżne.

12. Zna wyprowadzenie metody QR i jej podstawowe własności.

13. Zna metodę dziel i rządź znajdowania par własnych dla macierzy trójdiagonalnej.

14. Zna metodę Hymana.

15. Wie na czym polega tzw. przeklęństwo wymiaru na przykładzie zadania wielowymiarowego całkowania.

16. Zna metody Monte Carlo i Quasi-Monte Carlo. Zna podstawowe własności tych metod.

Kompetencje społeczne:

1. Rozumie znaczenie metod rozwiązywania przybliżonego układów równań, zadania własnego i całkowania wielowymiarowego jako narzędzi służących do modelowania praw przyrody.
Assessment methods and assessment criteria: (in Polish)

Egzamin.

Classes in period "Winter semester 2023/24" (past)

Time span: 2023-10-01 - 2024-01-28
Selected timetable range:
Navigate to timetable
Type of class:
Classes, 30 hours more information
Lecture, 30 hours more information
Coordinators: Piotr Krzyżanowski
Group instructors: Piotr Krzyżanowski
Students list: (inaccessible to you)
Examination: Examination

Classes in period "Winter semester 2024/25" (future)

Time span: 2024-10-01 - 2025-01-26
Selected timetable range:
Navigate to timetable
Type of class:
Classes, 30 hours more information
Lecture, 30 hours more information
Coordinators: Piotr Krzyżanowski
Group instructors: Piotr Krzyżanowski
Students list: (inaccessible to you)
Examination: Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
Krakowskie Przedmieście 26/28
00-927 Warszawa tel: +48 22 55 20 000 https://uw.edu.pl/ contact accessibility statement USOSweb 7.0.3.0 (2024-03-22)