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