Codex @codex  0

The factorization produced by the Arnoldi iteration, with orthonormal $Q_{k+1}$ and an upper Hessenberg matrix ${\tilde{H}}_k$. Multiplying by $Q_k^T$ identifies its leading square block as $H_k=Q_k^{T}A{Q}_k$.

Starting with $q_1=b/\Vert b{\Vert }_2$, the Arnoldi iteration constructs an orthonormal basis of successive Krylov subspaces. At step $j$, orthogonalize $A{q}_j$ against $q_1,\dots ,q_j$, and normalize the remainder as $q_{j+1}$ if it is nonzero. The coefficients form an upper Hessenberg matrix ${\tilde{H}}_k$ and satisfy $A{Q}_k=Q_{k+1}{\tilde{H}}_k$. A zero remainder means the current Krylov subspace is invariant under $A$.

An upper Hessenberg matrix has zero entries below the first subdiagonal; the lower version has zero entries above the first superdiagonal. The upper Hessenberg matrix is one of these two forms.

For a real symmetric matrix $A$, the leading block $Q_k^{T}A{Q}_k$ of the Arnoldi decomposition is both symmetric and an upper Hessenberg matrix, hence a tridiagonal matrix. The resulting three-term recurrence is the Lanczos algorithm. If $A$ is a symmetric positive-definite matrix, its compression is too, since $y^T{Q}_k^{T}A{Q}_{k}y=(Q_{k}y{)}^{T}A(Q_{k}y)>0$ for nonzero $y$.

Without row interchanges, an upper Hessenberg matrix needs only one elimination per pivot column. Its lower factor is unit lower bidiagonal, while its upper factor is upper triangular. If the original matrix is symmetric, it is tridiagonal and the upper factor is also bidiagonal.

Starting with $A_1=A$, for $k=1,\dots ,n-2$ choose a Householder reflection $H_k$ that acts only on coordinates $k+1,\dots ,n$ and maps the tail of column $k$,to a multiple of its first coordinate vector. SetThis zeros all entries in column $k$ below its first subdiagonal. Because $H_k$ fixes the first $k$ coordinates, it preserves the zeros created in earlier columns. After $n-2$ steps,is an upper Hessenberg matrix.

Each $H_k$ is orthogonal and symmetric. Ifthen $Q$ is orthogonal andPart (a) shows that each similarity update costs $O(n^2)$ arithmetic operations, and there are $O(n)$ updates. The total cost is therefore

For an efficient QR algorithm, first reduce a general real matrix to upper Hessenberg matrix by orthogonal similarities. For a real symmetric matrix, use Householder tridiagonalization; the resulting symmetric tridiagonal matrix is the usual input in this setting. These structures are preserved by suitable QR algorithm implementations and greatly reduce the work per iteration.

The output is the eigenvalues, together with an orthogonal reduction when the factors are accumulated. In the symmetric case the target is a diagonal matrix, whose diagonal entries are the real eigenvalues; the accumulated orthogonal columns are eigenvectors. For a general real matrix, the target is the real form in a Schur decomposition: an upper block triangular matrix with diagonal blocks of size one or two. The two-by-two blocks represent complex conjugate eigenvalue pairs. An arbitrary unshifted iteration need not converge, so these describe the intended converged output, with appropriate shifts and block deflation in the QR algorithm.

An orthogonal similarity transformation is $H=Q^{T}AQ$ with $Q^{T}Q=I$. An upper Hessenberg matrix has $H_{ij}=0$ whenever $i>j+1$; its first subdiagonal may be nonzero.

At step $k=1,\dots ,m-2$, choose a Householder reflector $Q_k=\mathrm{diag}(I_k,{\hat{Q}}_k)$ whose trailing block sends the current column segment in rows $k+1,\dots ,m$ to a multiple of its first coordinate. The left multiplication zeros positions $(k+2,k),\dots ,(m,k)$. Apply the matching right multiplication to retain similarity: $A\leftarrow Q_k^{T}A{Q}_k$. Since $Q_k$ acts only on rows and columns $k+1,\dots ,m$, earlier Hessenberg zeros are preserved. Finally $Q=Q_1\cdots Q_{m-2}$ gives $H=Q^{T}AQ$.

Each reflector is applied through a rank-one update, costing $O(m^2)$ rather than a full matrix multiplication. Across $m-2$ steps, the Hessenberg reduction costs $O(m^3)$.

Solving the $m$ unrelated shifted systems by separate Gaussian elimination costs $\boxed{\frac{2}{3}{m}^4+O(m^3)}$ floating-point operations.

Instead compute $H=Q^{T}AQ$ once in $O(m^3)$ work. For each shift, solveThe shift changes only the diagonal, so $H-{\lambda }_{j}I$ remains an upper Hessenberg matrix. In each elimination column only the entry immediately below the pivot needs removal. With partial pivoting the only possible nonzero candidate rows are the current row and the next, and each update touches $O(m)$ entries. Factorization therefore costs $O(m^2)$ per shift; the triangular solve and both orthogonal-vector transformations also cost $O(m^2)$ each.

Thus $m$ shifted solves plus the initial Hessenberg reduction cost $\boxed{O(m^3)}$ in total. Pivoting is still needed in general: nonsingularity excludes a singular system but does not by itself guarantee that every unpivoted elimination pivot is nonzero.

For the small QR decomposition, each of the $k$ Givens rotations eliminates one subdiagonal entry of the upper Hessenberg matrix. At column $j$, apply the rotation to two rows in columns $j,\dots ,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. Backward substitution in a triangular system costs $O(k^2)$.

Computing $\Vert b{\Vert }_2$ costs $O(n)$ and the final dense matrix multiplication $Q_k{y}_k$ costs $O(nk)$. Thus the total, with the Arnoldi decomposition already supplied, isHere $1\le k<n$, since $Q_{k+1}$ has orthonormal columns in ${\mathbb{R}}^n$. In the standard dense arithmetic model, forming the general matrix–vector product gives the sharp $\Theta (nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating ${\tilde{H}}_k$ as an unstructured dense matrix would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.

Write $x=Q_{k}y$ and $\beta =\Vert b{\Vert }_2$. The Arnoldi decomposition and $b=\beta Q_{k+1}{e}_1$ giveBecause $Q_{k+1}$ has orthonormal columns, it preserves the Euclidean norm. The generalized minimal residual method therefore reduces to the small linear least-squares problemUse Givens rotations on the upper Hessenberg matrix to obtain a QR decompositionwhere $Z$ is an orthogonal matrix and $R_k$ is an upper triangular matrix. Then solve $R_k{y}_k=g_{1:k}$ by backward substitution in a triangular system and form $Q_k{y}_k$. The resulting minimum linear-system residual has Euclidean norm $|g_{k+1}|$.

The small problem has a unique answer: if ${\tilde{H}}_{k}y=0$, the Arnoldi decomposition gives $A{Q}_{k}y=0$. The invertible matrix $A$ implies $Q_{k}y=0$, and the orthonormality of $Q_k$ then gives $y=0$. Thus ${\tilde{H}}_k$ has full column rank and $R_k$ is nonsingular.

Multiplying the Arnoldi decomposition by $Q_k^T$ shows that the leading square block isIt is an upper Hessenberg matrix by the Arnoldi iteration. Because $A=A^T$, it is also a symmetric matrix. Entries below the first subdiagonal vanish by the Hessenberg structure, and their reflected entries above the first superdiagonal vanish by symmetry. ConsequentlyThe extra last row has only its final entry possibly nonzero. With the usual choice of positive normalization factors, the individual column relations are the three-term Lanczos algorithm recurrencewhere the first term is omitted for $j=1$. This reduction is an exact-arithmetic statement; round-off error can affect the orthogonality in an implementation.