Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Analiza numeryczna
Tok studiów:
2016/2017
Kod:
AMA-3-301-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia III stopnia
Specjalność:
-
Kierunek:
Matematyka
Semestr:
3
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski i Angielski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
prof. dr hab. Kacewicz Bolesław (kacewicz@agh.edu.pl)
Osoby prowadzące:
prof. dr hab. Kacewicz Bolesław (kacewicz@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Ma rozszerzoną wiedzę o teoretycznych aspektach analizy numerycznej, zarówno dla zadań numerycznej algebry liniowej, jak i zadań obliczeniowych związanych z analizą matematyczną. Rozumie fenomeny złożonych obliczeń numerycznych związane z błędami zaokrągleń. Zna pojęcia i przykłady dotyczące złożoności zadań numerycznych. MA3A_W01 Egzamin
Umiejętności
M_U001 Potrafi analizować zadania obliczeniowe pojawiające sie w fizyce i naukach inżynierskich pod kątem kosztu i stabilności numerycznej. MA3A_U01 Egzamin
M_U002 Potrafi zidentyfikować potencjalne trudności obliczeniowe występujące przy rozwiązywaniu problemów. Wie jakimi kryteriami kierować się przy wyborze metody numerycznej, potrafi przy tym korzystać z właściwej literatury. MA3A_U01 Egzamin
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy lub rozumowań, zdaje sobie sprawę z potrzeby dalszego kształcenia. MA3A_K01 Egzamin,
Aktywność na zajęciach
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Ma rozszerzoną wiedzę o teoretycznych aspektach analizy numerycznej, zarówno dla zadań numerycznej algebry liniowej, jak i zadań obliczeniowych związanych z analizą matematyczną. Rozumie fenomeny złożonych obliczeń numerycznych związane z błędami zaokrągleń. Zna pojęcia i przykłady dotyczące złożoności zadań numerycznych. + - - - - - - - - - -
Umiejętności
M_U001 Potrafi analizować zadania obliczeniowe pojawiające sie w fizyce i naukach inżynierskich pod kątem kosztu i stabilności numerycznej. + - - - - - - - - - -
M_U002 Potrafi zidentyfikować potencjalne trudności obliczeniowe występujące przy rozwiązywaniu problemów. Wie jakimi kryteriami kierować się przy wyborze metody numerycznej, potrafi przy tym korzystać z właściwej literatury. + - - - - - - - - - -
Kompetencje społeczne
M_K001 Zdaje sobie sprawę ze słabych punktów swojej wiedzy lub rozumowań, zdaje sobie sprawę z potrzeby dalszego kształcenia. + - - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

(PL )
1. Arytmetyka zmiennopozycyjna (fl), reprezentacja liczb rzeczywistych, typowe operacje zmiennopozycyjne. Błędy zaokrągleń, numeryczna stabilność i poprawność algorytmów (formalne definicje), przykłady.

2. Numeryczna algebra liniowa – rozwiązywanie układów równań liniowych. Eliminacja Gaussa z wyborem elementu głównego, rozkład LU, numeryczna poprawność (dowód). Eliminacja Gaussa dla macierzy symetrycznych dodatnio określonych – własności w fl.

3. Przekształcenia Householdera I ich zastosowanie do rozkładu ortogonalno-trójkątnego (QR), numeryczna poprawność metody Householdera (dowód). Ortogonalizacja Grama-Schmidta jako metoda rozkładu QR, konieczność reortogonalizacji w fl, analiza w fl ortogonalizacji dwóch wektorów, numeryczna poprawność metody ortogonalizacji Grama-Schmidta (z poprawianiem).

4. Iteracyjne poprawianie rozwiązania układu równań liniowych (dowód odp. twierdzenia).

5. Algebraiczny problem własny. Twierdzenie Gerschgorina. Uwarunkowanie wartości własnych. Analiza metody bisekcji w fl. Analiza metody Wielandta w fl.

6. Sprowadzanie macierzy do postaci Hessenberga za pomocą podobieństw ortogonalnych (analiza w fl), metoda Hymana obliczania wyznacznika macierzy Hessenberga, metoda bisekcji z ciągu Sturma dla macierzy symetrycznych trójdiagonalnych. Metoda QR i jej zbieżność (dowód).

7. Przypomnienie wiadomości o interpolacji wielomianowej Lagrange’a I Hermite’a, postać Newtona wielomianu interpolacyjnego. Analiza algorytmu różnic dzielonych w fl. Wielomiany Czebyszewa – różne postaci. Przypomnienie wiadomości o interpolacji splinowej, algorytm i wyrażenie na błąd dla naturalnych splinów kubicznych (dowód).

8. Aproksymacja w przestrzeniach abstrakcyjnych. Przypomnienie wiadomości o aproksymacji średniokwadratowej. Wielomiany ortogonalne i ich własności (dowody).

9. Aproksymacja jednostajna. Podprzestrzenie Czebyszewa, twierdzenie Czebyszewa o alternansie. Algorytm Remeza i jego zbieżność (dowód).

10. Kwadratury – przypomnienie wiadomości. Błąd kwadratur Newtona-Cotesa (dowód).

11. Rozwiązywanie układów równań nieliniowych. Wykładnik zbieżności metod iteracyjnych. Twierdzenia o punkcie stałym: Banacha o odwzorowaniach zwężających, Brouwera. Twierdzenie Borsuka-Ulama. Metoda Newtona dla układów równań nieliniowych i jej zbieżność.

12. Złożoność problemów ciągłych – algorytm, informacja, promień I średnica informacji, algorytmy centralne i interpolacyjne, optymalna informacja.

13. Informacja adaptacyjna i nieadaptacyjna. Optymalne liniowe algorytmy dla problemów liniowych (lemat Smolyaka).

14. Złożoność problemów początkowych dla równań różniczkowych zwyczajnych – oszacowania z gory i z dołu w modelu najgorszego przypadku (problemy skalarne) – podstawowe wyniki.

(EN )

1. Floating-point arithmetic (fl), representation of real numbers, typical floating-point operations. Round-off errors, numerical stability and numerical well-behavior of algorithms (formal definition), examples.

2. Numerical linear algebra – solving systems of linear equations. Gaussian elimination with pivoting, LU decomposition, its numerical well-behavior (proof). Gaussian elimination for symmetric positive definite matrices – properties in fl.

3. Householder transformations and their application to the orthogonal-triangular (QR) decomposition of a matrix, numerical well-behavior of the Householder method (proof). The Gram-Schmidt (G-S) orthogonalization, the need of re-orthogonalization in fl, analysis of the G-S orthogonalization of two vectors in fl, numerical well-behavior of the G-S method.

4. Iterative refinement of the solution of linear systems of equations (proof of the theorem).

5. The algebraic eigenvalue problem. Gerschgorin’s theorem, conditioning of the eigenvalues. Analysis of the bisection method in fl. Analysis of Wieland’s method in fl.

6. Reduction of a matrix to Hessenberg form by orthogonal similarities (analysis in fl), its further applications (Hyman ‘s method for computing determinant of a Hessenberg matrix, the bisection method using the Sturm sequence for tridiagonal symmetric matrices). The QR method and its convergence (proof).

7. Lagrange and Hermite type polynomial interpolation, Newton’s form of the interpolation polynomial (recalling the material). Divided differences algorithm and its analysis in fl. Chebyshev polynomials – various formulas. Recalling the material related to spline interpolation, error formula and the algorithm for the cubic spline interpolation (proof).

8. Approximation in abstract spaces. Recalling the material related to the approximation in L2. Orthogonal polynomials and their properties (proofs).

9. Uniform approximation. Chebyshev subspaces, Chebyshev’s equioscillation theorem. Remez algorithm and its convergence (proof).

10. Numerical quadratures (recalling the material).Newton-Cotes quadrature error formula (proof).

11. Solving nonlinear equations. Order of convergence of iterative methods. Fixed point theorems: the Banach contraction theorem, Brouwer’s theorem, the Borsuk-Ulam theorem. Newton’s method and its convergence.

12. Complexity of numerical problems – algorithms, information, the radius and diameter of information, central and interpolation algorithms, optimal information.

13. Adaptive and nonadaptive information . Optimal linear algorithms for linear problems (Smolyak’s theorem).

14. Complexity of ordinary differential equations – upper and lower bounds in the worst case setting (scalar problems) – basic results.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 0 godz
Punkty ECTS za moduł 3 ECTS
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena z egzaminu.
Grade from examination.

Wymagania wstępne i dodatkowe:

Podstawy rachunku różniczkowego i całkowego oraz algebry liniowej.
Basic knowledge of calculus and linear algebra.

Zalecana literatura i pomoce naukowe:

1. J. Stoer, R. Bulirsch, Introduction to Numerical Analysis, Springer-Verlag, New York, 2002.

2. A. Bjorck, G. Dalquist, Numerical Methods, Dover Books on Math., 2003.

3. D. Kincaid, W. Cheney, Numerical Analysis, Brooks/Cole Publ. Comp., Pacific Grove, 1991.

4. J.H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice Hall, 1963.

5. J.F.Traub, G. Wasilkowski, H. Wozniakowski, Information-Based Complexity, Academic Press, 1988.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Kacewicz, Bolesław; Przybyłowicz, Paweł; Complexity of the derivative-free solution of systems of IVPs with unknown singularity hypersurface; J. Complexity 31, No. 1, 75-97 (2015).

2. Kacewicz, Bolesław; Przybyłowicz, Paweł; Optimal solution of a class of non-autonomous initial-value problems with unknown singularities; J. Comput. Appl. Math. 261, 364-377 (2014).

3. Kacewicz, Bolesław; On the quantum and randomized approximation of linear functionals on function spaces; Quantum Inf. Process. 10, No. 3, 279-296 (2011).

4. Kacewicz, Bolesław; Przybyłowicz, Paweł; Optimal adaptive solution of initial-value problems with unknown singularities; J. Complexity 24, No. 4, 455-476 (2008).

5. Kacewicz, Bolesław; Almost optimal solution of initial-value problems by randomized and quantum algorithms; J. Complexity 22, No. 5, 676-690 (2006).

6. Kacewicz, Bolesław; Improved bounds on the randomized and quantum complexity of initial-value problems; J. Complexity 21, No. 5, 740-756 (2005).

7. Kacewicz, Bolesław; Optimal and suboptimal algorithms in set membership identification;
Math. Comput. Model. Dyn. Syst. 11, No. 2, 159-169 (2005).

8. Kacewicz, Bolesław; Randomized and quantum algorithms yield a speed-up for initial-value problems;
J. Complexity 20, No. 6, 821-834 (2004).

9. Kacewicz, Bolesław; Asymptotic setting (revisited): analysis of a boundary-value problem and a relation to a classical approximation result; J. Complexity 20, No. 5, 796-806 (2004).

Informacje dodatkowe:

Brak