Skip to main content

Unit 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.