Introduction. Well-posedness and Condition Number of a Problem and of a Method. Sources of Error in Computational Models. Rounding of a Real Number in its Machine Representation.
[Q] Sections 2.1, 2.2, 2.4, 2.5.5
Files: Lecture1.pptx, illcondsyst.m
Conditioning Number exercises.
exercises01.pdf: Ex 1.1, 1.2, 1.3
Stability Analysis of Linear Systems. Matrix norms.
[Q] Section 1.11 (matrix norm)
[Q] Sections 3.1 (intro + 3.1.1, 3.1.2)
Matlab introduction.
Matlab files: ex5.m, roe_accumulation.m, round_err.m
Solution of Triangular Systems. Implementation of Substitution Methods. The Gaussian Elimination Method (GEM).
[Q] Sections 3.2 (intro + 3.2.1, 3.2.2), 3.3 (intro)
Gauss Elimination exercises.
exercises03.pdf: Ex 1, 2, 3
GEM as a Factorization Method. The effect of Rounding Errors. Implementation of LU Factorization. Pivoting. Cholesky Factorization. QR Factorization, SVD decomposition.
[Q] Sections 3.3, 3.4.2, 3.4.3, 3.5, and 1.9
LU factorization and SVD exercises
exercises04.pdf: Ex 2, 3, 4
Stationary iterative methods, SOR, Jacobi, Gauss-Seidel methods. Convergence.
[Q] Sections 4.1, 4.2.1-4.2.3
SVD exercises
exercises04.pdf: Ex 5
Stationary iterative methods
exercises05.pdf: Ex 1, 3.
Conjugate gradient.
[Q] Sections 4.3.3, 4.3.4
Krylov Subspace Methods vs Stationary Iterative Methods.
exercises06.pdf: Ex 1.1
Power method. Ideas of Krylov subspace methods.
[Q] Sections 5.3.1 (Power methods)
See the notes discussed in class for Krylov subspace methods. Also: [Q] Section 4.5
GMRES. The power method and the Google matrix
exercises06.pdf: Ex 1.2, 2.1
Rootfinding for Nonlinear Equations. Conditioning of a Nonlinear Equation. The Bisection Method, Methods of Chord, Secant, and Newton’s Method.
[Q] Sections 6.1, 6.2.1, 6.2.2
Convergence of Secant and Newton's methods. Stopping criteria.
[Q] Sections 6.3, 6.5
Rootfinding and Horner scheme
exercises07.pdf: Ex 1-4
The Horner Method. 6.4.2 The Newton-Horner Method.
[Q] Sections 6.4.1, 6.4.2
Newton’s Method for nonlinear systems.
[Q] Sections 7.1.1
Polynomial Interpolation. The Interpolation Error. Drawbacks of Polynomial Interpolation on Equally Spaced Nodes and Runge’s Counterexample. Stability of Polynomial Interpolation. Piecewise Lagrange Interpolation.
[Q] Sections 8.1.1, 8.1.2, 8.3, 8.6.1.
Approximation by Splines. Interpolatory Cubic Splines
[Q] Sections 8.7 (excluding 8.7.2).
Lagrange Interpolation.
exercises08.pdf: Ex 1, 2, 3.
Cubic splines.
exercises09.pdf: Ex 1.
Bézier Curves and De Casteljau algorithm.
[Q] Section 8.8.1
Approximation of Functions by Generalized Fourier Series. 10.1.1 The Chebyshev Polynomials. 10.1.2 The Legendre Polynomials
[Q] Section 10.1
Orthogonal polynomials.
exercises10.pdf: Ex 1, 2, 3.
Quadrature Formulae. Interpolatory Quadratures. The Trapezoidal Formula. The Cavalieri-Simpson Formula. Newton-Cotes Formulae. Composite Newton-Cotes Formulae. Gauss quadrature formulas.
[Q] Sections 9.1, 9.2, 9.3, 9.4, 10.2
Gauss quadrature.
exercises11.pdf: Ex 1.
The Cauchy Problem. One-Step numerical methods. Runge-Kutta (RK) methods.
[Q] Sections 11.1, 11.2, 11.3 (excluded 11.3.1, 11.3.2), 11.8 (excluded 1.8.2-1.8.4).
Test
Course completion requirements
It is necessary to obtain the practical course credit before passing the exam.
To get the course credit, one needs to obtain 12 points. The points will be awarded for:
Active presence at the practicals (1 point per presence).
Doing the Matlab homework (max 2 points for one homework; there will be four Matlab homework during the semester)
A written exam (max 12 points). There is a possibility of one additional attempt.
Requirements for the exam
The exam is written. The examination requirements are given by the topics in the syllabus, in the extent to which they were taught in the course.
For this course you will require access to a MATLAB installation. The university has a Total Academic Headcount MATLAB license, which allows you to install MATLAB locally on your machine (Windows, macOS, or Linux). Alternatively, with this license you can use MATLAB Online, which allows you to access a (lightweight) instance of MATLAB directly in your web browser; this should be sufficient for this course.
In order to install MATLAB locally, or access MATLAB Online, you must register for a MathWorks account using an email address ending with cuni.cz. Detailed instructions are available at cuni.cz/UKEN-1270.html.
Alternatively, you can use the free open source Octave application (in Windows, macOS, Linux, and BSD). The syntax and functions are mostly compatible with MATLAB (at least for the level we will be considering for this course).
Here you can find an introduction to Matlab.
Here a useful summary of Matlab basic functions.
Here is Matlab Onramp, a 2 hours online introduction with useful exercises.
Literature:
[F] Felcman J.: (2009). Numerická matematika, učební text k přednášce.
[Q] Quarteroni, A., Sacco, R., and Saleri, F. (2004). Numerical Mathematics (2nd edn), Volume 37 of Texts in Applied Mathematics. Springer, Berlin. ISBN 0-387-98959-5.
Material discussed in class (in order of appearance):