QR iteration 2x2 example

Consider the simplified 2x2 example:

$$A=\left(\begin{array}{cc}w& x\\ \epsilon & z\end{array}\right)$$

We perform a shift using $z$. After rescaling, we can reduce the problem to

$$A=\left(\begin{array}{cc}1& x\\ \epsilon & 0\end{array}\right)$$

assuming that $w\ne z$.

Let’s perform one step of the QR iteration. QR factorization + RQ multiplication:

$$\left(\begin{array}{cc}\frac{(1+{\epsilon }^2+x\epsilon )}{1+{\epsilon }^2}& \frac{x-\epsilon (1+{\epsilon }^2)}{1+{\epsilon }^2}\\ -\frac{x{\epsilon }^2}{1+{\epsilon }^2}& -\frac{x\epsilon }{1+{\epsilon }^2}\end{array}\right)$$

If we assume $|\epsilon |\ll 1$, then

$$|-\frac{x{\epsilon }^2}{1+{\epsilon }^2}|\sim |x{\epsilon }^2|$$

Unsymmetric case

• (2,1) entry: $\epsilon \to O({\epsilon }^2)$.
• Quadratic convergence

Symmetric case

$$\begin{array}{c}x=\epsilon \\ A=\left(\begin{array}{cc}1& \epsilon \\ \epsilon & 0\end{array}\right)\\ |-\frac{x{\epsilon }^2}{1+{\epsilon }^2}|\sim |{\epsilon }^3|\\ \epsilon \to O({\epsilon }^3)\end{array}$$

We get a cubic convergence.