Homework 4, due in class 2016-02-19

Growth ratio

  • The growth rate

    \[\begin{equation} \rho_n = \frac{\max_{i,j,k} |a^{(k)}_{ij} |}{\max_{i,j} |a_{ij} |}, \end{equation}\]

    measures how the elements grow during the elimination process (as before \(a^{(k)}_{ij}\) \(k=2,\ldots,n\) denote the elements in the \(k\) th step).

    In Gaussian elimination with partial pivoting (GEPP) the multipliers satisfy \(|l_{ik}| \le 1, \, i=k+1:n\). First use this fact to prove the estimate \(|a^{(k+1)}_{ij}| \le 2 \max_{i,j} |a^{(k)}_{ij} |\), then prove that \(\rho_n \le 2^{n-1}\) for GEPP.

  • Implement GEPP in Matlab and create matrices with elements \(a_{ij} = X-0.5\), \(a_{ij} = X\) and \(a_{ij} = 1/X\) where \(X\) is a uniformly distributed variable on \([0,1]\). Experiment with matrices of different size. How does the growth rate scale with the order of the matrix.

Condition number

  • Using Matlab, solve \(Ax=b\) for three right hand sides

    \[\begin{split}A = \left[ \begin{array}{cc} 1 & 3 \\ 3 & 1 \end{array} \right], \ \ b_1 = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right], \ \ b_2 = \left[ \begin{array}{c} 1\\ 1 \end{array} \right], \ \ b_3 = \left[ \begin{array}{c} 1 \\ -1 \end{array} \right].\end{split}\]
  • Experimentally investigate the sensitivity (conditioning) of the computations: Solve the problem with many different perturbed (make sure \(\Delta b\) can have both positive and negative entries) right hand sides, \(b + \Delta b\). The solutions are \(x+\Delta x\). Compute

    \[\kappa_{\rm exp.} = \max_{\Delta b}\frac{ R_{\rm out} }{ R_{\rm in}},\]

    with \(R_{\rm out} = \| \Delta x \|_2 / \| x \|_2\) and \(R_{\rm in} = \| \Delta b \|_2 / \| b \|_2\). Use the largest value of \(\kappa_{\rm exp.}\) as an estimate for the condition number and record the particular \(\Delta b\) that maximizes \(\kappa_{\rm ex.}\). Which right hand side gives the largest \(\kappa_{\rm exp.}\)?

  • How large is the theoretical condition number of the matrix \(A\), \(\kappa(A)\), (help cond)? Explain the relation between \(\kappa(A)\) and \(\kappa_{\rm exp.}\).

  • For \(b_2\) you should get an experimental condition number that is very close to the theoretical value. Show (with pen and paper) that the experimental condition number is maximized if the right hand side is chosen as the eigenvector of \(A\) corresponding to the eigenvalue with largest magnitude and the perturbation is chosen as the eigenvector corresponding to the eigenvalue with smallest magnitude. Is the worst perturbation in the \(b_2\) case close to that eigenvector?

Permutation matrices

  • Give the permutation matrix \(P\) that corresponds to the permutation vector \(p = (n, n − 1,...,1)\). Show that \(P = P^T = P^{−1}\), and that \(AP\) reverses the order of the columns of the matrix \(A \in R^{n\times n}\).
  • Show that if \(L\) is a lower triangular matrix, then \(PLP\) is upper triangular. Use this result to derive the factorization of \(PAP\) as a product of an upper triangular and a lower triangular matrix.

Misc

  • For a non-singular matrix \(A \in R^{n\times n}\) we can always find a \(PA = LU\) factorization. Show that the factorization is unique.