Homework 3

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

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?
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$ ?
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$ ?
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?
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$ .