List of topics to review for the final

• Definitions of model, discretization, convergence, roundoff, 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. Conditions for a linear system to have a unique solution, multiple solutions and no solutions. Definitions: 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. Algorithms: LU factorization without pivoting, with partial pivoting, with full pivoting. Complexity of LU factorization without pivoting for banded matrices, for full matrices. (Sections 5.1-5.5).
• Linear least squares fitting of data. Normal equations (Section 6.1).
• Solving nonlinear equations, Bisection, Newton and secant methods in one dimension. Rate of convergence for Newton. Jacobian of a function. Multidimensional Newton method formulation. (Sections 3.1-3.3, Chapter 9.)
• 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. Leapfrog method. Midpoint method. (Sections 17.1 and 17.2 beginning, 17.5; leapfrog defined in problem 7.)
• Iterative solvers for linear systems: fixed point form of the linear system, Jacobi and Gauss-Seidel iterations (Sections 7.1,7.3.)
• Power method for finding eigenvalues and eigenvectors (Section 8.1, first half). SVD (Section 8.2, definition only, geometric interpretation in 2D).
• Lagrange interpolation, formulas for basis polynomials (Section 11.2).
Cubic Bezier curves: Bernstein basis, formula for the curve, basic properties. K. Bakeer's notes
• Discrete Fourier Transform definitions. Complexity of direct DFT and FFT. Overall idea of FFT (Sections 14.2-14.3; a good explanation of the algorithm in wikipedia