= Solution
Write $x=Q_ky$ and $\beta=\|b\|_2$. The <Arnoldi decomposition> and $b=\beta Q_{k+1}e_1$ give
$$
Ax-b=Q_{k+1}(\widetilde H_ky-\beta e_1).
$$
Because $Q_{k+1}$ has <orthonormal> columns, it preserves the <Euclidean norm>. The <generalized minimal residual method> therefore reduces to the small <linear least-squares problem>
$$
\boxed{y_k=\underset{y\in\mathbb R^k}{\operatorname{argmin}}
\|\widetilde H_ky-\beta e_1\|_2,\qquad x_k=Q_ky_k}.
$$
Use <Givens rotations> on the <upper Hessenberg matrix> to obtain a <QR decomposition>
$$
Z^T\widetilde H_k=\begin{pmatrix}R_k\\0\end{pmatrix},\qquad
g=Z^T(\beta e_1),
$$
where $Z$ is an <orthogonal matrix> and $R_k$ is an <upper triangular matrix>. Then solve $R_ky_k=g_{1:k}$ by <backward substitution in a triangular system> and form $Q_ky_k$. The resulting minimum <linear-system residual> has <Euclidean norm> $|g_{k+1}|$.
The small problem has a unique answer: if $\widetilde H_ky=0$, the <Arnoldi decomposition> gives $AQ_ky=0$. The <invertible matrix> $A$ implies $Q_ky=0$, and the <orthonormality> of $Q_k$ then gives $y=0$. Thus $\widetilde H_k$ has <full column rank> and $R_k$ is nonsingular.
Back to article page
