Past exam of the numerical analysis course of the University of Oxford / 2014 / 1

A Givens rotation acts as the identity matrix outside two selected coordinates $i,j$, and has the following block on those coordinates:The convention with the opposite signs of the sines is equivalent after replacing $\theta$ by $-\theta$. A Householder reflection with nonzero normal vector $w\in {\mathbb{R}}^n$ isIt reverses the component parallel to $w$ and fixes the perpendicular hyperplane. Both are orthogonal matrices, so their transposes are their inverses and they preserve the Euclidean norm.

If $u=0$, any nonzero $w$, for instance the first Cartesian basis vector $e_1$, gives $H(w)u=0$ and $\alpha =0$. Suppose $u\ne 0$. Choosewhere ${\mathrm{sgn}}_{+}(r)=1$ for $r\ge 0$ and $-1$ otherwise. This choice ensures $w\ne 0$, including when $u$ is already on the first coordinate axis. Since ${\alpha }^2=u^{T}u$,Therefore the Householder reflection satisfiesThe orthogonality of $H(w)$, used here to check length preservation, gives $|\alpha |=\Vert H(w)u{\Vert }_2=\Vert u{\Vert }_2$. The chosen sign also avoids catastrophic cancellation in $w_1=u_1-\alpha$. This is a Householder reflection sending a vector to a coordinate axis with no zero-normal exception.

Set $A^{(0)}=A$. At step $k=1,\dots ,n-2$, let $u=A_{k+1:n,k}^{(k-1)}$ be the column below the diagonal. Choose a Householder reflection ${\hat{H}}_k$ sending $u$ onto its first coordinate axis, and embed it asIf $u=0$, use $P_k=I$. Left multiplication annihilates entries $k+2,\dots ,n$ in column $k$. Right multiplication performs the matching operation on row $k$, because the matrix remains symmetric. The first $k$ coordinates are fixed, so zeros already created in earlier columns and rows are preserved.

Here the orthogonality of each $P_k$ is used explicitly: $P_k^{-1}=P_k^T$, so each update is a similarity transformation and preserves eigenvalues. After $n-2$ steps,where $Q$ is orthogonal and $T$ is a real symmetric tridiagonal matrix. This is Householder tridiagonalization.

A QR factorization of a real $n\times n$ matrix isThus $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix. It exists even if $A$ is singular; requiring positive diagonal entries of $R$ is a convenient uniqueness convention for nonsingular $A$, rather than part of the general existence statement. Over the complex numbers, replace orthogonal by unitary and transpose by conjugate transpose.

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 $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.

The initial bottom-right entry is zero, so the chosen QR shift is ${\mu }_0=0$. One valid QR factorization is $Q_0=A$, $R_0=I$, using explicitly that $A^{T}A=I$. The update isIt repeats forever and never approaches a diagonal matrix. With the standard positive-diagonal convention for $R$, this factorization is unique, so the Rayleigh-shift iteration is stationary and fails to diagonalize $A$.

The failure is independent of harmless sign conventions. The columns of $A$ are already orthonormal, so another QR factorization can only replace $Q_0$ by $AD$ and $R_0$ by $D$, where $D$ is diagonal with entries $\pm 1$. Then $A_1=DAD$ still has zero diagonal and off-diagonal magnitudes one. Subsequent bottom-right shifts remain zero and the off-diagonal magnitude never decreases. The eigenvalues are $+1,-1$, with equal absolute values, explaining the lack of separation in the unshifted QR algorithm.

Let the real QR shift be $\mu$ and put $r=\sqrt{1+{\mu }^2}$. A valid QR factorization, including the singular cases $\mu =\pm 1$, isHere $Q^{T}Q=I$, and multiplying verifies $QR=A-\mu I$. Using this orthogonality in the shifted update givesIt is diagonal exactly when ${\mu }^2-1=0$. Therefore all real shifts giving the eigenvalues in one iteration areThe resulting diagonal is $(-1,1)$ or $(1,-1)$, respectively. Both QR shifts are exact eigenvalues. Sign changes in the QR factorization conjugate $A_1$ by a diagonal sign matrix and do not alter its zero pattern. This is Exact-shift diagonalization of a two-state swap matrix.