Homework

1. Derive GMRES and CG using the general projection method scheme

$$ \begin{array}{l} \text{Choose } V \text{ and } W, \text{ basis for } \mathbf{H} \text{ and } \mathbf L, \text{respectively} \newline \text{Compute the new approximation as } x_{\mathrm{new}} = x_0 + V(W^*AV)^{-1}W^*r_0 \end{array} $$

$r_0=b-Ax_0$, and compare them with the algorithms we have discussed during the lectures

2. Let ${x_m}$ be the sequence generated by GMRES for a nonsingular matrix $A$. Show that if $XAX^{-1}=J$ is the Jordan canonical form of $A$, then for any $m\geq 1$ it holds

$$ \|b-Ax_{m}\|_2 \leq \kappa_2(X) \min_{p\in P_m^1} \max_{\lambda_i\in \sigma(A)}\|p(J_{\lambda_i})\|_2 \|b-Ax_0\|_2 $$ where $P_m^1$ is the set of polynomials $p$ of degree $m$ such that $p(0)=1$.

3. Let $C_m$ be the $m$-th Chebyshev polynomial of the first kind. Use the fact that $$ \left\|\frac{C_m(x)}{2^{m-1}}\right\|_{\infty,[-1,1]} \leq \|p\|_{\infty,[-1,1]} $$ for any monic polynomial $p$ of degree $m$, to show that $$ \left\|\frac{C_m(x)}{C_m(a)} \right\|_{\infty,[-1,1]} \leq \|p\|_{\infty,[-1,1]} $$ for all polynomials $p$ of degree $m$ such that $p(a)=1$.