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. Increase in bandwidth in banded matrices due to pivoting in L and U factors. (Sections 5.1-5.3,5.6).
• Condition number. Effects of conditioning on the error in solution. (Section 5.7)
• Least squares fitting of data. Normal equations, QR factorization -- overall idea of the algorithm, Hausholder rotations. (Chapter from a different textbook linked from February 28 lecture: 3.1,3.2,3.3.1,3.3.2,3.4.1-3.4.4,3.5)
• Polynomial interpolation: system of equations for interpolation, Lagrange polynomials (Sections 10.1-10.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, March 6 lecture).
• Computing eigenvalues and eigenvectors: power method and inverse power method For what systems inverse power method is more efficient. (Sections 7.1-7.2).
• 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, and 9.1, linked from April 1 lecture).
• Systems of linear ODEs, definitions, reduction of high-order to first order. First- and second-order one-dimensional linear ODEs, solution formulas. Stiffness.
• 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. Verlet method. Relative advantages and disadvantages of implicit and explicit methods. (Sections 17.1 and 17.2 beginning, 17.5, notes on Verlet linked from April 8 lecture).
• Iterative solvers: fixed point form of the linear system, Jacobi and Gauss-Seidel iterations. (Section 7.1 from new version of the textbook, linked from April 24 lecture).
• Fourier series and Discrete Fourier Transform definitions. Complexity of direct DFT and FFT. (Chapter 14 and notes linked from April 28 lecture.)