Eigenvalue Iterations and the QR Algorithm: Examples and Counterexamples

Since $A^k{x}_0=2^{-1\mathrm{/}2}(4^k,1{)}^T$, normalising gives $x_k=\frac{1}{\sqrt{{16}^k+1}}\left[\begin{array}{c}{4}^k\\ 1\end{array}\right]=\frac{1}{\sqrt{1+{16}^{-k}}}\left[\begin{array}{c}1\\ 4^{-k}\end{array}\right]\mathrm{.}$

The second coordinate of $x_k$ is asymptotic to $4^{-k}$, so the angle to the dominant eigendirection $\mathbb{F}{e}_1$ decays like $4^{-k}$. This is exactly the rate predicted by [L1].

Since $A$ is diagonal with entries $1$ and $-1$, $x_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right],x_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]=x_0\mathrm{.}$

Therefore $x_{2k}=x_0$ and $x_{2k+1}=x_1$ for every $k\ge 0$. The sequence is periodic of period $2$, so it does not converge.

The matrix has dominant modulus $1$, but equal dominant moduli prevent convergence here, refuting the claim.

The right eigenvectors are $e_1$ for eigenvalue $2$ and $(1,-1{)}^T$ for eigenvalue $1$. A left eigenvector for eigenvalue $2$ is $(1,1{)}^T$, and $\left[\begin{array}{cc}1& 1\end{array}\right]x_0=0.$ So the start vector is orthogonal to the dominant left eigendirection.

Direct multiplication gives $A{x}_0=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]=x_0\mathrm{.}$ Hence every normalised power iterate equals $x_0$.

The power iteration never approaches the dominant eigendirection $e_1$, so the start condition in [L1] is genuinely necessary.

Here $(A-\mu I{)}^{-1}=\mathrm{diag}\text{\hspace{0.17em}⁣}(\frac{5}{21},5)\mathrm{.}$ The transformed eigenvalue magnitudes are $5\mathrm{/}21$ and $5$, so the eigendirection $e_2$ of the original eigenvalue $1$ becomes dominant.

The start vector has nonzero $e_2$-component, so [L1] applies and the normalised iterates converge to the line $\mathbb{F}{e}_2$.

The Rayleigh quotient of $x(t)$ is $\mu (t)=\frac{2+t^2}{1+t^2}\mathrm{.}$ Therefore $A-\mu (t)I=\left[\begin{array}{cc}{\displaystyle \frac{t^2}{1+t^2}}& 0\\ 0& -{\displaystyle \frac{1}{1+t^2}}\end{array}\right]\mathrm{.}$

If $t=0$, then $\mu (0)=2$ and $A-\mu (0)I=\mathrm{diag}(0,-1)$ is singular, so Rayleigh-quotient iteration for Hermitian matrices does not define a next iterate at that start vector. If $t\mathrm{\ne }0$, solving $(A-\mu (t)I)y=x(t)$ gives $y\propto \left[\begin{array}{c}{\displaystyle \frac{1+t^2}{t^2}}\\ -(1+t^2)t\end{array}\right],$ so after normalisation the new slope is $\frac{y_2}{y_1}=-t^3\mathrm{.}$

Thus every sufficiently small nonzero slope error $t$ becomes $-t^3$ in one step, which is the explicit two-dimensional form of the cubic behaviour from [L1].

The lower part of the first column of $A$ is $(3,4{)}^T$, whose Euclidean norm is $5$. The reflector $Q$ fixes the first basis vector and sends $(3,4{)}^T$ to $(5,0{)}^T$.

Direct multiplication gives the displayed matrix $Q^{T}AQ$, whose $(3,1)$ entry is $0$. Therefore it has no entries below the first subdiagonal, so it is upper Hessenberg. This is the $3\times 3$ instance of [L1].

For the unshifted step, a QR factorisation of $A$ gives $Q=\frac{1}{\sqrt{10}}\left[\begin{array}{cc}3& -1\\ 1& 3\end{array}\right],R=\frac{1}{\sqrt{10}}\left[\begin{array}{cc}10& 5\\ 0& 5\end{array}\right],$ so [L1] yields $A_1=RQ=\left[\begin{array}{cc}7\mathrm{/}2& 1\mathrm{/}2\\ 1\mathrm{/}2& 3\mathrm{/}2\end{array}\right]$.

For the shifted step, $A-\frac{3}{2}I=\left[\begin{array}{cc}\frac{3}{2}& 1\\ 1& \frac{1}{2}\end{array}\right],$ and a QR factorisation gives $Q=\frac{1}{\sqrt{13}}\left[\begin{array}{cc}3& -2\\ 2& 3\end{array}\right]\mathrm{.}$ Using [L1] again gives ${\tilde{A}}_1=\left[\begin{array}{cc}47\mathrm{/}13& -1\mathrm{/}13\\ -1\mathrm{/}13& 18\mathrm{/}13\end{array}\right]$.

Comparing steps 1.1 and 1.2 shows the effect of the shift: the off-diagonal magnitude drops from $1\mathrm{/}2$ to $1\mathrm{/}13$ in a single step.

The trailing $2\times 2$ block of $T$ is $\left[\begin{array}{cc}3& 1\mathrm{/}10\\ 1\mathrm{/}10& 2\end{array}\right]$, whose eigenvalues are $(25\pm \sqrt{26})\mathrm{/}10$. The smaller one is nearer to the bottom-right entry $2$, so it is the Wilkinson shift.

Carrying out one shifted QR step with that shift gives the displayed matrix $T_{+}$, whose bottom subdiagonal magnitude is about $2\times {10}^{-3}$, hence smaller than $1\mathrm{/}400$ and far below the original ${10}^{-1}$. This is a direct one-step computation using the shift from [L1].

The eigenvalues of $J_{\epsilon }$ are $1$ and $1+\epsilon$, so they differ from the repeated eigenvalue of $J$ by at most $\mathrm{\mid }\epsilon \mathrm{\mid }$. An eigenvector for $1$ is $e_1$, and an eigenvector for $1+\epsilon$ is $(1,\epsilon {)}^T$.

Hence an eigenbasis matrix is $X_{\epsilon }=\left[\begin{array}{cc}1& 1\\ 0& \epsilon \end{array}\right],X_{\epsilon }^{-1}=\left[\begin{array}{cc}1& -{\epsilon }^{-1}\\ 0& {\epsilon }^{-1}\end{array}\right]\mathrm{.}$ So $\mathrm{\parallel }{X}_{\epsilon }^{-1}{\mathrm{\parallel }}_2$ is of order $\mathrm{\mid }\epsilon {\mathrm{\mid }}^{-1}$, and therefore ${\kappa }_2(X_{\epsilon })$ is also of order $\mathrm{\mid }\epsilon {\mathrm{\mid }}^{-1}$.

As $\epsilon \to 0$, the eigenvalues of $J_{\epsilon }$ coalesce gently, but the eigenvectors become nearly parallel and the eigenbasis becomes badly conditioned. This refutes the claim and illustrates the warning in [L1].