Numerical Analysis - May 2021

1.

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

2.

(10p) Let $A\in {ℂ}^{m\times m}$ and $A=A^{*}$.

1. Prove that all eigenvalues of $A$ are real.
2. Let $x$ and $y$ be eigenvectors of $A$ corresponding to eigenvalues $\lambda$ and $\mu$ respectively. Give a sufficient condition on $\lambda$ and $\mu$ for $x$ and $y$ to be orthogonal.

3.

(10p) Prove that the determinant of a Householder reflector is negative one.

4.

(15p) Fix $0<\epsilon <1$ and suppose that $A\in {ℝ}^{m\times m}$ is symmetric and nonsingular. Show that if ${\parallel A-I\parallel }_F\ge \epsilon$, then ${\parallel A^{-1}-I\parallel }_F\ge \frac{\epsilon }{2}$, where ${\parallel ·\parallel }_F$ denotes the Frobenius norm.

5.

(15p) Determine the rate of convergence of the Rayleigh quotient $r\left(v_k\right)={v_k}^{T}A{v}_k$ to an eigenvalue of $A\in {ℝ}^{n\times n},A=A^T$, with vectors $v_k\in {ℝ}^n$ given by the normalized power method $v_{k+1}=\frac{A{v}_k}{\parallel A{v}_k\parallel }$.

6.

Suppose $Ax=b$ and $(A+\delta A)\mathrm{x̂}=b+\delta b$ and assume that

1. (10p) Show that $$\frac{\parallel \delta x\parallel }{\parallel x\parallel }\le \frac{\kappa \left(A\right)}{1-\kappa \left(A\right)\frac{\parallel \delta A\parallel }{\parallel A\parallel }}(\frac{\parallel \delta A\parallel }{\parallel A\parallel }+\frac{\parallel \delta b\parallel }{\parallel b\parallel })$$

   (1)

   where $\mathrm{x̂}=x+\delta x$ and $\kappa \left(A\right)=\parallel A\parallel \parallel A^{-1}\parallel$.

2. (10p) Let $\delta A=0$ and $$A=\left(\begin{array}{cc}0& 2\\ 1& 0\end{array}\right)$$

   Find vectors $\delta b$ and $b$ such that the bound (1) becomes an equality.

7.

(20p) Let $A\in {ℝ}^{n\times n}$ be symmetric and positive definite (spd), and consider the following iteration.

Here $L_k$ is lower triangular with positive diagonal elements.

1. Show that $A_k$ is similar to $A$, and that $A_k$ is spd (the iteration is therefore well-defined).

   Now consider the special case of a $2\times 2$ spd matrix,

   $$A=\left(\begin{array}{cc}a& b\\ b& c\end{array}\right),a\ge c$$
2. For this matrix, perform one step of the algorithm and write down $A_1$.
3. Use the result from (b) to argue that $A_k$ converges to $\mathrm{diag}({\lambda }_1,{\lambda }_2)$, where the eigenvalues of $A$ are ordered as ${\lambda }_1\ge {\lambda }_2>0$.