NLA Qualifying Exam Sample Question

Question

I'm curious if anybody has some advice on a problem.

Suppose $A$ is a real symmetric matrix with eigenvalues more or less uniformly distributed over $\left[2,18\right]$ together with an outlier at $\lambda=50$. How many steps of the conjugate gradient iteration must be taken to be sure of reducing the initial error $||{e_{0}}||_{A}$ by a factor of $20^{20}$?

By theorem $38.5$, if all the eigenvalues are in $\left[2,18\right]$, then the A-norms of the error satisfy,$$\frac{||{e_{n}}||_A}{||{e_{0}}||_A}\leq2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{n}.$$ Here $\kappa=\frac{18}{2}=9$ and so, $$\frac{||{e_{n}}||_A}{||{e_{0}}||_A}\leq2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{n}=2\left(\frac{\sqrt{9}-1}{\sqrt{9}+1}\right)^{n}=2\left(\frac{1}{2}\right)^{n}=\left(\frac{1}{2}\right)^{n-1}.$$

Setting $2^{-20}=2^{2-n}$ we find $n=22$ $~~~\blacksquare$

---

---

I asked my prof for input and he responded:

You need to take into account the outlier, as you did for Problem 3.

---

---

My solution for #3:

$A$ is a diagonalizable matrix with one eigenvalue being $-1$, and others residing in the unit disk centered at $2$ in the complex plane. Prove that the solution to $Ax=b$ through GMRES algorithm has error $$||{e_{n}}||\leq K 2^{-n}$$ for some constant K.

Theorem $35.2$ states,

at step $n$ of the GMRES iteration, the residual $r_{n}$ satisfies, $$\frac{||{r_{n}}||}{||{b}||}\leq\inf_{p_{n}\in P_{n}}||{p_{n}(A)}|| \leq\kappa(V) \inf_{p_{n}\in P_{n}}||{p_{n}}||_{\Lambda(A)}\leq\kappa(v)\inf_{p\in P_{n}} \max_{\lambda\in\Lambda(A)}|{p(\lambda)}|.$$ where $\Lambda(A)$ is the set of eigenvalues of $A$, $V$ is a nonsingular matrix of eigenvectors, and $||{p_{n}}||_{\Lambda(A)}$ is defined by $||{p}||_{S}=\sup_{x\in S}|{p(z)}|$.

We can choose a polynomial $$\hat{p}(z)=\left(1+z\right)q(z)=\left( 1+z \right) \left( 1-\frac{z}{2} \right)^{n-1}$$ so that $$\max_{1\leq\lambda\leq 3} |{q(\lambda)}|\leq\left( 1-\frac{1}{2} \right)^{n-1}$$ or equivalently $$\max_{|{\lambda-2}|\leq 1}|{q(\lambda)}|\leq 2^{1-n}.$$

Thus we have $$||{r_n}|| \leq \kappa(V)||{b}||\max_{\lambda\in\Lambda(A)}|{p(\lambda)}| = \kappa(V)||{b}||\max_{|{\lambda-2}|\leq 1}|{\lambda +1}| |{q(\lambda)}| \leq \kappa(V)||{b}||\max_{|{\lambda-2}|\leq 1} |{\lambda +1}| |{q(\lambda)}|$$ $$\leq \kappa(V)||{b}|| |{3 + 1}|2^{1-n}=\kappa(V)||{b}||2^{3-n}$$

Finally, $$||{e_{n}}||=||{A^{-1}r_{n}}||\leq\Big(8~\kappa(V)||{b}|| ||{A^{-1}}||\Big)2^{n},$$ and as $\Big(8~\kappa(V)||{b}|| ||{A^{-1}}||\Big)$ is constant we have our proof. $~~~\blacksquare$

---

---

I'm not sure I see what he's trying to say. Based on his response and the two problems, any thoughts on how he's expecting the first problem to be solved?

Answer 1

The error after $n$ iterations of CGD satisfies $$\dfrac{\|e_n\|_A}{\|e_0\|_A} \le \inf_{\substack{\deg p = n \\ p(0) = 1}}\max_{\lambda \in \Lambda(A)}|p(\lambda)| \le \inf_{\substack{\deg p = n \\ p(0) = 1}}\max_{\lambda \in [2,18] \cup \{50\}}|p(\lambda)|,$$ where I've used the fact that $\Lambda(A) \subseteq [2,18] \cup \{50\}$. Now, we just need to find a polynomial $p(\lambda)$ of small degree such that $p(0) = 1$ and $|p(\lambda)| \le 2^{-20}$ over $\lambda \in [2,18] \cup \{50\}$.

Note that the Chebyshev polynomial of degree $n$ $$T_n(x) = \dfrac{1}{2}\left((x+\sqrt{x^2-1})^n+(x-\sqrt{x^2-1})^n\right)$$ satisfies $|T_n(x)| \le 1$ for $x \in [-1,1]$. Hence, the polynomial $$p_n(\lambda) = \dfrac{T_{n-1}\left(\tfrac{20-2\lambda}{16}\right)}{T_{n-1}\left(\tfrac{20}{16}\right)}\left(1-\dfrac{\lambda}{50}\right)$$ has degree $n$, satisfies $p_n(0) = 1$, $p_n(50) = 0$, and $$|p_n(\lambda)| = \dfrac{\left|T_{n-1}\left(\tfrac{20-2\lambda}{16}\right)\right|}{\left|T_{n-1}\left(\tfrac{20}{16}\right)\right|}\left|1-\dfrac{\lambda}{50}\right| \le \dfrac{\tfrac{48}{50}}{T_{n-1}\left(\tfrac{20}{16}\right)} = \dfrac{\tfrac{48}{50}}{\tfrac{1}{2}\left(2^{n-1}+2^{-(n-1)}\right)} \le \dfrac{96}{25}\cdot 2^{-n}$$ for all $\lambda \in [2,18]$. Hence, $$\dfrac{\|e_n\|_A}{\|e_0\|_A} \le \inf_{\substack{\deg p = n \\ p(0) = 1}}\max_{\lambda \in [2,18] \cup \{50\}}|p(\lambda)| \le \dfrac{96}{25}\cdot 2^{-n}$$ for all integers $n \ge 1$. It's not hard to check that $n = 22$ yields $\dfrac{\|e_n\|_A}{\|e_0\|_A} \le \dfrac{96}{25}\cdot 2^{-22} < 2^{-20}$.

Note that this error bound is roughly a factor of $2$ worse than $2 \cdot 2^{-n}$, which is what we would have had if $\Lambda(A) \subseteq [2,18]$ instead of $\Lambda(A) \subseteq [2,18] \cup \{50\}$. As such, $A$ having one outlier eigenvalue of $50$ increases the number of CGD iterations by one.