Homework 3

Due: Thursday 3/15

---

1. This problem concerns forward and backward solvers.

   1. Recall that given an $n\times n$ lower triangular matrix $\mathbf{A}$ with non-zero diagonal and an $n$ dimensional vector $\mathbf{b}$, that we can solve the system

      \[ \mathbf{A}\mathbf{x} = \mathbf{b} \]

      using forward substitution. This takes the exceptionally simple form in MATLAB:

      n = length(b);
      x = zeros(n,1);
      for i=1:n
          x(i) = (b(i) - A(i,1:(i-1))*x(1:(i-1)))/A(i,i);
      end

      When $\mathbf{A}$ is instead upper triangular this method is called backward substitution. Modify the above MATLAB code to instead use backward substitution for a given upper triangular matrix $\mathbf{A}$ and vector $\mathbf{b}$. Use this algorithm to solve the problem

      \[ \mathbf{A}\mathbf{x} = \mathbf{b} \]

      for the following $\mathbf{A}$ and $\mathbf{b}$:

      1. \[ \mathbf{A} = \begin{bmatrix} -4 & 5 & 2 & -7 & 8\\ 0 & 10 & 6 & -5 & 0\\ 0 & 0 & -2 & -1 & 9\\ 0 & 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 & 10 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix}-9\\ -5\\ -6\\ 4\\ 7\end{bmatrix} \]
      2. \[ \mathbf{A} = \begin{bmatrix} 9 & 4 & 9 & -1 & 7 & -4 & 3\\ 0 & 1 & -6 & 3 & -5 & -8 & 1\\ 0 & 0 & 4 & 6 & 2 & 9 & 5\\ 0 & 0 & 0 & -3 & 2 & 3 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 10\\ 0 & 0 & 0 & 0 & 0 & 3 & -6\\ 0 & 0 & 0 & 0 & 0 & 0 & -8 \end{bmatrix},\quad \mathbf{b} = \begin{bmatrix} -8\\ -9\\ -2\\ -1\\ -3\\ 6\\ 3 \end{bmatrix} \]

   2. Show that the number of floating point operations for either backward or forward substitution is exactly

      \[ \text{flops}(n) = n^2, \]

      where $n$ is the size of the matrix.

2. We've seen in class that the most basic $LU$ factorization algorithm may fail for some matrices because of inconvenient zeros that arise as the algorithm proceeds. We showed how this could be avoided by `pivoting' or swapping rows to allow the algorithm to continue.

   Write a code in MATLAB that generates an $LU$ factorization with pivoting for a square matrix $\mathbf{A}$. Your pivoting strategy should be to swap the offending row with one that has the largest number (in absolute value) for that column. Your code must produce three quantities: the lower triangular $\mathbf{L}$ matrix with ones on the diagonal, the upper triangular $\mathbf{U}$ matrix, and a vector $p$ which is a permutation of the vector $\mathbf{p} = (1, 2, 3,\ldots n)^\top$ that keeps track of the pivots. For example if $n=3$, then $\mathbf{p} = (1 , 3, 2)$ would mean that the algorithm involved a pivot that swapped rows $2$ and $3$. For your convenience, I have included the MATLAB code lu_fac.m for $LU$ factorization without pivoting.

   Apply your new pivoting algorithm to the following matrices:

   1. \[ \mathbf{A} = \begin{bmatrix} -1 & 3 & -6 & 4 & 7\\ -2 & 6 & 1 & 7 & 5\\ 4 & -3 & -1 & -5 & -1\\ -2 & 2 & -3 & 4 & 3\\ 0 & 7 & -4 & -5 & 0 \end{bmatrix} \]
   2. \[ \mathbf{A} = \begin{bmatrix} 0 & -1 & -3 & 6 & 0\\ -2 & 2 & 1 & 6 & 1\\ 4 & 2 & 7 & -2 & 3\\ 6 & -6 & -1 & -4 & -6\\ 4 & 0 & -7 & 4 & 6 \end{bmatrix} \]

3. A permutation matrix $\mathbf{P}$ is a matrix which, when applied to a vector, permutes it's entries. It is defined as a matrix of ones and zeros where each row and column can only have exactly one non-zero entry. It can be viewed as an identity matrix whose rows have been permuted by the specific permutation operation it encodes. For instance the matrix

   \[ \mathbf{P} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{bmatrix} \]

   will swap the second and third entries of any vector it acts on.

   1. Show that for any permutation matrix $\mathbf{P}$ the inverse is operation is given by the transpose matrix. Namely,

      \[ \mathbf{P}^{-1} = \mathbf{P}^{\top}. \]

   2. Write a MATLAB code which takes a permuted vector the values $1,2,\ldots n$ and computes the permutation matrix associated with it. For instance we have

      \[ \begin{bmatrix}2 \\ 1 \\ 3\end{bmatrix} \Rightarrow \begin{bmatrix}0& 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{bmatrix}. \] Use this code to generate the permutation matrices for the following permuted vectors,
      1. \[\begin{bmatrix}3 & 7 & 4 & 8 & 5 & 1 & 10 & 6 & 9 & 2 \end{bmatrix}^\top\]
      2. \[\begin{bmatrix}4 & 2 & 1 & 9 & 3 & 5 & 10 & 8 & 7 & 6 \end{bmatrix}^\top\]
      3. \[\begin{bmatrix}10 & 7 & 4 & 1 & 9 & 6 & 3 & 8 & 5 & 2 \end{bmatrix}^\top\]
4. Let $\mathbf{A}$ be a symmetric matrix. Show that if $\mathbf{A}$ is positive definite, then the largest absolute value in the matrix can only appear on the diagonal. (Hint: Use the fact that $\mathbf{x}^\top\mathbf{A}\mathbf{x} > 0$ for $\mathbf{x} = \mathbf{e}_i \pm \mathbf{e}_{j}$ for $i\neq j$.)

5. For a given symmetric positive definite matrix $\mathbf{A}$, the Cholesky factorization $\mathbf{A} = \mathbf{U}^\top\mathbf{U}$ can be computed in MATLAB using following code:

   U = triu(A);    # Throw away lower triangular piece
   n = length(A);
   for k=1:n
       U(k,k:n) = U(k,k:n)./sqrt(U(k,k));   # Divide top row by sqrt(a_ii)
       for j= (k+1):n                       # Transform submatrix
           for i = (k+1):j
               U(i,j) = U(i,j) - U(k,i)*U(k,j);
           end
       end
   end

   Show that the number of floating point operations in this algorithm for an $n\times n$ matrix is given by

   \[ \text{flops}(n) = \frac{1}{3}n^3 + \mathcal{O}(n^2). \]

6. 1. Find the condition number $\kappa_\infty(\mathbf{A})$ of the matrix

      \[ \mathbf{A} =\begin{bmatrix} 1 & -2\\ -2 & \alpha \end{bmatrix} \]

      for $\alpha \neq 4$. What happens when $\alpha = 4$?

   2. Let $\mathbf{D}$ be the $n\times n$ diagonal matrix with $d_1, d_2, \ldots d_n$ on the diagonal. Show that the condition number is given by

      \[ \kappa_\infty(\mathbf{D}) = \frac{ \max_i |d_i|}{\min_i |d_i|} \]

   3. Let $\mathbf{P}$ be a permutation matrix. What are the condition numbers $\kappa_1(\mathbf{P})$ and $\kappa_\infty(\mathbf{P})$?