GMRES algorithm

These are the computational steps in this algorithm.

1. Arnoldi step: we compute column $k$ of ${\underline{H}}_k$ and column $k+1$ of $Q_{k+1}$.
2. We update the QR decomposition of ${\underline{H}}_k$ with the new column $k$. This requires a new Givens transformation:

$$G_k^T\cdots G_1^T{\underline{H}}_k=\left(\begin{array}{c}{R}_k\\ 0\end{array}\right)$$

The least-squares problem becomes

$${\Vert G_k^T\cdots G_1^T({\beta }_0{e}_1)-\left(\begin{array}{c}{R}_k\\ 0\end{array}\right)y^{(k)}\Vert }_2$$

Let’s compute

$${\beta }_0{G}_k^T\cdots G_1^T{e}_1=\left(\begin{array}{c}{p}_k\\ {\rho }_k\end{array}\right)$$

Then we have to solve $R_k{y}^{(k)}=p_k.$ The norm of the residual is

$$\Vert {\beta }_0{e}_1-{\underline{H}}_k{y}^{(k)}{\Vert }_2={\rho }_k.$$

3. The GMRES approximate solution is finally expressed as

$$x^{(k)}=Q_k{y}_k$$