Question 9.5.3: Incorporate shifting into the QR method for the matrix A = [...

To find the acceleration parameter for shifting requires finding the eigenvalues of

\left[\begin{array}{cc}a_{2}^{(1)} & b_{3}^{(1)} \\b_{3}^{(1)} & a_{3}^{(1)}\end{array}\right]=\left[\begin{array}{ll}3 & 1 \\1 & 3\end{array}\right],

which are \mu_{1}=4 \text { and } \mu_{2}=2 . The choice of eigenvalue closest to a_{3}^{(1)}=3  is arbitrary, and we choose \mu_{2}=2 and shift by this amount. Then \sigma_{1}=2 and

\left[\begin{array}{ccc}d_{1} & b_{2}^{(1)} & 0 \\b_{2}^{(1)} & d_{2} & b_{3}^{(1)} \\0 & b_{3}^{(1)} & d_{3}\end{array}\right]=\left[\begin{array}{lll}1 & 1 & 0 \\1 & 1 & 1 \\0 & 1 & 1\end{array}\right].

Continuing the computation gives

\begin{gathered}x_{1}=1, \quad y_{1}=1, \quad z_{1}=\sqrt{2}, \quad c_{2}=\frac{\sqrt{2}}{2}, \quad s_{2}=\frac{\sqrt{2}}{2} \\q_{1}=\sqrt{2}, \quad x_{2}=0, \quad r_{1}=\frac{\sqrt{2}}{2}, \quad \text { and } \quad y_{2}=\frac{\sqrt{2}}{2}\end{gathered}

so

A_{2}^{(1)}=\left[\begin{array}{ccc}\sqrt{2} & \sqrt{2} & \frac{\sqrt{2}}{2} \\0 & 0 & \frac{\sqrt{2}}{2} \\0 & 1 & 1\end{array}\right] .

Further,

z_{2}=1, \quad c_{3}=0, \quad s_{3}=1, \quad q_{2}=1, \quad \text { and } \quad x_{3}=-\frac{\sqrt{2}}{2},

so

R^{(1)}=A_{3}^{(1)}=\left[\begin{array}{ccc}\sqrt{2} & \sqrt{2} & \frac{\sqrt{2}}{2} \\0 & 1 & 1 \\0 & 0 & -\frac{\sqrt{2}}{2}\end{array}\right]

To compute A^{(2)} , we have

z_{3}=-\frac{\sqrt{2}}{2}, \quad a_{1}^{(2)}=2, \quad b_{2}^{(2)}=\frac{\sqrt{2}}{2}, \quad a_{2}^{(2)}=1, \quad b_{3}^{(2)}=-\frac{\sqrt{2}}{2}, \quad \text { and } \quad a_{3}^{(2)}=0,

so

A^{(2)}=R^{(1)} Q^{(1)}=\left[\begin{array}{ccc}2 & \frac{\sqrt{2}}{2} & 0 \\\frac{\sqrt{2}}{2} & 1 & -\frac{\sqrt{2}}{2} \\0 & -\frac{\sqrt{2}}{2} & 0\end{array}\right].

One iteration of the QR method is complete. Neither b_{2}^{(2)}=\sqrt{2} / 2 \text { nor } b_{3}^{(2)}=-\sqrt{2} / 2  is small, so another iteration of the QR method is performed. For this iteration, we calculate the eigenvalues \frac{1}{2} \pm \frac{1}{2} \sqrt{3}  of the matrix

\left[\begin{array}{cc}a_{2}^{(2)} & b_{3}^{(2)} \\b_{3}^{(2)} & a_{3}^{(2)}\end{array}\right]=\left[\begin{array}{cc}1 & -\frac{\sqrt{2}}{2} \\-\frac{\sqrt{2}}{2} & 0\end{array}\right]

and choose \sigma_{2}=\frac{1}{2}-\frac{1}{2} \sqrt{3} , the closest eigenvalue to a_{3}^{(2)}=0 . Completing the calculations gives

A^{(3)}=\left[\begin{array}{ccc}2.6720277 & 0.37597448 & 0 \\0.37597448 & 1.4736080 & 0.030396964 \\0 & 0.030396964 & -0.047559530\end{array}\right].

If b_{3}^{(3)}=0.030396964 is sufficiently small, then the approximation to the eigenvalue \lambda_{3} is 1.5864151, the sum of a_{3}^{(3)} and the shifts \sigma_{1}+\sigma_{2}=2+(1-\sqrt{3}) / 2 . Deleting the third row and column gives

A^{(3)}=\left[\begin{array}{cc}2.6720277 & 0.37597448 \\0.37597448 & 1.4736080\end{array}\right],

which has eigenvalues \mu_{1}=2.7802140 \text { and } \mu_{2}=1.3654218 . Adding the shifts gives the approximations

\lambda_{1} \approx 4.4141886 \text { and } \lambda_{2} \approx 2.9993964.

The actual eigenvalues of the matrix A are 4.41420, 3.00000, and 1.58579, so the QR method gave four significant digits of accuracy in only two iterations.