Eigenvalue Iterations and the QR Algorithm

If $(A+E)x=\mu x$, then $Ex=-(Ax-\mu x)=-r$. Because $\mathrm{\parallel }x{\mathrm{\parallel }}_2=1$, [L2] gives $\mathrm{\parallel }E{\mathrm{\parallel }}_2\ge \mathrm{\parallel }Ex{\mathrm{\parallel }}_2=\mathrm{\parallel }r{\mathrm{\parallel }}_2\mathrm{.}$ So every admissible perturbation has norm at least $\mathrm{\parallel }r{\mathrm{\parallel }}_2$.

Define $E:=-r{x}^{\ast }$. Then $Ex=-r(x^{\ast }x)=-r,$ so $(A+E)x=\mu x$. For any unit vector $y$, [L3] gives $\mathrm{\parallel }Ey{\mathrm{\parallel }}_2=\mathrm{\parallel }r{\mathrm{\parallel }}_2\mathrm{\mid }{x}^{\ast }y\mathrm{\mid }\le \mathrm{\parallel }r{\mathrm{\parallel }}_2,$ with equality at $y=x$. Hence $\mathrm{\parallel }E{\mathrm{\parallel }}_2=\mathrm{\parallel }r{\mathrm{\parallel }}_2$.

Step 1.1 gives the lower bound and step 1.2 attains it, so $\eta (A,\mu ,x)=\mathrm{\parallel }r{\mathrm{\parallel }}_2$.

By [L1], the chosen eigenvectors form a basis, so for every $k\ge 0$, $A^k{x}_0={\lambda }_1^k(c_1{v}_1+{\sum }_{i=2}^n{c}_i{\left(\frac{{\lambda }_i}{{\lambda }_1}\right)}^k{v}_i)\mathrm{.}$

The strict modulus inequality and $n\ge 2$ imply ${\lambda }_1\mathrm{\ne }0$. In the eigenbasis, the $v_1$-coefficient of $A^k{x}_0$ is $c_1{\lambda }_1^k\mathrm{\ne }0$, so $A^k{x}_0\mathrm{\ne }0$ for every $k\ge 0$. Therefore the iteration of [L2] is defined at every step and has the same direction as $A^k{x}_0$. Moreover, because $\mathrm{\mid }{\lambda }_i\mathrm{/}{\lambda }_1\mathrm{\mid }<1$ for $i\ge 2$, the bracket in step 1.1 tends to $c_1{v}_1$.

Let ${\alpha }_k$ cancel the phase of ${\lambda }_1^k{c}_1$. Then step 1.1 gives ${\alpha }_k{x}_k=\frac{v_1+{\sum }_{i=2}^n(c_i\mathrm{/}{c}_1)({\lambda }_i\mathrm{/}{\lambda }_1{)}^k{v}_i}{{\parallel v_1+{\sum }_{i=2}^n(c_i\mathrm{/}{c}_1)({\lambda }_i\mathrm{/}{\lambda }_1{)}^k{v}_i\parallel }_2}\mathrm{.}$ The numerator differs from $v_1$ by $O(\mathrm{\mid }{\lambda }_2\mathrm{/}{\lambda }_1{\mathrm{\mid }}^k)$, so the same is true after normalisation.

Therefore the normalised iterates converge projectively to the eigendirection of $v_1$, and the convergence rate is $O(\mathrm{\mid }{\lambda }_2\mathrm{/}{\lambda }_1{\mathrm{\mid }}^k)$.

The eigenvectors of $(A-\mu I{)}^{-1}$ are the same $v_i$, and the corresponding eigenvalues are $({\lambda }_i-\mu {)}^{-1}$. The hypothesis $\mathrm{\mid }{\lambda }_j-\mu \mathrm{\mid }<\mathrm{\mid }{\lambda }_i-\mu \mathrm{\mid }$ means $\mid \frac{1}{{\lambda }_j-\mu }\mid >\mid \frac{1}{{\lambda }_i-\mu }\mid (i\mathrm{\ne }j)\mathrm{.}$

Therefore $(A-\mu I{)}^{-1}$ has a simple eigenvalue of strictly largest modulus in the eigendirection $v_j$. The start vector has nonzero $v_j$-component by hypothesis, so [L2] applies.

Since [L1] identifies shifted inverse iteration with that power iteration, the iterates converge projectively to the eigendirection of $v_j$.

Because $x$ is unit and $h$ is tangent to the unit sphere at $x$, one has $⟨x,x⟩=1,\mathrm{Re}⟨x,h⟩=0.$ Differentiating $\rho (x+th)=\frac{⟨A(x+th),x+th⟩}{⟨x+th,x+th⟩}$ at $t=0$ therefore gives $D\rho (x)[h]=⟨Ah,x⟩+⟨Ax,h⟩\mathrm{.}$ By [L1], $⟨Ah,x⟩=⟨h,Ax⟩$, so $D\rho (x)[h]=2\mathrm{Re}⟨Ax,h⟩=2\mathrm{Re}⟨Ax-\rho (x)x,h⟩,$ because $\mathrm{Re}⟨x,h⟩=0$.

Since $⟨x,x⟩=1$, one has $⟨r(x),x⟩=⟨Ax,x⟩-\rho (x)⟨x,x⟩=0.$ So $r(x)$ itself lies in the tangent space at $x$.

Conversely, if $Ax=\lambda x$, then $\rho (x)=\lambda$ and $r(x)=0$, so step 1.1 gives $D\rho (x)[h]=0$ for every tangent vector $h$. Thus $x$ is a stationary point.

If $x$ is a stationary point, then step 1.1 gives $\mathrm{Re}⟨r(x),h⟩=0$ for every tangent vector $h$. Since step 2.1 places $r(x)$ in that tangent space, choosing $h=r(x)$ yields $\mathrm{\parallel }r(x){\mathrm{\parallel }}_2^2=0.$ Hence $r(x)=0$ and $Ax=\rho (x)x$.

Steps 1.1, 3.1, and 2.2 prove the gradient and stationary-point claims.

Let $\rho :=\mathrm{\mid }{\lambda }_2\mathrm{/}{\lambda }_1\mathrm{\mid }<1$. By [L4], the Hermitian matrix is diagonalisable, so [L1] applies. After choosing phases ${\alpha }_k$ of modulus one, one has $\mathrm{\parallel }{\alpha }_k{x}_k-q_1{\mathrm{\parallel }}_2=O({\rho }^k)\mathrm{.}$ Write ${\alpha }_k{x}_k=c_k{q}_1+z_k$ with $z_k\perp q_1$. Then $\mathrm{\mid }{c}_k-1\mathrm{\mid }+\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2=O({\rho }^k)$.

By [L2], the orthogonal complement $q_1^{\perp }$ is $A$-invariant. Since $x_k$ is unit and ${\mu }_k=⟨A({\alpha }_k{x}_k),{\alpha }_k{x}_k⟩$, the cross terms vanish: ${\mu }_k=\mathrm{\mid }{c}_k{\mathrm{\mid }}^2{\lambda }_1+⟨A{z}_k,z_k⟩\mathrm{.}$ Using $\mathrm{\mid }{c}_k{\mathrm{\mid }}^2+\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2^2=1$, this becomes ${\mu }_k-{\lambda }_1=⟨A{z}_k,z_k⟩-{\lambda }_1\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2^2\mathrm{.}$ Therefore $\mathrm{\mid }{\mu }_k-{\lambda }_1\mathrm{\mid }\le (\mathrm{\parallel }A{\mathrm{\parallel }}_2+\mathrm{\mid }{\lambda }_1\mathrm{\mid })\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2^2=O({\rho }^{2k})\mathrm{.}$

Using $A{q}_1={\lambda }_1{q}_1$, one has ${\alpha }_k{r}_k=A({\alpha }_k{x}_k)-{\mu }_k({\alpha }_k{x}_k)=c_k({\lambda }_1-{\mu }_k)q_1+(A-{\mu }_{k}I)z_k\mathrm{.}$ Since $\mathrm{\mid }{\alpha }_k\mathrm{\mid }=1$, $\mathrm{\parallel }{r}_k{\mathrm{\parallel }}_2\le \mathrm{\mid }{c}_k\mathrm{\mid }\mathrm{\mid }{\lambda }_1-{\mu }_k\mathrm{\mid }+(\mathrm{\parallel }A{\mathrm{\parallel }}_2+\mathrm{\mid }{\mu }_k\mathrm{\mid })\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2\mathrm{.}$ Step 2.1 and step 1.1 give $\mathrm{\parallel }{r}_k{\mathrm{\parallel }}_2=O({\rho }^k)\mathrm{.}$

The displayed bounds force ${\mu }_k\to {\lambda }_1$ and $r_k\to 0$.

By [L1] and [L2], choose an orthonormal eigenbasis $q,q_2,\dots ,q_n$ over the given field, with eigenvalues $\lambda ,{\lambda }_2,\dots ,{\lambda }_n$. Let $\gamma :={\min }_{i\ge 2}\mathrm{\mid }{\lambda }_i-\lambda \mathrm{\mid }>0.$ For ${\theta }_k:=\mathrm{dist}(x_k,\mathbb{F}q)$, [L4] gives the orthogonal decomposition $x_k=c_{k}q+z_k,z_k\perp q,\mathrm{\parallel }{z}_k{\mathrm{\parallel }}_2={\theta }_k\mathrm{.}$ Since the iterate has unit length, $\mathrm{\mid }{c}_k{\mathrm{\mid }}^2+{\theta }_k^2=1$.

The Rayleigh shift is ${\mu }_k:=⟨A{x}_k,x_k⟩\mathrm{.}$ Because $Aq=\lambda q$, $z_k\perp q$, and $A$ is Hermitian, the cross terms vanish: ${\mu }_k=\mathrm{\mid }{c}_k{\mathrm{\mid }}^2\lambda +⟨A{z}_k,z_k⟩\mathrm{.}$ Using $\mathrm{\mid }{c}_k{\mathrm{\mid }}^2+{\theta }_k^2=1$, this becomes ${\mu }_k-\lambda =⟨A{z}_k,z_k⟩-\lambda {\theta }_k^2\mathrm{.}$ Hence [L5] gives $\mathrm{\mid }{\mu }_k-\lambda \mathrm{\mid }\le (\mathrm{\parallel }A{\mathrm{\parallel }}_2+\mathrm{\mid }\lambda \mathrm{\mid }){\theta }_k^2\mathrm{.}$ Set $C_0:=\mathrm{\parallel }A{\mathrm{\parallel }}_2+\mathrm{\mid }\lambda \mathrm{\mid }$, and shrink $\delta$ so that $C_0{\delta }^2\le \gamma \mathrm{/}2$ and $\delta \le 1\mathrm{/}2$. Then whenever ${\theta }_k<\delta$, the shift satisfies $\mathrm{\mid }{\mu }_k-\lambda \mathrm{\mid }\le \gamma \mathrm{/}2$, so $\mathrm{\mid }{\lambda }_i-{\mu }_k\mathrm{\mid }\ge \gamma \mathrm{/}2$ for every $i\ge 2$.

By [L3], the next unnormalised iterate is $y_{k+1}:=(A-{\mu }_{k}I{)}^{-1}{x}_k\mathrm{.}$ Using the eigenbasis from step 1.1, $y_{k+1}=c_k(\lambda -{\mu }_k{)}^{-1}q+w_k,w_k:=(A-{\mu }_{k}I{)}^{-1}{z}_k\in q^{\perp }\mathrm{.}$ Because $\mathrm{\mid }{\lambda }_i-{\mu }_k\mathrm{\mid }\ge \gamma \mathrm{/}2$ on $q^{\perp }$, one has $\mathrm{\parallel }{w}_k{\mathrm{\parallel }}_2\le \frac{2}{\gamma }{\theta }_k\mathrm{.}$

Since ${\theta }_k<\delta \le 1\mathrm{/}2$, the identity $\mathrm{\mid }{c}_k{\mathrm{\mid }}^2+{\theta }_k^2=1$ gives $\mathrm{\mid }{c}_k\mathrm{\mid }\ge \sqrt{3}\mathrm{/}2$. After normalising $y_{k+1}$, the distance to the line $\mathbb{F}q$ is bounded by the ratio of the orthogonal and parallel parts: ${\theta }_{k+1}\le \frac{\mathrm{\parallel }{w}_k{\mathrm{\parallel }}_2}{\mathrm{\mid }{c}_k\mathrm{\mid }\mathrm{\mid }\lambda -{\mu }_k{\mathrm{\mid }}^{-1}}\le \frac{4}{\sqrt{3}\gamma }\mathrm{\mid }\lambda -{\mu }_k\mathrm{\mid }{\theta }_k\mathrm{.}$ Combining this with step 2.1 yields ${\theta }_{k+1}\le \frac{4C_0}{\sqrt{3}\gamma }{\theta }_k^3\mathrm{.}$

Taking $C:=4C_0\mathrm{/}(\sqrt{3}\gamma )$ proves $\mathrm{dist}(x_{k+1},\mathbb{F}q)\le C\mathrm{dist}(x_k,\mathbb{F}q{)}^3$ whenever $0<\mathrm{dist}(x_k,\mathbb{F}q)<\delta$ and the current Rayleigh-quotient step is defined. Hence the convergence is local and cubic.

By [L1], use the decomposition from the statement, where ${\mathrm{\Lambda }}_1=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_p)$ and ${\mathrm{\Lambda }}_2=\mathrm{diag}({\lambda }_{p+1},\dots ,{\lambda }_n)$. The hypothesis states exactly that $C_1$ is invertible.

The spectral gap implies ${\lambda }_p\mathrm{\ne }0$, so ${\mathrm{\Lambda }}_1^k{C}_1$ is invertible for every $k$. Hence $A^k{Q}_0$ has full column rank, every reduced QR step in [L2] is defined, and the column space of $Q_k$ equals that of $A^k{Q}_0$. Now $A^k{Q}_0=V\left[\begin{array}{c}{\mathrm{\Lambda }}_1^k{C}_1\\ {\mathrm{\Lambda }}_2^k{C}_2\end{array}\right]\mathrm{.}$ Multiplying on the right by $C_1^{-1}{\mathrm{\Lambda }}_1^{-k}$ shows that the same column space is the graph of ${\mathrm{\Lambda }}_2^k{C}_2{C}_1^{-1}{\mathrm{\Lambda }}_1^{-k}$ over the dominant invariant subspace.

The spectral gap implies $\mathrm{\parallel }{\mathrm{\Lambda }}_2^k{C}_2{C}_1^{-1}{\mathrm{\Lambda }}_1^{-k}{\mathrm{\parallel }}_2=O\text{\hspace{0.17em}⁣}\left({\mid \frac{{\lambda }_{p+1}}{{\lambda }_p}\mid }^k\right)\mathrm{.}$ Hence the graph in step 2.1 converges to the dominant invariant subspace at that rate.

Therefore the column space of $Q_k$ converges to the dominant invariant subspace, with the precise graph-norm rate stated above.

If $n\le 2$, every $n\times n$ matrix is already upper Hessenberg and every real symmetric one is already tridiagonal, so take the identity similarity. Assume $n\ge 3$. For $j=1,\dots ,n-2$, apply [L1] to the tail of column $j$ below the first subdiagonal inside the trailing $(n-j)\times (n-j)$ block. Embedding that reflector into the identity produces a unitary $Q_j$ that annihilates all entries of column $j$ below row $j+1$. Because $Q_j$ acts only on the trailing block, previously created zeros are preserved.

After the $n-2$ steps of 1.1, the product $H=Q_{n-2}^{\ast }\cdots Q_1^{\ast }A{Q}_1\cdots Q_{n-2}$ has zeros below its first subdiagonal, so [L2] says that $H$ is upper Hessenberg.

If $A$ is real symmetric, the same similarity steps remain real orthogonal. Each step that zeros the lower tail in column $j$ also zeros the matching upper tail in row $j$ because symmetry is preserved under orthogonal similarity.

Therefore the final matrix is symmetric and upper Hessenberg, hence tridiagonal by [L2]. This proves the symmetric claim.

From [L1], $A_{k+1}=R_k{Q}_k=Q_k^{\ast }{A}_k{Q}_k\mathrm{.}$ Iterating this identity yields $A_k={\widehat{Q}}_k^{\ast }A{\widehat{Q}}_k$.

Also $A_k{Q}_k=Q_k{R}_k{Q}_k=Q_k{A}_{k+1}$, so multiplying the factorisations gives $A^k=(Q_0{Q}_1\cdots Q_{k-1})(R_{k-1}\cdots R_1{R}_0)={\widehat{Q}}_k{\widehat{R}}_k$ with ${\widehat{R}}_k$ upper triangular. Thus the columns of ${\widehat{Q}}_k$ are the orthonormalised columns of $A^k$.

Step 1.1 proves unitary similarity, and step 1.2 identifies the iteration with simultaneous orthonormalised power iteration as in [L2].

For each $j=1,\dots ,n-1$, apply [L2] to the first $j$ columns of the simultaneous-iteration frame from [L1]. In eigenvector coordinates, the initial frame is $X^{-1}[e_1\cdots e_j]$; its leading $j\times j$ coefficient block is the leading principal block of $X^{-1}$ and is invertible by hypothesis.

Because $\mathrm{\mid }{\lambda }_j\mathrm{\mid }>\mathrm{\mid }{\lambda }_{j+1}\mathrm{\mid }$ for every $j$, each dominant $j$-dimensional invariant subspace is unique. Step 1.1 therefore shows that, for every $j$, the span $S_{j,k}$ of the first $j$ columns of ${\widehat{Q}}_k$ converges to $E_j:=\mathrm{span}(v_1,\dots ,v_j)$. Thus the orthonormal frames converge flag-by-flag to the ordered eigenvector flag, even though individual frame vectors may retain varying signs or phases.

By [L1], $A_k={\widehat{Q}}_k^{\ast }A{\widehat{Q}}_k$. Since $E_j$ is $A$-invariant and $S_{j,k}\to E_j$, the component of $A(S_{j,k})$ orthogonal to $S_{j,k}$ tends to zero. In the ${\widehat{Q}}_k$ coordinates this component is the block of $A_k$ below the first $j$ columns, so $(A_k{)}_{ij}\to 0$ whenever $i>j$.

The trace of the leading $j\times j$ block of $A_k$ is the trace of the compression of $A$ to $S_{j,k}$. By $S_{j,k}\to E_j$, it tends to the trace of $A{\mathrm{\mid }}_{E_j}$, namely ${\lambda }_1+\cdots +{\lambda }_j$. Subtracting the corresponding limit for $j-1$ gives $(A_k{)}_{jj}\to {\lambda }_j$.

Steps 3.1 and 3.2 prove that the strict lower triangle tends to zero and the diagonal tends to $({\lambda }_1,\dots ,{\lambda }_n)$. No convergence of the upper-triangular entries is asserted.

Because $H-\mu I$ is upper Hessenberg, each subdiagonal entry can be annihilated by an adjacent Givens rotation acting only on two consecutive rows. By [L3], the product of these rotations gives $Q$ and an upper triangular $R$.

Right-multiplying an upper triangular matrix by one adjacent Givens rotation can create a nonzero entry only one row below the diagonal in the two affected columns. Repeating this through the same adjacent sequence keeps $RQ$ upper Hessenberg.

Adding $\mu I$ changes only diagonal entries, so [L1] and step 2.1 show that $H_{+}=RQ+\mu I$ is again upper Hessenberg.

By [L1], the trailing $2\times 2$ block determines a unique Wilkinson shift $\mu$.

By [L2], the shifted step $T_{+}=RQ+\mu I$ is upper Hessenberg.