GMRES least-squares problem

GMRES problem: ${\min }_y\Vert b-A{Q}_{k}y{\Vert }_2$

This is a least-squares problem but the solution is simple.

Recall that from Arnoldi:

$$A{Q}_k=Q_{k+1}{Q}_{k+1}^{T}A{Q}_k$$

These are the steps to solve the least-squares problem:

$$\begin{array}{rl}\Vert b-A{Q}_{k}y{\Vert }_2& =\Vert Q_{k+1}{Q}_{k+1}^{T}b-Q_{k+1}{Q}_{k+1}^{T}A{Q}_{k}y{\Vert }_2\\ & =\Vert Q_{k+1}^{T}b-Q_{k+1}^{T}A{Q}_{k}y{\Vert }_2\end{array}$$

From the definition of the Krylov subspace and the fact that $Q_{k+1}$ is orthogonal, we get:

$$Q_{k+1}^{T}b=\Vert b{\Vert }_2{e}_1.$$

We are already familiar with this matrix

$$Q_{k+1}^{T}A{Q}_k\stackrel{def}{=}{\underline{H}}_k$$

This is the top left block in the upper Hessenberg form $H=Q^{T}AQ.$ Its size of $(k+1)\times k$.

The final least-squares problem we need to solve is

$$\underset{y}{\min }\Vert \Vert b{\Vert }_2{e}_1-{\underline{H}}_{k}y{\Vert }_2$$