Posted: 09/27/21

First draft due: 10/04/21, 11:55PM, Final draft due: 10/11/21

Note: This will be the last homework assignment with the two-stage submission process (first draft/comments/final draft). Subsequent homework assignments will use a single-stage submission.

Various

1Track 1

1. Consider $𝑨=\left[a_{ij}\right]\in {ℝ}^{m\times m}$ with elements

   ${\displaystyle a_{ii}=1,a_{ij}=-1\mathrm{for}i>j,a_{ij}=0\mathrm{for}j>i\mathrm{and}j\ne m,a_{im}=1\mathrm{for}\mathrm{all}i.}$

   1. Implement Gaussian elimination with partial pivoting (searching for maximum element in current column).

   2. Verify your implementation by generating random $𝒙\in {ℝ}^m$ for $m=10k$, $k=1,2,\dots ,6$, computing $𝒃=𝑨𝒙$, applying your implementation to solve the system and obtain $\stackrel{\sim }{𝒙}$. Compute $||𝒙-\stackrel{\sim }{𝒙}||$ in 1,2, inf-norms.

   3. Compare the above errors with built-in solver $\stackrel{\sim }{𝒙}=𝑨\backslash 𝒃$.

   4. Repeat (b) and (c) with

      ${\displaystyle a_{ii}=1+4ϵr}$

      with $ϵ$ machine epsilon, and $r$ a uniform random number in the interval $(0,1).$

2. With $𝑨$ from problem 1, construct the symmetric matrix

   ${\displaystyle 𝑩=\frac{1}{2}(𝑨+{𝑨}^T)+m𝑰.}$

   1. Implement the Cholesky algorithm to solve $𝑩𝒚=𝒄$.

   2. Carry out steps from Problem 1.b. How do the errors $||𝒚-\stackrel{\sim }{𝒚}||$ compare with those from 1.b?

2Track 2

1. For $𝑨\in {ℂ}^{m\times m},𝒙\in {ℝ}^m$, find the relative condition number of the following mathematical problems:

   1. $𝒇:{ℂ}^m\to {ℂ}^m$, $𝒇\left(𝒙\right)=𝑨𝒙$

   2. $𝒈:{ℂ}^m\to {ℂ}^m$, $𝒈\left(𝒃\right)={𝑨}^{-1}𝒃$

   3. $𝒉:{ℂ}^{m\times m}\to {ℂ}^m$, $𝒉\left(𝑨\right)={𝑨}^{-1}𝒃$

2. For $𝑨,𝑩\in {ℂ}^{m\times m}$, suppose an efficient solver for $𝑨𝒙=𝒃$ is available. Answer the following questions, with a view to solving $𝑩𝒚=𝒄$, with $𝑩$ assumed to be a good approximation of $𝑨$.

   1. For $𝒖,𝒗\in {ℂ}^m$, $𝑨,𝑨+𝒖{𝒗}^{\ast }$ of full rank, $$prove the Sherman-Morrison formula

      ${\displaystyle {(𝑨+𝒖{𝒗}^{\ast })}^{-1}={𝑨}^{-1}-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }{𝑨}^{-1}}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}.}$

      Write a pseudo-code algorithm on how to use the Sherman-Morrison formula to solve $𝑩𝒚=𝒄$, with $𝑩=𝑨+𝒖{𝒗}^{\ast }$.

   2. (Extra credit: 1 course point). Prove the generalization to rank-$k$ updates (Sherman-Morrison-Woodbury formula), $𝑼,𝑽\in {ℂ}^{m\times k}$

      ${\displaystyle {(𝑨+𝑼{𝑽}^{\ast })}^{-1}={𝑨}^{-1}-{𝑨}^{-1}𝑼{(𝑰+{𝑽}^{\ast }{𝑨}^{-1}𝑼)}^{-1}{𝑽}^{\ast }{𝑨}^{-1}.}$

      Again, write a pseudo-code algorithm on using the above to solve $𝑩𝒚=𝒄$, with $𝑩=𝑨+𝑼{𝑽}^{\ast }$.

3. Consider a decomposition of $𝑨\in {ℂ}^{m\times m}$ into blocks of size $k\times k$

   ${\displaystyle 𝑨=\left[\begin{array}{llll}{𝑨}_{11}& {𝑨}_{12}& \dots & {𝑨}_{1n}\\ {𝑨}_{21}& {𝑨}_{22}& \dots & {𝑨}_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ {𝑨}_{n1}& {𝑨}_{n2}& & {𝑨}_{nn}\end{array}\right].}$

   1. Write pseudo-code for the block form of Gaussian elimination. Carefully consider conditions to be checked at each step.

   2. Modify the above algorithm for $𝑨$ block tridiagonal.

   Solve Exercise 12.3, p. 96 of Trefethen & Bau, Numerical Linear Algebra.