Numerical Analysis - May 2024

1.

(15 points) Let $A,B\in {ℂ}^{m\times m}$ be arbitrary matrices. Show that

where ${\parallel .\parallel }_2$ and ${\parallel .\parallel }_F$ denote the 2-norm and Frobenius norm, respectively.

2.

(15 points) Let $A\in {ℂ}^{m\times n}$ with $m\ge n$. Show that $A^{*}A$ is nonsingular if and only if $A$ has full rank.

3.

(15 points) Answer the following questions about properties of matrices.

• Let $A,B\in {ℂ}^{n\times n}$, with $A$ nonsingular and $\parallel A^{-1}\parallel \parallel B\parallel =q\<1$. Show that $A+B$ is nonsingular, i.e., invertible.
• Let $A\in {ℂ}^{n\times n}$ be skew-Hermitian, i.e., $A^{*}=-A$. Show that the matrix $I+A$ is nonsingular and that ${(I+A)}^{-1}(I-A)$ is unitary.

4.

(15 points) Let $P\in {ℂ}^{m\times m}$ be a projector. Show $P$ is orthogonal if and only if $P=P^{*}$.

5.

(10 points) Suppose $A$ is an invertible $202\times 202$ matrix with ${\parallel A\parallel }_2=100$ and ${\parallel A\parallel }_F=101$. Give the sharpest possible lower bound on the 2-norm condition number $\kappa \left(A\right)$.

6.

(15 points) Prove Gerschgorin’s disk theorem: Let $A\in {ℂ}^{m\times m}$ with entries $\left\{a_{ij}\right\}$ and let $r_i=\sum _{j\ne i}\left|a_{ij}\right|$. Let $D_i$ be the closed disk in $ℂ$ with center $a_{ii}$ and radius $r_i$. If $\lambda$ is an eigenvalue of $A$, then $\lambda \in \underset{i}{\cup }{D}_i$; in other words, $\lambda$ lies within at least one of the disks $D_i$.

7.

(15 points) Suppose the Arnoldi iteration is executed for a particular $m\times m$ matrix $A$ and vector $b$ until at some step $n$, an entry $h_{n+1,n}=0$ is encountered.

• Show how the equality $A{Q}_n=Q_{n+1}{\mathrm{H̃}}_n$ can be simplified in this case. Recall that $Q_n$ is an $m\times n$ matrix whose columns are the first $n$ columns of $Q$ in $AQ=QH$, where $H$ is a Hessenberg matrix. In addition, ${\mathrm{H̃}}_n$ is the $(n+1)\times n$ upper-left section of $H$.
• Show that $K_n$ is an invariant subspace of $A$, i.e. $A{K}_n\subseteq K_n$, where $K_n$ is the $n^{\mathrm{th}}$ Krylov subspace, which is the span of $\{b,Ab,\dots A^{n-1}b\}$?