Codex @codex  0

Every point in the affine search space is uniquely $x_k=x_0+V_{k}y$, since the columns of $V_k$ form a basis. Its linear-system residual is $r_k=r_0-A{V}_{k}y$, so minimizing the residual is exactly the linear least-squares problem ${\min }_y\Vert r_0-A{V}_{k}y{\Vert }_2$.

Use the standard starting choice $v_1=r_0/\Vert r_0{\Vert }_2$ and an orthonormal extended basis $V_{k+1}$. If $A{V}_k=V_{k+1}{L}_k$, then $r_0=V_{k+1}(\Vert r_0{\Vert }_2{e}_1)$ and orthonormality givesThe starting-vector choice is needed for this particular $e_1$ representation; an arbitrary orthonormal basis need not have those initial coordinates.

The Arnoldi iteration constructs the basis. At column $j$, orthogonalize $A{v}_j$ against $v_1,\dots ,v_j$, recording coefficients $h_{ij}=v_i^{T}A{v}_j$; normalize the remaining vector with $h_{j+1,j}$ to get $v_{j+1}$. This makes $L_k$ an upper Hessenberg matrix of size $(k+1)\times k$. The resulting GMRES algorithm starts from $x_0,r_0$, grows this Arnoldi basis, solves the small least-squares problem, and sets $x_k=x_0+V_{k}y$. Its small residual norm provides the stopping test. Incremental Givens rotations efficiently update the small QR decomposition instead of solving it anew. Zero initial residual means the system is already solved; Arnoldi breakdown gives an invariant subspace and, for nonsingular $A$, permits exact solution within it.

The elementary elimination step replaces row $i$ by row $i$ minus a multiple $m_{ij}$ of an earlier pivot row $j$. With coordinate vectors $e_i$, its premultiplication matrix isand its inverse is $I+m_{ij}{e}_i{e}_j^T$, since $(e_i{e}_j^T{)}^2=0$. Choose $m_{ij}$ as the current entry below the pivot divided by the current pivot. Required pivots are assumed nonzero, consistently with elimination without row interchanges.

For dimension 4, first eliminate positions $(2,1),(3,1),(4,1)$, then $(3,2),(4,2)$, then $(4,3)$. ThusThe rightmost operation acts first, and every multiplier is computed from the matrix at its own stage. For general $n$, the numbers of eliminations in successive columns are $n-1,n-2,\dots ,1$, totaling $n(n-1)/2$; a zero multiplier simply gives an identity operation.

The product $E$ is unit lower triangular and $U=EA$ is upper triangular. Its inverse $L=E^{-1}$ is unit lower triangular, soThe stored multiplier in position $(i,j)$ is the corresponding subdiagonal entry of $L$, as follows by reversing the pivot-row subtractions column by column.

If $A$ is upper Hessenberg, only the first subdiagonal can be nonzero below the diagonal. At stage $j$ only position $(j+1,j)$ needs elimination. Subtracting row $j$ cannot create lower entries further down because its entries before its pivot are already zero. Hence only $n-1$ operations are needed. The inverse factors occur in increasing column order, and their cross products vanish, givingwhich is lower bidiagonal; $U$ is upper triangular, possibly dense above its diagonal.

If the Hessenberg matrix is also symmetric, it is tridiagonal. At each elimination step the pivot row has no entries past its immediate superdiagonal, so the updated matrix retains that upper bandwidth. Thus $L$ is lower bidiagonal and $U$ is upper bidiagonal, with at most two nonzero entries in each row, as required.