Skip to main content

Unit 3.3.1 Using unitary matrices

A fundamental problem to avoid in numerical codes is the situation where one starts with large values and one ends up with small values with large relative errors in them. This is known as catastrophic cancellation. The Gram-Schmidt algorithms can inherently fall victim to this: column \(a_j\) is successively reduced in length as components in the directions of \(\{ q_0, \ldots, q_{j-1} \} \) are subtracted, leaving a small vector if \(a_j \) was almost in the span of the first \(j \) columns of \(A \text{.}\) Application of a unitary transformation to a matrix or vector inherently preserves length. Thus, it would be beneficial if the QR factorization can be implementated as the successive application of unitary transformations. The Householder QR factorization accomplishes this.

The first fundamental insight is that the product of unitary matrices is itself unitary. If, given \(A \in \C^{m \times n} \) (with \(m \geq n \)), one could find a sequence of unitary matrices, \(\{ H_0, \ldots , H_{n-1} \} \text{,}\) such that

\begin{equation*} H_{n-1} \cdots H_0 A = \FlaTwoByOneSingleLine {R}{0}, \end{equation*}

where \(R \in \Cnxn \) is upper triangular, then

\begin{equation*} A = \begin{array}[t]{c} \underbrace{H_0^H \cdots H_{n-1}^H} \\ Q \end{array} \FlaTwoByOneSingleLine {R}{0} \end{equation*}

which is closely related to the QR factorization of \(A \text{.}\)

Homework 3.3.1.1.

Show that if \(A \in \Cmxn \) and \(A = Q \FlaTwoByOneSingleLine {R}{0},\) where \(Q \in \Cmxm \) is unitary and \(R \) is upper triangular, then there exists \(Q_L \in \Cmxn \) such that \(A = Q_L R, \) is the QR factorization of \(A \text{.}\)

Solution
\begin{equation*} Q \FlaTwoByOneSingleLine {R}{0} = \FlaOneByTwoSingleLine{ Q_L }{ Q_R } \FlaTwoByOneSingleLine {R}{0} = Q_L R, \end{equation*}

The second fundamental insight will be that the desired unitary transformations \(\{ H_0, \ldots , H_{n-1} \} \) can be computed and applied cheaply, as we will discover in the remainder of this section.