Web Page for Math 440
Fall Semester 2014
Numerical Analysis
SYLLABI: PDF
TEXTBOOK: "Fundamentals of Matrix Computations", David Watkins, Wiley, 2010.
HOMEWORK ASSIGMENTS:
#1, Due Sept 8: Hand in your MATLAB m-files for any problems that require coding. You will be docked points for codes that does not run or has mistakes.
(1) Ex. 1.1.10. This was already mostly done in class on the second day. Use the tic and toc commands to compute CPU time in MATLAB.
(2) Write a MATLAB code that implements matrix-matrix multiplication using pseudo-code (1.1.13). You can simply modify your code from part (1). Add a check in your code that the inner-dimensions of A and X agree.
(3) Ex. 1.1.20.
(4) Ex. 1.2.4.
(5) Ex. 1.2.16. Use MATLAB to solve the problem when m=20, c=d=0, and f(x)=1. The toeplitz function will be useful.
#2, Due Sept 17:
(1) First, do Exercise 1.3.17(a) by hand. Then modify ForwardSub.m so that it implements backward substitution for upper-triangular matrices (call it BackwardSub.m), and use your algorithm to solve the same system. Verify that the two results are the same. Hand in a listing of your code;
(2) Exercise 1.3.23, hint: use induction;
(3) Exercise 1.4.16, test your algorithm on the matrix A Exercise 1.4.21;
(4) Exercise 1.4.21, compute the Cholesky factorization by hand in part (a) and verify it's the same as your algorithm gave in 1.4.16.
#3, Due Sep 30:
(1) 1.4.44 and 1.4.64.
(2) Modify AO2D.m so that it solves the system A'*A=A'*b using the Cholesky factorization of A'*A both with and without symmetric approximate minimum degree reordering (symamd in MATLAB). Generate the sparsity plots for the original and reordered matrix using the spy function, as well as spy plots of the Cholesky factorizations of both matrices (four plots all together). Does CPU time improve when the reordering is used? Hand in a listing of your code.
(3) 1.8.4; 1.8.9; 1.8.11.
(4) 1.8.12, test your algorithm on the matrix given in 1.8.4.
#4, Due Oct 10:
(1) 2.1.17
(2) 2.1.30
(3) 4.1.11 & 4.1.13
(4) SVD application (also the week 6 lab): use the truncated SVD on the 2D example Deblur2D.m. Report the optimal truncation level, i.e., the one that minimizes ||x_recon-x_true||, and plot the corresponding reconstruction.
#5, Due 10/21 (SVD problems): 4.3.8,9; 5.8.14,16,18.
#6, Due 10/31 (QR problems):
(1) 3.2.14 (use a rotator)
(2) 3.2.39
(3) 3.2.47
(4) Hand in your code for *both parts* of the Week 9 lab.
COMPUTER LABS/CODE:
Week 1, MATLAB m-file for matrix multiplication: MatMultRowFun.m.
Week 2, Using MATLAB's toeplitz function: ToeplitzMatrix.m.
Week 2, m-file for forward substitution ForwardSub.m
Week 3, m-file for adaptive optics application in 1D AO1D.m. Lab problem: modify line 21 of AO1D.m so that the Cholesky factorization is used instead of '\' for solving the system. Note that this is what is done in operational adaptive optics systems, though in two-dimensions.
Week 3 Lab, PDF: a lab on the Kronecker product and using sparse reordering to reduce fill-in for the Cholesky factorization.
Week 5, m-file for deblurring (deconvolution) example from class Deblur1D.m.
Week 5 Lab: work on the problems at the bottom of Deblur1D.m.
Week 6 Lab: work on the problem at the bottom of Deblur2D.m.
Week 7 Lab, PDF: GaussianDrawsPCA.m, Eigenfaces.m, and faces.zip.
Week 9 Lab: (i) Use the QR factorization to solve the least squares problem found in AO2D.m; (ii) Write your own QR using reflector.m and test it on a random 10x10 matrix to verify that it works.