Homework 3

Problem Set 3. Due Wed, Oct 11th at the beginning of class.

  1. Show how to compute the inverse of a matrix efficiently using Gaussian elimination. Show this for the matrix  \begin{bmatrix} 1 & -1 & 2 \\ 3 & 1 & 0 \\ 2 & 1 & -1 \end{bmatrix} . What is the arithmetic complexity of inverting an n \times n integer matrix? What is the bit complexity if each entry of the matrix uses at most b bits?
  2. Suppose that A is a symmetric matrix with eigenvalues strictly between 0 and 1. Show that (I-A)^{-1} = I+\sum_{i=1}^\infty A^i.  What is the error if we truncate after k terms, i.e., give a bound on \|(I-A)^{-1} - B\| where B = I+\sum_{i=1}^k A^i?
  3. To solve Ax=b, consider the iteration: x^{i+1}= A^Tb + (I-A^TA)x^i, x^0 = 0. What is the rate of convergence, provided A has singular values 0<\lambda_n \le \lambda_{n-1} \le \ldots \le \lambda_1 < 1?
  4. Consider the continued fraction expansion of a real number r = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \ldots}}. Let the successive approximations be p_k/q_k. Show that p_k, q_k satisfy the following recurrences p_{k+1} = a_kp_k + p_{k-1}, q_{k+1}= a_k q_k + q_{k-1}. What are the base values?
  5. Regression. For an m \times n matrix A, what is the optimal solution to min_x \|Ax-b\|? Show that it is unique for any nonzero A.