Numerical Analysis - August 2024

1.

(15 points) Let $A=\left[\begin{array}{ccc}4& 1& 0\\ 1& 2& -1\\ 0& -1& 3\end{array}\right]$

• Without computing the eigenvalues, explain why the eigenvalues are real.
• Use Gershgorin’s disk theorem to show that all eigenvalues are nonnegative.

2.

(15 points) Let $\parallel .\parallel$ be an induced matrix norm. If $A$ is an $n\times n$ matrix with $\parallel A\parallel <1$, show that $I+A$ is nonsingular, i.e., it has a matrix inverse. In addition, show that

3.

(15 points) If $A\in {\mathbb{R}}^{n\times n}$ is symmetric and positive definite, show that

holds for all $1\le i,j\le n$.

4.

(10 points) Let $P\in {\mathbb{C}}^{m\times m}$ be a nonzero projector. Show that ${\parallel P\parallel }_2\ge 1$.

5.

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

6.

(15 points) Consider the linear system

1. Find the exact solution.
2. Find the solution using Gaussian Elimination without pivoting.
3. Find the solution using Gaussian Elimination with partial pivoting.

7.

(15 points) The following two questions involve the conjugate gradient iteration and the Arnoldi iteration.

1. Consider the conjugate gradient algorithm for solving $Ax=b$ for a symmetric positive definite $A\in {\mathbb{R}}^{m\times m}$. What property(ies) does the nth iterate of the algorithm satisfy?
2. Consider the Arnoldi iteration. What property(ies) does the nth iterate of the algorithm (i.e., the matrix $Q_n$) satisfy? How can the Arnoldi iteration be used as an eigenvalue approximation algorithm?