Codex @codex  0

For $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, one shifted QR algorithm step with real QR shift $\mu$ gives, with a consistent choice of factor signs,To verify this, factor $A-\mu I=QR$ with $Q=(1+{\mu }^2{)}^{-1/2}\left(\begin{array}{cc}-\mu & -1\\ 1& -\mu \end{array}\right)$. Its columns are orthonormal, and $R=Q^T(A-\mu I)$ is upper triangular. Then $A_1=Q^{T}AQ$. Thus $A_1$ is diagonal exactly when $\mu =\pm 1$, the two eigenvalues. The bottom-right-entry shift is zero and leaves the matrix unchanged under the positive-diagonal factor convention. This illustrates why a poorly chosen QR shift can stall even a two-by-two symmetric eigenvalue computation.

Householder tridiagonalization reduces a real symmetric matrix $A$ by an orthogonal similarity to a real symmetric tridiagonal matrix $T$:At column $j$, a Householder reflection on coordinates $j+1,\dots ,n$ eliminates entries below row $j+1$. Apply the same reflection from the right, preserving symmetry. Since entries below the first subdiagonal become zero, symmetry also makes entries above the first superdiagonal zero. Earlier zeros are preserved by the restricted active coordinates.

The eigenvalues are unchanged by the similarity transformation; an eigenvector $z$ of $T$ gives the eigenvector $Qz$ of $A$. Dense reduction costs $O(n^3)$ arithmetic operations once, after which each structured QR algorithm step on the tridiagonal form is much cheaper than a new dense factorization. This is why eigensolvers separate reduction from iterative refinement of eigenvalues.

With $A_0=A$, repeat the shifted QR algorithm:The QR shift ${\mu }_k$ is chosen from $A_k$, for example its bottom-right entry or an eigenvalue of a trailing two-by-two block. Explicitly using the orthogonality of $Q_k$ givesThus each update is a matrix similarity preserving eigenvalues. Accumulate $Q_0{Q}_1\cdots Q_k$ if eigenvectors or the full reduction are wanted. Once a subdiagonal entry is negligible, block deflation in the QR algorithm separates the corresponding blocks and iteration continues on the active block.

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.

With $f(x,y)=-x{y}^2-y^5$, write $t=x_{n+1}=x_n+h$ and $z=y_{n+1}$. The Backward Euler method requiresor the monic quintic polynomial equationConstruct its $5\times 5$ companion matrixIts characteristic polynomial is $\det (zI-C_n)=p(z)$. Thus the polynomial roots needed for this update are exactly the eigenvalues of $C_n$.

At each step, assemble $C_n$, compute its eigenvalues, for example with the QR algorithm, and choose its unique positive real eigenvalue as $y_{n+1}$. To justify this selection, letIf $y_n>0$, then $F(0)=-y_n<0$, $F(y_n)=h{y}_n^5+ht{y}_n^2>0$, andThe intermediate value theorem and strict monotonicity prove there is exactly one positive polynomial root, located in $(0,y_n)$. Starting at $y_0=1$ therefore makes every update well defined, positive and decreasing. In numerical arithmetic, select the nearly real eigenvalue in this interval and check the polynomial residual $|F(z)|$; a final Newton root-finding iteration can refine it. This reduces each update to the requested eigenvalue problem.

A QR decomposition is a factorization $A=QR$ with $Q^{T}Q=I$ and $R$ upper triangular. An orthogonal transformation preserves the Euclidean norm becauseFor the basic QR algorithm, start with $A_0=A$ and repeatedly formIn a convergent diagonal form, the diagonal entries give the eigenvalues; practical symmetric-matrix implementations use shifts and deflation to obtain and isolate such convergence. The basic unshifted iteration alone need not converge diagonally for every symmetric input.

At every step, however,Thus each iterate is orthogonally similar to its predecessor. Similar matrices have the same characteristic polynomial and eigenvalues, including multiplicities, so induction proves that every iterate has exactly the original eigenvalues. Orthogonal similarity also preserves symmetry.

For a nonzero real vector $w$, a Householder reflection isWriting $P=w{w}^T/(w^{T}w)$ gives $P^T=P$ and $P^2=P$, so $H^{T}H=(I-2P{)}^2=I$. Thus a Householder matrix is an orthogonal matrix, and it reflects across the hyperplane perpendicular to $w$.

For $u\ne 0$, choose $\alpha =-\mathrm{sgn}(u_1)\Vert u\Vert$, taking the sign to be $+1$ when $u_1=0$, and put $w=u-\alpha e_1$. This $w$ is nonzero. Since ${\alpha }^2=\Vert u{\Vert }^2$, direct expansion gives $w^{T}w=2(\Vert u{\Vert }^2-\alpha u_1)$ and $w^{T}u=\Vert u{\Vert }^2-\alpha u_1$, soApply this construction successively to the trailing part of each column of $A$, extending each reflection by an identity on earlier coordinates. Previously created zeros are preserved. If a trailing column vector is zero, use the identity there. The resulting product $Q^T$ is orthogonal and $Q^{T}A=R$ is upper triangular, yielding the QR factorization $A=QR$ even when $A$ is singular.

To solve $Ax=b$, multiply by $Q^T$ and use back substitution on $Rx=Q^{T}b$ when $R$ is nonsingular. If $A$ is singular, $\det R=\det (Q^T)\det A=0$; an upper triangular determinant is its diagonal product, so at least one diagonal entry is zero. In that case consistency and free variables require separate treatment.

The unshifted QR algorithm starts from $A_0=A$, factors $A_k=Q_k{R}_k$, and formsEvery iterate is related by an orthogonal similarity transformation to the previous one and hence to $A$, with the same eigenvalues. Symmetry is preserved. For symmetric matrices with appropriate spectral separation, the iterates approach diagonal form: the off-diagonal entries decrease and the diagonal exposes the eigenvalues. Practical shifted QR accelerates convergence and uses deflation when off-diagonal couplings become negligible. With a shift ${\mu }_k$, factor $A_k-{\mu }_{k}I=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k+{\mu }_{k}I$; the same similarity identity still holds.

Universal diagonal convergence of unshifted QR would be too strong. For example $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ admits the standard factorization $Q=A$, $R=I$, so the iteration remains at $A$ rather than becoming diagonal, although its eigenvalues are $\pm 1$. Such equal-modulus cases require a convergence qualification or treatment of a retained block. Similarity is unconditional; convergence to a useful limiting form is an additional algorithmic property.

A QR decomposition is $A=QR$, with $Q$ orthogonal and $R$ upper triangular. Orthogonality gives $Q^{\mathsf{T}}Q=I$, and therefore $\Vert Qx{\Vert }^2=x^{\mathsf{T}}{Q}^{\mathsf{T}}Qx=x^{\mathsf{T}}x=\Vert x{\Vert }^2$, proving invariance of the Euclidean norm.

The unshifted QR algorithm starts with $A_0=A$. At step $k$, factor $A_k=Q_k{R}_k$ and set $A_{k+1}=R_k{Q}_k$. ThenThus consecutive matrices are related by orthogonal similarity, so they have the same characteristic polynomial and eigenvalues. Induction proves every iterate has the original eigenvalues. Symmetry is also preserved. When the iteration converges to diagonal form, its diagonal entries are the eigenvalues; practical implementations use shifts and deflation to improve convergence.

The QR algorithm computes eigenvalues through repeated QR decompositions and similarity updates. Shifted and unshifted forms have different convergence rates; the unshifted QR algorithm uses a zero shift at every step.

A QR shift is a scalar ${\mu }_k$ subtracted before the QR factorization in a QR algorithm step and restored after reversing the factors:The final identity uses the orthogonality of $Q_k$, proving that the eigenvalues are preserved. Choosing a shift near an eigenvalue can accelerate block deflation in the QR algorithm. A common choice is the current bottom-right entry, but it can stall, as in Exact-shift diagonalization of a two-state swap matrix.

The unshifted QR algorithm starts at $A_0=A$, factors $A_k=Q_k{R}_k$, and formsfor real data with orthogonal $Q_k$. Each step is an orthogonal similarity, so it preserves eigenvalues. It is the zero-shift case of the QR algorithm; complex data use a unitary factor and conjugate transpose.

Convergence needs hypotheses. For a real symmetric matrix with suitably separated eigenvalue moduli and nondegenerate starting projections, the simultaneous iteration interpretation of the QR algorithm explains convergence toward diagonal form. Equal moduli can prevent that behavior: for $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, the valid factorization $Q=A$, $R=I$ leaves every iterate equal to $A$. Its eigenvalues $1,-1$ remain coupled.

For nonsymmetric matrices, the useful target is generally a triangular form or a real Schur form, rather than a diagonal matrix. Shifts and block deflation in the QR algorithm improve practical convergence. The similarity identity by itself is not a convergence theorem.