QR iteration with shift

• Let’s assume $A$ is upper Hessenberg.
• Let us choose an approximate eigenvalue $\mu$.
• For example, $\mu =[T_k{]}_{nn}$.
• This should approximate the smallest eigenvalue of $A$.

Then:

$$|{\lambda }_n-\mu |\ll |{\lambda }_{n-1}-\mu |$$

We had mentioned this idea previously.

For our previous theoretical result, we have that

$$\text{span}(Q_k[:,1:n-1])\to \text{span}(Q[:,1:n-1])$$

with rate

$${\left|\frac{{\lambda }_n-\mu }{{\lambda }_{n-1}-\mu }\right|}^k$$

But since the matrices are orthogonal, we also get convergence of the last column, which is orthogonal to the subspace spanned by the previous $n-1$ columns. So

$$\text{span}(Q_k[:,n])\to \text{span}(Q[:,n])$$

Consider again:

$$T_k=Q_k^{H}A{Q}_k,\text{and}T=Q^{H}AQ.$$

The last row of $T_k$ converges to the last row of $T$: $[0,\dots ,0,{\lambda }_n]$.

We can now use deflation, and work with a smaller $n-1\times n-1$ matrix.

By repeating this process, we make $A$ smaller and smaller and on the way, we obtain all the eigenvalues of $A$.