REVIEW FOR CMSC/AMSC 460 Fall 2007 -------------------------------------------------------------- Unit 1 Review: Be able to: make use of these capabilities of Matlab: vector operations, including the ``dot" commands, scripts, special fonts, xor, length, linspace, logspace, plot, semilogx, semilogy, title, xlabel, ylabel, sprintf, disp, input, ginput, axis, grid, legend, set, for, if, while, zeros, size, max, sum, close, figure, diary, hist, rand, randn, subplot, floor, fix, round, any, all, flops, &, |, \ identify sources of errors represent a number in fixed point binary. perform binary addition. identify the range of fixed point numbers with a d digit representation. define overflow and underflow. represent a number in floating point by computing its exponent and mantissa. give the number of digits and range of exponents in the IEEE floating point standard. use rounded or chopped arithmetic. analyze the propagation of error in a sequence of operations. compute absolute and relative errors or error bounds. cure catastrophic cancellation. define forward and backward error. -------------------------------------------------------------- Chapter 2 and 3 Review (Skip 2.4.4, 3.2) Be able to: derive linear systems to compute coefficients for spline interpolation in a variety of bases. determine the coefficients of an interpolating polynomial using the Newton basis. explain the pitfalls in using the power basis. use Horner's rule for the Newton basis and for the power basis. use inverse interpolation to find a root of an equation. compute a piecewise linear interpolant to a set of data. use bisection to find the interval in which a point lies, so that its piecewise linear interpolant can be evaluated. use the error bounds for polynomial and spline interpolation to determine how many points are sufficient to achieve a given accuracy. define a spline. give the conditions defining the natural boundary conditions and the "not a knot" conditions for a cubic spline. explain when each type of interpolation is appropriate, and when smoothing should be used instead. determine the sensitivity of the interpolating function to small changes in the data. -------------------------------------------------------------- Chapter 4 Review (Skip 4.5) Be able to: determine bounds on the accuracy of quadratures derive quadrature methods through polynomial or spline interpolation. write the equations that determine the weights and evaluation points for a Gauss quadrature rule. give the ``degree'' of Newton-Cotes, Gauss, and Gauss-Kronrod rules. apply the quadrature rules to simple problems. discuss how ``adaptive'' quadrature programs work. discuss how numerical integration programs work. -------------------------------------------------------------- Chapter 5 Review (Skip 5.3, 5.4.2, and 5.5) write row or column oriented algorithms. tell whether a given algorithm is good for Fortran (column oriented) or C (row oriented). define matrices efficiently in Matlab using "diag" and row and column operations. define matrices by blocks. quickly give the operations counts for matrix-vector product and matrix-matrix product. compute norms of vectors and matrices (1, 2, inf, and fro). explain how the fast Fourier transform works and why the operations count is O(n log n) when n is a power of 2. -------------------------------------------------------------- Chapter 6 Review: (Skip 6.2) Be able to: write algorithms for forward and backward substitution on triangular problems. solve systems with the same matrix but several right-hand sides without refactoring the matrix. take advantage of special structure in a matrix such as bandedness or triangularity. do operations counts for matrix algorithms. give operations counts for forward or back substitution (n^2), Gauss elimination or LU factorization (2/3 n^3), and other common algorithms. (See the tables in the book.) know why we never compute an inverse of a matrix unless we actually need to look at the elements, and know how to efficiently implement formulas that seem to require inverses (e.g., Sherman-Morrison). distinguish between residual and error and relate them to forward and backward error analysis. compute the condition number of a matrix and know its significance. use the bound ||e||/||x|| <= cond(A) ||r||/||b||. discuss why pivoting is essential in LU factorization -------------------------------------------------------------- Chapter 7 Review: (Skip 7.4) Know that A \ b solves the least squares problem when the number of rows in A is greater than the number of columns. set up a least squares problem, as in the example. derive the normal equations by differentiating the norm-squared of the residual. use the QR factorization to solve a least squares problem or to find a basis for the range and nullspace of a matrix. -------------------------------------------------------------- Chapter 8 Review: (Skip 8.1.1. Skim 8.2.1 and 8.2.2.) Be able to: write code for solving a nonlinear equation (single variable case) using bisection, Newton, or secant algorithms. compare the cost, speed, and reliability of different algorithms. use fmin to find a minimizer of a function of a single variable. use fmins to find a minimizer of a function of several variables. use nonlinear least squares to solve a nonlinear system of equations. -------------------------------------------------------------- Chapter 9 Review: Be able to: derive the Euler method by polynomial fitting. define and use the concepts of local error, global error, and stability. explain why the Backward Euler method is sometimes more effective. use Euler, Backward Euler, Runge Kutta, or an Adams method to solve differential equations. understand why predictor-corrector codes are used. set error tolerances appropriately. use ODE23 and ODE45 -------------------------------------------------------------- Some practice problems: p 47: 1.4.2 1.4.5 1.4.6 1.4.7 1.4.8 1.4.9 p 82: 2.1.3 p 88: 2.2.4 p132: 3.3.2 3.3.6 p144: 4.1.1 4.1.2 p148: 4.2.5 p159: 4.4.3 p186: 5.2.1 5.2.9 p193: 5.3.3 p220: 6.2.1 p232: 6.3.3 6.3.4 p238: 6.4.1 6.4.4 p246: 7.1.1 7.1.5 p282: 8.1.5 8.1.6 8.1.9 p304: 8.2.2 p324: 8.4.6 p338: 9.1.1 9.1.3