$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator*{\minimize}{minimize} \DeclareMathOperator*{\maximize}{maximize} \DeclareMathOperator{\subjectto}{subject to} \newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\MIN}[2]{\begin{array}{ll} \minimize_{#1} & {#2} \end{array}} \newcommand{\MINone}[3]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\MINthree}[5]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \\ & {#4} \\ & {#5} \end{array}} \newcommand{\MAX}[2]{\begin{array}{ll} \maximize_{#1} & {#2} \end{array}} \newcommand{\MAXone}[3]{\begin{array}{ll} \maximize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mSigma}{\ensuremath{\mat{\Sigma}}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}} \newcommand{\vlambda}{\vecalt{\lambda}}$

# Homework 10

Please answer the following questions in complete sentences in a typed, clearly prepared manuscript. This homework is due by Monday, November 20th, 2017, 4:30am. However, everyone is given an automatic, full-points extension until Wednesday, November 22nd, 2017 at 4pm. This is designed to give you maximum flexibility in order to plan your time. We highly suggest sticking to the original due date, but there is absolutely no penalty for taking more time.

## Problem 0: Homework checklist

• Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

• Make sure you have included your source-code and prepared your solution according to the most recent Piazza note on homework submissions.

## Problem 1: Arnoldi and the Krylov Matrix

Denote the $k$th Krylov subspace $\mathbb{K}_k(\mA,\vb) = \text{span}\{ \vb, \mA \vb, \ldots, \mA^{k-1} \vb \}.$ In $k$ steps of the Arnoldi process we consruct an orthogonal matrix $\mQ = [ \vq_1, \ldots, \vq_k ]$ that is an orthonormal basis for $\mathbb{K}_k$. Define the $k$th Krylov matrix as $\mK_k = \bmat{ \vb & \mA \vb & \cdots & \mA^{k-1} \vb }$. Suppose we compute the QR factorization of $\mK_k$. Show that, up to signs, the matrix $\mQ$ from Arnoldi and the orthogonal matrix in the QR factorization are the same.

## Problem 2: GMRES and polynomials

It turns out that the GMRES solution to $\mA \vx = \vb$ in step $k$, $\vx^{(k)}$, can be viewed as constructing a degree $k$ polynomial, q(x), such that $||q(\mA)\vb||_2$ is minimized. Think of it this way: since $\vx^{(k)}$ is in $\mathbb{K}_k(\mA,\vb) = \text{span}\{ \vb, \mA \vb, \ldots, \mA^{k-1} \vb \}.$, we know $\vx^{(k)} = c_0 \vb + c_1 \mA^1 \vb + \ldots + c_{k-1} \mA^{k-1} \vb$ for some scalars $c_j$. If we define the polynomial $q(x) = c_0 + c_1 \vx^1 + \ldots + c_{k-1} \vx^{k-1}$, then we can express $\vx^{(k)} = c_0 \mI \vb + c_1 \mA^1 \vb + \ldots + \mA^{k-1} \vb = q(\mA)\vb$.

Then since GMRES constructed $\vx^{(k)}$ to minimize $||\vb - \mA \vx^{(k)}||_2$, we know that the polynomial $q(x)$ is the degree $k-1$ polynomial that minimizes $||\vb - \mA q(A) b||_2$, since $\vb - \mA \vx^{(k)} = \vb - \mA q(A) \vb$.

1. Suppose GMRES converged to the exact solution $\vx$ to the system $\mA \vx = \vb$ in $t$ iterations, i.e. it constructed $\vx^{(t)}$ in $\mathbb{K}_t(\mA,\vb)$ such that $\vx^{(t)}$ is the exact solution to $\mA \vx = \vb$. Show that there exists a degree $t$ polynomial $p(x) = -1 + \sum_{j=1}^{t} p_j x^j$ such that $p(A) \vb = 0$

2. Let $\mA = \mI + \ve \ve^T$ be a square matrix (where $\ve$ is the column vector of all 1s of appropriate dimensions). Suppose we use GMRES to solve the system $\mA \vx = \vb$. In exact arithmetic, how many steps will GMRES take to converge to the exact solution? (Hint: figure out how to use part 1). Be sure to explain \textit{how you determine what the answer is. Note, your result should be self contained and not utilize the theory discussed in class -- this is good practice for the final; if you do use a theorem to justify your answer, you may lose a few points.}

3. Write the solution $\vx$ from part 2 in terms of $\mA$ and $\vb$. Explain how you determine it.

## Problem 3: Krylov-ish methods

Read about the steepest descent method in Golub and van Loan, section 11.3.2. The consider algorithm 11.3.1. Notice that the algorithm computes the residual at each iteration, except they call it $\vg$ instead of $\vr$: If $\vg^{\text{old}}$ was the residual before and $\vg$ is the next residual computed, show that $\vg^{\text{old}}$ and $\vg$ are orthogonal.