Math 614: Numerical Linear Algebra --- Fall 2019
To contact the instructor: j.rhodes@alaska.edu
Course syllabus: M614syl.pdf
Note: Classroom has changed to 204
Chapman
Required Textbook: Numerical
Linear Algebra, by Lloyd N. Trefethen and David
Bau, III, 1997 / xii + 361 pages / Softcover / ISBN:
978-0-898713-61-9 / List Price $72.00 / SIAM Member Price $50.40
Note: Students may join SIAM (the
Society for Industrial and Applied Mathematics) for $25, or for
free if they are among the first two to ask the instructor for a
nomination. Even at $25, the cost is almost offset by the
discount price for the text, and comes with lots of other
benefits as well. See SIAM Student Membership.
Homework Assignments:
The dates below are when problems
were assigned. Unless otherwise noted, problems are always due
the following Monday.
Homework should be typed, in LaTeX,
following the template HWtemplate.tex. Problems should
be presented in the order they were assigned.
Problems are from T&B, unless
otherwise stated.
- 8/26 1.1, 1.2, #1 Let A=[2 1 1; -2 0 1; 4 4 6], b=[1;
-4; -4]. By hand solve Ax=b. Compute rank, determinant,
inverse (if possible), and eigenvalues of A. Verify your
results with MATLAB
- 8/28
1.4, 2.1 ,2.6, 2.7, #1 Show the product of
unitary matrices is unitary.
- 8/30 2.2, 2.3, 2.4, 3.1, 3.2
- 9/2 LABOR DAY
- 9/4 3.3, 3.4, 3.5, #1 Show
any matrix norm induced from vector norms is actually a norm
(i.e., satisfies equations (3.15) of the text).
- 9/6 4.1, 4.4, #1 Use
appropriate MATLAB commands to find the singular value and
eigen decompositions of A=[3 1 0; 0 2 1; 0 0 1] and B=[1 1 0;
0 1 1; 0 0 1]. One of these 4 results should be wrong or
produce an error message. Which one, and why?
- 9/9 4.2, 5.1, 5.3
- 9/11 5.2 ,5.4
- 9/13 6.1, 6.2, 6.3
- 9/16 6.4, 6.5
- 9/18 7.1, 7.2, 7.5, #1 Show the calculation to obtain the Legendre
polynomials P_2, P_3 in the text. Then calculate P_4.
- 9/20 8.3, Make sure you have access to MATLAB,
download the m-files GS.m and GStest.m and make sure you can run them.
- 9/23 #1 Program Modified GS, and conduct
Experiment 2 of Lecture 9., 10.1, 10.2
- 9/25 10.3
- 9/27 11.3, #1(a) If Sigma is
diagonal and mxn of full rank n, what is the pseudoinverse
Sigma^+? Justify your answer. (b) If A is mxn of full rank n
and has svd U\Sigma V*, what is the svd of A^+? Justify your
answer.
- 9/30 12.3
- 10/2 12.1
- 10/4 13.2, 13.3
- 10/7 14.1a-c,e-g, 14.2a
- 10/9 15.1a-d,15.2
- 10/11 study for exam
- 10/14 MIDTERM EXAM
- 10/16 none
- 10/18 #1 Show that taking the
inner product of a vector x with a vector v in C^n is
component-wise backward stable in v, and hence backward
stable. That is, with x fixed show that the computed value of
v'x is (\tilde v)'x where |v_i-\tilde v_i|/|v_i|
=O(n\epsilon_m). #2 Use the previous problem to quickly
conclude that taking the product of a matrix A with a fixed
vector x is backward stable in A. #3
What is the operation count for solving an nxn upper
triangular system by back substitution? Explain your answer.
- 10/21 18.1,18.4
- 10/23 19.1,19.2
- 10/25 #1 Solve Ax=b by finding
A=LU and solving 2 triangular systems, for A=[-2 1 -1; -4 1
0;2 -4 10], b=[3 9 12]'.
- 10/28 20.1 20.3a, 20.4, 21.1
- 10/30 21.4
- 11/1 23.1, 23.2
- 11/4 23.3, #1a) By hand compute an LDL* factorization of A=[2, -2, 6;-2, 1, -7;6, -7, 18], and use it to determine whether or not A is positive definite. b) Use MATLAB's ldl command to compute such a factorization for the same matrix. You should get a different result. Explain what you think MATLAB did, and, more importantly, why. You may refer to MATLAB's help.
- 11/6 24.1, 24.4a
- 11/8 #1 For 2x2 and 10x10 matrices,
experimentally investigate power iteration to determine
eigenvectors/values. Specifically, for 5 random matrices produced by MATLAB's "randn",
and a random vector x_0 of each size, determine how many iterations
are needed to obtain the dominant eigenvector and eigenvalue to
at least 12 digits of accuracy. (You may assume MATLAB's eig
command gives the "true" values.) #2 By hand, determine exact
eigenvectors and eigenvalues of A=[5 1; -9 -1], and explain why
investigating power iteration on A and A+10^{-10}*randn(2)
should be interesting. Then do so, as in the previous problem, but use several different random starting vectors.
- 11/11 25.1, #1Write MATLAB code to obtain an upper
Hessenberg form of a square matrix; i.e., given A, find Q and H
with A=QHQ^*. (You may be able to modify your Householder QR
code from earlier in the course.) Demonstrate it works correctly
on two 5x5 random matrices, one Hermitian and one not.
- 11/13 25.2, 27.5, 27.6
- 11/15 28.1, 28.2 a,b,c(Householder only), #1
In MATLAB, experiment with using the basic QR algorithm to find eigenvalues (i.e.,
iterate [Q R]=qr(A); A=R*Q). You should do experiments with some random hermitian matrices (obtained by A=B+B' where B is random)
and their upper Hessenberg forms (obtained by hess(A)), as well as some random matrices with no special structure and their upper Hessenberg forms.
Pick an appropriate size of matrix and number of trials to do -- it need not be a lot. Make interesting observations.
- 11/18 29.1(but use MATLAB's hess, so you can skip part (a), and MATLAB's qr, rather than your own qr code)
- 11/20 33.2
- 11/22 33.1, #1 In MATLAB, program the Arnoldi iteration. Then, for a random 100x100 hermitian matrix A and random vector b use your code to find the Arnoldi approximations to the eigenvalues of A, comparing them with the actual eigenvalues. (You may use MATLAB's eig command to find the eigenvalues of each H_n, and to find the `true' eigenvalues of A.) Print out all eigenvalue approximations for n=2 through 20, and show your results graphically. Comment on your example results. Repeat for a non-hermitian A. (Note: These are much smaller examples than you would use Arnoldi on in practice, but should illustrate how it behaves.)
- 11/25 34.1
- 11/27-29 THANKSGIVING BREAK
- 12/2 35.1, 35.2
- 12/4 none
- 12/6 none
- 12/11 FINAL EXAM 10:15-12:15