Subsection 10.3.3 Simple tridiagonal QR algorithm
ΒΆNow, consider the \(4 \times 4 \) tridiagonal matrix
\begin{equation*}
\left(
\begin{array}{c c c c}
\alpha_{0,0} \amp \alpha_{0,1} \amp 0 \amp 0 \\
\alpha_{1,0} \amp \alpha_{1,1} \amp \alpha_{1,2} \amp 0 \\
0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\
\end{array}
\right).
\end{equation*}
From \(\left( \begin{array}{c} \alpha_{0,0} \\ \alpha_{1,0} \end{array} \right),\) one can compute \(\gamma_{1,0} \) and \(\sigma_{1,0} \) so that
\begin{equation*}
\left(
\begin{array}{c c}
\gamma_{1,0} \amp -\sigma_{1,0} \\
\sigma_{1,0} \amp \gamma_{1,0}
\end{array}
\right)^T
\left(
\begin{array}{c}
\alpha_{0,0} \\
\alpha_{1,0}
\end{array}
\right)
=
\left(
\begin{array}{c}
\widehat{\alpha}_{0,0} \\
0
\end{array}
\right)
.
\end{equation*}
Then
\begin{equation*}
\left(
\begin{array}{| c c | c c} \hline
{\widehat{\alpha}_{0,0} } \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\
0 \amp \widehat{\alpha}_{1,1} \amp \widehat{\alpha}_{1,2} \amp 0 \\ \hline
0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3}
\end{array}
\right)
=
\left(
\begin{array}{|c c | c c} \hline
\gamma_{1,0} \amp \sigma_{1,0} \amp 0 \amp 0 \\
- \sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
\left(
\begin{array}{| c c | c | c}\hline
\alpha_{0,0} \amp \alpha_{0,1} \amp 0 \amp 0 \\
\alpha_{1,0} \amp \alpha_{1,1} \amp \alpha_{1,2} \amp 0 \\ \hline
0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3}
\end{array}
\right)\text{.}
\end{equation*}
Next, from \(\left( \begin{array}{c} \widehat{\alpha}_{1,1} \\ \alpha_{2,1} \end{array} \right) \text{,}\) one can compute \(\gamma_{2,1} \) and \(\sigma_{2,1} \) so that
\begin{equation*}
\left(
\begin{array}{c c}
\gamma_{2,1} \amp -\sigma_{2,1} \\
\sigma_{2,1} \amp \gamma_{2,1}
\end{array}
\right)^T
\left(
\begin{array}{c}
\widehat{\alpha}_{1,1} \\
\alpha_{2,1}
\end{array}
\right)
=
\left(
\begin{array}{c}
\widehat{\widehat{\alpha}}_{1,1} \\
0
\end{array}
\right)
.
\end{equation*}
Then
\begin{equation*}
\left(
\begin{array}{c | c c | c }
\widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\ \hline
0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp
\widehat{\widehat{\alpha}}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\
0 \amp 0 \amp \widehat{\alpha}_{2,2} \amp \widehat{\alpha}_{2,3} \\ \hline
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\
\end{array}
\right)
=
\left(
\begin{array}{c | c c | c}
1 \amp 0 \amp 0 \amp 0 \\ \hline
0 \amp \gamma_{2,1} \amp \sigma_{2,1} \amp 0 \\
0 \amp - \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
\left(
\begin{array}{c | c c | c }
\widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\ \hline
0 \amp \widehat{\alpha}_{1,1} \amp \widehat{\alpha}_{1,2} \amp 0 \\
0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\ \hline
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\
\end{array}
\right)
\end{equation*}
Finally, from \(\left( \begin{array}{c} \widehat{\alpha}_{2,2} \\ \alpha_{3,2} \end{array} \right),\) one can compute \(\gamma_{3,2} \) and \(\sigma_{3,2} \) so that \(\left( \begin{array}{c c} \gamma_{3,2} \amp -\sigma_{3,2} \\ \sigma_{3,2} \amp \gamma_{3,2} \end{array} \right)^T \left( \begin{array}{c} \widehat{\alpha}_{2,2} \\ \alpha_{3,2} \end{array} \right) = \left( \begin{array}{c} \widehat{\widehat{\alpha}}_{2,2} \\ 0 \end{array} \right) \text{.}\) Then
\begin{equation*}
\left(
\begin{array}{c c | c c |}
\widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\
0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp
\widehat{\widehat{\alpha}}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\ \hline
0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\
0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3} \\ \hline
\end{array}
\right)
=
\left(
\begin{array}{c c | c c |}
1 \amp 0 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp \gamma_{3,2} \amp \sigma_{3,2} \\
0 \amp 0 \amp - \sigma_{3,2} \amp \gamma_{3,2} \\ \hline
\end{array}
\right)
\left(
\begin{array}{c c | c c |}
\widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\
0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp
\widehat{\widehat{\alpha}}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\ \hline
0 \amp 0 \amp \widehat{\alpha}_{2,2} \amp \widehat{\alpha}_{2,3} \\
0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\ \hline
\end{array}
\right)
\end{equation*}
The matrix \(Q \) is the orthogonal matrix that results from multiplying the different Givens' rotations together:
\begin{equation}
Q =
\left(
\begin{array}{| c c | c c} \hline
\gamma_{1,0} \amp - \sigma_{1,0} \amp 0 \amp 0 \\
\sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
\left(
\begin{array}{c | c c | c}
1 \amp 0 \amp 0 \amp 0 \\ \hline
0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\
0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
\left(
\begin{array}{c c | c c |}
1 \amp 0 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\
0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline
\end{array}
\right).\label{chapter10-eqn-Q1}\tag{10.3.1}
\end{equation}
However, it needs not be explicitly formed, as we exploit next.
The next question is how to compute \(R Q \) given the QR factorization of the tridiagonal matrix. We notice that
\begin{equation*}
\begin{array}{r}
\underbrace{
\left(
\begin{array}{| c c | c c} \hline
\widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp
\widehat{\alpha}_{0,2} \amp 0 \\
0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp
\widehat{\widehat{\alpha}}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\ \hline
0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\
0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3}
\end{array}
\right)
\left(
\begin{array}{| c c | c c} \hline
\gamma_{1,0} \amp - \sigma_{1,0} \amp 0 \amp 0 \\
\sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
}
\left(
\begin{array}{c | c c | c}
1 \amp 0 \amp 0 \amp 0 \\ \hline
0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\
0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
\left(
\begin{array}{c c | c c |}
1 \amp 0 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\
0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline
\end{array}
\right)
\\
\underbrace{
\left(
\begin{array}{| c c | c c} \hline
\tilde{\alpha}_{0,0} \amp \tilde{\alpha}_{0,1} \amp
\color{gray}{\widehat{\alpha}_{0,2}} \amp 0 \\
\tilde{\alpha}_{1,0} \amp \tilde{\widehat{\alpha}}_{1,1} \amp
\widehat{\widehat{\alpha}}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\ \hline
0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\
0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3}
\end{array}
\right)
\hspace{0.75in}
\phantom{
\left(
\begin{array}{c | c c | c}
1 \amp 0 \amp 0 \amp 0 \\ \hline
0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\
0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline
0 \amp 0 \amp 0 \amp 1
\end{array}
\right)
}
}
\phantom{
\left(
\begin{array}{c c | c c |}
1 \amp 0 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\
0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline
\end{array}
\right)
}
\\
\underbrace{
\left(
\begin{array}{c | c c | c}
\tilde{\alpha}_{0,0} \amp \tilde{\tilde{\alpha}}_{0,1} \amp
\color{gray}{\tilde{\alpha}_{0,2}} \amp 0 \\ \hline
\tilde{\alpha}_{1,0} \amp \tilde{\tilde{\alpha}}_{1,1} \amp
\tilde{\alpha}_{1,2} \amp
\widehat{\widehat{\alpha}}_{1,3} \\
0 \amp \tilde{\alpha}_{2,1} \amp \tilde{\alpha}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\ \hline
0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3}
\end{array}
\right)
\hspace{1.1in}
\phantom{
\left(
\begin{array}{c c | c c |}
1 \amp 0 \amp 0 \amp 0 \\
0 \amp 1 \amp 0 \amp 0 \\ \hline
0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\
0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline
\end{array}
\right)
}
} \\
\left(
\begin{array}{c c | c c |}
\tilde{\alpha}_{0,0} \amp \tilde{\tilde{\alpha}}_{0,1} \amp
\color{gray}{\tilde{\alpha}_{0,2}} \amp 0 \\
\tilde{\alpha}_{1,0} \amp \tilde{\tilde{\alpha}}_{1,1} \amp
\tilde{\tilde{\alpha}}_{1,2} \amp
\color{gray} {\tilde{\alpha}_{1,3}}\\ \hline
0 \amp \tilde{\alpha}_{2,1} \amp \tilde{\tilde{\alpha}}_{2,2} \amp \tilde{\alpha}_{2,3} \\
0 \amp 0 \amp \tilde{\alpha}_{3,2} \amp \tilde{\alpha}_{3,3} \\ \hline
\end{array}
\right).
\hspace{1.1in}
~
\end{array}
\end{equation*}
A symmetry argument can be used to motivate that \(\tilde{\alpha}_{0,2} = \tilde{\alpha}_{1,3}= 0 \) (which is why they appear in gray, if you look carefully). This also explains why none of the elements above the first superdiagonal become nonzero.
Remark 10.3.3.1.
An important observation is that if \(A \) is tridiagonal, then \(A \rightarrow Q R \) (QR factorization) followed by \(A := R Q \) again yields a tridiagonal matrix. In other words, any QR algorithm previously discussed (simple, shifted, with deflation) when started with a tridiagonal matrix will generate a succession of tridiagonal matrices.