A nonbreakdown LSQR iterate minimizes residual on its Krylov space

If $k=0$, [F2] gives ${\mathcal{K}}_0(A^{T}A,A^T{r}_0)=\{0\}$, so the feasible set is $\{x_0\}$ and $x_0$ is its residual minimizer. Henceforth assume $k\ge 1$, so the stated nonbreakdown run initializes $u_1,v_1$. The initial vector $u_1=r_0\mathrm{/}\mathrm{\parallel }{r}_0{\mathrm{\parallel }}_2$ is unit. Suppose $u_1,\dots ,u_j$ and $v_1,\dots ,v_j$ are orthonormal and satisfy the earlier Golub–Kahan recurrences. For $i<j$, $⟨A{v}_j,u_i⟩=⟨v_j,A^T{u}_i⟩=0$ by [F5]–[F7], because $A^T{u}_i$ lies in $\mathrm{span}\{v_{i-1},v_i\}$; for $i=j$, $⟨A{v}_j,u_j⟩={\alpha }_j$ by the definition of ${\alpha }_j$. Therefore $A{v}_j-{\alpha }_j{u}_j$ is orthogonal to $u_1,\dots ,u_j$, and division by the nonzero ${\beta }_{j+1}$ gives a unit $u_{j+1}$ orthogonal to them. For $i<j$, $⟨A^T{u}_{j+1},v_i⟩=⟨u_{j+1},A{v}_i⟩=0$ by [F5]–[F7], since $A{v}_i={\alpha }_i{u}_i+{\beta }_{i+1}{u}_{i+1}$ lies in $\mathrm{span}\{u_1,\dots ,u_j\}$; for $i=j$ the inner product equals ${\beta }_{j+1}$. Thus $A^T{u}_{j+1}-{\beta }_{j+1}{v}_j$ is orthogonal to $v_1,\dots ,v_j$, and division by the nonzero ${\alpha }_{j+1}$ gives a unit $v_{j+1}$ orthogonal to them. Induction proves both orthonormality relations through step $k$.

The column recurrences in [F1] assemble as $A{V}_k=U_{k+1}{B}_k$. Also $r_0={\beta }_1{u}_1={\beta }_1{U}_{k+1}{e}_1$. Hence for every $z\in {\mathbb{R}}^k$, $b-A(x_0+V_{k}z)=r_0-A{V}_{k}z=U_{k+1}({\beta }_1{e}_1-B_{k}z)\mathrm{.}$ Orthonormality from [step 1.1] and the Euclidean norm definition [F5] imply $\mathrm{\parallel }b-A(x_0+V_{k}z){\mathrm{\parallel }}_2=\mathrm{\parallel }{\beta }_1{e}_1-B_{k}z{\mathrm{\parallel }}_2$.

Each Givens rotation in [F1] is orthogonal because $(a\mathrm{/}\rho {)}^2+(b\mathrm{/}\rho {)}^2=1$ when $\rho =(a^2+b^2{)}^{1\mathrm{/}2}>0$. Number the rows and columns here from one. Since $B_k$ is lower-bidiagonal, rotation $i$ annihilates its entry in row $i+1$, column $i$, while preserving the zeros in earlier columns; induction gives $Q{B}_k=\left(\genfrac{}{}{0px}{}{R_k}{0}\right)$ for the product $Q$ of all $k$ rotations, with $R_k$ upper triangular. Its diagonal entries are the nonzero rotation pivots $\rho$, so back substitution returns $z_k$ with $R_k{z}_k=d_k$. Write $Q{\beta }_1{e}_1=\left(\genfrac{}{}{0px}{}{d_k}{{\eta }_k}\right)$. Orthogonality gives, for every $z$, $\mathrm{\parallel }{\beta }_1{e}_1-B_{k}z{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{d}_k-R_{k}z{\mathrm{\parallel }}_2^2+\mathrm{\mid }{\eta }_k{\mathrm{\mid }}^2$. The computed $z_k$ attains the lower bound $\mathrm{\mid }{\eta }_k{\mathrm{\mid }}^2$, proving its minimizing property directly from the instructions; it is unique by [F4], since the nonzero diagonal of $B_k$ makes it full column rank. Thus $x_k=x_0+V_k{z}_k$ minimizes the true residual over $x_0+\mathrm{span}\{v_1,\dots ,v_k\}$ by [step 2.1].

The recurrence gives, for $j\ge 1$, $A^{T}A{v}_j={\alpha }_j{\beta }_j{v}_{j-1}+({\alpha }_j^2+{\beta }_{j+1}^2)v_j+{\alpha }_{j+1}{\beta }_{j+1}{v}_{j+1},$ with the first term omitted at $j=1$. Every coefficient ${\alpha }_{j+1}{\beta }_{j+1}$ is nonzero in a nonbreakdown run, so induction shows $\mathrm{span}\{v_1,\dots ,v_k\}=\mathrm{span}\{v_1,A^{T}A{v}_1,\dots ,(A^{T}A{)}^{k-1}{v}_1\}$. Since $v_1=A^T{r}_0\mathrm{/}({\beta }_1{\alpha }_1)$, [F2]–[F3] identify this span with ${\mathcal{K}}_k(A^{T}A,A^T{r}_0)$. Substitution into [step 3.1] proves the Statement.