Near a simple Hermitian eigenvector, Rayleigh-quotient iteration converges cubically

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.