First, see review_topics_for_midterm.txt Material AFTER exam 1 =============================== Chapter 4, sections 4.1-4.3,4.5 --------------------------------------- Taylor series, simplification tricks, error bounds Asymptotic approximations, Newton hulls Interpolation Constant-time nearest-neighbor table lookup Linear interpolation Lagrange polynomial interpolation barycentric implementation creation efficiency, evaluation efficiency Runge phenomena Chebyshev interpolation Minimize oo-norm of error node calculation formula Pade approximations Chapter 7, Quadrature, sections 7.1-7.3, 7.5 --------------------------------------- Riemann Rule Newton-Cotes rules trapezoidal, simpson, 3/8's simpson, boole local and composite forms Truncation error, Local Precision, composite precision use of taylor series in calculation Other rules Romberg integration Richardson Extrapolation precision Midpoint rule Gauss-Legengre vs Clenshaw--Curtis problems created by singularities (jumps, infinite derivatives) Practical: quad(), quad8() Chapter 5, sections 5.1-5.2 --------------------------------------- Least squares for overdetermined linear systems measures of "best fit" Least squares solutions of over-determined systems Normal equations, interpretation, residual rank, column and row spaces conditions for existence and uniqueness of solutions Coefficient of Determination b2 in ColNull(A) implies A^T b2 = 0 b1 in ColSpace(A) implies b1 = A z for some z Performance Applications - Kepler, Taylor how to fit a line, plane, power function, exponential How to solve with matlab, also polyfit Cholesky Factorization, efficency QR version, efficency Chapter 11, Eigenvalues and eigenvectors, 11.1-11.2 --------------------------------------- hand methods for 2x2 systems Power method for symmetric matrices how to approximate eigenvalue Convergence rate Improvements inverse theorem shifting theorem cubic convergence of shifted inverse method Francis Algorithm Chapter 9, Differential equations, 9.1-9.2, 9.7 --------------------------------------- Examples Eigenvalues and Matrix exponential expm for x' = A x General concept of a vector field nth-order ordinary equations can be written as system of n first-order equations Approximations to a Derivative Taylor series method for f' and f'' Truncation error (same as for quadrature) Forward Euler Method Backward Euler Method ode45, Runga--Kutta Chapter 8, Optimization, 8.1, first part of 8.3 --------------------------------------- Discrete problem Brute force argmin_{x \in U} f(x) setup, existence, uniqueness Calculus methods Gradient descent Convex, strictly convex definitions, existence, uniqueness Quasi-concave Golden Ratio method performance line search, Gradient search, steepest decent, greedy methods Mona Lisa examples Costs and benefits When is simplex algorithm useful? Monte carlo Simulated annealing algorithm, good and bad Montecarlo integration area of a circle volume of a 4-sphere performance Black-Scholes-Merton Fast matrix multiplication and the FFT