Math 143M

You can also view this page in French, courtesy of Mary Orban.

Greensheet

Final exam: Monday, December 12, 2011, 7:45pm-10pm

Class material:

Homework:

1. Due September 21. Turn in ONLY the 4 matrices that are the answers to the 4 questions below
1. Generate a 4x4 matrix which (through multiplication on the left) adds 3 times the 4th row to the 1st
2. Generate a 4x4 matrix which (through multiplication on the right) subtracts 2 times the 2nd column from the third
3. Compute LU decomposition of the 3x3 Pascal matrix (in MATLAB, the Pascal matrix is given by pascal(3)
4. Reduce the 4x4 Pascal matrix P to a triangular form such that pi,j=0 for all i,j such that i+j<5. You can use MATLAB and row and/or column elimination operations as you see fit. The answer should look like this:
0 0 0 *
0 0 * *
0 * * *
* * * *

2. Due October 5
1. Compute the Cholesky decomposition of the matrix (in MATLAB notation) A=[1 2 -1 -3; 2 5 -4 -5; -1 -4 9 5; -3 -5 5 15].
2. The following program takes as an input a column vector b and returns a column vector x. Its cost as a function of n (where n is length of the vector b) is a*nc. Find a and c. Can you tell what the program does?
3. Due October 19
1. Compute the condition number of the Hilbert matrix of size 3, 8, and 12 (using the 2-norm).
2. For any matrix A, show that ||ATA||2 =||A||2 and that the condition number of ATA is the square of the condition number of A.
3. Prove or disprove: If A is symmetric positive definite, then A + I is symmetric positive definite.
4. Prove that if ||A||<1, then A-I is nonsingular. The norm can be any operator norm.
4. Due October 31: Write a program that performs the QR decomposition of a tridiagonal matrix and establish that it takes O(n) time (store only the appropriate data in the matrix and in Q).
5. Due December 6: Demonstrate that the QR iteration on a tridiagonal matrix computes its eigenvalues in O(n2) time. Here is the code, just add flop counting.

Midterm: Turn in by November 21

1. Compute the smallest eigenvalue of the 100-by-100 matrix H=1/(i+j). (Hint: This matrix is a Cauchy matrix. The determinant of a Cauchy matrix C(i,j)=1/(xi+yj) is
det C = [\prodi< j(xj-xi)(yj-yi)]/ [\prodi,j(xi+yj)].
Any submatrix of a Cauchy matrix is also Cauchy. You can use Cramer's rule in order to compute accurate formulas for H-1 and then compute its largest eigenvalue. See also the note above on the Cauchy inverse.
2. Compute the smallest eigenvalue of the 200-by-200 Pascal matrix. Details on the Pascal matrix can be obtained here.
Solution: While there are many approaches to solve this problem, one way would be to compute the largest eigenvalue of the inverse. The inverse (which has checkerboard sign pattern) can (once again) be computed without performing any subtractions if one takes the correct approach. Instead of eliminating the matrix in the typical Gaussian elimination fashion, try to eliminate it by using only ADJACENT rows and columns. This process is called Neville elimination. Once you eliminate the first row and first column, you will see that the Schur complement is also a Pascal matrix of one size less. In matrix form this elimination can be written as

L * Pn * LT = P'n-1

where L is lower bidiagonal matrix with ones on the main diagonal and -1 on the first subdiagonal and P'n-1 is an n-by-n matrix with zeros in the first row and column, except for the (1,1) entry (which equals one), and the matrix Pn-1 in the lower right hand corner. You can now observe (no need to prove) that if you have (Pn-1)-1 you can compute (Pn)-1 using the above equality without performing any subtractions.