Numerical Linear Algebra with Applications

17.9 Computing the QR Decomposition Using Householder Reflections

To transform an m × n matrix into upper triangular form, we must zero out all the elements below the diagonal entries a₁₁, a₂₂, …, a_kk, where k = min (m − 1, n). We know how to do this for a₁₁ (Algorithm 17.4), and now we will demonstrate how to zero out the elements below the remaining diagonal entries. This is done by implicitly creating a sequence of Householder matrices that deal with submatrix blocks, as illustrated in Figure 17.6.

Figure 17.6 Transforming an m × n matrix to upper triangular form using householder reflections.

Zeroing out all the elements below a₁₁ using ...