List of topics to review for the final
- Model, discretization, convergence roundoff errors: definitions.
Relative and absolute errors. Example when roundoff error exceeds
the discretization error for a derivative (Chapter 1.)
- IEEE floating point arithemtics: mantissa, biased exponent, sign:
field sizes and for double precision. Normalized and denormalized
numbers, infinity, NaN: how special values are used.
(Steve Hollasch's notes.)
Matrices: Eigenvalues, eigenvectors, determinant. Singular matrices.
Conditios for existence of a unique solution, multiple solutions
and no solutions.
Symmetric matrices, symmetric positive definite (SPD) matrices,
properties of eigenvalues and eigenvectors of SPD matrices.
Matrix norms: L2, L1. (Chapter 4.)
Gaussian elimination algorithm.
Back substitution, forward substitution.
LU factorization without pivoting,
with partial pivoting, with full pivoting: algorithms in detail.
Complexity of LU factorization without pivoting for banded matrices,
for full matrices. Cholesky decomposition: algorithm,
computational cost compared to LU (Sections 5.1-5.6).
Linear least squares fitting of data. Normal equations (Section 6.1).
Solving nonlinear equations, Bisection and Newton methods in one dimension.
Convergence condition for one-dimensional Newton, rate of convergence
for Newton. Multidimensional Newton method formulation.
(Sections 3.1-3.3, Chapter 9.)
Systems of linear ODEs, definitions, reduction of high-order to first
order. First- and second-order one-dimensional linear ODEs,
solution formulas. Stiffness. (Chapter
- Implicit and explicit integration methods for ODEs.
Euler and backward Euler method for ODEs. Conditions for stability
for the forward Euler method. Stability of backward Euler.
Numerical damping. Midpoint method.
(Sections 17.1 and 17.2 beginning, 17.5.)
Iterative solvers: fixed point form of the linear system,
Jacobi and Gauss-Seidel iterations, gradient descent.
- Polynomial interpolation: system of equations for interpolation,
Lagrange polynomials (Section 11.1, 11.2).
- Curves. Bezier curves: Bernstein basis, basic properties
(affine invariance, convex hull), computing tangents. B-splines:
defining properties (C2-continuity, mimimal support size,
affine invariance); linear B-splines; obtaining a basis function
for cubic spline: no formulas, main steps.
(Lecture notes linked from the lectures.)
Fourier series and Discrete Fourier Transform definitions. Complexity of direct DFT and FFT. (Sections 14.1-14.3 and notes linked from the lecture.)