**Math 143M**

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

**Class material:**

- Flop counting: test.m and test2.m.
- QR decomposition using Givens rotations givens.m.
- QR Iteration on a general matrix
- QR Iteration on a tridiagonal matrix
- Reduction of a matrix to bidiagonal form: bidiag.m. Uses givenskill.m.
- Cauchy matrix manipulation: Cauchy.m, CauchyInverse.m, CauchyDet.m.
- Derivation of computable formulas for the inverse of a Cauchy matrix.
- Practice problems for the final exam: here and here.

**Homework:**

- Due September 21. Turn in ONLY the 4 matrices that are the answers to the 4 questions below
- Generate a 4x4 matrix which (through multiplication on the left) adds 3 times the 4th row to the 1st
- Generate a 4x4 matrix which (through multiplication on the right) subtracts 2 times the 2nd column from the third
- Compute LU decomposition of the 3x3 Pascal matrix (in MATLAB, the Pascal matrix is given by pascal(3)
- Reduce the 4x4 Pascal matrix P to a triangular form such that p
_{i,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 * * *

* * * * - Due October 5
- 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].
- 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*n
^{c}. Find a and c. Can you tell what the program does? - Due October 19
- Compute the condition number of the Hilbert matrix of size 3, 8, and 12 (using the 2-norm).
- For any matrix A, show that ||A
^{T}A||_{2}=||A||^{2}and that the condition number of A^{T}A is the square of the condition number of A. - Prove or disprove: If A is symmetric positive definite, then A + I is symmetric positive definite.
- Prove that if ||A||<1, then A-I is nonsingular. The norm can be any
*operator*norm. - 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).
- Due December 6: Demonstrate that the QR iteration on a tridiagonal matrix computes its eigenvalues in O(n
^{2}) time. Here is the code, just add flop counting.

**Midterm: Turn in by November 21**

- 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/(x
_{i}+y_{j}) is

det C = [\prod_{i< j}(x_{j}-x_{i})(y_{j}-y_{i})]/ [\prod_{i,j}(x_{i}+y_{j})].

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. - 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 * P_{n}* L^{T}= 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 P_{n-1}in the lower right hand corner. You can now observe (no need to prove) that if you have (P_{n-1})^{-1}you can compute (P_{n})^{-1}using the above equality without performing any subtractions.