Interactive Educational Modules in
Scientific Computing

Householder QR Factorization

This module illustrates computing the QR factorization of a matrix using Householder's method. The initial matrix is reduced to upper triangular form by applying a sequence of Householder transformations to annihilate the subdiagonal entries in successive columns.

The user first selects a matrix size, then selects a matrix by choosing a preset example, a random matrix, or typing in desired entries. The successive steps of Householder QR factorization are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current column is indicated by an arrow. For each successive column, a Householder transformation is determined that annihilates the subdiagonal entries of the given column. The corresponding Householder vector v is displayed on the right, and the computed values of the scalars α and β are shown in text boxes. The Householder transformation is also applied to the remaining columns of the matrix. The factorization process is complete when the original matrix has been reduced to upper triangular form. Formats provided for displaying numeric entries include exponential (e), fixed (f), and generic (g), with g the default.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 3.5.1, especially Algorithm 3.1 and Example 3.8.

Developers: Jessica Schoen and Michael Heath